Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers

up vote 7 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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