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

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

递归回溯器:这与下面描述的递归回溯器求解方法有点关联,并且需要叠加到迷宫的大小。在雕刻的时候,要尽可能贪心,如果一个人在当前的牢房旁边,就要把他刻成一个未成形的部分。每次移动到新单元格时,都将前一个单元格推到堆栈上。如果当前位置旁边没有未映射的单元格,则将堆栈弹出到上一位置。当你把所有东西从堆栈中弹出时,迷宫就完成了。该算法产生的迷宫具有尽可能高的“河”因子,死角较少但较长,通常是一个非常长且曲折的解。它运行得相当快,尽管prim的算法有点快。递归回溯不起墙加法器的作用,因为这样做往往会导致沿着外部边缘的解路径,其中迷宫的整个内部通过一个单根连接到边界。

它们只产生10%的死胡同

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

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

1. Kruskal's
2. Prim's
3. Recursive Backtracker
4. Aldous-Broder
5. Growing Tree
6. Hunt-and-Kill
7. Wilson's
8. Eller's
9. Cellular Automaton (容易)
10. Recursive Division (很容易)
11. Sidewinder (可预测的)
12. Binary Tree (瑕疵)

有关详细信息,请查看 mazelib 在Github上,一个实现所有标准迷宫生成/求解算法的python库。

一个非常简单的解决方案是将随机权重分配给图的边缘并应用 Kruskal's algorithm 找到最小生成树。

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

奇怪的是,通过稍微改变“规范”规则并从随机配置开始, Conway's Game of Life 似乎产生了相当不错的迷宫!

(我不记得确切的规则,但这是一个非常简单的修改,倾向于“密集”细胞群…)

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

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

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

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

从满墙的网格开始。 选择一个单元格,将其标记为迷宫的一部分。将单元格的墙添加到墙列表中。 当列表中有墙时:

从列表中选择一个随机墙。如果对面的牢房还没有进入迷宫:

(i)使墙壁成为通道,并将对面的单元标记为迷宫的一部分。

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

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

要了解更多信息,请单击 here

以下是用伪代码编写的DFS算法:

创建单元堆栈(LIFO)以保存单元位置列表
set totalcells=网格中的单元格数
随机选择一个单元格并将其称为当前单元格
设置VisitedCells=1

当VisitedCells<totalCells 查找当前单元格的所有邻居,所有墙都完好无损
如果找到一个或多个 随机选择一个
拆掉它和电流单元之间的墙
将当前单元格位置推送到单元格堆栈上
使新单元格成为当前单元格
向可见单元格添加1 其他的 从单元格堆栈中弹出最近的单元格项
使其成为当前单元格 菊苣 最后的