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

Question

假设你想在一个N×M网格上有一个简单的迷宫,有一条路径通过,并且有很多死角,但看起来"正确"(就像有人手工制作而没有太多微小的死角而且所有那些).有没有一种已知的方法来做到这一点？

Answer 1

事实证明,有12种经典算法可以生成"完美"的迷宫.如果迷宫只有一种解决方案,它就是完美的.以下是每个算法的一些链接,按照我的偏好粗略排序.

1. 克鲁斯卡的
2. 普里姆的
3. 递归回溯
4. 奥尔德斯 - 布罗德
5. 生长树
6. 亨特和杀
7. 威尔逊
8. 埃勒的
9. 细胞自动机 (简易)
10. 递归分区 (非常简单)
11. 响尾蛇 (可预测)
12. 二叉树 (有缺陷)

有关更多信息,请查看GitHub上的mazelib,这是一个实现所有标准迷宫生成/求解算法的Python库.

Answer 2

来自http://www.astrolog.org/labyrnth/algrithm.htm

递归回溯:这与下面描述的递归回溯解决方法有些相关,并且需要叠加到迷宫的大小.在雕刻时,尽可能贪婪,如果一个人在当前的牢房旁边,他们总是刻在一个未经制作的部分.每次移动到新单元格时,按下堆叠上的前单元格.如果当前位置旁边没有未编辑的单元格,则将堆栈弹出到上一个位置.当你从堆栈中弹出一切时,迷宫就完成了.该算法使Mazes具有尽可能高的"河流"因子,具有更少但更长的死角,并且通常是非常长且扭曲的解决方案.它的运行速度非常快,尽管Prim的算法速度要快一些.递归回溯不能用作墙加法器,

它们只产生10%的死角

是该方法生成的迷宫的一个例子.

Answer 3

一个非常简单的解决方案是将随机权重分配给图形边缘,并应用Kruskal算法来查找最小生成树.

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

Answer 4

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

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

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

Answer 5

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

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