《Game AI Pro》高效的人群模拟

发表于 2021-02-19 分类于《Game AI Pro》

关于《Game AI Pro》 Efficient Crowd Simulation for Mobile Games 的学习笔记。主要涉及构建高效的人群模拟。

简介

人群模拟是游戏人工智能行业不断探索和尝试的课题。现代游戏中充斥着越来越多的AI控制的智能体。因此，创建一个真实、稳健、对设计者友好的运动系统势在必行。
虽然许多路径可能有相似的部分，传统的寻路方法为各个智能体计算单独的路径。这些冗余的路径计算限制了在移动设备上对大量单位的模拟。
移动塔防游戏《Fieldrunners 2》使用矢量流场和操纵行为的组合来有效地模拟成千上万的智能体，即所谓的单位。本文将介绍Fieldrunners 2所采用的流场生成、流采样和单位移动的系统以及动态人群模拟系统的构建和平衡过程。

网格

网格提供了游戏世界的差异化，并定义了单位可以在其中移动的区域。对于《Fieldrunners 2》，网格单元的大小比最宽的单位略宽，因此每个计算出的路径都可以被每个单位通过。每个网格单元可以是open的，表示一个单位可以通过，也可以是blocked的，表示该单元无法通过。

流场

单位依照静态矢量流场在网格中移动。流场表示网格中每个单元的最佳路径方向，是连续流函数的近似值。对于给定的一组目的点，流函数定义了一个归一化向量的向量场，表示到最近目的点的最佳路径方向。流函数类似于流体动力学中描述流动的常用方法，不同之处在于所有的流向量都是归一化的。鉴于这个定义，我们可以将流场定义为流函数的离散。
流场以与标准寻路系统相同的方式引导单位到达最近的目的地；然而，单位的路径信息被记录在流场中，消除了单位单独计算路径的需要。
流场是针对每一个潜在目的点集的，因此可以被所有共享一组目的地点的单位使用。由于流场表述的是整个游戏世界的路径信息，所以除非网格的可通行区域或目的点集合发生变化，否则它不需要更新。
例如，如果一座横跨河流的桥被摧毁了，那么流场只需要重新计算一次，以说明可通行区域的变化。跟随该流场的单位将根据游戏世界的变化而隐性地改变各自的路径。
流场由每个网格单元的单个归一化向量组成。一个流场和一组唯一的目的点一起称为路径。例如，对应于m乘n网格的路径是一组m*n个归一化向量和一组一个或多个目的点构成的点集。由于表示流函数所需的向量数量，这种方法可能会产生极高的内存使用率。内存消耗与网格单元数和独立路径数的乘积呈线性关系。Fieldrunners 2中的地图最多限制为三个唯一的路径，而且地图网格大小足够小，因此流场内存使用量并不是一个重要问题。
网格大小以及流场的分辨率并不需要很高，就能产生可信的运动特征。使用双线性插值，一个连续的流动函数可以从低分辨率流场中的四个最接近的向量中得到近似值。随着网格分辨率的增加，流场计算同一流函数的采样率越来越高。流场中矢量的双线性插值可以提高单位路径的连续性。

流场的生成

流场是通过修改后的传统点对点寻路函数生成的。Fieldrunners 2中使用的算法是Dijkstra，但是，其他的寻路算法也能够生成流场。
Fieldrunners 2中使用的算法首先将每条路径的目的地的网格单元添加到开放列表中。随着Dijkstra算法的正常迭代，节点从开放列表中移除，并链接到附近计算出路径成本最低的单元格。当开放列表中的单元格被扩展时，新扩展的单元格的流向量被设置为指向它被链接到的单元格的方向。该算法不是在找到路径时终止，而是扩展所有添加到开放列表中的可通行单元格，为每个单元格分配一个流向量，并在开放列表为空时终止。
每当路径的目标集或网格的可遍历区域发生变化时，前面的算法就会为每个路径生成一个流场。

单位

Fieldrunners 2需要一个能够支持几十个不同单位的人群动力学系统，每个单位都有独特的运动特性。Fieldrunners 2中的单位是基于Boid模型的简单智能体。每个单位都有一组物理属性，和操纵行为共同控制其运动。单位的物理属性（如质量、大小，敏捷）定义了它独特的移动特性。
一个单位的操纵行为通过对其施加一组力来控制。这些转向力的优先组合会给单位施加一个加速度，从而实现真实的、可感知的智能运动。操纵行为在游戏中被广泛用于控制单位运动，并在许多出版物中进行了描述（例如《游戏人工智能编程案例精粹》,这里是我的学习笔记）。在《Fieldrunners 2》中，作者对一些操纵行为的标准实现进行了修改，以支持更多的动态单元交互。

操纵行为

Fieldrunners 2中的单元使用了五种操纵行为。这五种行为按优先级降序排列，包括流场跟随（flow-field following）、避障（obstacle avoidance）、分离（separation）、队列（alignment）和聚集（cohesion）。在每个模拟步骤中，一个单元只受指定的转向力总大小的影响。操纵行为所产生的力按优先顺序加入到运行的总量中，并截断到最大值。其他任何未被添加到总量中的转向力都被忽略。也即带优先级的加权截断累计。

其中分离、队列和聚集共同描述了集群行为。集群行为用于使单位在靠近其他单位时，以群体的形式凝聚移动。
避障帮助速度较快的单位智能地绕过速度较慢的单位进行机动。避障操纵行为会产生一个垂直于单元速度的 “side stepping “力，并与邻近单元的位置和相对速度成比例。原始实现由于是考虑静态障碍，并不会考虑障碍的速度。
分离操纵行为产生的力是由邻近单元的动能与受力单元的动能之比来衡量的。质量和速度较小的单位（也即更灵活）将更容易让步于较大的，机动性较差的单位。原始实现则只与距离和方向有关。
流场跟随使单元按流场指定的方向移动。通过对四个最接近的流向量进行线性插值，计算出单元位置的流场方向。

于是，质量、最大截断力、最大速度和邻接半径属性描述了一个单位的独特行为。

质量用于计算操纵行为产生的加速度，和单位的动能。
最大截断力决定了在一个模拟步骤中可以影响单元的最大转向力。同时，单元的敏捷度被定义为单元的最大截断力与其质量的比值–单元的最大加速度。
最大速度属性限制了单元的速度大小。
邻接半径属性则限制了计算集群行为时考虑的半径。

校正单位的移动

我们有必要为每一个单位找到正确的属性值集，以产生期望的行为。在基于操纵行为的模拟中，这是非常困难的。设计者开发并使用了一种系统的校正参数方法来平衡Fieldrunners 2中的单位属性值集。为了简单起见，所有单位都使用了一套相同的加权的、先验的操纵行为，依靠它们的物理属性来实现独特的行为。以下为可参考的校正方法：

将最大速度属性设置为一个合理的值，其余的属性则给出一个任意的基础值。因为一个单元的最大速度最容易可视化，它提供了一个很好的调整起点。
调整最大截断力，以产生该类型单位的可信运动特征。因为最大截断力会影响单位的敏捷度，它将改变视觉方面，如转弯速度和制动能力。
给定一组同质的单位，单位邻接半径属性的变化结果可以很容易地单独观察。较小的邻接半径将使单元更紧密地聚集在一起，而增加邻接半径将使单元分散开来。
所有单元的质量都是相对调整的。注意当调整单位的质量时，其敏捷度必须保持不变，否则之前调整过的单位的移动特性就会改变。

移动设备的限制与性能考察

这种方法中最大的运行时性能问题是用于计算集群转向力的相邻单位列表的生成和处理。在Fieldrunners 2中，通过使用松散的四叉树来减少相邻单元搜索空间，性能问题得到了缓解。
移动处理器上的浮点运算可能会很慢，尽量减少路径和运动计算所需的运算次数也能带来改进。在Fieldrunners 2中，存储向量模的平方是一个常见的优化。这使得向量长度比较可以使用向量模的平方，消除了计算许多浮点平方根值的需要。
当大量单位需要导航到一组共同目标时，基于流场的系统提供了最大的好处。单位间每一个独特的目标位置集都需要一个单独的流场。随着独特的目标集数量的增加，维持必要的流场所需的计算和内存会变得非常复杂和庞大。表示流场所需的内存随着网格单元数的增加而线性增长，而寻路计算复杂度相当于所使用的寻路算法的最坏情况复杂度。在Fieldrunners 2的情况下，使用了Dijkstra算法，其产生的准线性时间复杂度取决于网格单元的数量。最小化流场内存消耗的一种方法是将流向量保存为 “北 “向量（通常为<0,1>）的特定旋转。当访问一个给定单元的流向时，已知的基础向量被重新创建并旋转到该单元的特定数量。另外，如果流向量恰好在特定的方向(例如，向量的基)，它们可以被存储为一个字节整数，其中的值对应于特定的方向。
随着移动硬件向多核处理器发展，正确利用多线程算法变得非常重要。产生多个流场的问题很容易被建模为一个并行过程。流场的相互独立性使得每个流场可以与其他流场并行计算，可能在不同的线程或进程中进行。操纵行为的组成和独立性使得它们也可以并行计算，只要它们被累积起来并集体应用到单元中。流场生成和操纵行为计算的内在并行性使得多线程本身的优化变得微不足道。

优势与改进

在《Fieldrunners 2》中选择了这种单位移动方式，是因为它提供了一系列独特的好处。流场域中预先计算并存储了路径信息，因此对于一个给定的世界配置，它只计算一次。流场域的这一特性在《Fieldrunners 2》中提供了显著的性能优势，因为世界的路径不经常被修改。
世界中所有位置的寻路信息都是一次性计算的，产生了与Dijkstra算法相当的基于网格大小的复杂度。传统的寻路方法的时间复杂度与单位数量呈线性关系，而这种方法的时间复杂度与模拟的单位数量呈线性关系。对于《Fieldrunners 2》来说，这使得具有数千个独立和多样化单元的复杂场景能够以较高的帧率在移动设备上运行。
像这种基于操纵行为的方法在定义独特的单元行为方面提供了极大的灵活性。操纵行为依靠单位的属性值集来定义复杂的行为，有利于模块化和封装化。新的操纵行为的属性值集或对现有操纵行为的修改都可以很容易地应用到单位中，以定义独特的运动风格。
基于流场的寻路技术提供了一种独特的方式，通过计算每个点的最佳路径来减少冗余的寻路计算。出于简单，Fieldrunners 2中使用的流场生成技术是基于Dijkstra算法的。更先进的寻路算法，如Theta*，可以生成更平滑的流场。流场还可以通过混合静态和动态流场来扩展。尽管有这些潜在的改进，但静态流场和操纵行为还是为Fieldrunners 2提供了一个高鲁棒性、真实的人群模拟。