How can I plot a radius of all reachable points with pathfinding for a Mob?

I am designing a tactical turn based game. The maps are 2d, but do have varying level-layers and blocking objects/terrain. I'm looking for an algorithm for pathfinding which will allow me to show an opaque shape representing all of the possible max-distance pixels that a mob can move to, knowing the mob's max pixel distance.

Any thoughts on this, or do I just need to write a good pathfinding algorithm and use it to find the cutoff points for any direction in which an obstacle exists?

• 1) Does your game feature tile-based movement? Your question seems to imply it doesn't, since you're talking about pixels. 2) Do you already have a specific path finding algorithm in place which plans a path to a target location for a given mob? You will need this anyway, and you might be able to reuse it for this problem. Specifying it might make answering your question easier. – Eric Nov 7 '12 at 10:41
• 1) No, at this point, I'm letting the player / mobs move pixel-by-pixel, even though the maps are laid out in tile fashion. 2) I haven't implemented any path-finding, yet, no, and you're right - I have to do that, anyway, so I may as well make it a priority, first, and just allow characters to do something like move anywhere inside of their radius on the horizontal axis in the meantime. – PugWrath Nov 7 '12 at 15:51
• Well, then every pixel is a tile. – Markus von Broady Nov 7 '12 at 16:48
• You may also be interested in how far enemies can attack from those tiles, the algorithm for that is here: stackoverflow.com/questions/20638583/… – Alex Stone Dec 30 '13 at 5:07

Start of with the simplest pathfinding algorithm (I believe) Breadth-first search: This is actually a very good algorithm if you want to find the best possible path, especially if various tiles have different movement ratios (how much movement points it costs to enter/leave the tile, e.g. mountain could take 3 points and road only 1/3). Because you have a limited movement, your BFS will end pretty quickly, most probably letting you calculate paths for one unit in a single frame without FPS drop below 60.

For an algorithm below I'll assume a little harder scenario, where there are various movement costs of tiles.

Here's the recipe:: You will need:

• the value representing how far you can go, named movement_points
• one dictionary of tile:movement_points_to_reach_it pairs named costs
• one list of tiles_to_check
• one list of tiles_being_checked
• starting tile, for which you check possible paths, let's name the tile a hero.

Let's make the cake:

1. Add hero to tiles_to_check
2. Initialize boolean changed variable with true
3. Start While (changed) loop.
1. changed = false;
2. tiles_being_checked = tiles_to_check;
3. Assign new Array to tiles_to_check.
4. Iterate through all tiles_being_checked
• iterate through all tiles surrounding the current tile being checked and run a processTile function:
• t=tiles_being_checked[i]; for(x=t.x-1; x<=t.x+1; x++) for(y=t.y-1; y<=t.y+1; y++) if (x!=t.x || y!=t.y) processTile(t, x, y)

In processTile(tile, x, y) do:

1. next_tile = world_grid[x][y];
2. Check if next_tile is passable, e.g. it's not a water tile. (if yes, return)
3. Check the cost of moving from tile to the next_tile and save it as cost; (take care of if it's diagonal movement - multiply by square root of 2 - and what's this/next tile's movement cost.
4. total_cost = costs[tile] + cost;
5. Check if there are enough movement points to reach it: if (total_cost > movement_points) return;
6. Check if there already exists this tile (as a key) in your costs dictionary, and if yes, check if you already found a better or equal way for this tile: if (costs[next_tile] <= total_cost) return
7. If not, write the new cost costs[next_tile] = total_cost
8. add next_tile to tiles_to_check
9. set changed = true.

In the end use costs dictionary to check if a tile can be reached by given movement points (it exists as a key in the dictionary) and to check how much movement points it will cost. To check for the path:

1. Choose a destination tile (that can be reached)
2. Set currentX = tile.x; currentY = tile.y;
3. Set cost = MAX_INT;
4. Create an Array of tiles path = new Array ();
5. start while ( currentX != startTile.x || currentY != startTile.y ) loop.
1. Iterate through neighboring tiles...
2. ... and if a given neighboring tile, let's name it a nTile has lower cost than current: if (costs[nTile] < cost) { cost = costs[nTile]; currentX=nTile.x; currentY=nTile.y;
6. Reverse the array.
• Thanks - I'll look this algorithm over and see if I can't implement it, at least for AI path-finding, if not for the solution to this particular issue. – PugWrath Nov 7 '12 at 15:53
• Finished the answer. Click here to see what changed: gamedev.stackexchange.com/posts/43310/revisions – Markus von Broady Nov 7 '12 at 16:45
• Why does the tile to the top right of the smiley face have a distance of 1 instead of 2? – Adam Nov 8 '12 at 1:18
• @Adam I've spotted that too, that's most probably a mistake. – Markus von Broady Nov 8 '12 at 9:34
• Well, ideally you'd at least alternate between 1,2 distance for diagonal paths, right? Since it's basically 1.44 * normal distance to move diagonally? – PugWrath Nov 8 '12 at 16:52