5
\$\begingroup\$

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.

\$\endgroup\$

3 Answers 3

8
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\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
    Commented Nov 29, 2010 at 18:28
2
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\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
    Commented Nov 29, 2010 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
    Commented Nov 29, 2010 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
    Commented Nov 29, 2010 at 17:14
0
\$\begingroup\$

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

\$\endgroup\$

You must log in to answer this question.

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