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

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

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

克鲁斯卡的

普里姆的

递归回溯

奥尔德斯 - 布罗德

生长树

亨特和杀

威尔逊

埃勒的

细胞自动机 (简易)

递归分区 (非常简单)

响尾蛇 (可预测)

二叉树 (有缺陷)

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

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

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

它们只产生10%的死角

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

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

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