《众神争霸》寻路实现

一．概述

—  《众神争霸》是一款10V10的Dota类竞技游戏，对寻路的要求是：

•           单位之间需要规避阻挡
•           大量单位的高效寻路
•           小兵之间要有一定间距，方便补兵
•           英雄能在小兵很小的缝隙间行走

—  目前游戏是基于网格的A*寻路，阻挡规避是基于RVO(Reciprocal Velocity Obstacle)算法。

—  由于客户端是基于帧同步技术，所以寻路分为表现层寻路和逻辑层寻路。

二．表现层寻路

•           之前的方案中只有逻辑层寻路，逻辑层会计算所有单位的寻路，而且断线重连和录像回放也都需要寻路，所以性能消耗比较大。
•           目前增加了表现层寻路，只针对英雄，玩家在使用技能时就寻一条路径出来，然后将路径发送到网络，这样逻辑层就不需要寻路了，只有在碰到阻挡的时候才需要寻。
•           由于寻路计算分布在每个客户端，就减少了逻辑层和服务器的计算压力。
•            由于发送的路径到逻辑层，所以断线重连和录像回放就比较快。
•            表现层使用分帧寻路以免拖累FPS。最大搜索节点数60000，单帧搜索节点数10000，一次寻路最多6帧，一般最远距离也就3、4帧，单帧消耗5、6毫秒。
•           分帧寻路时技能的发送会延后几帧，为了保证技能的顺序执行，将技能请求缓存到技能队列中，后续Tick时发送。
•           表现层目前只考虑静态阻挡和建筑动态阻挡。

•           表现层使用技能时的流程图：
•            
•           表现层处理技能队列的流程图：

三．   逻辑层寻路

•            英雄：首先使用表现层发过来的路径行走，如果在行走的过程中碰到其他单位就在逻辑层重新寻路。
•                      小兵：小兵是按照配置的Waypoints直接行走的，阻挡规避使用的是RVO算法。行走的过程中碰到静态阻挡时会重新寻路，追击的单位死亡或视野丢失时会返回waypoints继续走。 

四．寻路算法

•            RgPathFinder实现具体的网格A*寻路,返回平滑过的路径。分为单次寻路和分帧寻路。
•            如果搜索超过最大节点数，返回H值最小的节点，也就是离目标点最近的点。
•            扩展节点的过程中，如果当前点与目标点的距离小于最小到达距离signDistance，就以该点作为目标点返回。
•           如图，在扩展节点的过程中发现红点与target的距离小于signDistance，单位会直接走到红点位置，而不是越过阻挡。
•          
•           如图，当signDistance很小时，单位会绕过阻挡

五.     性能

•           网格A*的性能瓶颈在于扩展节点时的堆排序，时间复杂度为O(nlgN)，网格越多性能消耗越大。目前阻挡图已经由1024 x 1024改为512 x 512。
•           区分英雄和小兵的最大寻路距离，英雄最大寻路格子数为四分之一地图60000。小兵都是短距寻路，最大格子数为8000。小兵一般很少寻路，使用RVO走waypoints，只有碰到静态阻挡时才寻路。
•           由于目前增加了表现层寻路，所以计算量分了很大一部分到各个客户端。
•           尝试过一些A*的变种，比如四叉树、JPS(Jump Point Search)，虽然效率上完全能满足要求，但是搜出来的路径比较粗略，NavMesh处理单位的地图阻挡效率比较低.，所以他们并不适合Moba类游戏。 
•           如图常规的A*寻路，消耗37ms，灰色表示阻挡，蓝色表示扩展的格子
•          
•           JPS寻同样的路径只需1.8ms
•             

六.   阻挡规避(Collision Avoidance)

•           使用了RVO(Reciprocal Velocity Oblstacle)算法，直译就是相互速度阻挡，是一种处理本地阻挡避让的算法。大概的原理就是，每个单位都会形成一个速度阻挡区域，行走时自动避让这些阻挡区域。阻挡区域的划分可以有不同的方式，目前我们用的是ORCA，但是比较复杂，为了便于解释我用另一种方式。

•           阻挡区域VO(Velocity Obstacle)，如下图，白色圆圈表示单位，黄色的扇形表示阻挡区域，扇形分的越细，阻挡规避时的路径越平滑。

•            自动规避阻挡的过程，如下图，每个单位都有个朝目标点行走的预期速度向量V，当有其他单位进入阻挡区域时，这个区域就会被标记成被占用，单位就会从其他可行走的区域中寻找一个向量与V相加，这个向量就是单位新的速度。黄色圆圈表示最大阻挡区域，红色圆圈表示警戒区域，会对单位速度产生不同的影响。

•           下图演示两个单位同时朝对方方向走过去的过程：
•            
•          
•            
•          

•           寻路与RVO的结合
  •                                    首先用寻路算法寻一条路径，然后单位依次走向路径点，单位在行走的过程中使用阻挡规避算法，自动避让其他单位和静态阻挡
  •                                    如下图，黑色的线表示阻挡墙壁，墙壁和其他单位都会影响单位的阻挡区域，单位想从A到C，首先使用寻路找到一条路径ABC，然后将单位到B点的向量作为Preferred Velocity，RVO驱动单位走到B点，用同样的方法从B走到C。

•            RVO的优缺点
  •                                    优点：能很自然的处理动态单位之间的本地自动阻挡规避，效率很高，能同时模拟成百上千的单位。
  •                                    缺点：规避静态阻挡的效果不太理想，容易产生震荡，比如我们的游戏中，如果前面有多个静态单位时，小兵会来回徘徊。

•           一些想法
  •                                    由于RVO在处理静态阻挡时会出现震荡，可以尝试两种方法：
    •                                                            继续使用RVO，单位静止时不再参与RVO计算，其他单位碰到该单位的阻挡就直接寻路，单位移动时重新参与RVO计算。
    •                                                             
    •                                                            去掉RVO，小兵按waypoints行走，行走的过程中碰到阻挡后，首先寻一条只考虑静态阻挡的路径，然后在附近寻一条考虑动态阻挡的路径，最后合并静态和动态两条路径。
    •                                                             
  •                                    由于我们的寻路类似LOL，英雄可以在很窄的小兵空隙间穿行，而小兵之间又保持一定的间距不重叠。目前我们的小兵重叠比较多，造成补兵困难。可以考虑分层寻路，英雄用512x512阻挡图，小兵用256x256的阻挡图，这样就可以保证英雄与其他单位距离很近，小兵与小兵的距离被拉开。