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?

  • \$\begingroup\$ 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. \$\endgroup\$ – Eric Nov 7 '12 at 10:41
  • \$\begingroup\$ 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. \$\endgroup\$ – PugWrath Nov 7 '12 at 15:51
  • \$\begingroup\$ Well, then every pixel is a tile. \$\endgroup\$ – Markus von Broady Nov 7 '12 at 16:48
  • \$\begingroup\$ You may also be interested in how far enemies can attack from those tiles, the algorithm for that is here: stackoverflow.com/questions/20638583/… \$\endgroup\$ – Alex Stone Dec 30 '13 at 5:07

Start of with the simplest pathfinding algorithm (I believe) Breadth-first search: bfs pathfinding

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.
  • \$\begingroup\$ 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. \$\endgroup\$ – PugWrath Nov 7 '12 at 15:53
  • \$\begingroup\$ Finished the answer. Click here to see what changed: gamedev.stackexchange.com/posts/43310/revisions \$\endgroup\$ – Markus von Broady Nov 7 '12 at 16:45
  • \$\begingroup\$ Why does the tile to the top right of the smiley face have a distance of 1 instead of 2? \$\endgroup\$ – Adam Nov 8 '12 at 1:18
  • \$\begingroup\$ @Adam I've spotted that too, that's most probably a mistake. \$\endgroup\$ – Markus von Broady Nov 8 '12 at 9:34
  • \$\begingroup\$ 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? \$\endgroup\$ – PugWrath Nov 8 '12 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.