Why is this maze generation algorithm producing one way roads?

Question

I'm trying to write an algorithm to create mazes. The algorithm (DFS) looks like this:

Start at a random cell.

Mark the current cell as visited, get a list of the neighbors. For each neighbor, starting with a randomly selected neighbor:
If that neighbor hasn't been visited, remove the wall between this cell and that neighbor, and then recurse with that neighbor as the current cell.

But it produces mazes like this:

and I don't know why the algorithm creates full lanes instead of creating dead ends as well to make it look more like a maze instead of a one way road.

I suspected bad random selection, faulty backtracking or that the algorithm marks each cell as visited in the recursive step resulting in no dead ends as it can't go back to a cell but I can't narrow down the problem. Small mazes seem to produce the same problem.

Code:

std::vector<std::pair<int, int>> getAdjacentCells(Cell arr[N][M], int i, int j)
{
    std::vector<std::pair<int, int>> neighbor_vec;
    if(i-2 >= 0)
        neighbor_vec.push_back(std::pair<int, int>(i-2, j));
    if(i+2 < N)
        neighbor_vec.push_back(std::pair<int, int>(i+2, j));
    if(j-2 >= 0)
        neighbor_vec.push_back(std::pair<int, int>(i, j-2));
    if(j+2 < M)
        neighbor_vec.push_back(std::pair<int, int>(i, j+2));

    return neighbor_vec;
}


void genMaze(Cell arr[N][M], int i, int j)
{
    // mark the current cell as visited
    Cell &curCell = arr[i][j];
    curCell.visited = true;
    curCell.isWall = false;

    // get a list of its neighbors
    std::vector<std::pair<int, int>> neighbors = getAdjacentCells(arr, i, j);

    // shuffle neighbor vector
    std::random_shuffle( neighbors.begin(), neighbors.end() );

    for(std::pair<int, int> coord : neighbors)
    {
        int x,y;
        x = coord.first;
        y = coord.second;

        Cell &curNeighbor = arr[x][y];

        if(!curNeighbor.visited)   // remove wall inbetween given cell and neighbor
        {

            if(!(i-x))   // on the same column
            {

                if(j-y < 0)  // right hand neighbor
                {
                    arr[i][j+1].isWall = false;
                    return genMaze(arr, x,y);
                }
                else    // left hand neighbor
                {
                    arr[i][j-1].isWall = false;
                    return genMaze(arr, x,y);
                }

            }
            else     // not in the same column
            {

                if(i-x < 0)  // bottom neighbor
                {
                    arr[i+1][j].isWall = false;
                    return genMaze(arr, x,y);
                }
                else    // top neighbor
                {
                    arr[i-1][j].isWall = false;
                    return genMaze(arr, x,y);
                }

            }
        }

    }

    arr[i][j].isEnd = true; // mark ending
}

The cell class consists only flags. It seems to be the same algorithm as post (although different problem): maze problem and Recursive backtracker algorithm

I would be grateful for any ideas or explanations.

First of all, how well do you know the algorithm being used? To be able to debug your code in any meaningful way, you need to know the algorithm fairly well. Once you do, then use a debugger to step through the code statement by statement until you detect a problem. And remember that it helps to start with the smallest input set possible that replicates the faulty behavior. — Some programmer dude
Why do you expect that this algorithm cannot produce dead ends? I see nothing that would prevent this algorithm from removing walls in a spiral pattern, to arrive at a dead end in the middle. — Sam Varshavchik
@SamVarshavchik After playing around with the maze size, it never did produce a maze with a dead end. Only one way paths. — DavisR5
That's probably because of some artifact resulting in a faulty random number generator, as evidenced by the shown path. Once the flaw in the random number generator is identified (and since the rng isn't shown here, that's something that only you can figure out, since only you know what the mysterious rng function does), you'll have plenty of dead ends. — Sam Varshavchik
To generate dead ends, the algorithms would need to sometimes choose not to dig through to any of the unvisited neighbors. But yours always goes somewhere; almost every visited cell would have exactly two ways out, one through which the algorithm entered and one through which it chose to exit. — Igor Tandetnik

DavisR5 DavisR5 · Accepted Answer · 2021-07-28T11:58:24

The algorithm produces a one way path as further generation of other paths is not included. It needs to further produce dead ends after the first on is created. In the algorithm I implemented, I did not account for further generation of other paths;

So when a dead-end is reached, it needs to backtrack through the path until it reaches a cell with an unvisited neighbour. Then it continues the generation with a new path until a dead end is reached. This stops when all valid neighbors of all cells have been visited.

Code to add before marking the end:

for(int a = 0; a < N; a++)
{
    for(int b = 0; b < M; b++)
    {
        if(arr[a][b].visited) // for every visited cell in the maze, get their neighbors
        {
            std::vector<std::pair<int, int>> neighborOfCurCell = getAdjacentCells(arr, a, b);

            int visitedNeighborCount = 0;

            // for every neighbor, count the unvisited cells
            for(auto neighbor : neighborOfCurCell)
            {
                Cell &currentNeighbor = arr[neighbor.first][neighbor.second];

                if(currentNeighbor.visited)
                    visitedNeighborCount++;
            }

            // if there is an unvisited neighbor after completing a path, backtrack with current cell
            if(visitedNeighborCount < neighborOfCurCell.size())
                return genMaze( arr, a, b );
        }
    }
}

Example:

Why is this maze generation algorithm producing one way roads?

1 Answers