legamerdc / pathfinding Goto Github PK

笔者能找到的最早的支持碰撞的多人游戏是WarCraftIII，他给我们提供了支持碰撞寻路系统的基本思路：

1. 单位在静止时占据4(2x2) - 16(4x4)个格子。其他单位在行动时不能通过这些格子，其他单位在此时寻路时会感知到这些障碍，并且寻路结果会绕开这些格子
2. 单位在移动时不会占据格子，其他单位在此时寻路无法感知到这些单位
3. 单位在移动时，可能在下一个计算帧与其他单位发生碰撞（即距离小于两者半径合），此时该单位将停止，并将立即占据周围格子。单位将在之后某个计算帧重新发起寻路。

虽然 war3 的寻路碰撞系统比较老旧，有一些问题(单位占据的格子跟单位所在位置有偏差、单位行动不顺畅、单位需要等到碰撞发生了才会重寻路)。但是它也有很多优点，重寻路频率低(发生碰撞才重寻路)，计算量少(不需要每个计算帧处理多个单位间的移动信息，单位静止才改变terrain)，对计算帧的频率要求低(没有碰撞避免，计算帧开销低)，这些优点使得他是MMO环境下可能最佳的碰撞实现基础算法。

相似的思路是暴雪的另外一款游戏StarCraftII，这款游戏与war3相同之处在于: 单位同样需要停止才会生成静态障碍，对其他单位寻路产生影响。不同之处在于: 1. sc2使用navmesh建模，并使用动态编辑navmesh以支持动态更新障碍； 2. 多个单位在互相冲突的行军过程中不会等到要碰撞了才停止，而是使用了steering behavior来引导避免单位的碰撞、跟随。值得注意的是，sc2单位在处理跟友方单位与敌方单位的碰撞时策略不一样(友方单位可以挤开停止的友方单位，还可以和友方单位进行一定程度的碰撞；而与敌方单位碰撞时则是刚体且无法挤开)，这就要求我们在处理地形的时候需要维护多套navmesh，因为sc2最多只有有限的玩家和敌友关系，因此需要维护的navmesh并不多。介绍

dota2的寻路系统分为长寻路和本地寻路，长寻路仅考虑地形障碍为单位行军提供大致方向，本地寻路用于处理单位碰撞、避免和寻路矫正。值得特别注意的是dota2的玩家单位间不会进行碰撞避免，因为卡位是该游戏的核心玩法之一 资料

另一个值得参考的是unity引擎的默认第三方寻路引擎recast&detour navigation，该算法同样是使用navmesh建模地形，单位移动时通过rvo处理碰撞避免，并通过本地重寻路 来矫正寻路(当单位偏离寻路路径时)。资料

稍微总结一下现有游戏的碰撞方案的特点：

1. 大多分为长寻路和短寻路，长寻路提供大致行军方向，短寻路只处理本地的碰撞和矫正，这样做的目的是提高性能。
2. 所有的方案都需要处理本地重寻路，并将动态障碍(单位静止造成的临时障碍)纳入寻路，以提高寻路成功率。
3. 部分方案不采用障碍避免，或者只在特定单位间采用障碍避免，目的是为了实现游戏玩法。
4. 除了开源库的unity寻路引擎外，大部分游戏的寻路系统都是专门为该游戏玩法设计的。因为存在碰撞的游戏碰撞都是游戏机制的一部分，不同单位对之间的碰撞行为并不一样，需要针对设计

本文将方案拆分为长寻路，本地寻路，碰撞行为，碰撞避免。并针对每块部分给出一个可行的方案。

大部分长寻路方案采用类似HPA*的方案，将地图划分为 NxN 的正方形区域(节点)，然后计算地图中所有正方形区域的联通图。当单位寻路时，只需要在节点间计算节点路径即可。寻路性能与节点大小N负相关。注意：

1. 长寻路方案并不关系底层寻路使用navmesh或者是grid，因为只有在本地寻路时才会跑真正的地形寻路
2. 在划分节点时，一个节点内可能有多个不互相联通的区域，此时需要把不同的联通区域算作不同的节点
3. 节点间的寻路可以使用goal bounding为寻路加速，经过该加速方案后普遍的长寻路开销应该在 100us 级别
4. 节点间寻路还有诸多额外好处，例如：预估距离，快速判断连通性，寻路结果不容易出现大偏移

本地寻路反而更加类似未加碰撞的寻路算法，使用navmesh 或者 grid 作为底层障碍建模都可以。

1. 由于需要支持动态障碍，因此如果采用navmesh用于寻路时需要采用支持动态调整的结构，如CDT，这类结构调整时的复杂度比较高，实现也比较复杂。特别是当我们需要对不同的单位队间采用不同的碰撞处理时，那么就需要对每种可能的情形单独运算一次。
2. 当使用grid作为障碍描述结构时则相对简单，只需要对动态障碍设置相应的bit即可。但缺点是碰撞精度取决于grid的大小，较小的grid虽然表现会更好但是开销也会变高，类似war3的游戏选择grid大小为单位的 1/16-1/4。
3. 也可以在初次寻路时使用navmesh，仅在碰撞产生后使用grid寻路，这样即可以获得navmesh的高精确性也可以利用grid寻路初始化低开销的优点。
4. 本库采用的是 grid + jps算法用于本地寻路，原因在于：grid寻路的实现比较简单，我们的场景要求每个阵营都有一套碰撞逻辑，在阵营比较多的时候grid寻路初始化开销比较低。
5. 考虑到单个grid本地寻路比较容易无解(本地路径都被堵了)，参考 AOE IV的方案，可以在本地寻路时纳入周围6-9个grid来寻路。

不使用碰撞避免的流程相对简单：单位寻路并行走，直到下个tick会与其他单位碰撞，此时，该单位停止行走，并在若干个tick后重新发起寻路。

使用碰撞避免的流程相对复杂一点：

1. 计算当前所有单位下帧位置与预期速度
2. 根据所有单位的预期速度预期速度计算碰撞避免后速度作为真实速度。
3. 根据以上速度计算单位下个帧是否会碰撞，如果是则停止行走并等待若干tick后重新发起寻路。

以上方案中的碰撞避免的算法比orca中的处理会少一些，因为我们可以通过动态障碍参与寻路来兜底。下图展示了一下计算帧为4时的一些示例：

本库使用 orca 算法用于碰撞避免，原理是当多个单位接近碰撞时，两两间各自让出速度中的碰撞分量的一半。然后对每个单位根据出让限制通过线性规划的方式找到最接近原本速度的方式。