本文所有代码可在项目地址查看

上学期的游戏开发期末作业做了一个Roguelike恐怖游戏,学习整理了一些资料,对于此篇文章的想法由来已久。
由于后来暑假搞服务外包大赛搁置了一段时间,如今诸多事务告一段落,终于有空玩一玩自己的东西。

最早接触Roguelike是从以撒开始,虽然就生成地形的艺术性上Roguelike的特定规则不如类似MineCraft的模拟自然壮丽。但与特定规则配合带来的无穷游戏性却是诸多类型中无二的。过程化生成永远是游戏技术界的一颗明珠,然而在摘得明珠的那一刻,或许游戏设计就不复存在了。

第一种算法

先上一张图

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

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

  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两端的e1e2是否属于一棵生成树
    • 是,无动作
    • 否,绘制e1,v,e2并合并树
  3. V中删除v
  4. V不为空,则返回 1. ,V为空则完成

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

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

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

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

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

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

Prim:初始V为空,所有e\inE标记为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\inE均被标记为1,结束,否则返回 3. 。

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

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

下为运行结果


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

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

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

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