总起

本文主要基于Procedural Content Generation in Games第三章介绍构造性方法，他们的主要用途在于地牢和关卡，这些方法能在极短进行生成，并且不会进行评估或重新生成。

关于PCG in Games之前的笔记可见：

第一章读书笔记 PCG in Games 程序化内容生成 介绍 - 知乎

第二章读书笔记 PCG in Games 程序化内容生成2 基于搜索的方法 - 知乎

地牢的概念来源于桌游《龙与地下城》，并成为RPG游戏的一大特征，包括《塞尔达传说》系列和《最终幻想》系列。

Rougelike游戏来源于《Rogue》，特点是程序化实时生成地牢，《暗黑破坏神》是此类游戏的延续者。

一个典型的地牢生成方法考虑以下三种要素：

1.模型，以简单、抽象的方式替代整个地牢，并提供最终结构的一个简单预览；

2.构造模型的方法；

3.根据模型创建真正地牢内容的方法。

本章创建方法特性：

1.建设性的，每次运行只产生一个输出结果；

2.运行速度快，有一些甚至可以实时创建关卡；

3.只提供有限的属性，只能对结果进行有限的控制。

本章将讨论的方法：

1.空间分割法；

2.基于代理；

3.元胞自动机；

4.基于语法方法；

5.平台生成方法。

构造性方法

空间分割法

通过递归将空间进行细分，并将获得的子空间组织到一个树型结构中。对于计算机图形来说这类方法特别重要，比如高效的射线投射、视锥剔除和碰撞检测。

具体的方法：

1.BSP（binary space partitioning，二元空间划分），最流行；

2.四叉树、八叉树。

使用四叉树生成地牢：

1.一张2^n*2^n像素的图片，其内容可以是黑白两种颜色；

2.根节点代表整张图片，四个子节点代表上个节点图像的四个象限；

3.按照2的步骤一直分割，直到最终叶子节点只有一种颜色。

使用BSP生成地牢：

1.将空间沿着垂直或水平方向进行分割，分出的单元格可以有不同的大小；

2.随机选择一个叶子节点继续进行分割；

3.设定一个叶子节点不能被分为某个更小的尺寸；

4.最终每个叶子节点都包含一个单一的房间；

5.拥有相同父节点的房间会进行连接。

生成效果如下图，a使用四叉树，b使用BSP：

本节生成地牢的方法遵循了一种宏观方法，即算法扮演着全视地牢的建筑师角色，而不是像下节中基于代理的方法所呈现的一个“盲目的”挖掘者，它们通过递归分区生成地牢，并能保证所有生成的两个房间都不会重叠。

基于代理方法

基于一个AI代理挖掘出地牢，该方法的AI行为参数对地牢的外观有很大影响，但很难被猜测，需要经过大量的测验和试错。

一个高随机的方法：

1.代理转变方向的概率和放置房间的概率都设定为5%；

2.将代理设置到地图的任意位置并朝向任意方向；

3.挖掘一个格子；

4.检测是否要改变方向或放置房间；

5.如果没有改变方向或放置房间，则将分别的概率提高5%；

6.在地牢没有生成的足够大之前，跳到第3步继续生成。

这种高随机的方法很容易出现重叠房间和死路，因此我们将对AI代理进行一定的前瞻性设置。

第二种方法：

1.在地牢中放置一个代理；

2.设置变量Fr = 0，Fc = 0；

3.尝试放置一个房间，保证它与任意房间不相交，如果放置了房间设置Fr为1；

4.尝试在任意方向放置一个3到7个单位长度的走廊，保证它与任意房间不相交，如果放置了走廊设置Fc = 1；

5.如果Fr == 1或者Fc == 1，则跳回到第2步。

这种方法相比而言稍微好了一点，但是在最差情况下也有过早结束的问题：

总之与本章中介绍的大多数方法相比，代理方法的参数会对生成结果的可玩性和娱乐价值产生非常大的影响，调整这些参数达到最佳效果并不是一件简单的任务。

元胞自动机

元胞自动机是一个离散型的计算模型，而它作为计算模型、生长发育模型、物理现象模型等，在计算机科学、物理学甚至生物学的一些分支中得到了广泛的研究。

原理：

1.由n维网络、一组状态和一组转换规则构成；

2.一般情况下使用的网络是一维的（向量）或二维的（矩阵）；

3.每一个元胞可以是状态中一个：最简单的例子状态可以是打开或关闭的；

4.实验开始时各个细胞拥有各自的状态，然后随着时间推进，每个元胞由自己和邻居t-1时的状态来确定t时的状态。

领域（其大小可以是1或大于1）：

1.一维，向左向后延伸的单位；

2.二维，Moore摩尔领域和von Neumann冯诺依曼领域。

Johnson等人使用元胞自动机来生成类似洞穴的无限地牢，洞穴应该看起来像是自然侵蚀形成的，而非拥有笔直的边缘和角落。

控制地图生成过程的四个参数：

1.岩石单元的百分比（无法进入的区域）；

2.元胞自动机运行次数n；

3.定义岩石的邻域阈值T；

4.邻近细胞的数目。

生成步骤：

1.设置每个房间50x50的格子，每个细胞拥有两种状态：空或石头；

2.“喷洒”石头，针对每个元胞有一定概率是石头（比如0.5）；

3.如果相邻的细胞中至少有T个（例如5）是岩石，则该细胞在下一个时间变成岩石，否则它将变成自由空间；

4.以上的处理进行n次（例如4）。

这样简单的生成能获得惊人的栩栩如生的洞穴房间，如下图b，使用了参数：n = 4、T = 5。

不过元胞自动机也有其缺点，它的参数比较难以理解，每个参数还对多项特性有影响，并且比较难以定制化。

基于语法方法

使用自然语言描述地牢结构。

Adams使用图像语法生成了一个FPS关卡：

1.节点代表房间；

2.相邻的两个节点代表两个房间之间拥有一条走廊。

这种方法不会生成任何几何细节，比如房间大小。通过高层次的、拓扑的关卡进行表示，接着搜索算法查找最为匹配的结果。

Adams研究的一个限制是语法规则，特别是参数，它们是专门的且硬编码的。

Dormans通过图像语法生成有向图，作为游戏任务流程顺序的模型，每个任务都被抽象成节点和边的网络，然后由形状语法生成相应的游戏空间。

受到Dormans研究的启发，van der Linden等人提出了一种用于生成地牢关卡的玩法语法。游戏设计师使用面向游戏玩法的词汇来表达先验设计约束，包括玩家在游戏中执行的指令，它们的顺序和组合，相互关系和相关内容。

以下图片a展示了van der Linden等人编写的具体语法内容，b展示了最终生成的效果：

平台生成方法——基于节奏

Smith等人基于节奏概念进行关卡生成，将用户时间和重复联系在一起。

生成节奏组：

1.创造一系列玩家行动；

2.将这些行动转换成相应的几何图形；

3.通过组合节奏组生成多个关卡；

4.评估选择最佳关卡。

Smith提供了一个控制生成的过程：

1.一条贯穿关卡的道路；

2.生成不同类型的节奏；

3.几何组件的类型和分配频率；

4.收藏品跟关卡是分开的。

每个节奏组也有一些参数，比如跳跃频率、跳跃道具(弹簧)出现的频率。另一组参数提供对节奏长度、密度、拍型的控制。

Smith等人所定义的节奏概念并不直接适用于地牢，但使用穿过房间和走廊的节奏可能具有类似的价值。

平台生成方法——ORE

Mawhorter等人提出的Occupancy Regulated Extension（占用率查询扩展），这种方法依赖于预先编写的关卡块，然后使用关卡块来组装关卡。

步骤：

1.选择一个随机的潜在位置（占用率）来放置一个块；

2.选择一个与环境兼容的块；

3.新的块与已存在的关卡图形进行合并。

Mawhorter等人没有提到算法中特殊的控制参数，但是策划仍然拥有一些控制。这种混合主导的方法能够提供最大程度的控制，但是如果做得过火，这种方式和手动构建就基本没什么区别了，能在PCG中所获取的收益就会减少。

平台生成示例

《洞穴探险》关卡生成的阶段：

1.通过可用模板房间生成关卡的主要布局，并放置入口点和出口点；

2.障碍生成，使用代理穿过关卡在预留空间中启发式的放置障碍物；

3.怪物生成，再使用另一个代理搜索并寻找足够空间放置一个怪物。

《无限马里奥》，Ben Weber提供了一种生成方法，基于代理进行多次遍历：

1.创建起始点到终点的初始通道；

2.添加山丘；

3.添加管道或大炮等静态元素；

4.添加移动的敌人；

5.添加未连接的水平块；

6.添加可收集的硬币。

本章可以使用平台AI竞争的关卡赛道生成器(Level Generation Track of the Platformer AI Competition)进行练习。

总结

构造性方法通常在roguelike游戏、平台类游戏中使用，因为方法运行可预估且运行时间短。

1.空间分割法，递归将区域分割的更小；

2.基于代理，使用某种方式穿越地牢进行挖掘；

3.元胞自动机，可以创建类似自然侵蚀形成的效果；

4.基于语法方法，使用生成规则构建地牢，在第五章有更广泛的讨论；

5.平台生成方法，使用带有概率的简单规则进行生成，也很容易使用到地牢生成中。

参考

《Procedural Content Generation in Games》