生成迷宫的好算法是什么？

Question

假设您想要一个 N × M 网格上的简单迷宫，有一条路径通过，并且有大量死胡同，但这看起来“正确”（即就像有人手工制作的，没有太多微小的死角之类的）。有已知的方法可以做到这一点吗？

Answer 1

从 http://www.astrolog.org/labyrnth/algrithm.htm

递归回溯器：这与下面描述的递归回溯求解方法有些关系，并且需要堆栈达到迷宫的大小。雕刻时，尽可能贪婪，如果当前单元格旁边有一个未制作的部分，则始终雕刻到未制作的部分。每次移动到新单元格时，将前一个单元格压入堆栈。如果当前位置旁边没有未制作的单元格，则将堆栈弹出到上一个位置。当您从堆栈中弹出所有内容时，迷宫就完成了。该算法导致迷宫具有尽可能高的“河流”系数，死胡同更少但更长，并且通常是非常长且曲折的解决方案。它运行得相当快，尽管 Prim 的算法要快一些。递归回溯不能用作墙加法器，因为这样做往往会导致沿着外部边缘的解决方案路径，其中迷宫的整个内部通过单个茎连接到边界。

他们只产生 10% 的死胡同

是该方法生成的迷宫的示例。

Answer 2

事实证明，有 12 种经典算法可以生成“完美”迷宫。如果迷宫只有一种解决方案，那么它就是完美的。以下是每个算法的一些链接，按照我的偏好大致顺序排列。

1. 克鲁斯卡尔的
2. 普里姆的
3. 递归回溯器
4. 奥尔德斯-布罗德
5. 成长的树
6. 猎杀
7. 威尔逊的
8. 埃勒的
9. 元胞自动机 （简单的）
10. 递归除法 （好简单）
11. 响尾蛇 （可预测的）
12. 二叉树 （有缺陷）

欲了解更多信息，请查看 迷宫 在 GitHub 上，一个实现所有标准迷宫生成/求解算法的 Python 库。

Answer 3

一个非常简单的解决方案可能是将随机权重分配给图边并应用 克鲁斯卡尔算法 找到最小生成树。

关于迷宫生成算法的最佳讨论： http://www.jamisbuck.org/presentations/rubyconf2011/index.html （几天前在 HN 上）。

Answer 4

奇怪的是，通过稍微改变“规范”规则并从随机配置开始， 康威的生命游戏 似乎会生成非常漂亮的迷宫！

（我不记得确切的规则，但这是一个非常简单的修改，往往会“致密”细胞群......）

Answer 5

我最喜欢的方法是使用 Kruskal 算法，但是当随机选择并删除边缘时，根据其连接的边缘类型对选择进行加权。

通过改变不同边缘类型的权重，您可以生成具有许多不同特征或“个性”的迷宫。请参阅我的示例：

https://mtimmerm.github.io/webStuff/maze.html

Answer 6

生成迷宫的方法之一是 Prim 算法的随机版本。

从充满墙壁的网格开始。选择一个单元格，将其标记为迷宫的一部分。将单元格的墙壁添加到墙壁列表中。虽然列表中有墙：

从列表中随机选择一面墙。如果对面的单元格尚未进入迷宫：

(i) 将墙设为通道，并将对面的单元格标记为迷宫的一部分。

(ii) 将单元格的相邻墙壁添加到墙壁列表中。

如果对面的单元格已经在迷宫中，则从列表中删除墙。

更多了解请点击 这里

Answer 7

这是用伪代码编写的 DFS 算法：

创建一个 CellStack (LIFO) 来保存单元位置列表
设置 TotalCells = 网格中的单元格数量
随机选择一个单元格并将其命名为 CurrentCell
设置已访问单元格 = 1

而访问cells <TotalCells发现所有墙壁都完好无损的CurrentCell的邻居
如果找到一个或多个随机选择一个
推倒它和 CurrentCell 之间的墙
将 CurrentCell 位置推送到 CellStack 上
使新单元格成为 CurrentCell
将1添加到访问室中，其他弹出了Cellstack的最新单元格
使其成为电流式Endif Endif Endif