Recursive backtracking maze leaves tiles sometimes

Question

I have a basic backtracking algorithm that generates mazes for me. But sometimes it does not "visit" all tiles/cells. I'm wondering what is wrong, the algorithm does backtrack properly and it should check all directions on each tile/cell but the "unvisited" tiles/cells do not get touched at all.

This is the backtracking algorithm:

void GenerateMaze(Coordinate tilePos)
    {
        //Mark the current position visited
        tileMap[tilePos.x, tilePos.y].visited = true;
        //Randomize directions
        Shuffle<Coordinate>(directions);
        foreach(Coordinate d in directions)
        {
            //Check if the new position is within bounds
            if (tilePos.x + d.x >= 0 && tilePos.x + d.x < mapWidth && tilePos.y + d.y >= 0 && tilePos.y + d.y < mapHeight)
            {
                //Check if the tile is already visited
                if (!tileMap[tilePos.x + d.x, tilePos.y + d.y].visited)
                {
                    //Carve through walls from this tile to next
                    Carve(tilePos, d);
                    //Recursively call this method on the next tile
                    GenerateMaze(new Coordinate(tilePos.x + d.x, tilePos.y + d.y));
                }
            }
        }
    }

In case you are interested, this is the Carve method:

private void Carve(Coordinate position, Coordinate direction)
    {
        if (direction.Equals(new Coordinate(-1, 0)))
        {
            Debug.Log("Carving West from: ");
            tileMap[position.x, position.y].west = true;
            tileMap[position.x + direction.x, position.y + direction.y].east = true;
        }
        else if (direction.Equals(new Coordinate(1, 0)))
        {
            tileMap[position.x, position.y].east = true;
            tileMap[position.x + direction.x, position.y + direction.y].west = true;
        }
        else if (direction.Equals(new Coordinate(0, -1)))
        {
            tileMap[position.x, position.y].south = true;
            tileMap[position.x + direction.x, position.y + direction.y].north = true;
        }
        else if (direction.Equals(new Coordinate(0, 1)))
        {
            tileMap[position.x, position.y].north = true;
            tileMap[position.x + direction.x, position.y + direction.y].south = true;
        }
    }

It just sets the correct wall flags to true depending on the direction the algorithm is going.

In the image bellow you see the maze has 3 "unvisited" tiles. This mostly happens in corners.

Here it leaves a single tile untouched but this time not on the sides.

On a 10x10 maze this seems to happen about 1/10 times. The problem tiles stay unvisited so the algorithm does not process them at all. But since it travels past them and every direction of there neighbors is tested they really should be joining the maze. So what can be wrong?

Answer 1

The problem is

Shuffle<Coordinate>(directions);

At each step, you shuffle the content in directions

But, also remember that, in each step, you iterate through every coordinate in directions

foreach(Coordinate d in directions)
{
     //Visit child node
}

So,because you are discovering the matrix using DFS style, thus, while you are iterating the directions in the parent node, you also visit all its child node. And again, shuffling the directions while visiting each child, this may randomly destroy the iterating process in parent node by messing up the current order of element in directions.

Simple example

In parent, directions order is (0,1,2,3)

Visit first child (direction 0)-> shuffle directions (1,0,2,3)

Go back to parent node, now you will skip one node (direction 1), as the directions content has been changed.

Change this DFS into BFS will fix this problem.

Pseudo code:

Queue<Coordinate> q;
q.add(start)
while(q is not empty){
    Coordinate point = q.dequeue();
    shuffle directions
    for(each direction in directions){
        Add unvisited child node into q
    }
}