DFS迷宫生成

Question

目前我正在尝试使用以下算法生成迷宫：

// m_maze is a m_dim*m_dim matrix filled which '#' which means a wall and ' ' means a free cell
// const int dxdy[4][2] = { {0, -1}, {-1, 0}, {0, 1}, {1, 0} }; // {UP, LEFT, DOWN, RIGHT}
void Maze::generate() {
std::queue<std::pair<int, int>>neighbours;
neighbours.emplace(0, 0);
m_maze[0][0] = ' '; // marking a free cell
while (!neighbours.empty()) {
    std::pair<int, int> currentCell = neighbours.front();

    for (int d = 0; d < 4; d++) {
        const int newX = currentCell.first + 2*dxdy[d][0];
        const int newY = currentCell.second + 2*dxdy[d][1];

        if (newX >= 0 && newY >= 0 && newX <= m_dim && newY <= m_dim && m_maze[newX][newY] && m_maze[newX][newY] == '#') {
            m_maze[currentCell.first + dxdy[d][0]][currentCell.second + dxdy[d][1]] = ' ';
            m_maze[newX][newY] = ' ';
            neighbours.emplace(newX, newY);
        }
    }

    neighbours.pop();
}
}

问题是输出看起来像这样：

                         #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 ##########################

我认为这个问题来自 if() 语句中的指令，但我不确定。我接受这些指示的方式是：我要拆除一堵墙，然后将下一个单元格标记为空闲。有什么建议吗？

Answer 1

为什么你的算法产生如此规律的结果是因为不存在随机性。 一步步思考算法的工作原理。

在起点 (0,0) ：迷宫变为

@__#####
_#######
_#######
########
########
########

其中，'@'是当前位置，“可用空间”用'_'显示

接下来，

___#####
_#######
@__#####
_#######
_#######
########

然后

___#####
_#######
___#####
_#######
@__#####
########

下一步，“@”的下边位置已经是“_”，只能向右步进。所以就变成了

__@__###
_#######
___#####
_#######
___#####
########

由于后续所有步骤都相同，因此结果如下。

_______#
_#######
_______#
_#######
_______#
########

此示例与您的结果之间的方向不同，但这取决于如何使用数组的索引。