Pathfinding

This is not a comprehensive guide to pathfinding. I wanted to post some code for finding the possible movement targets on a grid, which is typically the first step in selecting a path within a visual interface, but at this time I don't have the intention of adding pathfinding code.

I can recommend the very comprehensive guides at the following pages.

Build New Games

Red Blob Games

Possible movement (squares)

Here are the basic steps involved in a "bounds finder" that unlike a pathfinder (which searches for a singular path between two points) looks for ALL possible squares that can be moved to given a certain nubmer of movements.

The code outline is actually fairly simple. Keep in mind that to use this code you'll need the ability to store variables on each tile in the square grid.

There are essentially 5 different steps.

  1. Each tile has a "cost" property, start by setting all tiles to 0.
  2. Place the starting tile coordinates into a list by themselves.
  3. Make a 2nd list of all tiles that is empty.
  4. Check each neighbor of each tile in list 1.
    • If you can move to that neighbor, add the neighbor to the 2nd list and assign the cost of movement from the tile.
    • If you can not move to that tile. Do nothing.
  5. Replace list 1 with list 2. Repeat until there is nothing in list 2 to copy to list 1.

Let's look at an example below. As the demo says you can click on the squares in the window below to toggle whether or not the code can "walk" through them. Consider the center circle to the starting point of the bounds finder. This code looks at all possibilities and shows cooler colors as being further away from the starting point and warmer colors as closer.

The actual code involved in such an operation is obviously slightly more complex.

So complex I haven't started writing the example yet!