《众神争霸》寻路实现

发表于2015-10-27
评论9 1.4w浏览

.概述

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

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

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

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

 

二.表现层寻路

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

 

  •           表现层使用技能时的流程图:http://km.oa.com/files/post_photo/293/192293/504004c66e85f2b00ec21b187543baef.gif
  •            
  •           表现层处理技能队列的流程图:http://avocado.oa.com/fconv/files/201402/0dc1cd5fbf3b76df15de2f2d360c9b10.files/image003.gif

 

三.   逻辑层寻路

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

 

四.寻路算法

http://avocado.oa.com/fconv/files/201402/0dc1cd5fbf3b76df15de2f2d360c9b10.files/image004.jpg

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

 

五.     性能

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

 

六.   阻挡规避(Collision Avoidance)

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

 

  •           阻挡区域VO(Velocity Obstacle),如下图,白色圆圈表示单位,黄色的扇形表示阻挡区域,扇形分的越细,阻挡规避时的路径越平滑。http://avocado.oa.com/fconv/files/201402/0dc1cd5fbf3b76df15de2f2d360c9b10.files/image009.jpg

 

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

 

  •           下图演示两个单位同时朝对方方向走过去的过程:http://avocado.oa.com/fconv/files/201402/0dc1cd5fbf3b76df15de2f2d360c9b10.files/image011.jpg
  •            
  •           http://avocado.oa.com/fconv/files/201402/0dc1cd5fbf3b76df15de2f2d360c9b10.files/image013.jpghttp://avocado.oa.com/fconv/files/201402/0dc1cd5fbf3b76df15de2f2d360c9b10.files/image014.jpg
  •            
  •           http://avocado.oa.com/fconv/files/201402/0dc1cd5fbf3b76df15de2f2d360c9b10.files/image015.jpg

 

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

 

  •            RVO的优缺点
    •                                    优点:能很自然的处理动态单位之间的本地自动阻挡规避,效率很高,能同时模拟成百上千的单位。
    •                                    缺点:规避静态阻挡的效果不太理想,容易产生震荡,比如我们的游戏中,如果前面有多个静态单位时,小兵会来回徘徊。
  •           一些想法
    •                                    由于RVO在处理静态阻挡时会出现震荡,可以尝试两种方法:
      •                                                            继续使用RVO,单位静止时不再参与RVO计算,其他单位碰到该单位的阻挡就直接寻路,单位移动时重新参与RVO计算。
      •                                                             
      •                                                            去掉RVO,小兵按waypoints行走,行走的过程中碰到阻挡后,首先寻一条只考虑静态阻挡的路径,然后在附近寻一条考虑动态阻挡的路径,最后合并静态和动态两条路径。
      •                                                             
    •                                    由于我们的寻路类似LOL,英雄可以在很窄的小兵空隙间穿行,而小兵之间又保持一定的间距不重叠。目前我们的小兵重叠比较多,造成补兵困难。可以考虑分层寻路,英雄用512x512阻挡图,小兵用256x256的阻挡图,这样就可以保证英雄与其他单位距离很近,小兵与小兵的距离被拉开。

 

如社区发表内容存在侵权行为,您可以点击这里查看侵权投诉指引