回溯迷宫算法似乎并没有一路返回

Question

基本上，我有这样的：首先，一堆代码生成一个不可穿越的迷宫。它根据一些参数在二维阵列的某些空间中随机设置墙壁。然后我有一个回溯算法，通过它来敲除墙壁，直到整个事情是可穿越的。问题是，程序似乎并没有一直返回到堆栈中。

这是非常标准的回溯代码。该算法从随机位置开始，然后以伪代码进行：

move(x, y){
如果你可以上去但还没有去过那里：
移动 (x, y - 1)
如果你可以向右走但还没有去过那里：
移动 (x + 1, y)
...
其他

方向依此类推。每次您移动时，都会在坐标处设置两个独立的二维布尔数组（一个临时的，一个永久的），以表明您已经处于某个元素中。一旦无法继续前进，它就会检查永久二维数组，看看它是否已经无处不在。如果没有，它会随机选择一堵位于已访问空间和未访问空间之间的墙（根据临时数组）并将其删除。整个过程是在 while 循环中调用的，因此一旦它遍历了迷宫的一块，临时 2D 数组就会被重置，同时保留另一个数组，并在另一个随机位置再次遍历，直到永久 2D 数组显示整个迷宫已经完成。被遍历。 move 方法中的检查是与临时 2D 数组进行比较，而不是与永久数组进行比较。

这几乎可行，但我不断在最终生成的迷宫中发现一些无法到达的区域。否则它会按照我想要的方式生成一个迷宫，效果非常好。问题是，我发现这样做的原因是它没有一直回到堆栈中。

如果我将其更改为检查临时二维数组而不是永久数组的完成情况（从而使其在一次运行中进行一次完整遍历以将其标记为完成，而不是在多次迭代中进行完整运行），它将继续下去等等。我必须设置一个计数器来打破它。结果是一个“迷宫”，有太多的墙壁被拆除。检查算法所采用的路线，我发现它没有正确回溯，并且没有回到堆栈中足够远的位置，并且通常只是卡在单个元素上数十次递归，然后无缘无故地声明自己已完成根本没有，并且需要拆除零的墙。

我已经尝试运行前一个迷宫两次，但它不断地撞倒不需要被撞倒的墙壁，并使迷宫变得过于稀疏。我不知道为什么会发生这种事。

Answer 1

当我试图制定一种创建迷宫的方法时，我也遇到了类似的问题。
制作迷宫时最重要的是尽量不要在迷宫中创建由相连的房间组成的孤立“岛屿”。这是我的伪代码解决方案

Room r=randomRoom();

while(r!=null){
    recursivelyDigNewDoors(r);
    r=null;
    for(i=0;i<rooms.count;i++){
        if(rooms[i].doors.length == 0 && rooms[i].hasNeighborWithDoor() ){ 
        //if there is a room with no doors and that has a neighbor with doors
        Create a door between the doorless room and the one 
        connected to the rest of your maze
        r=rooms[i];
        }
   }
}

，其中 recursivelyDigNewDoors 很像您的 move() 函数

实际上，您可能想将

• “门”描述为缺少墙壁
• ，将没有门的房间描述为有四堵墙的房间

但一般原则是：

1. 在某处开始递归算法
2. 当算法停止时：找到一个有 1 个未访问过的方格和 1 个已访问过的方格的地方。
3. 将这两个方块链接在一起并从之前未访问过的方块继续
4. 当没有两个方块满足 (2) 时，您就完成了并且所有方块都已连接