寻路和Flocking算法的结合

最近本来在研究行为树， 然后无意间发现了一本名叫《Artificial Intelligence for Games, Second Edition》的书，就顺便看了起来。

书中第三章提到了一个Flocking算法，该算法一般用于模拟群体（羊群，鸟群，鱼群，人群）的移动行为。

这让我想起了大约一年前，他们QQ群里分享了一个蚁群行军的视频。当时为了研究他是如何时实现的，还特意去学习了VO，RVO算法（没有学会），最终也没有实现出来。

这次，我想用Flocking算法再试一次。

先简单介绍一下Flocking算法。

对于鸟群中的一只鸟而言，除了他本身要飞行的速度向量Velocity外，还有三个额外的分量来辅助校正最终的速度向量。

这三个额外分量分别如下：

Separation：每只鸟都会考虑到它们相对周围其他鸟的位置，如果过近，就会产生一个排斥速度分量。

Cohesion： 每只鸟都会检查自己半径R范围内鸟的位置，计算出这群鸟的质心，产生一个向质心靠拢的速度分量。

Alignment: 每只鸟都会检查自己半径R范围内的鸟的速度，计算出这群鸟的平均速度，然后产生一个向平均速度靠拢的速度分量。

最终每只鸟的速度为：Velocity + Separation + Cohesion + Alignment（在叠加过程中，可以根据情况给每个分量加上相应的权重）。

Flocking在没有障碍物的场景，比如天空，海底，平原等表现都很不错。但是一旦进入有障碍物的场景如蚁穴，就会很难工作。

这时就需要加入寻路系统来提供路径支持。

然而，事情并没有这么简单。

由于有Separation，Cohesion，Alignment速度分量的存在，即使我们给每只鸟单独寻出来一条路径，也不能保证这只鸟就一定会严格按照路径行走。

比如我们为某只鸟寻出来的路径为((0,0), (0,1),(0,2))(我们把地图切成很多小块格子，坐标为格子坐标，不是实际的世界坐标)。

在从(0,0)到(0,1)运行的过程中，由于鸟群的干扰，可能会把这只鸟挤到了(1,1)格子，这时可能(1,1)是到不了(0,2)的，需要重新寻路。

这就意味着，每只鸟每跨过一个格子，就需要重新寻路一次，这么大的开销足以使FPS降到5。

在网上搜到一种解决方案。

给整个鸟群指定一个Leader。为Leader计算一条路径，Leader严格按照路径行走。鸟群中的其他鸟使用Flocking算法来跟随Leader即可。

我尝试了这种方案后，发现这个方案在绕过大片障碍物时非常好用。但是在通过狭窄通道时，很容易发生跟随失败，导致一些鸟永远卡在那里不能行动。

比如下面这种情况:

                   xxxxxL
                  x
  ------------ x --------------
                  x
                   x
                      xB

Leader在位置L处，B位置处的鸟要跟随Leader，必然要产生一个从B位置向L位置的速度。

如果B鸟按这个跟随速度运动，就会被卡在墙的一侧，永远的脱离队伍。

我尝试优化这种方案，除了Leader之外，我加入了Target角色。

所有的鸟在运动时，会在自身周围一定范围内寻找一个Leader或Target作为跟随的目标。

找到跟随目标之后，自身也会变成Target角色，供其他鸟跟随。

如果找不到合适的跟随目标，自己就会变成临时Leader。然后重新计算一条路径，并严格按照路径运动。直到遇见一个合适的Target之后，这只鸟就会再次变回Target。

这种方案可以应对各种极端障碍物情况。但是这个方案几乎把Flocking所有的特性都抹掉了，鸟群在整个运动过程中会排成一字长蛇阵，看起来非常不自然。

我找到当时的QQ聊天记录，仔细读了几遍，然后换了个思路。

计划让鸟群运行到某个目标点那一刻，使用Dijkstra算法计算出地图上所有格子到目标点的最佳运动方向。

这里有个小技巧，我们使用目标点作起始点，然后运行Dijkstra算法。

当Open列表为空时，就已经完成了地图上所有格子到目标点的最佳方向计算。

每只鸟在移动前，根据当前位置计算出当前格子，然后直接查询出下一步的目标点。

理论上，根据目标点计算出鸟的Velocity速度向量，再叠加Separation，Cohesion，Alignment速度分量就是最终的速度值。

然而，现实是残酷的。

经过实验发现，由于鸟群的作用力，经常会有鸟被挤进障碍物中，尤其是在经过狭窄通道时。

因此我们还需要静态避障速度分量。

在《Artificial Intelligence for Games, Second Edition》中第“3.3.15 Obstacle and Wall Avoidance”节中，讲到可以使用射线检测来躲避静态障碍物。

测试发现，当角度比较奇葩时，射线检测不到障碍物的存在，从而导致最终被挤到墙里面去，3.3.15节也有提到过这种情况。

最终，我采用了AABB来检测周围是否存在障碍物，当有障碍物时，根据障碍物的质心和当前鸟的位置来产生一个远离障碍物的速度分量，这个分量的权重要显著大于其他4个速度分量。

如果障碍物形状态复杂时，可能需要重写AABB检测逻辑，根据相交的边计算出远离障碍物的速度分量。

到目前为止，最大的开销就剩下为地图上所有格子计算最佳方向了。

如果地图过大，这样计算是不现实的。

在写这篇文章时，我想到了一个优化算法，还没来得及测试。

通过观察Flocking算法，不难发现鸟群中的鸟几乎全是按照大致相同的路线行走的。

也就是说，只要我们想办法生成一个有宽度的路径，基本上就可以满足给鸟群寻路的需求了。

首先使用AStar算法，从整个鸟群的质心到目标点计算出一条路径。

然后，对第一步中路径的每个格子，都使用Dijkstra算法，计算出周边格子到这个格子的最短路径。计算时要限制Dijkstra算法遍历的深度。只要我们选取的深度合适，大部分鸟行走的格子都会被命中。

值得一提的是，在应用Dijkstra算法时，路径中相临格子的周围是相互覆盖的，需要根据权重进行刷新。

举个例子：

已经使用AStar算法计算出A到D的路径为(A,B,C,D)。

对格子B应用Dijkstra算法时，对邻居E生成了最佳运动方向为向B运动，E到D的权重为E(1)+B(2) = 3。

对格子C应用Dijkstra算法时，同样会处理到邻居E，这时不能简单的跳过E，而应该计算E到D的权重为E(1) + C(1) = 2。

这时应将E的最佳运动方向改为向C而不是B。

如果某只鸟被挤到了一个我们事先没有计算过的格子上，就使用AStar以此格子为原点向目标点寻路。

这里有一个可以优化的地方，我们已经有了一条很宽的路径，只要AStar寻到已有的路径格子就可以停止继续寻路了。

最后，Demo在此。