关于生成迷宫的锯齿形

Question

老师，我发现对于本节课的代码，不管是在让random queue更随机前还是更随机后，我们生成的迷宫都有大量锯齿形，请问这是什么原因造成的？我们又可以如何规避这个问题？

Answer 1

liuyubobobo 2022-10-26 03:55:55

如何更“随机”本身是一个非常大的话题了。我可以提供一些思路：

首先，你需要分析一下，为什么会产生这种情况？（自己试试看？有必要的话，实际跟踪一下现在的程序，看一看到底为什么会产生这种“锯齿状”的形状？）

==========

其核心原因是，我们的算法本质还是广度优先遍历，只不过广度优先遍历的顺序随机了而已。广度优先遍历就会导致，在一个节点的时候，会优先把这个节点周围没有遍历的节点都“占住”，回忆一下，如果我们使用纯粹的广度优先遍历生成的迷宫，本质是不是就是一个“大号的锯齿”？

怎么解决？一个显然的思路是，广度优先遍历应该和深度优先遍历结合起来。也就是，我们在一个节点，去根据广度优先遍历“占住”他的四个方向的节点以后，应该有一定的概率基于某一个方向做深度优先遍历。

以下的代码是我尝试的基于这个思路修改的 run 函数。其中我把从一个节点向外扩展四个方向封装成了一个 expand 函数，这样方便调用。你可以看到，在 expand 函数中，有一定的概率（我设置的是 90%）基于扩展的一个方向的节点继续扩展（即深度优先遍历）。

注意，为了进一步引入随机性，expand 中对四个方向的遍历顺序每次也是随机的。具体参考以下代码：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

private void run(){         setRoadData(-1, -1);                   RandomQueue<Position> queue = new RandomQueue<Position>();         Position first = new Position(data.getEntranceX(), data.getEntranceY()+1);         queue.add(first);         data.visited[first.getX()][first.getY()] = true;         data.openMist(first.getX(), first.getY());                   while(queue.size() != 0){             Position curPos = queue.remove();             expand(curPos, queue);         }                   setRoadData(-1, -1);     }           void expand(Position cur, RandomQueue<Position> q){                   // 进一步随机，每次遍历四个方向的顺序是随机的，而非固定的         ArrayList<Integer> dirs = new ArrayList<>();         for(int i = 0; i < 4; i ++) dirs.add(i);         Collections.shuffle(dirs);                   for(int i = 0 ; i < 4 ; i ++){             int newX = cur.getX() + d[dirs.get(i)][0]*2;             int newY = cur.getY() + d[dirs.get(i)][1]*2;             if(data.inArea(newX, newY) && !data.visited[newX][newY]){                 Position newPosition = new Position(newX, newY);                 q.add(newPosition);                 data.visited[newX][newY] = true;                 data.openMist(newX, newY);                 setRoadData(cur.getX() + d[dirs.get(i)][0], cur.getY() + d[dirs.get(i)][1]);                                   //90% 的概率基于这个方向再往深度走一层                 if(Math.random() < 0.9) expand(newPosition, q);             }         }     }

加入这一机制之后，这一情况就好转很多。在我的环境下的一次运行结果如下：

如果你对此还不满意，还可以思考更多随机的策略，比如：

1）锯齿本质就是长度为 1 就到思路的通路。我们是否可能在可能的情况下，让每条通路的长度至少为 2?（更进一步，至少为 3？至少为 4）

2）即使如此，锯齿还是无法避免的，因为当空间过于“拥挤”的时候，通路没地儿可去，只能走一步就退回来了。那么在这种情况下，我们是否能直接就把这个锯齿的通路扔掉？（整个迷宫的通路不在占据 board 上每一个间隔的格子了。）

3）我们现在深度拓展的概率是 90%，这个概率是个定值，我们是否可能让这个值也是随机的（或者变化的）？（注意，因为你不需要产生锯齿，所以这个概率值在初始应该比较高，以多走一层防止锯齿的出现，所以让这个概率值完全的随机也不是好主意。一个简单的方式是让这个概率值递减，这有点儿类似模拟退火的思想。）

等等等等。

这个程序可供拓展的地方非常多，印象里，这一章的最后，我也会介绍更多和迷宫生成相关的拓展内容。整体，当来到更加“真实世界”的程序中的时候，很多问题是 open 的。没有一定的对或者一定的不对。但是，当你尝试解决一个问题的时候，你需要做的是：

1）用更加数学（或者形式化的方式）定义问题本身。（比如你的描述，“锯齿形”的迷宫，就不是形式化的。我将其定义成“长度为 1 的通路”，就是更形式画的。）

2）一旦问题定义清晰了，很多时候可能得解决方案也就出现了。（一但能定义清楚了我们其实不希望有那么多“长度为 1 的通路”，我们就可以尽量让通路的长度至少为 2。）

继续加油！：）

• 提问者 tobeabee #1

  非常感谢！