5
\$\begingroup\$

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?

\$\endgroup\$
4
  • \$\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
    Commented Nov 7, 2012 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
    Commented Nov 7, 2012 at 15:51
  • \$\begingroup\$ Well, then every pixel is a tile. \$\endgroup\$ Commented Nov 7, 2012 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
    Commented Dec 30, 2013 at 5:07

1 Answer 1

6
\$\begingroup\$

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.
\$\endgroup\$
9
  • \$\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
    Commented Nov 7, 2012 at 15:53
  • \$\begingroup\$ Finished the answer. Click here to see what changed: gamedev.stackexchange.com/posts/43310/revisions \$\endgroup\$ Commented Nov 7, 2012 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
    Commented Nov 8, 2012 at 1:18
  • \$\begingroup\$ @Adam I've spotted that too, that's most probably a mistake. \$\endgroup\$ Commented Nov 8, 2012 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
    Commented Nov 8, 2012 at 16:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .