随机迷宫生成算法

@2024年3月12日 1.6k字 §算法 #生成器

随机迷宫算法是一种用于自动化生成迷宫的算法，广泛用于游戏制作，且迷宫可以与各种元素相结合碰撞，组装出不同的玩法，其中最著名的要数日式 RPG 中的各种迷宫攻略。

由于迷宫的数学本质实际上是一个图，因此大量的随机迷宫生成器都是基于图论的。
一个迷宫的拓扑结构可以是一棵树，这通常意味着迷宫特定的入口和出口之间有且仅有唯一的一条道路；迷宫还可以是一个 有环图 结构，使得入口与出口之间有多条可能的通路，而有环结构往往都是通过在基础的树结构上应用一定的规则，给原本不连通的节点之间 添加边 来实现。

随机迷宫生成的本质即在拥有一定数量的节点和边的（全）连通图 $G$ 上，通过删除部分边获得其一个子图 $G'$ ，使得入口节点和出口节点之间的路径尽可能复杂。

随机 DFS 算法

既然迷宫是一个图，那么用图论算法来处理获得子图便是显而易见的方法，其中最简单的一种就是基于 深度优先搜索（DFS）所得到的随机 DFS 算法。随机 DFS 算法利用栈结构，通过每一步对图的边进行随机选择来生成随机的迷宫，其具体步骤如下：

将当前节点标记为“已访问”
如果当前节点周围有其他的未访问邻接节点：
选择任意一个未访问的邻接节点
将当前节点与未访问节点连接
将未访问节点当作当前节点回到开头进行递归

通过以上递归计算，最终每个节点都会被访问，并且会生成一颗随机的树结构，通过对树结构的处理你就可以获得对应的迷宫结构：

当然，如果迷宫非常大的话，直接用递归可能会爆栈，这时你可以将递归转换为迭代，只需要自己模拟栈即可，不是什么特别难的事。

随机 Kruskal 算法

Kruskal 算法是一种最小生成树算法，其核心要义是将所有的边按照从小到大排序，从最短边开始依次选择，将不连通的两个端点连接在一起，最后可以得到一个树结构，且其总边长度是所有可能生成树中最小的。

既然其要义是选择最短边，那么我们可以仿照此思路，通过随机选择任意一个可能的边，然后将它们连接在一起，就是用于迷宫生成的 随机 Kruskal 算法。其运行步骤如下：

生成所有边的列表，为每一个节点建立一个集合，每个集合只包含该节点自己
对于边列表，只要列表中还有边，从中随机取出一个：
1. 如果这条边的两个端点属于不同的集合：
  1. 将两个节点连接
  2. 将两个节点各自的集合互相合并
2. 从列表中删掉这条边

处理集合合并与查询问题当然只需要用强大的并查集即可实现 $O(\alpha(V))$ （几乎是 $O(1)$ ）时间复杂度：

随机 Prim 算法

既然 Kruskal 算法可以改成随机迷宫生成算法，那么同样作为最小生成树算法的 Prim 算法自然也能。

Prim 算法的核心是从某个节点出发，将所有的邻接边放到一个集合中，每次选择集合中最短的边进行扩张，再重复将扩展出来的节点的邻接边放到集合里，直到所有的节点都被连接为止。

对于随机 Prim 算法，我们就不需要选择最短边进行扩张了，可以直接从边集里随机选择边进行扩张，其运行步骤如下：

选择一个起点，将其所有的连边放入集合，并将起点标记为“已访问”
只要图中还有节点没被访问：
1. 从边集中随机选择一条边，将其从边集中取出
2. 如果其对应的端点均已被访问，则重新选择边
3. 否则将端点标记为“已访问”，连接这两个端点，并将新扩展出来的连边放入边集

Prim 算法不需要并查集，只需要标记节点访问情况，因此相对 Kruskal 更加简单：

Wilson 算法

经过对如上的三种算法进行测试，不难发现随机 DFS 更倾向于生成更多的长走廊，而 Kruskal 和 Prim 则更加倾向于生成短路和死胡同，有没有一种算法可以平衡长路和短路？
Wilson 算法就很好地做到了这一点，它使用循环擦除随机游走法，生成一个均匀分布的无偏样本随机迷宫。

其运行步骤如下：

在迷宫中随机选择一个节点，作为迷宫
选择一个节点开始进行随机游走，如果游走路径形成了一个环，则将这个环删除，继续进行游走
如果游走遇到了已经生成的迷宫，则固定游走的路径，将其变成新的迷宫
从 (2) 开始重复生成，直到所有的节点都被访问

听起来有些迷，但是我们可以看看可视化：

Aldous-Broder 算法

这是一种比较低效的生成算法，相应的，它的实现思路也非常简单：

选择一个随机的节点，将其标记为“已访问”
只要图中还有节点没被访问：
1. 根据选定的节点，随机选择它的一个邻接节点
2. 如果这个邻接节点没有被访问：
  1. 将两个节点连接
  2. 将该邻接节点标记为“已访问”
3. 将当前选定节点设定为这个邻接节点

如果你看了这种算法的运行情况，你会知道什么叫无头苍蝇乱撞路……