# What algorithm to use for path mapping?

I am making a turn based game with tiles, much like Final Fantasy Tactics. I am trying to develop an algorithm for mapping out a list of available tiles to walk on. So for example, I am at (0,0) and I have a range of 2 - ie I can walk to any tiles that within two tiles away from me.

Things to account for:

• I have a set number of steps I can take - which was 2 in the example above
• There may be enemies or walls that will block my path
• The tiles are hex-based so I have 6 possible places to move to

The plan is basically to

• determine the places I can walk to
• if the tile is available, add it to a list of walkable tiles from this location - so that I can use it in a pathfinding algorithm and so that I don't have check this location again

Basically I need an algorithm to map possible paths from a location. I thought of the A*,dijkstra, bfs,dfs but I think they require knowing the nodes beforehand.

Any help would be appreciated, thanks!

P.S. Path-mapping would be a better tag but I can't make a new one.

Breadth-first or depth-first search would do this job more efficiently than your answer suggesting that you will use A*. You can search each node with one run of the algorithm instead of one run for each node.

Pseudocode for a depth-first approach might look like this:

reachable_places_list = empty list (or set, or map, or something similar)

function find_all_reachable_nodes(current_node, distance_travelled):
for each node adjacent to current_node that is reachable:
if distance_travelled + 1 < 2:
find_all_reachable_nodes(node, distance_travelled + 1)

find_all_reachable_nodes(player_position, 0)


You also don't need to use 'a very high value' to exclude blocked nodes from a graph search (whether A*, DFS, BFS, or whatever) - simply don't add them to the list or queue of nodes to be queried in future.

• ah, a recursive solution! If you say this is more efficient, then yes I think I will implement this. However, my enemies move, even walls may disappear, so I have to account for that before adding to my list. Also, each tile might have a 'height' value which was why I thought A*, but I think that it can be factored in the distance somehow. Thanks Kylotan. – f20k Nov 29 '10 at 18:28

I thought of the A*,dijkstra, bfs,dfs but I think they require knowing the nodes beforehand.

You can use those just fine. Your problem set is small enough I'm sure that you don't need to precompute anything. Just run A* every move and you'll have your paths computed given whatever the state of the board is.

• Sorry but could you please clarify what you mean running A* every move? Do you mean at every turn, or every time you move to another node? Also, this system will be used by the player and the AI, so I can't just keep moving the player's unit towards the target tile without knowing the target tile and if the user can reach it or not (because of an obstacle) – f20k Nov 29 '10 at 16:37
• Every turn. And I'm not sure what you mean by the player's target tile, surely you get that input from the player? – Tetrad Nov 29 '10 at 16:55
• No, say I was the player, and I had a range of two. I want to see which tiles I can walk to before I pick where to go and an enemy is in my range, blocking my way (therefore limiting my range). How would I determine the tiles I can walk to? But I think I found the answer – f20k Nov 29 '10 at 17:14

Thanks Tetrad, I found out how to do it. Basically, for all the tiles in my range, I apply A* from that tile to where I am standing on. Also assign a very high value to walls/enemies. Then if I can reach my location within 2-moves, then that tile is valid. Then I can add it to my list of nodes.

Its sort of like applying A* but in the opposite direction