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'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).

enter image description here

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).

share|improve this question
    
I'm thinking it's called path finding, for a search term? If you use path finding then you could have counters to handle what you need –  Exikle Sep 9 '13 at 12:48
    
This is essentially part of path finding (calculating meta data for movement costs). You only determine locations that are within range, but you don't necessarily determine the route you'd take as well. –  Mario Sep 9 '13 at 21:44
1  
It's not real-time (RTS) if it's turn-based à la FFTactics. :p –  Alayric Sep 9 '13 at 22:24
    
In 2d, you could use Taxicab/Manhattan calculation en.wikipedia.org/wiki/Taxicab_geometry –  Gerben Jacobs Sep 11 '13 at 14:41

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer
    
I think Dijkstra's is overkill in this case. The OP doesn't need a path to all possible movement destinations, just a yes/no answer on whether an agent can get there. He can compute a path later once the user has picked one. –  Michael Kristofik Sep 9 '13 at 15:13
    
The cost of using Dijkstra's algorithm to calculate the path after a destination has been decided upon is almost exactly the same as using it upfront (unless you use a heuristic approach like A* for pathing). Not doing it up front simply creates redundant work, as Dijkstra would answer both the questions 'where can I go' and 'how do I get there?'. It also allows for the addition of complications to the environment that change the movement cost, though that may be unnecessary for the application. Further, the approach is well documented, which is helpful to the implementer. –  TASagent Sep 9 '13 at 17:18
1  
On looking over Mario's answer, he actually describes Dijkstra's algorithm, except he inverts the distance, and doesn't mention it is Dijkstra. –  TASagent Sep 9 '13 at 17:20
1  
Wouldn't say it's Dijkstra, because you're not really looking for a shortest route nor are you trying to reach some specific point. It is essentially the first part of Dijkstra's Algorithm, that's true though. The problem with your wording, using Dijkstra, can be misleading and I think this is also what confused Michael. He probably thought you suggested using Dijkstra once for each field/cell. –  Mario Sep 9 '13 at 21:41
1  
Ending up using this approach as it worked well and is very easy to extend to handle obstacles. –  NRaf Sep 11 '13 at 21:57

Most simple (and probably most naive) approach I can think of right now:

  • Start at your character and mark all surrounding fields as steps - 1.
  • Iterate over all newly marked fields and once again mark their surrounding fields as steps - 1 where steps would be the current field's step number, unless the new field has an already higher number.
  • Repeat the last step till you're running out of steps.
share|improve this answer
1  
This algorithm has a name: Flood Fill. –  Michael Kristofik Sep 9 '13 at 15:09
6  
@MichaelKristofik: I would call it breadth first search. Flood fill does not keep track of distances. –  BlueRaja - Danny Pflughoeft Sep 9 '13 at 16:18

I think what you're looking for might be Manhattan Distance. Assuming no obstacles, you can say that a square is reachable simply if:

|toX-fromX| + |toY-fromY| < maxMoveDistance

This algorithm may not be the right direction to go if you're going to have obstacles later; one possible way to adapt it might involve having obstacles cast 'shadows' and re-evaluating from the nearest point.

EDIT (Because I have a bit more spare time now):

By 'shadows' I mean something like this, if 0 is a reachable square, C is the character, and X is an obstacle:

 012345678
0    0
1   00
2  000X
3 000C000
4  00000
5   000
6    0
 012345678

Since (5, 2) is an obstacle, you start by assuming that you can't get to anything with x>=5 AND y<=2. You can then recalculate from another square; if you want to go to (5, 1) you could calculate the manhattan distance from (4, 1) and see if that + the distance from the character to (4, 1) is less than the player's movement distance.

This is a fairly trivial example, but if you have multiple obstacles and/or a bit longer movement range, it should be able to handle the complexity.

Whether it'd actually be any better than just flood-filling, either in programming complexity or execution efficiency, I have no clue. Just seemed like a more interesting way to solve the problem.

share|improve this answer
    
What do you mean by casting shadows? –  NRaf Sep 10 '13 at 22:33
1  
Edited for clarification. –  Amadeus9 Sep 11 '13 at 14:26

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.