为什么这种迷宫生成算法会产生单向道路？

Question

我正在尝试编写一个算法来创建迷宫。算法 (DFS) 如下所示：

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.

但它会产生这样的迷宫：

而且我不知道为什么算法会创建完整的车道而不是死胡同，并使它看起来更像迷宫而不是单行道。

我怀疑是错误的随机选择、错误的回溯或者算法在递归步骤中将每个单元格标记为已访问，导致没有死胡同，因为它无法返回到单元格，但我无法缩小问题范围. 小迷宫似乎也会产生同样的问题。

代码：

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
}

单元格 class 仅包含标志。它似乎与 post 算法相同（尽管问题不同）：maze problem and Recursive backtracker algorithm

如有任何想法或解释，我将不胜感激。

Answer 1

该算法会生成一条单向路径，因为 不包括 进一步生成其他路径。创建第一个后，还需要进一步产生死角。在我实现的算法中，我没有考虑进一步生成其他路径；

因此，当到达死胡同时，它需要通过路径回溯，直到到达具有未访问邻居的单元格。然后它以新的路径继续生成，直到到达死胡同。当访问了所有单元格的所有有效邻居时，这将停止。

标记结束前添加的代码：

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 );
        }
    }
}

示例：

为什么这种迷宫生成算法会产生单向道路？

Why is this maze generation algorithm producing one way roads?

c++

algorithm

maze

generator

depth-first-search