回溯迷宫算法似乎不会一直回退

基本上，我有这样的观点：首先，一堆代码会生成一个不可穿越的迷宫。它根据几个参数在二维数组的某些空间中随机设置墙。然后我有一个回溯算法去穿透墙壁，直到整个事物都可以穿越。事情是，该程序似乎并没有回到堆栈中。回溯迷宫算法似乎不会一直回退

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

移动（X，Y）{
如果你可以去了，还没有去过那里已经：
移动（X，Y - 1）
如果你可以去正确的，并没有在那里已经：
移动（X + 1，Y）
...
}

等了其他方向。每次移动时，都会在坐标处设置两个独立的布尔二维数组（一个临时的，一个永久性的），以表明您已处于某个元素中。一旦它不能进一步发展，它会检查永久2D阵列，看看它是否到处都是。如果不是，它会随机挑选一个在访问和未访问空间（根据临时数组）之间的边界并移除它的墙。整个事件在一个while循环中被调用，所以一旦它遍历了迷宫的一部分，临时2D数组就会被重置，而另一个被保留，并且它会在另一个随机位置再次遍历，直到永久2D数组显示整个迷宫已经被遍历。移动方法中的检查与临时二维数组进行比较，而不是永久性数组。

这几乎可以工作，但我在最终生成的迷宫中不断找到一些无法到达的区域。否则，它会以我想要的方式创造一个迷宫。事情是，我发现这样做的原因是它不会一直回到堆栈中。

如果我将其更改为检查临时二维数组以完成而不是永久性数组（因此使其在一次运行中执行一次完整遍历以将其标记为完整，而不是在多次迭代中执行完整运行），它将继续前进。我必须设置一个柜台来打破它。结果是一座“迷宫”，墙壁被拆除的太多了。通过检查算法所采用的路线，我发现它没有正确地回溯，并且没有返回到堆栈中几乎足够远的堆栈中，并且在宣布自己无缘无故完成之前经常被卡住在单个元素上进行数十次递归完全消除了需要拆除的零墙。

我已经尝试了两次运行较早的那个，但它不断敲出不需要被淘汰并使得迷宫太稀疏的墙。我不知道为什么这会发生。

来源

2011-04-05 AndroidHopeful

我试图创建一个创建迷宫的方法时遇到了类似的问题。制作迷宫时最重要的事情就是不要在迷宫中创建连通房间的孤立“岛屿”。这里是我的伪代码解决方案

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是很多像你的举动（）函数

在现实中，你可能想

描述了一个“门”作为缺少的壁
和没有门的房间作为一个带四个壁

乙UT斯达康总的原则是：当算法停止

启动递归算法某处
：找到一个地方，那里有1未访问广场和1走访。
链接这两个一起，从先前未访问过的方形
继续当没有两个正方形满足（2）您已完成，所有的广场连接

来源

2011-04-11 12:07:51

谢谢，但我想它了。傻我没有考虑确保方法有返回值，并且返回值分配给每个递归。难怪它没有工作。我没有告诉它维持一个堆栈回去！几个小小的变化，我现在有一个迷宫生成算法，令人惊讶的是，从1x1方格的纯网格到人口稀少的任何配置都可以工作。我得到了一个非线性的迷宫，但仍然需要大量的遍历来完成。虽然谢谢！ – AndroidHopeful 2011-04-15 16:10:25

回溯迷宫算法似乎不会一直回退

回答

相关问题