《众神争霸》寻路实现
发表于2015-10-27
一.概述
《众神争霸》是一款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的阻挡图,这样就可以保证英雄与其他单位距离很近,小兵与小兵的距离被拉开。
- 由于RVO在处理静态阻挡时会出现震荡,可以尝试两种方法: