Why is my recursive pathfinding algorithm not behaving correctly?

Question

For a project I have procedurally generated a series of 'tiles' with coordinates from (0,0) --> (x, y) where (x,y) is the maximum width and height of the tile array. This tile array is then populated randomly with squares and is given an entrance and multiple exit points. I am trying to create an algorithm which, given a starting point, checks whether all the exit points can be reached. To do this, each tile contains data regarding their N-E-S-W adjacent tiles, and a recursive function is called which checks the current tile for an exit, then moves to the North tile, then does the same for East, West, then South.

Here is a (pseudo) example of the code except instead of checking for exits it visits all available tiles and counts them (or it's meant to):

public class Algo
{
    public int Count(Tile tile)
    {
        tile.Visited = true;
        foreach (direction in NESW)
        {
            if(!tile.direction.IsPopulated & !tile.direction.Visited)
            {
                 return Count(tile.direction) + 1;
            }
        }
        return 0;
     }
}

IsPopulated is a boolean which returns true if a tile is populated with a square, Visited is boolean which returns true if the tile has been visited. There is a perimeter of squares around the tile space which ensures the algorithm stays within the bounds of the tile space

For a tile layout like this:

arrows indicated start, direction, and finishing point of the algorithm (the darker bits are populated tiles)

The algorithm returns 17 instead of the expected 21.

It seems as though, when the algorithm reaches a tile which cannot move in any direction, the function returns the count, instead of returning to the call stack and trying again.

Another version I have tried works as expected, however, it is not fruitful and mutates a member variable of the class outside of the method.

public class Algo2
{
    count = 0;
    public void Count(Tile tile)
    {
        tile.Visited = true;
        count += 1;
        foreach (direction in NESW)
        {
            if(!tile.direction.IsPopulated & !tile.direction.Visited)
            {
                 return Count(tile.direction);
            }
        }
     }
}

This returns a value of 21 and works as expected.

Why does the non-fruitful recursive function with side-effects work, while the fruitful function with no side-effects does not?

That just returns 1, and the visit order is the same as previous - visiting 17 tiles in the order shown on the picture — JimothyBucksworth
Yes, sorry, just change return 0 to return 1, because in first method you doesn't count 'leafs' — sTrenat
That just returns an additional 1 - so 18. I think the problem is with the recursion happening within the for loop, rather than how the recursion is stopped. — JimothyBucksworth
Can you provide some data that we could try to test? I still think that return 1 should do equivalent as your 2nd method — sTrenat
What kind of data would you like? The return 0 only serves to end the function. Changing that value would add to the return value by an arbitrary amount, with no logic attached to why it's doing so — JimothyBucksworth

Olivier Jacot-Descombes Olivier Jacot-Descombes · Accepted Answer · 2020-07-04T12:16:02

Finding a path involves back-tracking. I.e., you try to find a path. If you reach the target, you stop. If you reach a dead end or a path already visited, you clear the Visited flag and return, i.e. you give the control back to a less nested recursion level. This level then tries other directions.

Something like this:

bool FindPath(Tile tile)
{
    tile.Visited = true;
    if (tile.IsTarget)
    {
        return true;
    }
    foreach (direction in NESW)
    {
        var nextTile = tile.direction;
        if(!nextTile.IsPopulated && !nextTile.Visited && FindPath(nextTile))
             return true;
        }        
    }
    // Back tracking
    tile.Visited = false;
    return false;
}

If the initial call to FindPath returns true, the path to the target is marked with Visited = true tiles.

Another option is to find all the possible paths to the target (or to several targets). To do this, you would output the currently found path and then continue.

List<Tile> _path = new List<Tile>();

void FindAllPaths(Tile tile)
{
    tile.Visited = true;
    _path.Add(tile);
    if (tile.IsTarget)
    {
        OutputPath(_path);
        return; // If you want to go past a target to
                // find other targets, remove this `return`.
    }
    foreach (direction in NESW)
    {
        var nextTile = tile.direction;
        if(!nextTile.IsPopulated && !nextTile.Visited)
        {
             FindPath(nextTile);
        }        
    }
    // Back tracking
    tile.Visited = false;
    _path.Remove(tile);
}

Instead of using a list with path tiles in the OutputPath method, you can also loop through all the tiles and check the Visited flag. For large mazes it may be more efficient to use a list.

These two algorithms are not aimed at counting all the non-populated tiles. But you could count the path tiles giving you the path length. If you use a list, this is the list count, otherwise you would back-track the count as well. I.e., tile.Visited = true; count++; at the beginning and tile.Visited = false; count--; at the end.

Why is my recursive pathfinding algorithm not behaving correctly?

1 Answers