图形引擎实战：RVO动态避障使用分享
大家好我是畅游引擎部的考拉，今天给大家分享一下我们在工作中对于RVO算法的一些改动和使用经验。近期在进行NPC相关工作有一个需求是让许多NPC在大街上走的时候可以相互避让，这个问题使用Navmesh的动态寻路也可以部分解决，但是unity原生的Navmesh太过封闭很难做一些适应性修改，不宜在项目中进行使用，所以在经过调研后决定用RVO算法来解决动态避障的问题。
一、概述
大体上来说，RVO算法就是一个每个Agent在选取下一帧的前进方向时会基于全局所有Agent位置和理想前进方向进行计算，互相影响的Agent会各自沿远离的速度方向避让一段距离，来保证在移动过程中没有碰撞。RVO算法的原理网上也有很多讲解的博文在这里我就不再赘述了，RVO算法的源码和一篇讲解十分详细的帖子我会贴在文章最后面。这里选用的RVO算法也是2D版本的，因为NPC的主要移动方式还是地面上的行走，加上一些高度的判断也可以解决问题。
二、使用要点和改进
这里就用C#代码进行示例，RVO的C#版源码运行方式是：存在一个RVO模拟器，在使用过程中需要把场景中会进行避障的NPC作为Agent注册进去，每帧设置NPC的位置和理想前进方向，RVO模拟器在经过Step后会得到所有Agent在下一步的位置和速度。
1、理想速度设置
这里要注意的第一个要点是设置理想速度方向，在设置时要加上一个随机的微小扰动，因为两个Agent的理想速度如果完全对称可能会造成死锁。
2、避障权重的设置
上文说到RVO算法原理大致上是全局计算，Agent之间相互避障，但是这个相互避让的程度在源码中时写死的为0.5，也就是Agent之间沿不碰撞的速度分量各自避让一半，我们可以对这个权重进行修改，让每个Agent拥有不同的权重来实现更丰富的表现。
比如如果要在避障场景中加入静止不动的NPC或者主角，他们的避障权重就要设置为极小值，因为他们没有办法在RVO的计算中去完成自己那一部分躲避动作，所以就需要依靠设置一个极小的避障权重让对方完成几乎所有的避障动作。
相同权重避障&不同权重避障的效果对比：
视频链接：https://zhuanlan.zhihu.com/p/627264791
3、环绕攻击解决方案
此外RVO还有一个重要的使用场景，那就是在RTS等单位较多的游戏中常常会有多个单位环绕攻击的需求，如果不采用动态避障算法，他们的表现可能是像《红色警戒》中单位中相互碰撞卡顿，或者是像《暗黑破坏神手游》中将怪物模型的碰撞体积变小，造成模型堆叠的情况，表现都不是太好。
在这里分享一种基于RVO的环绕攻击解决方案，我们假设怪物要进行攻击的目标地点是以目标为中心的一个环形区域，那么就可以将怪物NPC环绕攻击的移动分为两个阶段，第一个阶段是在在射线检测的帮助下行进到攻击距离范围内，第二个阶段是在攻击范围内站定，在RVO的影响下调整自己的位置，给后续加入的NPC流出空地。
如上图所示，怪物NPC会朝自身与目标的连线方向，在身体两侧各打一条射线，如果没有发生碰撞则朝这个方向前进，如果发生碰撞，则以目标方向为正方向，分别往顺时针和逆时针方向偏转45°、90°得到5条射线，根据射线的碰撞距离来判断探索的方向。
当怪物NPC到达目标的环形区域后就进入的第二个阶段，这时后续的NPC如果想挤进区域中就会通过RVO系统影响到已经站定的NPC。
如上图所示，agent1是一个已经到达指定位置的NPC，agent2还在调整中，agent2会通过RVO算法对agent1有一个为V的推动效果，但是为了不影响agent1所保持的攻击距离，我们将v沿着与目标连线的垂直方向进行分解得到V1，让agent1沿V1方向移动，最后得到的调整效果就会比较平滑。最终效果如下图所示。
三、辅助方法
在把RVO接入项目的时候我们往往还要考虑RVO的边界问题，要在RVO中添加Obstacle防止NPC在互相躲避时往墙体或者障碍的方向移动，我采用的方法是提取Navmesh轮廓，Navmesh描绘的刚好就是场景中的可行走地面。通过分析navmesh的数据我们可以观察得到，navmesh是由三角面拼接得到的，从边的角度出发，在navmesh内部的边都出现过多次，只有轮廓上的边在navmesh数据中只出现一次，通过这种特点我们可以提取出navmesh的轮廓。
在提取过程中也有一些需要注意的点，首先navmesh中相同的顶点可能出现多次，需要对其进行去重来为后续的步骤做准备，在对比两个点是否同时要注意考虑误差（比如0.0001f），其次由于Navmesh的数据结构有的时候并不是特别规则，如下图所示：
正常情况下我们将顶点去重，建立一个hashSet就可以判断同一条边的出现次数，以此来判断轮廓，但是也有些情况（如右图所示）边的出现次数要在合并较短边后再进行判断。
如上图所示，红色轮廓就是提取出来的结果。
四、性能测试和优化
RVO算法的Tick方法默认是多线程tick每个Agent，在PC上的消耗可以忽略不计，在Intel i7-9700的CPU下15个Agent的tick消耗为0.18ms。
但在Android下，由于不用机型多线程表现不同，在一些机型（比如MI10）下将Agent的tick方式改为同步性能还会更好一些。
在一些复杂场景中，如果边界太过复杂，RVO的性能消耗可能发生在边界的搜索上，这个时候可以适当缩短一些边界检查的距离可以减少性能消耗。
五、总结
最后希望大家都能使用RVO算法优化自己的游戏表现，为玩家带来更好的游戏效果。
---------------------------------------------------------------------------------------------------
RVO算法：https://gamma.cs.unc.edu/RVO2/
讲解博文：https://blog.csdn.net/lsccsl/article/details/119732620
RVO C#版源码：https://github.com/snape/RVO2-CS
欢迎加入我们！感兴趣的同学可以投递简历至：CYouEngine@cyou-inc.com
#搜狐畅游##引擎开发工程师##游戏开发##校招#
美团泡池子165人在聊