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:
        add node to reachable_places_list if it's not already there
        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.

  • \$\begingroup\$ 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. \$\endgroup\$
    – 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.

  • \$\begingroup\$ 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) \$\endgroup\$
    – f20k
    Nov 29 '10 at 16:37
  • \$\begingroup\$ Every turn. And I'm not sure what you mean by the player's target tile, surely you get that input from the player? \$\endgroup\$
    – Tetrad
    Nov 29 '10 at 16:55
  • \$\begingroup\$ 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 \$\endgroup\$
    – 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


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.