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

假设您要在N x M网格上创建一个简单的迷宫，该迷宫有一条路径，并且有很多死角，但是看起来"正确"(即像有人手工制作的那样，没有太多微小的死角，所有这些 )。 有已知的方法吗？

---

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

克鲁斯卡尔的

普里姆斯

递归Backtracker

阿尔多·布罗德

越来越多的树

猎杀

威尔逊的

埃勒的

蜂窝自动机(简易)

递归除法(非常简单)

响尾蛇(可预测)

二叉树(有瑕疵)

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

---

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

Recursive backtracker: This is somewhat related to the recursive backtracker solving method described below, and requires stack up to the size of the Maze. When carving, be as greedy as possible, and always carve into an unmade section if one is next to the current cell. Each time you move to a new cell, push the former cell on the stack. If there are no unmade cells next to the current position, pop the stack to the previous position. The Maze is done when you pop everything off the stack. This algorithm results in Mazes with about as high a"river" factor as possible, with fewer but longer dead ends, and usually a very long and twisty solution. It runs quite fast, although Prim's algorithm is a bit faster. Recursive backtracking doesn't work as a wall adder, because doing so tends to result in a solution path that follows the outside edge, where the entire interior of the Maze is attached to the boundary by a single stem.

他们只产生10％的死角

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

---

一个非常简单的解决方案是将随机权重分配给图边缘，然后应用Kruskal算法查找最小生成树。

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

---

奇怪的是，通过稍微更改"规范"规则并从随机配置开始，Conway的《生命游戏》似乎产生了相当不错的迷宫！

(我不记得确切的规则，但这是一个非常简单的修改，倾向于"致密化"细胞群……)

---

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

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

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

---

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

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

从列表中选择一个随机的墙。如果对面的单元格还不在迷宫中：

(i)使墙壁成为一个通道，并在另一侧标记牢房作为迷宫的一部分。

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

如果另一侧的牢房已经在迷宫中，请从列表中移除墙。

欲了解更多信息，请点击这里

---

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

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

而VisitedCells

---