随机迷宫算法是一种用于自动化生成迷宫的算法，广泛用于游戏制作，且迷宫可以与各种元素相结合碰撞，组装出不同的玩法，其中最著名的要数日式 RPG 中的各种迷宫攻略。
由于迷宫的数学本质实际上是一个 图，因此大量的随机迷宫生成器都是基于图论的。
一个迷宫的拓扑结构可以是一棵 树，这通常意味着迷宫特定的入口和出口之间有且仅有唯一的一条道路；迷宫还可以是一个 有环图 结构，使得入口与出口之间有多条可能的通路，而有环结构往往都是通过在基础的树结构上应用一定的规则，给原本不连通的节点之间 添加边 来实现。
随机迷宫生成的本质即在拥有一定数量的节点和边的（全）连通图 上，通过删除部分边获得其一个子图 ，使得入口节点和出口节点之间的路径尽可能复杂。
随机 DFS 算法
既然迷宫是一个图，那么用图论算法来处理获得子图便是显而易见的方法，其中最简单的一种就是基于 深度优先搜索（DFS）所得到的随机 DFS 算法。随机 DFS 算法利用栈结构，通过每一步对图的边进行随机选择来生成随机的迷宫，其具体步骤如下：
- 将当前节点标记为“已访问”
- 如果当前节点周围有其他的未访问邻接节点：
- 选择 任意 一个未访问的邻接节点
- 将当前节点与未访问节点连接
- 将未访问节点当作当前节点回到开头进行递归
通过以上递归计算，最终每个节点都会被访问，并且会生成一颗随机的树结构，通过对树结构的处理你就可以获得对应的迷宫结构：
当然，如果迷宫非常大的话，直接用递归可能会爆栈，这时你可以将递归转换为迭代，只需要自己模拟栈即可，不是什么特别难的事。
随机 Kruskal 算法
Kruskal 算法是一种最小生成树算法，其核心要义是将所有的边按照从小到大排序，从最短边开始依次选择，将不连通的两个端点连接在一起，最后可以得到一个树结构，且其总边长度是所有可能生成树中最小的。
既然其要义是选择最短边，那么我们可以仿照此思路，通过随机选择任意一个可能的边，然后将它们连接在一起，就是用于迷宫生成的 随机 Kruskal 算法。其运行步骤如下：
- 生成所有边的列表，为每一个节点建立一个集合，每个集合只包含该节点自己
- 对于边列表，只要列表中还有边，从中 随机 取出一个：
- 如果这条边的两个端点属于不同的集合：
- 将两个节点连接
- 将两个节点各自的集合互相合并
- 从列表中删掉这条边
- 如果这条边的两个端点属于不同的集合：
处理集合合并与查询问题当然只需要用强大的并查集即可实现 （几乎是 ）时间复杂度：
随机 Prim 算法
既然 Kruskal 算法可以改成随机迷宫生成算法，那么同样作为最小生成树算法的 Prim 算法自然也能。
Prim 算法的核心是从某个节点出发，将所有的邻接边放到一个集合中，每次选择集合中最短的边进行扩张，再重复将扩展出来的节点的邻接边放到集合里，直到所有的节点都被连接为止。
对于随机 Prim 算法，我们就不需要选择最短边进行扩张了，可以直接从边集里随机选择边进行扩张，其运行步骤如下：
- 选择一个起点，将其所有的连边放入集合，并将起点标记为“已访问”
- 只要图中还有节点没被访问：
- 从边集中随机选择一条边，将其从边集中取出
- 如果其对应的端点均已被访问，则重新选择边
- 否则将端点标记为“已访问”，连接这两个端点，并将新扩展出来的连边放入边集
Prim 算法不需要并查集，只需要标记节点访问情况，因此相对 Kruskal 更加简单：
Wilson 算法
经过对如上的三种算法进行测试，不难发现随机 DFS 更倾向于生成更多的长走廊，而 Kruskal 和 Prim 则更加倾向于生成短路和死胡同，有没有一种算法可以平衡长路和短路？
Wilson 算法就很好地做到了这一点，它使用循环擦除随机游走法，生成一个均匀分布的无偏样本随机迷宫。
其运行步骤如下：
- 在迷宫中随机选择一个节点，作为迷宫
- 选择一个节点开始进行随机游走，如果游走路径形成了一个环，则将这个环删除，继续进行游走
- 如果游走遇到了已经生成的迷宫，则固定游走的路径，将其变成新的迷宫
- 从 (2) 开始重复生成，直到所有的节点都被访问
听起来有些迷，但是我们可以看看可视化：
Aldous-Broder 算法
这是一种比较低效的生成算法，相应的，它的实现思路也非常简单：
- 选择一个随机的节点，将其标记为“已访问”
- 只要图中还有节点没被访问：
- 根据选定的节点，随机选择它的一个邻接节点
- 如果这个邻接节点没有被访问：
- 将两个节点连接
- 将该邻接节点标记为“已访问”
- 将当前选定节点设定为这个邻接节点
如果你看了这种算法的运行情况，你会知道什么叫无头苍蝇乱撞路……
