A* Limiting Path Length

Unity Engine
1

Short version: how do I make an A* algorithm such that I can specify the maximum length of a path that can be returned (and, if it finds a path that’s too long, it tries to find a new path that isn’t.) I can assume that whichever tile is selected as a target tile does have a valid path that can be made to it; there won’t be a situation where that isn’t true.

Long version:

I have a basic A* implementation that look like this:

public List<Vector2i> FindPath(Vector2i start, Vector2i end)
{
    if (start.Equals(end))
        return new List<Vector2i>();

    ResetNodes();

    PathNode startNode = searchArea[start.x, start.y];
    PathNode endNode = searchArea[end.x, end.y];

    startNode.open = true;

    startNode.distanceToEnd = Heuristic(start, end); // Simple Manhattan distance.
    startNode.accumCost = 0;

    openList.Add(startNode);

    while (openList.Count > 0)
    {
        PathNode current = FindBestNode(); // Find node with the lowest F value.

        if (current == null)
            break;

        if (current == endNode)
            return FindFinalPath(startNode, endNode); // Walk the nodes backwards (using parent references).

        for (int i = 0; i < 4; i++)
        {
            Vector2i neighborPos = current.tilePos + Vector2i.directions[i];

            PathNode neighbor = null;

            if (Map.InTileBounds(neighborPos.x, neighborPos.y))
                neighbor = searchArea[neighborPos.x, neighborPos.y];

            if (neighbor == null || !neighbor.passable)
                continue;

            ushort cost = (ushort)(current.accumCost + neighbor.tileCost); // TileCost is for a weighting system.
            ushort heuristic = Heuristic(neighbor.tilePos, end);

            if (!neighbor.open && !neighbor.closed)
            {
                neighbor.accumCost = cost;
                neighbor.distanceToEnd = (ushort)(cost + heuristic);
                neighbor.parent = current;
                neighbor.open = true;
                openList.Add(neighbor);
            }
            else
            {
                if (neighbor.accumCost > cost)
                {
                    neighbor.accumCost = cost;
                    neighbor.distanceToEnd = (ushort)(cost + heuristic);

                    neighbor.parent = current;
                }
            }
        }

        openList.Remove(current);
        current.closed = true;
    }

    return new List<Vector2i>();
}

While certainly not very optimized, it does the job of finding a path. Here’s the problem: I add a tileCost weighting system so that the pathfinder will try to avoid specific tiles if possible.

Entities have a movement points system - that is, they can only move a certain amount of tiles each turn.
They may choose to move to a tile that can be reached with their current amount of available moves, but there may be a tile that the pathfinder tries to avoid. It will avoid it and create a path to the target correctly. However, the target path requires walking more tiles than the entity can move in that turn.

In this case, I need the pathfinder to choose to go through the tiles that it would otherwise avoid. However, I can’t seem to make this happen without freezing Unity in an infinite loop or failing to find a path entirely. This may be because I’m new to this algorithm and don’t fully understand it.

I’ve tried putting the current node in the closed list upon reaching a dead end (running out of moves), I’ve tried adding a max cost to tiles past where moves would run out, I’ve tried doing a system where I check the path at the end and if it’s too long, fill its tiles with a high cost value and then try recomputing a new path… all of these end in infinite loops or failure to find any path.

So, I simply need a way to limit the maximum length of a path that can be returned and force a recalculation of paths when that happens (it shouldn’t keep reconsidering the same path over and over).

Should I be trying another algorithm?

2

A star finds the shortest path from point A to point B, assuming that the heuristic is valid. If the returned path is too long, then there is no path which is shorter.

It sounds to me that you want to consider different end points when the returned path is too long. If A → B is too long, then find a different point C, between A and B, and path to that. At the end of the search from A to B, you have the returned path, and you know the maximum movable distance. So step through each point along the path, calculate how much movement is consumed to travel along it, and determine the best stopping point when the movement is exceeded.

3

I’ll try to illustrate what I mean. Here’s a rather poorly drawn grid.

2552174--177500--1.png
We have a start and end location. The shortest path to this end position is straight right from the start. Let’s say this entity can move 4 cells in the turn, so it has just enough to get there.

But we have this red x tile. This tile is a walkable tile - it CAN be moved across. But there’s a cost on it that makes it unfavorable to do so. So my goal is to tell the pathfinder to [try] to avoid that tile if it can. And it produces a result that looks like:

2552174--177501--2.png

This is a valid path, but requires moving 6 tiles to get there. The entity can only move 4. So what I want is that the pathfinding algorithm forces the path to go through the red x (since it’s a walkable path) even though it was unfavorable to walk through it. It should find that there isn’t another valid path except through it.

I can’t seem to make this happen.

4

It sounds like this is what you want?

  • Find a path <=4 tiles long that avoids high movement costs.
  • If no such path exists, try to find a path <=4 tiles long while ignoring all movement costs.

I think you just want to fallback to a pathfinding algorithm that doesn’t use movement costs. Or use the same algorithm after reassigning all tiles to have equal movement cost.

5

It seems I may have been overthinking it. Thanks for that hint, I’ll see what I can do.