手机游戏中高效的人群模拟

手机游戏中高效的人群模拟 
——Graham Pentheny 

24.1 介绍 

    人群模拟是游戏AI行业正在进行的探索和实验的主题[Pelechano等。 07，Sung等。 04]。 现代游戏充满了越来越多的AI控制代理。 因此，迫切需要创建一个逼真的，坚固耐用且对设计者友好的运动系统。 
    即使许多路径可能具有相似的部分，传统的寻路方法也会为单个代理计算单独的路径。 这些冗余的路径计算禁止在移动硬件上模拟大量单元。 
移动塔防游戏Fieldrunners 2使用矢量流场和转向行为的组合来有效地模拟成千上万的特工，称为单位。 本文将描述Fieldrunners 2使用的流场生成，流采样和单位移动系统。将从头开始详细描述构建和平衡动态人群模拟系统的过程。 

24.2 格子 

    网格提供游戏世界的离散化，并定义了单位可在其中行驶的区域。 对于Fieldrunners 2，网格单元的大小比最宽的单元略宽，因此每个单元都可以遍历所有计算路径。 每个网格单元可以打开以指示某个单元可以通过它，也可以被阻止以指示该单元无法通过。 

24.3 流场 

    单元遵循静态矢量流场在网格中移动。流场表示网格中每个单元的最佳路径方向，并且是连续流函数的近似值。给定一组目标点，流函数定义归一化向量的向量场，指示指向最近目标的最佳路径的方向。流动函数类似于描述流体动力学中的流动的常用方法[Cabral and Leedom 93]，不同之处在于所有流动向量均已归一化。 
    给定这个定义，我们可以将流场定义为流函数的离散化。 
    流场以与标准寻路系统相同的方式将装置引导至最近的目的地；但是，单位的路径信息被编码在流字段中，从而无需单位单独计算路径。 
向量流字段特定于每组潜在目标，因此可以由共享一组目标点的所有单元使用。因为流场表示整个游戏世界的路径信息，所以除非网格的可路径区域或目标点集发生更改，否则无需更新路径信息。 
    例如，如果横跨河流的桥梁被破坏，则流场仅需重新计算一次即可解决可通行区域的变化。跟随该流场的单位将根据游戏世界的变化隐式更改其各自的路径。 
流场由每个网格单元的单个归一化向量组成，如图24.1所示。流场和唯一的一组目标点一起称为路径。 
例如，对应于m×n网格的路径是一组m * n个归一化向量和一组一个或多个目的地点。由于表示流量函数所需的向量数量众多，因此这种方法可能潜在地产生过高的内存使用率。内存消耗线性依赖于网格单元数和独立路径数的乘积。 Fieldrunners 2中的地图最多只能使用三个唯一的路径，并且地图网格的大小足够小，以至于流场内存的使用并没有被证明是一个重要的问题。 
    网格的大小以及流场的分辨率不需要很高即可产生可信的运动特性。使用双线性插值法，可以从低分辨率流场中的四个最接近的向量中近似得出连续的流量函数[Alexander 06]。随着网格分辨率的提高，流场会计算出相同流函数的越来越高的采样率。向量在流场中的双线性插值可改善单位路径的连续性和有机性。 

24.4 生成流场 

    流场是通过修改后的传统点对点寻路函数生成的。 Fieldrunners 2中使用的算法基于Dijkstra的算法Dijkstra [59]；但是，替代的寻路算法可以适当地生成流场。 
Fieldrunners 2中使用的算法首先将每个路径目标的网格单元格添加到打开列表中。随着Dijkstra算法正常迭代的进行，节点将从公开列表中删除，并以计算出的路径成本最低的方式链接到附近的单元。在扩展打开列表中的单元格时，新扩展的单元格的流矢量设置为指向其链接到的单元格的方向。该算法不展开找到路径的终止，而是扩展添加到打开列表的所有可遍历单元格，为每个单元分配流矢量，并在打开列表为空时终止。该书网站（http://www.gameaipro.com）上的本文附带的演示代码在GenerateFlowField（）函数中包含流场生成的完整实现。 
    每当更改路径的目标集或网格的可遍历区域时，都可以使用上述算法来为每个路径生成一个流场。 

24.5 单位 

    Fieldrunners 2需要一个人群动力学系统，该系统能够支持数十种不同的单元，每个单元都具有独特的运动特性。 Fieldrunners 2中的单位是基于Craig Reynolds的Boid模型[Reynolds 99]的简单自治代理。每个单元都有一组物理属性和操纵行为，共同控制其运动。转向行为的集合及其实现在所有单元类型上都是一致的。单位的物理属性（例如，总质量，大小，敏捷度）定义了其独特的运动特征。 
    Fieldrunners 2中的单位表示为具有各自速度的点质量。单位的转向行为通过向其施加一组力来控制其点质量。这些转向力的优先组合可以使装置加速，从而实现逼真的，智能的运动。转向行为已广泛用于控制单位移动的游戏中，并在众多出版物中进行了描述[Reynolds 99，Millington和Funge 09]。在Fieldrunners2中，对某些转向行为的标准实现进行了特定修改，以支持更多的动态单元交互。 
    Fieldrunners 2中的单位使用五个转向行为的有限的，贪婪的，优先的求和（图44.2中显示了其中的四个）。按优先级从高到低排列的五个行为包括流场跟随，避障，分离，对齐和内聚。在每个模拟步骤中，一个单元仅受指定的总转向力大小影响。由转向行为产生的力会按优先级顺序添加到行驶总和中，直到达到最大大小为止。尚未添加到总力中的所有转向力都将被忽略。 
    分离力，对齐力和内聚力共同描述了聚集行为[Reynolds 99]。在Fieldrunners 2中，聚集被用来鼓励单位在靠近其他单位时作为一个整体移动。 
避开障碍物有助于较快的单位在较慢的单位周围智能地机动。避障和分离行为的实现方式与雷诺兹的原始实现方式[Reynolds 99]略有不同。避障转向行为会产生垂直于设备速度并与邻居的位置和相对速度成比例的“侧向踩踏”力。由分离转向行为产生的力通过邻居的动能与施加该力的单元的动能之比来缩放。质量和速度较小的单位（大概更灵活）会更容易屈服于较大的，机动性较小的部队。 
    最后，流场跟随沿流场指定的方向移动单元。 
    通过线性内插四个最接近的流量矢量来计算单元位置处的流场方向。 
质量，最大作用力，最大速度和相邻半径属性描述了单位的独特行为。 除了由转向行为产生的加速度之外，质量还用于计算单元的动能。 最大力值指示可以在单个模拟步骤中影响设备的最大转向力组合大小。 单位的敏捷度值定义为单位的最大力量与其质量（单位的最大加速度）之比。 最后，最大速度属性限制了单位速度的大小，邻居半径属性将用于计算聚集力的邻居集合限制为一定半径内的邻居。 

24.6 调整单位移动值 

    必须找到一个单元的正确属性值集才能产生所需的行为。 
    在基于转向行为的模拟中，这是众所周知的困难和艰巨的。设计者开发了一种系统化的方法，设计人员使用它来平衡Fieldrunners 2中的单元属性。为简单起见，所有单元都使用相同的一组加权优先驾驶行为，这取决于它们的物理属性来实现独特的行为。 
    首先，将最大速度属性设置为合理的值，并为其余属性赋予任意的基本值。因为最容易看到一个单元的最大速度，所以它提供了一个很好的起点。其余值将分别进行调整。 
    接下来，调整最大作用力值，以产生该类型单个单元的可信运动特性。因为最大力会影响设备的敏捷性，所以它将改变视觉效果，例如转弯速度和制动。 
给定一组同构单位，可以容易地孤立地观察到该单位的邻居半径属性的更改结果。较小的邻居半径将使单位更紧密地聚集，而增加邻居半径将使单位扩展。 
最后，所有单位的质量都相对于彼此进行了调整。调整单元的质量时，其敏捷性必须保持恒定，否则先前调整的单元运动特性将发生变化。 

24.7 移动平台限制和性能注意事项 

    这种方法中最大的运行时性能问题是用于计算聚集转向力的相邻单元列表的生成和处理。在Fieldrunners 2中，通过使用松散的四叉树[Ulrich 00]来减少相邻单位的搜索空间，从而缓解了性能问题。具有较大邻居半径的单元将产生大量要考虑的邻居，从而降低性能。结合聚集力的计算可以提供可测量的性能改进，因为中间值可以在后续计算中重用。 
    移动处理器上的浮点运算速度可能很慢，并且最小化路径和移动计算中所需的运算数量也可以带来改进。 
存储表示矢量幅度作为其各自平方值的标量是Fieldrunners 2中的常见优化方法。这允许矢量长度比较使用平方矢量幅度，从而无需计算许多浮点平方根值。 
当大量单元需要导航到一组共同目标时，基于流场的系统将提供最大的好处。每个单元之间唯一的一组目标位置都需要一个单独的流场。随着独特目标集数量的增加，维持必要流场所需的计算和内存可能变得异常复杂和庞大。表示流场所需的内存随网格单元的数量线性增长，而寻路的计算复杂度等于所用寻路算法的最坏情况的复杂度。在Fieldrunners 2的情况下，使用了Dijkstra的算法，该算法产生的准线性时间复杂度取决于网格单元的数量。最小化流场内存消耗的一种方法是将流向量保存为“北”向量的特定旋转（通常为<0,1>）。当访问给定单元的流动方向时，将重新创建已知的基向量并将其旋转特定于该单元的量。可选地，如果流向量被限制在特定方向（例如，基本方向）上，则它们可以被存储为一个字节整数，其中其值对应于特定电势方向。 
随着移动硬件向多核处理器发展，正确利用多线程算法变得很重要。生成多个流场的问题可以轻松地建模为并行过程。流场的相互独立性允许每个字段与其余字段并行计算，可能在不同的线程或进程中进行计算。 
    转向行为的组成和独立性也使它们可以并行计算，只要它们被累积并共同应用于单位即可。 
总之，流场生成和转向行为计算的固有可并行性使多线程优化变得微不足道。 

24.8 优点 

    之所以选择Fieldrunners2作为单位移动的方法，是因为它提供了一组独特的独特好处。路径信息被预先计算并存储在流场中；因此，对于给定的世界配置，仅计算一次。流场的这一特性在Fieldrunners 2中提供了显着的性能优势，因为世界的可改变性很少被修改。 
    一次即可计算出世界上所有位置的路径信息，从而产生了与Dijkstra算法相当的基于网格大小的复杂性。与时间复杂度相对于单位数量呈线性关系的传统寻路方法相比，该方法相对于模拟的单位数量是恒定的。对于Fieldrunners 2，这使复杂的场景具有成千上万个独立且多样化的单元，可以交互帧速率在移动设备上运行。 
这样的基于转向行为的方法在定义唯一的单元行为时提供了极大的灵活性。转向行为依赖于组合来定义复杂的行为，从而使专业化和附加功能模块化并封装。新转向行为的组成或现有转向行为的修改都可以轻松地应用于单元，以定义独特的运动风格。 

24.9 结论与未来工作 

    Fieldrunners 2中使用的系统使用静态矢量流场和操纵行为来模拟移动设备上的数千个单元。与传统的寻路技术不同，所提出的导航系统通过对来自矢量流场中所有区域的路径信息进行编码，从而最大限度地减少了冗余路径的计算。 
    基于流场的寻路技术提供了一种独特的方法，可以通过计算每个点的最佳路径来减少多余的寻路计算。出于简化和设计原因，Fieldrunners 2中使用的流场生成技术基于Dijkstra的算法。更高级的寻路算法，例如Theta * [Nash等。 07]，可以产生更平滑，更有机的流场。通过混合静态流场和动态流场，可以扩展流场，以合并单元的替代动机和关注点[Alexander 06]。尽管有这种潜在的改进，但静态流场和转向行为为Fieldrunners 2提供了可靠，逼真的人群模拟。

References 
[Alexander 06] B. Alexander. “Flow fields for movement and obstacle avoidance.” In AI 
Game Programming Wisdom 3, edited by Steve Rabin, pp. 159–172. Boston, MA: 
Charles River Media, 2006. 
[Cabral and Leedom 93] B. Cabral and L. Leedom. “Imaging vector fields using line integral 
convolution.” SIGGRAPH ’93 Proceedings of the 20th Annual Conference on Computer 
Graphics and Interactive Techniques, pp. 263–270, 1993. Available online (http://www. 
cg.inf.ethz.ch/teaching/scivis_common/Literature/CabralLeedom93.pdf). 
[Dijkstra 59] E. Dijkstra. “A note on two problems in connexion with graphs.” Numerische 
Mathematik 1, pp. 261–271, 1959. Available online (http://www-m3.ma.tum.de/ 
foswiki/pub/MN0506/WebHome/dijkstra.pdf). 
[Millington and Funge 09] I. Millington and J. Funge. Artificial Intelligence for Games, 
pp. 55–95. Burlington, MA: Morgan Kaufmann, 2009. 
[Nash et al. 07] A. Nash, K. Daniel, S. Koenig, and A. Felner. “Theta*: Any-angle path planning on 
grids.” Proceedings of the AAAI Conference on Artificial Intelligence (2007), pp. 1177–1183, 
2007. Available online (http://idm-lab.org/bib/abstracts/papers/aaai07a.pdf). 
[Pelechano et al. 07] N. Pelechano, J. M. Allbeck, and N. I. Badler. “Controlling individual agents in high-density crowd simulation.” SCA ’07 Proceedings of the 2007 ACM 
SIGGRAPH/Eurographics Symposium on Computer Animation, pp. 99–108, 2007. 
Available online (http://www.computingscience.nl/docs/vakken/mpp/papers/12.pdf). 
[Reynolds 99] C. W. Reynolds. “Steering behaviors for autonomous characters.” Proceedings of the Game Developers Conference (1999), pp. 763–782, 1999. Available online 
(http://www.red3d.com/cwr/papers/1999/gdc99steer.pdf). 
[Sung et al. 04] M. Sung, M. Gleichar, and S. Chenney. “Scalable behaviors for crowd simulation.” Computer Graphics Forum, Volume 23, Issue 3, pp. 519–528. September 2004. 
Available online (http://www.computingscience.nl/docs/vakken/mpp/papers/21.pdf). 
[Ulrich 00] T. Ulrich. “Loose octrees.” In Game Programming Gems, edited by Mark DeLoura, 
pp. 444–453. Hingham, MA: Charles River Media, 2000.