Recursively calculate possible pathway on a grid depending on max walk distance

Question

I have a character that is placed on a grid. It has a variable maximum walking distance. Grid fields can be walkable or not walkable. As the character may has to walk around certain not walkable fields to reach his destination his maximum walking distance isn't allways represented by a circle.

See these examples:

Without obstacles, walking distance 7:

With obstacles, walking distance 7: Note how the obstacles affect the players maximum walking distance

To calculate this i've written this recursive function:

static Vector2Int[] GetWalkableFields (Vector2Int position, int steps) {
    List<Vector2Int> walkableFields = new List<Vector2Int>();

    if (steps > 0) {
        foreach (Vector2Int v in GetNearbyFileds(position)) {
            if (m_mc.IsInBounds(v) && m_mc.IsWalkable(v.x, v.y)) {
                walkableFields.Add(v);
                walkableFields.AddRange(GetWalkableFields(v, steps - 1));
            }
        }
        return walkableFields.ToArray();
    } else {
        Vector2Int[] v = { position };

        return v;
    }
}

And this function, that returns all four neighbour fields of a field:

public static Vector2Int[] GetNearbyFileds(Vector2Int position) {
    Vector2Int[] neighbors = new Vector2Int[4];
    neighbors[0] = new Vector2Int(position.x, position.y - 1);
    neighbors[1] = new Vector2Int(position.x, position.y + 1);
    neighbors[2] = new Vector2Int(position.x - 1, position.y);
    neighbors[3] = new Vector2Int(position.x + 1, position.y);

    return neighbors;
}

The function is called with the players position and maximum walking distance (steps) and get's the four neighbour fields and unless the steps are zero calls itselve for every neighbour field with the maximum walking distance decremented.

As you can see in the screenshots, this works absolutely fine. The problem is, as the calculation not only goes away from the player but, in some recursion paths, goes back and fourht between tiles until stepcount zero is reached without even having traveled one field, that this way of calculating the path is really resource heavy. For a walking distance of 7 there are 27646 possible walkways that all are getting calculated. If a player is able to walk 11 fields the calculation takes a few seconds, if he can walk 12 fields Unity crashes while calculating.

Is there a way to calculate this more efficient?

Thank you in advance.

Answer 1

You're on the right track, but we can improve on this in three ways:

1. Introduce to notion of a "Closed Set" (a way to mark sites we've visited so we don't need to re-visit them)

2. Iterate in a breadth-first rather than depth-first manner, so we visit cells in order of shortest distance from the start point.

   This ensures we don't inadvertently mark a cell visited after finding a long route to it, blocking us from exploring a shorter route through that cell later in the search.

3. Don't allocate new collections (new List...) in every iteration of the search - this puts more load on the garbage collector than we need.

Here's an example of how we can do this. Here we pass in & populate a dictionary mapping positions to distances. The caller can then iterate over the keys of that dictionary to find all the reachable sites, and check the values associated with those keys if they need to know the distance to them. You can use this information to reconstruct the shortest path to any reachable site.

// Simple record for book-keeping about our search in progress.
struct PathfindingNode {
     public readonly Vector2Int position;
     public readonly int distance;

     public PathfindingNode(Vector2Int position, int distance) {
         this.position = position;
         this.distance = distance;
     }
}

// Stores the nodes at the frontier of our search.
// The Queue type ensures we visit nodes in a breadth-first order.
Queue<PathfindingNode> _openSet = new Queue<PathfindingNode>();

// Populates a dictionary of reachable tiles.
void FindReachableCells(Dictionary<Vector2Int, int> reachable, Vector2Int startPoint, int maxSteps) {

    // Clear the results of any previous pathfinding.
    reachable.Clear();

    // Seed the pathfinding with our start point.
    reachable.Add(startPoint, 0);
    _openSet.Enqueue(new PathfindingNode(startPoint, 0));

    // As long as there are nodes in the frontier...
    while(_openSet.Count > 0) {
        // Pop the oldest one out of the collection.
        PathfindingNode parent = _openSet.Dequeue();

        // Check each neighbouring cell for reachability,
        // and add it to the collection if we can reach it.  
        float childDistance = parent.distance + 1;    
        CheckChild(parent.position.x - 1, parent.position.y, childDistance, maxSteps, reachable);
        CheckChild(parent.position.x + 1, parent.position.y, childDistance, maxSteps, reachable);
        CheckChild(parent.position.x, parent.position.y - 1, childDistance, maxSteps, reachable);
        CheckChild(parent.position.x, parent.position.y + 1, childDistance, maxSteps, reachable);    
    }
}

void CheckChild(int x, int y, int distance, int maxDistance, Dictionary<Vector2Int, int> reachable) {
    var position = new Vector2Int(x, y);

    // Exclude nodes that are out of bounds or not walkable.        
    if(map.IsInBounds(position) == false || map.IsWalkable(position) == false)
        return;

    // Exclude nodes we've already visited by some other route.
    if(reachable.ContainsKey(position))
        return;

    // Aha! We found a new walkable node in range. Add it to our reachable set.
    reachable.Add(position, distance);

    // And if we have room to go further, add it to our frontier
    // to later explore its neighbouring nodes.
    if(distance < maxDistance)
        _openSet.Enqueue(new PathfindingNode(position, distance));
}

Answer 2

I am not sure what is the code you wrote, but when you are getting all nearby fields, it will return you field that you have already checked for. By recursion, you naturally iterate much more squares than necessary. The solution is: have a hashmap of already visited squares, and if the square is visited, do not look for his neighbors. Well, for this, path searching algorithm can be used (which is something you tried to write ,,come up with"). I would suggest you to look up algorithms like BFS, you can find many examples along with sources online. BFS marks visited squares so it is optimized. Also, the complexity would be N, N being the max amount of squares you can visit.

Alternatively, please note that BFS is not so performant if you have no or small amount of obstacles, for that would be better A* (if you will later walk towards some point).

Feel free to contact me for more info.

PS: Can you share the game you have so far? I would like to see it (if it is online)