前言

前段时间学校游戏开发课大作业，做了一个Roguelike的恐怖游戏。搜集整理了一些迷宫生成的算法。

当初也受了indienova上一些文章的启发。现在在此把学到的一些东西理一理分享出来。

第一次写这种东西，感觉有点啰嗦，还请大家不要介意，也可以直接看项目地址

代码写在Unity环境下，应该可以直接使用。

第一种算法

先上一张图

这是我最早拍脑袋凭着感觉写的一个算法结果，给定区域长宽和分支概率，可以生成一张迷宫图。

这完全就是随机挖洞大法，其步骤如下：

1. 计算当前扫描点周围可以挖的方块
2. 随机选一个方块挖开
3. 若周围还有可挖方块，按分支概率随机挖开另一方块，设为新扫描点
4. 所有扫描点执行 1 操作
5. 若周围无方块可挖，中止此扫描点工作。

可以看出，这个算法有相当的缺陷，生成的迷宫总面积不可控，在运气不好的极端情况下，会产生比预期面积小很多的迷宫。
即使我们将分支概率调到100%，依旧会有黑色的空洞存在：

而且生成的迷宫非常扭曲怪诞，这很克苏鲁。或许我们可以风格化一下……

此时的迷宫已经勉强可以使用，但是与传统迷宫的差别依旧非常大。
它的斜线非常多。这会使得游戏过程中包含八个方向，对玩家的方向感是极大的考验，很难再记住地图，容易晕头转向。

对于这个算法，相比室内环境，更适合生成自然环境下迷宫。也可以作为无主线、弱主线沙盘游戏的大地图生成的一环。

递归分割

接下来这个算法与第一个就是两个极端——生成完全没有斜线的迷宫。
话不多说，先上图：

在介绍本算法前，需要提出一个概念

完美迷宫Perfect maze：没有回路，也没有孤立区域的迷宫。用图论来解释，就是可以用生成树表示的迷宫，迷宫中两点有且仅有一条路径。

这个算法是一个分治算法，即将一块大的生成区域分成4块小区域分别生成迷宫并保证联通，以此类推，直到不可细分。

分块很简单，长宽上各取一个随机数即可。如何保证迷宫完美呢？
我们看极端情况，对于一个田字形区域，生成完美迷宫的方法是敲开三堵墙。

利用分治算法的特性，每一层递归都是完美迷宫，直到全图生成完美迷宫。
算法不难，注意递归状态的边界情况就行。

这种分治递归的痕迹在生成的地图俯视图上很明显，但对于置身其中的玩家或许就不是了。

它生成的迷宫完全没有斜线，横平竖直，同时会生成4*4的小房间。
用作城市地图、或建筑环境的迷宫非常合适。

当然在游戏中地图没有回路是非常致命的，一个完美迷宫会让玩家疲于奔命，并不方便设计玩法。
对于回路，我们只需要消除死路就行了，也就是那些三面临墙的格子，在地图生成完后遍历死路，按一定概率打通即可。

生成树算法 Kruskal & Prim

绝大多数的编程问题都可以用数学工具解决，当然我们的迷宫生成算法也不例外。
数学中最适合表达迷宫的符号莫过于 图，下面两个算法是迷宫生成中应用最普遍的理论之二。

首先我们需要将地图转换为便于数学表达的形式。
之前两个算法在处理地图时都是以 方块 为单位的，即每一个方块不是墙就是路。
而 图 的基本组成是 点 与 边 ，对于一个待处理的迷宫，我们做如下转换。

迷宫大小10*10，其中白块代表 点，红块代表 边，而黑块代表 虚无，只是填充物质罢了。

如果一个 图 中，任意两 点 都能通过 边 组成的路径联通，称之为 连通图。

而如果一个 连通图 上没有回路，则我们可以称之为 树，因为没有回路，所以每对点之间有且仅有一条路径联通。

可以看到，树 与我们完美迷宫的概念不谋而合，所以现在我们的任务是找到包含所有点的一棵 树。

最小生成树

生成树，顾名思义，就是从给定的 点,边 集合中生成一棵符合要求的树。
下面介绍的两种最小生成树算法都可以胜任。

虽然写作最小生成树，但这两个算法其实可以做到“按一定条件生成树”。
“最小”是算法的典型描述，即在有权边的集合中找出权值最小的树。原算法使用贪心算法求解。

而在这里，我们的条件就是：随机。

下面简单介绍一下这两个算法的步骤：

两个算法都需要 点 的集合E,与 边 的集合V。对于上图，E代表所有白块，V代表所有红块

Kruskal：
一开始每个点将自己作为单独的一棵树。

1. 从V中随机选出一条边v
2. 判断v两端的e1，e2是否属于一棵生成树
   • 是，无动作
   • 否，绘制e1,v,e2并合并树
3. 从V中删除v
4. 当V不为空，则返回 1. ，V为空则完成

ps:判断与合并两点所在树可以使用并查集相关算法，在项目代码中UFset类就是并查集的c#实现之一

这里简单讲下并查集，并查集是指一些不相交集合的 合并 与 查询 问题，

对应到我们迷宫问题中就是：合并不相连的生成树、查找两点是否属于同一个生成树。

并查集使用了一种称为 路径压缩 的算法，使得所有子节点的父节点均指向跟根节点。

虽然压缩算法是为了提高合并效率，但压缩算法本身时间复杂度也是O(n)，所以我们只在查询一个节点时，才对此节点所在路径进行压缩，并且在合并时，将小树并入大树，以平衡效率。

经过优化的并查集合并算法时间复杂度可达神奇的常数级，比起之前的全图标记不知道高到哪里去了，证明就在此略过，有兴趣的同学可以去深入学习一下。

===============

Prim：初始V为空，所有e∈E标记为0

1. 随机选一个点e
2. 将与e相连的边的集合{Ve}并入入V，e标记为1
3. 从V中随机选一条边v
4. 判断v两端情况
   • 均为1：无动作
   • 一个0一个1：将为0的点e标记为1，绘制v,e,将e连接的边并入V
   • 均为0：不可能
5. 从V中删除v
6. 当所有e∈E均被标记为1，结束，否则返回 3. 。

ps:可以维护一个包含所有v∈V的标记表，防止被重复并入V，提高效率

以上为算法步骤，建议配合代码食用更佳。

下为运行结果

前者为Kruskal，后者为Prim。白路黑墙。

可以看到两个算法的生成迷宫风格几乎一样，并且都较为接近传统迷宫。可以用于各类需要迷宫生成的游戏。

值得一提的是这两个算法都可以加入房间，只需将房间预先生成，在将剩余可生成的点与边的集合放入算法中运行即可。
关于这个详细可以参考房间和迷宫：一个地牢生成算法

到这里关于游戏中迷宫生成最常用的几个算法已经写完了。除了上述几种以外，迷宫的生成方法还深度广度优先搜索之类很多。
此外还有诸多适用于特定游戏系统的地图生成算法，如MC中的噪音，Unexplored中的环状地图等