# 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