1

基本上,我有这个:首先,一堆代码生成一个不可穿越的迷宫。它根据一些参数在二维数组的某些空间中随机设置墙壁。然后我有一个回溯算法通过它来敲掉墙壁,直到整个东西都可以遍历。问题是,程序似乎并没有回到堆栈中。

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

move(x, y){
如果你可以往上走但还没到过:
move (x, y - 1)
如果你可以往右走但还没到过:
move (x + 1, y)
。 ..
}

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

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

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

我尝试过两次运行前面的那个,但它一直在敲掉不需要敲掉的墙壁并使迷宫变得太稀疏。我不知道为什么会发生这种情况。

4

1 回答 1

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)时,您就完成了并且所有正方形都已连接
于 2011-04-11T12:07:51.500 回答