How to find all possible destinations, within a certain walking distance of a unit?

Question

I have a standard 2D grid that i use for pathfinding. I already use A* to find the path of my units when I want to move them around.

What I need to implement now is a preview of all possible destinations of the unit when it is selected.

Here is what I want to achieve. The yellow/orange cells represent the possible destinations.

I want to make this as optimized as possible, because it can be executed on very big maps and for multiple units.

I have something in mind but I wonder if there is better approach for this.

Here is my idea:

1. Get a list of all cells that are walkable in a square around my unit. The square will be from Unit.X - Unit.Speed to Unit.X + Unit.Speed for X axis and Unit.Y - Unit.Speed to Unit.Y + Unit.Speed for Y axis.

2. For each element in this list, execute A* search to see if it is possible to find a path.

By doing the search for only the cells that are within my unit range I should be able to do this on big maps.

Basically this is the same feature that we have in games like Heroes 3 and many other turn based games.

Screenshot:

I was also wondering when it is a good idea to execute this pathfinding logic. When you select a unit (might result a spike) or when something moves on the map to update the list of all possible destinations of all units on the map.

Answer 1

You're over-thinking this. There are well-known optimal algorithms to solve it without running A* over and over.

If the edges of your graph can have different traversal costs, then you want to run Dijkstra's algorithm (like A* with no heuristic), ignoring neighbours beyond your total cost limit. All the nodes it visits and adds to the closed set are within your movement range.

If the edges of your graph all have the same traversal cost, then breadth-first search suffices, with a maximum hop count. Again, ignore neighbours that would take you beyond your hop count budget, and all the nodes you visited and added to the closed set are within your movement range.

Both algorithms give you the whole reachable set in a single invocation from your starting point, without needing to pick out candidate reachable tiles in advance.

Answer 2

In the end, a simple BFS as DMGregory recommended really did the work.

This particulate implementation uses C#, but it can be easily recreated in other language.

public List<Node> GetPossibleDestinations(Graph graph, Node start, int distanceLimit)
{
    var frontier = new Queue<Node>();
    frontier.Enqueue(start);
    var visited = new List<Node>();
    visited.Add(start);

    while (frontier.Count > 0)
    {
        var currentNode = frontier.Dequeue();

        if (currentNode.distance >= distanceLimit)
        {
            continue;
        }

        var neighbors = graph.GetNeighbours(currentNode);
        foreach (var neighbor in neighbors)
        {
            if (neighbor.nodeType == NodeType.Open && !visited.Contains(neighbor))
            {
                frontier.Enqueue(neighbor);
                visited.Add(neighbor);
                neighbor.distance = 1 + currentNode.distance;
            }
        }
    }

    return visited;
}

public List<Node> GetNeighbours(Node node)
{
    List<Node> neighbours = new List<Node>();

    for (int x = -1; x <= 1; x++)
    {
        for (int y = -1; y <= 1; y++)
        {
            if (x == 0 && y == 0)
                continue;

            int checkX = node.gridX + x;
            int checkY = node.gridY + y;

            if (checkX >= 0 && checkX < graphSizeX && checkY >= 0 && checkY < graphSizeY)
            {
                neighbours.Add(nodes[checkX, checkY]);
            }
        }
    }

    return neighbours;
}