Displaying possible movement tiles

Question

What's the fastest way to highlight all possible movement tiles for a player on a square grid? Players can only move up, down, left, right. Tiles can cost more than one movement, multiple levels are available to move, and players can be larger than one tile. Think of games like Fire Emblem, Front Mission, and XCOM.

My first thought was to recursively search for connecting tiles. This quickly demonstrated many shortcomings when blockers, movement costs, and other features were added into the mix.

My second thought was to use an A* pathfinding algorithm to check all tiles presumed valid. Presumed valid tiles would come from an algorithm that generates a diamond of tiles from the player's speed (see example here http://jsfiddle.net/truefreestyle/Suww8/9/). Problem is this seems a little slow and expensive. Is there a faster way?

---

Edit: In Lua for Corona SDK, I integrated the following movement generation controller. I've linked to a Gist here because the solution is around 90 lines of code.

https://gist.github.com/ashblue/5546009

Answer 1

A* is for finding the shortest path from vert a to vert b. Its not a good fit for finding all verts x distance from vert a.

A Depth First Search (DFS) should be suitable for your problem and very cheep on both memory and clock cycles. There is another basic search algorithm called the Breadth First Search (BFS) that would run at similar speeds but uses slightly more memory because it stores all possible edges instead of immediately exploring them.

Things such as edges effecting speed can be handled by tracking distance (for example if a tile is 50% speed then its twice the length of other tiles) and only pushing new verts onto the stack if they are closer than the maximum distance. For example a bit of tinkering to the standard DFS algorithm gives you the below where all vertices labeled explored are within range of your character.

Note the below may not look it but its pseudocode. Not guaranteed to compile.

procedure Iterative_DFS(startVert) {
    startVert.distance = 0;
    var pop = true;
    HashSet discovered = new HashSet();
    Stack s = new Stack(startVert);
    s.push(startVert)
    while (!s.empty) {
          var t = s.pop();
          pop = true;
          foreach (vert v in t.adjacent) {
              if (!discovered.contains(v)) {
                  v.distance = t.distance + v.travel;
                  if (v.distance < maxDistance) {
                      discovered.add(v);
                      S.push(v);
                      pop = false;
                      break;
                  }
              }
          }
          if (pop) {
              label t as explored
              S.pop()
          }
     }
}

Answer 2

Final Update

• Unit.MovementPoints = 5
• Segment.Distance = 2
• First.Segment.Position = (1, 0, 1)

In the end what worked for me was actually Dijkstra's/BFS which searches nothing, there is no end point. You could extend this to create a Flow Field if you backtrack each tile but it's not required for this use case. Code represents a general idea and an algorithm, it's from my project, so it won't work out of the box.

// PolytopialSegmentsStructure = it's my grid.
// Segment = tile.
// Segment.Id = I set it to be the index in cached array from 0 to n.

// This is my thingy to get cost of a tile, you can ignore this.
[SerializeField] private ExperimentalSegmentCostRelation _experimentalSegmentCostRelation;

public override Segment[] GetNeighbours(Segment segment, int maxCost)
{
    this._experimentalSegmentCostRelation.Initialize(segment.PolytopialSegmentsStructure);

    int capacity = segment.PolytopialSegmentsStructure._RelativeBounds.size.x * segment.PolytopialSegmentsStructure._RelativeBounds.size.y * segment.PolytopialSegmentsStructure._RelativeBounds.size.z;

    Queue<Segment> frontier = new Queue<Segment>(capacity: capacity);

    frontier.Enqueue(item: segment);

    Dictionary<int, float> cost = new Dictionary<int, float>(capacity: capacity)
    {
        [segment.Id] = 0.0f
    };

    while (frontier.Count > 0)
    {
        Segment current = frontier.Dequeue();

        Segment[] neighbours = current.GetNeighbours();

        for (int a = 0; a < neighbours.Length; a++)
        {
            Segment next = neighbours[a];

            float newCost = cost[current.Id] + this._experimentalSegmentCostRelation.GetCost(next) + 1; // + this.Distance(current, neighbours[a]) // + 1 was to replace distance

            if (newCost <= maxCost && (!cost.ContainsKey(next.Id) || newCost < cost[next.Id]))
            {
                cost[next.Id] = newCost;

                frontier.Enqueue(next);
            }
        }
    }

    // This is me getting all of the tiles/segments this way because each key is Id anyway.
    // In your case you might need to store your visited tiles this way `Dictionary<int, Segment>` where `int` would be `Segment.Id`.
    // Or some other way.
    // But in my case I can just get these visited tiles this way.
    Segment[] segments = new Segment[cost.Keys.Count];

    int i = 0;
    foreach (int segmentId in cost.Keys)
    {
        segments[i] = this._gridSegmentsCache[segmentId];

        ++i;
    }

    return segments;
}

More Details (My thoughts and steps I took to discover that algorithm above works.)

For small maps Flow Field algorithm would work in some cases.

I am also looking for the same thing. What I understood is in case we have max steps to take to reach some point that Flood Fill and similar algorithms won't work. The reason - they don't take into account the calculation of number of steps taken to reach the point. So in the end we need the same algorithm that is going to calculate a shortest path to do the job of calculating all possible distances it can reach with this amount of movement points.

We could use concept of Flow Field to optimize memory footprint and only save number of moves that need to be taken from one point of map to another. But the issue with this approach is not memory, it's rather we would have to recalculate this field each time some change on a map changes the movement cost of a tile. One tile can affect many paths that were calculated before, so it would only be efficient for maps that don't change their movement cost of a tile.

What if you don't care about movement points to reach some tile? - You can just as well do the Flood Fill constrained by distance to check if this tile is reachable at all. Or if you don't need to check if it's reachable - then for a grid and hex maps it's easy to just calculate the tiles from simple math like Clamp((int)(localPos +- radius), 0, maxX); - then use this result to iterate through tiles to get the ones you need. (This is rough pseudo-code, just for example.)

But of course, if we take CIV 5 as an example, imagine tile changing to mountains, enemy unit stepping on a tile, your other unit occupies that other tile, a building, an obstacle, a river, an ocean. If we take into account all of these variables I can assume that Flow Field would be a lot slower than using A*.

DFS or BFS?

Using DFS or BFS = not possible for weighted graphs. https://stackoverflow.com/questions/30409493/using-bfs-for-weighted-graphs

So our case like CIV 5 wouldn't work.

A*

If we have a case like CIV 5 and our Unit has 5 movement points and we need to get all of the tiles that we can reach with those 5 movement points - then we need to use pathfinding algorithm that is going to be used to find path to a tile player chooses this Unit to go to, otherwise the result of path a Unit takes and tiles that Unit can reach will be inconsistent.

In code: Select all tiles that are distanced at Units movement points as if each tile cost was 1 or lower possible distance. Run A* on each of those to get correct distances and to check if they are reachable.

I keep thinking that there is a more efficient approach, even when using A*. I would love to hear any ideas to optimize this to not run A* on every possible tile. I think @UnderscoreZero is closer to the most efficient and right approach, it might even be the one. I am just leaving all of the considerations that I have taken till this point.

Conclusion

I came to a conclusion that we just need to calculate a Weighted Flow Field and stop adding neighbours when max number of movement points is reached.

Basically a Weighted Flow Field with distance limit and starting from position of a Unit.

(Feel free to correct me if I am wrong, I would be very thankful for finding a better approach or fixing a mistake.)

Additional Resources

https://www.youtube.com/watch?v=zr6ObNVgytk

https://www.youtube.com/watch?v=tSe6ZqDKB0Y

https://www.redblobgames.com/pathfinding/a-star/introduction.html

https://www.redblobgames.com/pathfinding/tower-defense/

Answer 3

You can actually do this without A*. I did this on a hex grid using recursion but the premise is the same.

You start at your characters current position with the set number of moves. then move outward in all directions reducing the number of moves by the amount of moves required to enter that square. Then repeat for each square you entered.

One thing to remember is that when moving to a square already visited, you must check the movement that the character had on that square, if it is higher than your current movement, don't enter the square.

Once you are done, you highlight any square that has 0 or more moves on it.

I did this in sort of a hacky way in that the moves were saved to each point on the map rather than an array but to me it ended up working very well. No A* required.