3月, 2022 | 重归混沌的BLOG

寻路和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在此。

行为树的一种高效实现

在我的玩具项目中，需要有一定智能的NPC来辅助人类攻击防御塔。

通常实现智能会采用状态机，行为树，GOAP等技术。

GOAP技术我没有研究过，行为树在早些年大致了解过一些。因为觉得行为树性能太差，不可能取代状态机实现，之后就再也没有研究过了。

随着这些年我性能强迫症的好转，再加上听到行为树的次数逐年增加，我打算趁机仔细研究一下。

我找来《Behavior Trees in Robotics and AI》仔细读了一遍。这本书详细介绍了行为树，并且对比了行为树和状态机之间的优劣。

根据《Behavior Trees in Robotics and AI》描述，行为树一般有4种控制节点（Sequence, Fallback, Parallel, Decorator)和两种执行节点（Action和Condition)。只有执行节点才能成为叶子节点。

先来简单描述一下最重要的两种控制节点, Sequence和Fallback。

Sequence节点: 当执行Sequence节点时，从左往右顺序执行子节点，直到某一个子节点返回Failure或Running状态，伪码如下：

//Algorithm 1: Pseudocode of a Sequence node with N children
for i 1 to N do
    childStatus <- Tick(child(i))
    if childStatus = Running then
        return Running
    else if childStatus = Failure then
        return Failure
return Success

Fallback节点：当执行Fallback节点时，从左往右顺序执行子节点，直到某一个子节点返回Success or Running状态，伪码如下：

//Algorithm 2: Pseudocode of a Fallback node with N children
for i 1 to N do
    childStatus <- Tick(child(i))
    if childStatus = Running then
        return Running
    else if childStatus = Success then
        return Success
return Failure

Action和Condition节点，是我们具体的业务逻辑，不是本次优化的重点。

对比行为树和状态机可以发现，行为树比状态机额外多出的开销，就是在执行执行节点之前，必须要先穿过控制节点。

如果我们在运行时能避过控制节点，只执行执行节点，那行为树和状态机的开销差别就只是多了几次函数调用而已。

仔细思考过之后，我认为这是可能的。

结合上面对Sequence和Fallback节点的定义。我们不难发现，在编程语言中，Sequence就是and(与)逻辑，而Fallback就是or(或)逻辑。

整棵行为树的控制节点就是用来描述if-else的逻辑，叶子节点是相应的业务逻辑。从这个角度来看，行为树和语法树有颇多相似之处。

不难发现，整棵树的执行路径，其实依赖于特定执行节点的特定返回值。

某一个执行节点（叶子节点）返回Failure或Success, 整棵行为树下一步要执行的执行节点是固定的。

某个执行节点返回Running，整棵树就停止执行。在下一Tick之后从头执行，这种情况比较简单，暂时不需要考虑。

来看一棵简单的行为树：

如果 Action 1 Done 返回Success，下一步将要执行的执行节点（叶子节点）就是 Actino 2 Done。
如果 Action 1 Done 返回Failure, 下一步将要执行的执行节点（叶子节点）就是 Action 1。

这种逻辑可以递归到所有的执行节点。

这样，我们只需要两张跳转表（Success跳转表，Failure跳转表)，就可以在运行时，以状态机的开销来实现行为树的功能。

以上面的行为树为例，我们可以生成如下跳转表：

local tree = {
["Action 1 Done"] = {
    ["Success"] = "Action 2 Done",
    ["Failure"] = "Action 1"
},
["Action 1"] = {
    ["Success"] = "Action 2 Done",
    ["Failure"] = nil, --nil 代表整棵树执行结束
},
["Action 2 Done"] = {
    ["Success"] = nil,
    ["Failure"] = "Action 2"
},
["Action 2"] = {
    ["Success"] = nil,
    ["Failure"] = nil,
}
}

在运行时，我们首先执行整棵行为树的第一个节点"Action 1 Done"。

如果"Action 1 Done"返回Success, 根据表tree可知，下一步需要执行的是"Action 2 Done"。

如果"Action 2 Done"返回Failure, 根据表tree可知，下一步需要执行的是"Action 2"。

这样我们仅需要生成一个跳转表，就可以在运行时抹掉所有控制节点所带来的开销。

最终，我花了200行代码实现了根据行为树生成上述跳转表的逻辑。

PS.我把生成跳转表的行为称之为编译。如果控制节点是Parallel或Decorator类型，或者有记忆功能。在编译过程中，需要将其保留，不能将其编译掉。不然无法完成和行为树等价的逻辑。

PPS. 在示例代码，我使用了behavior3来编辑行为树。

内测过程中Shader出现的问题

兜兜转转一年多，终于再次内测了。

这次在客户端开发中，我们的指导思想是能用GPU做的坚决不用CPU做，除非GPU出现了瓶颈。因此我们大量使用了自定义Shader。

由于我之前其实没有太多Shader的编写经验，这次上线之后暴露了不少实践性问题。

首先遇到的就是精度问题。

在地表渲染过程中，如果碰到下雨天，我们会在地面湿滑到一定程度之后生成涟漪。

这个功能是直接做在地形Shader中的，与涟漪Bug相关的代码如下：

//ripple.a = 0.4117647
float f1 = frac(ripple.a + _Time.y);

上线之后，我们发现在小米系列手机上，当_Time.y的值大于300之后, f1的值会产生跳变。

经过抓帧之后发现。

当_Time.y`为`300.033`时`f`等于`0.5019608`, 此时`f`的正确值应该是`0.4447647

当_Time.y`为`300.066`时，`f`的值还是等于`0.5019608`, 此时`f`的正确值应该是`0.4777647

将代码改为如下：

//ripple.a = 0.4117647
float f1 = frac(ripple.a + frac(_Time.y));

在_Time.y`为`300.033`和`300.066`时，f1的值分别为`0.4431373`和`0.4784314。

与正确值相比，误差分别是0.0016274`和`0.0006667。

这些数值是通过颜色调试法取得，而像素的颜色精度只有1/255(0.0039216), 因此可以认为误差是颜色调试法带来的，而整个计算是精准的。

这说明了高通系列的GPU，其float在计算过程中，要比IEEE 754标准的浮点型精度更低，可能远小于7位有效数字。

这也给我提了一个醒，当我们的Shader需要长时间运行时，一定要注意_Time.y过大之后，在运算过程中会精度丢失的问题。即使GPU完全按照IEEE 754标准来实现，只要运行的时间足够久，也会出现这个问题（比如我们的树，在所有客户端上，只要运行超过4个小时之后，就会静止不动）。

有些情况下，不是简单加一个frac函数就能解决问题的。这时，就需要将与_Time.y相关的数值移到C#中去计算，然后在每一帧的Update中，向Shader设置变量，这么做会有一个额外好处，可以将对_Time.y相关的计算减少到每帧一次。如果在shader中计算_Time.y相关的逻辑，则每一个顶点或像素都需要重新计算一次。

另外一个Bug还是与精度有关，不过是以另一种方式存在。

在世界地图中，如果玩家立国，需要将国家的颜色铺满整个行省，而行省的形状是异形的，如果使用Quad的方式去铺满整个地图，会带来大量的Overdraw。

因此在实现过程中，我们给整个大地图设计了一张IDMap, 每一个像素都会有一个整数ID来代表他所在的行省。

在FragmentShader中，我们采样IDMap之后，并不直接用于渲染，而是将他转换成整数ID，然后使用ID来当索引查询当前行省的颜色。将查询到的颜色用于渲染。

大概代码如下：

fixed4 frag (v2f i) : SV_Target
{
    fixed4 c = tex2D(_MainTex, i.uv);
    int n = clamp(c.a * 255, 0.0, 45.0);
    return _Colors[n];
}

上线之后，我们发现在华为系列手机，这个n会有偏差（安卓系统和鸿蒙系统表现还不太一样），但是在国内其他主流手机，如小米，Oppo上不会出现。

在问题排查过程中，我一度怀疑是精度问题。因此不停地在图片格式上做文章。直到最后我才发现我犯了一些常识性错误。

首先，RGBA32格式的图片是指RGBA的4个通道分别占用一个byte(8bit)来表示一个通道颜色值。

图片文件中，实际存储的颜色值是0~255的整型，而不是0~1的浮点型，也就是说单通道精度最高也只能到1/255。

而我们实际使用过程中n的值只是0~45，远低于1/255，不可能是图片精度问题。

其次，在计算过程中 1/255*255 `的结果实际上并不是`1`而是`0.99999999999975左右。

在Intel、AMD、高通系列芯片上，int a = (int)(1.0 / 255.0 * 255.0), a是会等于1的。

在麒麟系列芯片，a则会等于0，我不能说麒麟系列芯片的精度够或是不够，只能说我写的代码不规范。

这次的教训告诉我，浮点型在不同平台的实现过程中，会有平台相关性。

定位到了问题，修复自然就是一件很简单的事。

int n = clamp(round(c.a * 255), 0.0, 45.0);

或者

int n = clamp(c.a * 255 + 0.0000001, 0.0, 45.0);

都可以解决问题。