Finding possible moves for an entity in a 2d tiled game

Question

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 1

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.

Answer 2

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.

Answer 3

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.