I'm having issues coming up with a specific search term for this, but how would one go about finding the possible moves in a 2D turn-based strategy game (i.e. FF:Tactics, Fire Emblem, Advance Wars).
I'm not so much thinking about terrain (or even collision) at this point. I'm just wondering what algorithm I can use to figure out that X entity can move 5 tiles and attack 2 farther tiles than that.
I know I can use something like Dijkstra to find the distance between two points. One possible implementation is starting at the players location and then branching off from there until the distance returned by Dijkstra is greater than the move count.
Just wondering if someone could point me in the right direction (i.e. name of algorithms, technique, articles, etc).
Answer
I think a bounded Dijkstra is precisely what you want to use. The way that Dijkstra finds the distance between two points is it maps out the distance to every node from an origin node, and then 'selects' the shortest path from this distance map. You want to do virtually the same thing, except you want the distance node graph it creates as output, rather than a path to any particular point.
The one modification you'll want to make is to skip calculating the distance from nodes that have already exceeded your maximum movement range. Then you'll have a node graph of all of the nodes that the unit can travel to, plus a border, so just cut out the nodes that have a distance greater than the movement allowance.
Viola.
In other words, pretty much what you described in your question is what you need to do. It also has the benefit of being able to use the output to do the pathfinding, without need to do any further calculations.
No comments:
Post a Comment