C/C++教程

读书笔记 PCG in Games 程序化内容生成2 基于搜索的方法

本文主要是介绍读书笔记 PCG in Games 程序化内容生成2 基于搜索的方法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

总起

本文主要基于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》

《人工智能与游戏》

 

这篇关于读书笔记 PCG in Games 程序化内容生成2 基于搜索的方法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!