寻路

基于NavMesh寻路、漏⽃寻路、RVO动态避障⾃创的服务器

⼤规模寻路+动态避障算法的实现

⼀、描述

TW项⽬是⼀个拥有较⼴阔野外空间的SLG游戏，玩家的军队⽅阵可以在野外进⾏长距离⾏军、短距离⾃由⾏军、占领要塞、驻扎、形

成战⽃阵型战⽃等⾏为。其中，野外的⼭脉、河流等会产⽣静态阻挡；⽽由玩家迁城、把守要塞、驻扎等⾏为，会在野外地图上产⽣动态阻

挡。

每个服务器活跃军队⽅阵⽬标5万个，每天产⽣的长距离寻路请求可能达⼏⼗万或者百万个，并且都需要在服务器端计算，⽤常规的

A*寻路、navmesh寻路、ROV避障算法计算量巨⼤，影响服务器效能。所以我们可以采⽤两种解决⽅案：第⼀是做⼀个寻路服务器；第⼆

是选择优化算法。本⽂给出了第⼆种优化算法⽅案。

⼆、需求

1、长、短距离寻路

2、寻路校验（如果有前端寻路，那么后端需要校验）

3、动态避障

注：以上所有需求是2D寻路

三、寻路

1、⾸先⽤navmesh寻路算法作为第⼀步，为野外地图创建静态寻路⾯⽚；

2、然后⽤“⼩边剔除”、“凸多边形合并”的算法尽量合并⾯⽚（这样做可以使内存占⽤最⼩），如下图；

左边的线段BC被剔除，⽤BE+CE取代。右侧HG、GJ线段被剔除，⽤HJ取代。

KN线段被直接剔除，两个凸多边形合并

3、⽤漏⽃寻路算法离线计算所有的⾯⽚到所有其他⾮相邻⾯⽚的最优路径，并记下途径⾯⽚索引、⾯⽚重⼼距离边的垂线的平均长度、路

程距离、权重等参数，形成“路径数据”保持到⽂件（最优路径可以不⽌⼀条）；

4、后端在计算寻路请求的时候，算法如下：

4.1）起点终点在同⼀个⾯⽚内，直接返回；

4.2）起点终点所在⾯⽚相邻（没有途经⾯⽚），直接返回；

4.3）起点终点所在⾯⽚途径⼀个⾯⽚，并且有多个这样的最优路径，需要分别计算起点、终点到相邻⾯⽚交点的长度+途径⾯⽚重⼼

距离边缘长度，选择最短的；

4.4）起点终点所在⾯⽚途径⼀个⾯⽚，并且有多个这样的最优路径，需要分别计算起点、终点到相邻⾯⽚交点的长度，选择最短的；

5、后端校验，只需要看路径是否在“路径数据”即可。

6、前端收到后端穿来的路径后，只需要按“漏⽃寻路”算法，在需要的时候进⾏计算即可。

四、避障

由于我们的障碍物是可能突然出现在前⽅的，我们并不能像ROV那样预先计算，选择⼀个另外路径，所以我们躲避障碍物的⽅式为：不会

提前改变路径，⽽是到障碍物⾯前后才改变。

下图是RVO避障算法，蓝点⽅阵知道障碍物（红球）的存在，会与红球相撞的蓝点会提前改变路径

下图是我们的动态避障算法，本来obj要从C点移动到K点，但是由于有障碍物的出现，于是到快与障碍物相撞的D点时转向，⾛D-E-F-H-K

各点，到达⽬标点与障碍物包围圆切线位置时⾛直线奔向⽬标点

此算法依赖于如下⼏点前提条件：

1.障碍物都可以被圆包围，不会⽆限⼤，按照圆（折线）躲避不会违和。

2.紧贴着障碍物的周围是可以⾛的，也就是障碍物不能连起来形成更⼤的障碍。

本来要从N⾛到P点，结果⾛到O点时发现障碍物A。

1、将A的包围圆分成12份，每份30度。

2、由于已知A点位置，圆半径（基本都是固定半径），AB与AC夹⾓度数（30度），所以可知B,C,D,E,,,M等12个点的位置

3、由于绕开障碍物只需要绕最多90度，所以最多只需要⾛3个点。

4、当对象⾛到O点，发现障碍物时，⾸先计算A点在直线NP的位置，如果A点在直线下⽅，则从上⾯绕；相反如果A点在直线上⽅，则从下

⾯绕

5、计算AO夹⾓如果⼩于AD⾓则⾛折线OD，其他以此类推

6、计算C点在直线DP的上⽅，则需要⾛折线DC

7、计算B点在直线CP的上⽅，则需要⾛折现CB

8、此时已经⾛了3个点了，可以直接⾛BP奔向⽬的地。如果不满3个点，则计算下⼀个点M在直线BP下⽅，则不需要⾛M了。

复杂度分析

1.当A已知时，由于包围圆的半径是固定值，所以B,,M点通过加减法就可以得到

2.接下来在计算⼀次AO夹⾓（两次浮点数乘法）

3.接下来最多计算3此点与直线的关系（每次是两次浮点数乘法）

五、总结

寻路的算法有很多，各⾃应⽤在不同的场景。通过筛选了⼗⼏种不同的寻路算法后，本⽂参考、采⽤或者部分采⽤了其中4，5种，也

将⼀些算法拆解只⽤其中⼀部分，然后还⾃创了⼀些寻路算法，⾃创部分是最⼤化的⽤空间换取时间，最终达到了后端的长距离⾏军粗路径

寻路CPU消耗很低的优化效果，不需要增加新的硬件就可以⽀持服务器端⼤规模寻路。