前言：上周末和同组的朋友们一起参加了CiGA Game Jam 2023的活动，以TOUCH为主题制作了一款类似《魔塔》的冒险小游戏，除了一套简单的元素交互系统之外，游戏里的一大重点是自动化的随机地图生成算法，它保证了每一局游戏的地图都是独特的。
本文就是来探讨这个比赛项目中的随机地图生成算法机制的。
正文
地图是游戏中非常重要的一个组成部分，它有许多不同的类型和设计方法，地图设计的好坏往往直接影响着玩家的游戏体验。
而无论是哪种地图设计方法，其本质都离不开数学概念中的“图”，即一类用于表示多个节点间连接关系的数据结构描述，以及由此派生出的许多算法。
即便是现在的各种3A大作，第一人称射击，动作角色扮演，开放世界等等类型的游戏，它们的地图设计从抽象层面上来说，依然是最简单的图结构，无非就是图中的节点包含的内容更丰富，连接更复杂多变罢了。
撇开这些高端的地图不谈，仅就传统的2D游戏而言，它们的地图机制和设计方案相对来说是比较有限的，可以是预先画好的一整张大地图，也可以是大小地图结合，通过类似“进入地图点”的方式衔接。
而当地图的构成方式被限定在“瓦片式地图”这个狭窄的范围内之后，地图的设计方法也变得相对确定起来。
第一类别自然是最常见的一种，即手工设计地图，通过编辑器转化为数据保存下来，并在游戏中读取展示。
这种做法好处很多，地图设计感强，可玩性和地图机制的平衡性可以设计的很好，也基本不会出现地图BUG。
但缺点也很明显，投入工时多，内容固定，反复游玩时无法提供新鲜感。
与之相对的就是第二类别，算法自动生成地图，这种做法的好处和缺点与第一类正好相反，它的设计感不好做，可玩性和机制平衡性也难以设计，地图BUG可能出现。
好处则是实时生成，随机性强，新鲜感消退较慢。
由此可以看出，算法生成地图这种方案更适合一部分开放世界或者RogueLike游戏。
基于瓦片式地图的生成算法有好几种，比如洞穴生成算法，迷宫生成算法和房间地图生成算法等，而接下来要介绍和讨论的是一种结合了迷宫生成和房间铺设两种机制的算法，用它能够生成一些同时具备多个房间和迷宫走廊的地图结构，很适用于RogueLike游戏。
该算法来自于文章《Rooms and Mazes: A Procedural Dungeon Generator》
它的基本思路就是按如下步骤生成迷宫地图：
- 选取房间
- 在房间外生成迷宫
- 用门连接所有迷宫走廊和房间
- 去除所有死胡同，留下单一的通路
对于第一步的“选取房间”，原作者采用了一个非常简单粗暴的方式，即随机选择房间的大小和位置若干次，如果随机出来的房间和其它已经选择好的房间没有重叠则将其选择出来，否则抛弃掉再来一次。
运行了一定次数的循环后便可以得到随机房间的分布。
这当然是一种略显低效的做法，而且结果并不稳定，想要对其进行优化改造的话，可以参考另一篇文章《Procedural Dungeon Generation Algorithm》
这篇文章里提到了一种有些“特别”的房间生成算法，不同于常见的圆内随机取点加验证的方法，这种特别的生成方法借助了游戏引擎的物理系统的一些特性，它的操作方法大概描述如下：
- 通过圆内取点的方式随机生成一些房间，并且暂时不考虑它们相互重叠的问题。
- 给每个房间加上刚体和碰撞器
- 运行物理系统，此时这些房间会因为相互排斥而分离开来
- 在没有房间继续受到排斥后记录所有房间的当前位置即可
不得不说这一方案非常巧妙，但同时它的可实施性也确实不太高，尤其是在多线程快速生成地图的时候。
一个替代方案自然是手动模拟这个物理运算过程，比如采用AABB包围框算法不停遍历所有被选出来的房间并改变其坐标位置，直至所有房间都不再重叠为止。
至于在实际使用中如何选择，那就得看具体需求了。
有了生成好的房间，下一步就是在房间之外生成迷宫，由于这里并非是要生成真正意义上的迷宫，而是需要生成一些“通道走廊”来填充房间之外的区域，因此并没有采用一些经典的迷宫生成算法，而是采取了暴力开路的方式。
即遍历整个地图“内部”（也就是留出最外圈作为外墙）的每一个地块，如果发现它既不属于某个房间，也没有被打开，则从它开始选取任意方向“开路前进”，直至遇到房间墙壁或者地图外圈才转弯。
为了增加生成算法的多样性，在这个过程中加入一个随机“拐弯”的概率，即使没有遇到房间墙壁或者外圈，也会有一定概率发生拐弯。
到这里为止，地图里已经有了房间和房间外的“迷宫”，但这些区域都没有被连接到一起，因此下一步便是寻找可以用于连接的地块，将它们修改为“门”即可。
这一步算法的核心要点在于“分区”的概念，即将不同的房间以及“迷宫走廊”都标识成不同的“区域”，然后在区域的邻接点上选择可以作为“门”的地块。
分区过程类似泛洪，即从一个点出发进行遍历，给房间内的空地块和迷宫走廊都打上“标签”，计算结束后会得到一张“分区地图”，之后只要从这个分区地图上找到可用的邻接点作为门即可。
到这里其实地图的生成就可以说是结束了，有了分布在各处的多个房间，有了连接房间的走廊，最后的消除死胡同其实是个可选项，主要看游戏本身是否需要保留这些“错误道路”。
甚至还可以继续添加一些细节，比如将某些特定位置的走廊扩展成小房间，用来放置一些过渡性的摆设或者机制等。
总之，这一套地图生成机制适合于同时对房间和迷宫元素都有需求的情况，而且还能对它进行灵活的定制化改造，在制作RogueLike游戏时是值得考虑的一种地图生成方案。
附言：我们组正在做的游戏就打算采用这种地图生成的方案，欢迎大家来看看
名称：《边界迷航》
链接：https://www.gcores.com/games/102523