RTS游戏中的群体寻路系统

 “游戏单位寻路是一件玩家很少注意到的事情，直到它不能正常工作，然后这个小问题就变成了一个引发愤怒、世界末日一般的问题。”

           ---- Patrick Wyatt

一、什么是群体寻路

  群体寻路通常被描述为在复杂地形中的多单位集体运动模型，其难点主要是在大规模的寻路中如何在维持各单位相对独立性的同时，维护群体的完整性。

  大规模的部队移动是许多游戏必须面对的一个挑战，特别是在RTS游戏中，经常需要面对几十上百个单位移动到同一地点的问题。这里面主要需要克服两个困难：

如何寻路？是整个部队作为一个整体进行寻路，还是各单位独立寻路？

如何避碰？面对可能导致寻路失败的单位碰撞、障碍物碰撞，要如何避免？

除此之外，一个寻路系统可能还需要满足以下几个要求：

高性能，RTS游戏中的地图较为复杂，需要处理的情况更多

拓展性，为游戏其他系统和模块留足设计空间

易编辑，方便高层级的Level Design

真实自然，能避开障碍物找到最优路线

动态避碰，当地形发生改变，或者突然出现其他单位的时候，不至于寻路失败

二、其他游戏的群体寻路

  寻路系统在业内已经有许多比较成熟的解决方案，从早期的基于规则的方案到近些年的基于算法的方法，下面将简单的介绍一下。

命令与征服(1995) :单位生成的路径只考虑从A点到B点的距离，忽略任何障碍物。这使得单位在移动时彼此重叠，在目的地才重新分开。

所有单位每次都会计算一次最短路径

如果两个单位在同一条导航路径上相遇，则会多次改变运动方向，以躲避其他单位

群体寻路时，单位是互相重叠的，只有在抵达目的地后才会散开

魔兽争霸1&2 : 地图是以Tile为基础设计的，因此使用A*算法来寻找最优路径，但经常会遇到建筑物多占用了额外的Tile，导致寻路有瑕疵的问题。

群体寻路时，若导航路径上出现了新建筑或其他障碍物，则会导致导航路径失效

若在移动时，单位撞到了其他东西，则会向左走或向右走，若一段时间后还没找到就放弃

若在移动时，单位遭受到攻击（或其他事件）则会离开原有的导航路径，执行其他AI行为

单位之间经常发生碰撞，导致寻路失败，两个单位都无法移动

星际争霸1：该作沿用了魔兽争霸的引擎，但画面表现形式又与其不同，因此开发人员编写了大量的规则和设计了巨大的状态机来实现寻路系统，导致寻路系统性能急剧下降。

群体寻路时，单位探测到前方路径上有其他单位，会暂时停止移动，等待其他单位移动过去，再继续沿着原来的路径移动。这能有效避免碰撞发生，但会浪费大量时间

由于星际争霸1是基于魔兽争霸引擎开发的，因此其他方面基本与魔兽争霸相同

星际争霸2：使用了 Flocking System with Flow Fields 技术来实现群体寻路系统，通过计算每个单位的流场来驱动单位移动，并通过 Flocking Module 来控制单位进行避障。

群体寻路时，所有单位不会发生碰撞，不会发生重叠，不会突然的停顿

多个群体互相穿插运动时，也能很流畅的进行避障，且维持一定的阵型，寻路结束后，所有群体完整性不会被破坏

三、群体寻路是如何实现的

  在早期的RTS游戏中，主要以A*算法进行寻路，并基于规则进行避障。这种设计的缺点在于需要耗费大量的计算资源在寻路中，并需要编写大量的规则来实现动态避碰的效果。

 Tile-based algorithm A* (A-Star)

由于寻路算法A*只考虑地形（修改后的A*也可以考虑游戏对象），它必须由一组规则来补充，这些规则根据游戏及其需要而变化。例如，在《魔兽争霸2》中，有一条规则：如果一个单位撞上了其他单位而不能滑过它们，它将重新寻找一条导航路径。这在少量单位的情况下工作良好，但是当试图在一条狭窄的通道中移动大量的单位时，一些单位不可避免地会撞到他们前面的单位并试图重新搜索一条路径。

  正如所见，这些规则非常有限。在某些情况下，他们必须牺牲一些更自然的行为来使整个系统正常运作。真正的最短路径算法会给游戏带来极大的麻烦，这是游戏设计者在选择算法时必须考虑的一个陷阱。针对基于tile的A*算法在处理群体寻路时的局限性，提出了一种基于流场的群集运动系统（the Flocking System with Flow Fields），使群体寻路系统性能进一步的优化，在避碰效果上更加的自然。

Flow Fields + Flocking (or Swarm) Behavior

  游戏《星际争霸2：自由之翼》和《最高指挥官2》以及大多数现代RTS游戏都使用带有流场的群集系统来维持对大部队的流体控制。在每个单元周围产生局部动态流场。在调整群体运动之前，将群体的流场合并在一起。

Pathfinding technique: Flow Fields

  流场是另一种寻找路径的方法，这种方法对含有更多单位的群体更有效。流场是一个网格，其中每个网格正方形都有一个方向向量。这个矢量应该指向最有效的到达目的地的方向，同时避开静态障碍物。

Movement behavior: Flocking (or Swarm)

  群集模型是由人工生命和计算机图形学专家克雷格·雷诺兹（Craig Reynolds）定义的。群，根据定义，是一群一起巡航的鸟。雷诺兹将一般的模拟群集实体称为“boids”，创建了boids人工生命模拟（1986）。基本的群集模型由三个简单的转向行为（分离、对齐和内聚）组成，这些行为描述了个体boid如何根据其附近群体的位置和速度移动。因此，群中的实体（或boids）以大致相同的速度巡航，在没有严格安排的情况下形成一个有凝聚力的群体。

  该算法可以找到最少数量的导航节点，并允许单位自主控制转向行为顺利地绕过障碍物及其邻居。从逻辑上讲，每个单位都有传感器，当与另一个单元碰撞时，它会通知第一个单位转向适当的方向以避开另一个单位。

四、简单的架构设计

  一个简单的群体寻路系统架构，通常可分为两层结构：

Pathfinding Module: 以 NavMesh & A* 为主的寻路模块，获取群体/单位到目标位置的导航路径

Group Movement Module: 群体移动模块，管理所有群体，及群体内的所有单位，单位在群体中表现出 Flocking Behavior

  在群体移动模块中，可通过设置规定一个群体是沿着统一的导航路径进行移动，还是各单位以较为松散的方式进行移动（但仍维持在同一个群体中）。

  并且，在群体移动模块中，可以使用状态机来管理单位的移动，这样可以为后续的设计留下足够的空间，方便与其他AI系统进行交流。

  通常，可以用一个Group类来管理群体，删除/添加单位、设置阵型、设置群体目标等，还可以含有以下属性：

群体在保持一致的情况下可以移动的最大速度：这是由最慢的单位的速度决定的，或者最慢的单位在一个组中移动得更快一些，或者为了追赶而临时提高速度。

群体的质心：群体的参考点。

群体首领：为群体寻路并决定整个群体走哪条路线的单位。群

体阵型：群体中的所有单位以“首领”为中心，维持一定的相对位置

  一个Units结构体来存储单位的信息，包括位置、群体信息、阵型信息和各种状态等，其中寻路运动状态为：

Wait for path：如果单位有一个有效的目标，则会向寻路模块请求一条路径。

Follow path：单位从路径的一个航路点移动到下一个航路点。此状态还管理单元的碰撞预测和避免。

Goal reached：当单位达到目标时，它将进入此状态。

Increase waypoint：当单位到达下一个地标时，该状态用路径的下一个航路点更新下一个地点。

五、动态避碰系统

  解决了群体寻路、单位移动的问题后，还有一个非常重要的问题需要考虑，那就是动态避碰。一个实用、高性能的动避碰系统可以为游戏体验增色不少。

  没有动态避碰，单位经常会发生寻路中发生碰撞导致寻路失败的情况。通常避碰系统有以下几种：

物理碰撞：当单位发生碰撞时，通过规则让单位实现避让的效果

速度避免：在速度空间中计算各单位的实时速度，从中选出在不会导致碰撞发生的速度，如RVO、ORCA算法

群集行为：利用类鸟群算法来模拟群体运动，实现碰撞避免效果

  当然，大多数情况下只依靠一种算法是很难实现出完美的、自然的避碰效果的。在实际开发中，通常需要结合寻路系统和地图情况来进行大量的修改优化，比如导航节点失效问题，运动抖动问题等。

六、总结

  游戏中角色的寻路和移动，对玩家来说是同呼吸一样自然的事情，直到它出现问题。游戏体验是在一个又一个的微小细节当中建立起来的。大到一次技能的释放是否准确，小到角色的一个转身。玩家总能在设计者意想不到的地方发现瑕疵，进而产生不满。对RTS游戏（或涉及到大量单位集体运动的类型）来说，如何实现一个高性能、易扩展又自然的群体寻路系统是一件重要又具有挑战的任务。从顶层的导航系统，到底层的移动模块、动态避碰系统，都需要设计者和开发人员花费大量的时间和精力去打磨。

  本文也只是简单的介绍了群体寻路系统的一些简单、通用的设计，若读者想要将其用到自己的游戏项目中，还需要阅读更多的资料，进行大量的设计和测试才行。

七、参考

https://sandruski.github.io/RTS-Group-Movement/

https://zsummer.github.io/2019/06/08/2019-06-08-rvo/

https://gameinstitute.qq.com/community/detail/102644

Reciprocal Collision Avoidance for Multiple Car-like Robots

https://zhuanlan.zhihu.com/p/78873379

https://www.gdcvault.com/play/1021986/Forced-Based-Anticipatory-Collision-Avoidance

https://www.gameres.com/487419.html

https://zhuanlan.zhihu.com/p/88155091

https://wuzhiwei.net/group-path-movement/

https://blog.csdn.net/a1047120490/article/details/105108701

https://indienova.com/indie-game-development/path-finding-algorithm-in-rts/

https://www.shuzhiduo.com/A/q4zVLlvl5K/

http://www.red3d.com/cwr/steer/gdc99/

https://www.gamasutra.com/view/feature/3314/coordinated_unit_movement.php?print=1

Tested Pathfinding

https://github.com/tomascarreras1000/Research-Project-Group-Movement/tree/master/docs