基本上,我有这个:首先,一堆代码生成一个不可穿越的迷宫。它根据一些参数在二维数组的某些空间中随机设置墙壁。然后我有一个回溯算法通过它来敲掉墙壁,直到整个东西都可以遍历。问题是,程序似乎并没有回到堆栈中。
这是非常标准的回溯代码。该算法从一个随机位置开始,然后以伪代码进行:
move(x, y){
如果你可以往上走但还没到过:
move (x, y - 1)
如果你可以往右走但还没到过:
move (x + 1, y)
。 ..
}
其他方向依此类推。每次移动时,都会在坐标处设置两个单独的 2D 布尔数组(一个是临时的,一个是永久的),以表明您已经在某个元素中。一旦它不能继续前进,它就会检查永久二维数组,看看它是否无处不在。如果不是,它会随机选择一个在已访问空间和未访问空间之间的墙(根据临时数组)并将其移除。这整个过程是在一个while循环中调用的,所以一旦它遍历了迷宫的一大块,临时二维数组就会被重置,而另一个则保留,它会在另一个随机位置再次遍历,直到永久二维数组显示整个迷宫已经被遍历。move 方法中的检查与临时二维数组进行比较,而不是永久数组。
这几乎可行,但我一直在最终生成的迷宫中找到一些无法到达的区域。否则,它会按照我想要的方式生成迷宫。问题是,我发现这样做的原因是它不会一直回到堆栈中。
如果我将其更改为检查临时二维数组是否完成而不是永久数组(从而使其在一次运行中进行一次完整遍历以将其标记为完成,而不是在多次迭代中进行完整运行),它将继续下去等等。我必须设置一个计数器来打破它。结果是一个“迷宫”,移除了太多太多的墙壁。检查算法采用的路线,我发现它没有正确回溯,并且没有回到堆栈中足够远的距离,并且经常只是在一个元素上卡住了几十次递归,然后无缘无故地宣布自己完成根本没有拆除零的墙需要拆除。
我尝试过两次运行前面的那个,但它一直在敲掉不需要敲掉的墙壁并使迷宫变得太稀疏。我不知道为什么会发生这种情况。