总起

本文主要基于Procedural Content Generation in Games第二章介绍PCG领域最重要的方法之一——搜索方法，而其中进化算法是我们主要使用的方法之一。

关于PCG in Games第一章的笔记可见：

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

关于进化算法介绍可见：

Python 进化算法的简单介绍和实现 - 知乎

OK，接下来进入正题，首先我们对本章内容进行概括。

什么是基于搜索方法的程序化内容生成？

定义：方案空间中存在一个足够好的方案，我们一直进行迭代和寻找，使方案更好并把坏方案丢弃，最终会获得一个我们需要的方案。

三个核心组件：

1.搜索算法，是基于搜索方法的引擎，我们将会看到一些简单的进化算法就能运行的很好。当然使用一些先进的算法也有很多好处，例如可以考虑约束条件或专攻某些特殊的内容表示形式；

2.内容表示方式，从数组到图片到字符串。定义了（同时限制）什么内容可以被生成，并且决定了是否有可能进行有效的搜索；

3.一个或多个评估方法，用于评估备选方案的质量。开发一个可靠的评估方法往往是最为困难的任务。

本章我们将依次讨论各个核心组件，并且举几个具体的例子来针对不同的游戏生成不同的内容。

进化搜索算法

进化算法是基于达尔文进化论的自然选择启发的随机算法。

核心思想是控制一个族群，当每一代进行进化的时候，最适应的个体将能得到繁衍的机会，而最不适应的个体将从族群中移除。

一个具体的算法：µ + λ进化策略（以下简称µ + λ ES，进化策略是进化算法的一个大类，还有比较有名的是遗传算法GA）。

µ代表每次生成保留的数量，即精英；λ表示每代生成的数量。

例如，µ = λ = 50：

1.初始化µ + λ个体；

2.切洗族群，可选操作，可以防止梯度损失；

3.使用评估函数获取每个个体的适应度；

4.根据适应度进行排序；

5.移除λ个最差个体；

6.使用μ族群拷贝回λ种群生成后代；

7.突变后代；

8.如果找到足够质量的个体或者生成次数达到最大则停止，否则继续到第二步进行下一次的生成。

尽管这个算法非常简单，µ + λ ES还是非常有效的，即使简单的1 + 1 ES也能取得很好的效果。

其他的算法，比如GA，更依赖于组合而非突变。也有一些另类的算法如群体智能。具体的内容可以参考Eiben和Smith的书《进化计算导论》。

如果表达形式很简短，如数字或向量，则可使用CMA-ES；多目标算法NSGA-II。

内容表示形式

在游戏内容生成场景中，基因型可能是创建关卡的间接指令，而表现型是真正的游戏关卡。

例如，《超级马里奥兄弟》可能的几种表示形式：

1.直接的，作为一张关卡地图，基因型中的每个变量都对应表现型中的一个块（比如砖块、问号块）；

2.间接一些，列出不同游戏实体的位置和属性，比如敌人、平台、裂口和山丘；

3.更间接一些，一个拥有不同可重用模式的存储库，描述他们在地图中是怎么分布的，比如山、硬币的集合通过旋转、缩放进行分布；

4.非常间接，一个可以调整的属性列表，比如间隙数量、敌人密度、硬币总量、缺口宽度等；

5.最间接，一个随机数的种子。

不同的表示形式拥有不同的搜索空间。我们理所当然的认为最直接的方式能获得最佳的细节控制，但是它容易导致“维度灾难”，即直接的表示形式产生了一个非常大的搜索空间，而越大的搜索空间，越不容易找到一个确定的解。

另一个行为准则是表示形式最好拥有良好的局部性，即基因型的一个小小改变也应该导致表现型的一个小小改变，从这个意义上来说最后一种也不适合作为搜索的首选，因为没有局部性，这种情况下搜索和随机搜索的效果一样差。

至于具体选择哪种表示形式则取决于想要解决的问题。

我们将在第九章更进一步讨论这个话题。

评估函数

评估函数的主要作用是针对每个候选方案给出一个具体的分数，根据更优的分数获取更好的方案，如果没有合适的评估函数就不可能找到合适的内容。

评估函数很难被设计，比如乐趣就很难被测量，针对这一问题可以有不同视角的回答：一些研究将乐趣视为玩家具体的行为，如赛车游戏中玩家达到的平均速度；

另一些则倾向于直接询问玩家。

由此产生了三种不同的经典评估函数：

1.直接；

2.基于模拟；

3.基于交互。

直接

根据表现型直接计算适应度，容易实现并方便计算，但有时很难设计某些方面的评估函数。

主流的两种类型：

1.理论驱动，针对玩家经验的直觉或定性的理论；

2.数值驱动，直接收集玩家的体验，比如问卷调查或生理测量。

基于模拟

通过AI代理游玩游戏内容后进行评估，统计计算代理的行为和游玩的风格还有最终的得分。

两种思路：

1.可玩性测试，比如2d平台游戏中测试是否有从起点到终点的路径；

2.增加玩家某方面体验，使AI代理模仿人类的行为，比如神经网络控制的车辆用于评估赛道。

重点需要区分方法是静态的还是动态的：

1.静态的方法在游玩过程中AI代理的行为保持一致；

2.动态的方法AI代理的行为将会在游玩过程中进行适应，动态的一般用于评估关卡是否易于学习。

基于交互

评价内容来源于人类。（这跟直接方式数值驱动的区别我认为是，基于交互的强调游戏内容在游玩中进行数据收集，是实时的）

比如Hastings的研究，基于玩家使用该武器时长和频繁度来评估武器的质量；Cardamone的研究，赛道的分数基于玩家的偏好。

显示的数据收集会打断玩家的游玩，而基于交互的可以在复杂的情况下进行数据的收集。

例子

星际争霸的地图

表示形式：地图被表示为一个实数的向量（大约100个维度），转换结果是一个二维数组，其每个单元都对应地图中的一块。

评估函数：8种不同的评估函数用于评估基地的位置、资源的摆放和基地间的路径。

算法：SMS-EMOA，一种最先进的多目标进化算法用于两个或三个目标的组合。有些目标是冲突的，所以我们不能使用所有的目标，但某些目标组合可以产生有趣且公平的地图。

赛道

表示形式：使用一些实数向量来代表贝塞尔曲线的控制点。

评估函数：训练一个神经网络（通过另一种进化过程）来使得AI游玩像个人类，然后候选的赛道使用基于模拟的方法进化，让神经网络驾驶并且进行评估其是否有挑战性且多样化。

算法：连锁精英方法 (cascading elitism)类似于μ + λ ES，但是拥有多个阶段可以确保评估多个目标。

进化得到的一连串贝塞尔曲线组成的赛道：

桌游规则

表示形式：一种桌游专用的语言使用字符串表示（一个表达式树），短短几行就可以用来描述整个游戏。

评估函数：使用一种极大极小的搜索算法评估其游戏时长、平局频率、规则使用数量。

算法：基础的遗传算法。

银河装备竞赛

表示形式：粒子武器通过神经网络进化，方法叫做NEAT。每一个粒子武器都被表示为单个神经网络用来控制其速度和颜色。

评估函数：在游玩过程中进化，越被玩家使用适应度越高。

算法：集体的分布式进化计算。

总结

在基于搜索的PCG中，进化算法或其他随机搜索/优化算法常用于游戏内容的生成，内容生成器可被视为在内容空间中搜索最佳满足评估函数的内容。

因此设计基于PCG解决方案时主要有两个问题：

1.内容表示；

2.评估函数。

内容表现型可以使用几种不同的方法在基因型中进行表示：

1.直接表示；

2.间接表示（可以有不同程度的间接形式）。

间接表示丢失了某些内容生成的细度，因此在整个内容空间中分布较为稀疏，不过它能更好的处理维度灾难问题。

三种评估函数：

1.直接；

2.基于模拟；

3.基于交互。

直接评估函数速度很快，基于模拟需要AI游玩，基于交互则需要一个人类在流程中。

基于搜索的PCG在当前学术界十分流行且有许多已发表的研究，一些完整已发布的游戏吸收并使用了这些PCG研究。

参考

《Procedural Content Generation in Games》

《人工智能与游戏》