欧阳鹏程

摘 要 在大型多人角色扮演类游戏的服务器世界中存在大量由AI控制的角色，这些角色需要在世界中进行位移寻路的计算。本文介绍了一种在经典寻路算法基础上，结合物理系统的寻路解决方案，并描述了在实际项目中的实现方式与效果验证。

关键词 寻路算法;动态寻路;导航网格;物理碰撞;碰撞算法

1静态寻路算法

1.1 算法简介

在大型多人角色扮演类游戏的服务器世界中，不但存在着大量由玩家扮演的角色，同时还存在着大量由AI控制的非玩家角色（简称：NPC）。这些NPC需要模拟真实的运动行为，在世界各处行走。

图1展示了在游戏中玩家和NPC分别在客户端和服务端中的显示方式。虽然游戏客户端使用3D图形技术来表现华丽的视觉效果，但是在服务端的逻辑世界中是基于二维空间进行计算的。

角色在二维空间中表示为一个有一定半径的圆，同时场景中存在大量不可行走的区域，比如墙、山、房子等。因此，当NPC角色在场景中移动时必须绕开这些区域。如何计算出一条能够绕开这些不可行走区域的路径，成为一个需要研究的算法。

由于这些不可行走区域不会变化，因此我们称这类算法为静态寻路算法。

1.2 生成导航网格

静态寻路算法首先需要对场景进行建模，将场景中的可行走区域边界计算出来。计算出来的可行走区域表达为一个n多边形。如图2所示，灰色区域为可行走区域N多边形。

然后将N多边形进行三角面剖分，这里可以采用经典的Delaunay三角面剖分算法。如图3所示，将可行走区域进行三角面剖分后的结果。

这些相连的三角形称为导航网格，NPC的寻路就依赖导航网格数据进行计算。

1.3 基于导航网格的寻路算法

导航网格中的三角形都是相互连接的，因此需要先建立三角形连接关系的数据，可以用图数据结构来表示三角形间的连接关系。如图4所示。

当NPC需要在导航网格中由A點移动到B点时。首先计算出起点A和终点B所在的三角形Ta和Tb。然后根据三角形之间的连通关系计算出起点三角形Ta和终点三角形Tb之间的最短三角形连接通路。最短路径的计算可以采用经典的A*算法。

获得最短连通三角形通路后，将所有三角形的中心点连接起来，就获得了一条在可行走区域中由起点A到终点B的可达路径。如图5所示。

由于这条路径经过各三角形的中心点，因此还不是最优路径。

1.4 路径优化

获得了连通三角形列表后，计算出连通三角形列表之间共享的边。角色最终的移动路径必然连续穿越所有共享边。

然后以起点A到终点B的方向为最优选择，依次计算路径在每条共享边上的最优点。再将这些点相连，就可以获得起点A到终点B的最优路径。如图6所示。

以上介绍了经典静态寻路算法的计算原理，但是在实际项目中会遇到如下几个问题：

场景中存在不断运动的需要避让的NPC。要求NPC之间相互阻挡，不能互相穿插。

静态寻路算法并没有考虑角色的大小。角色体积较大时，在墙角移动时会穿插到墙体内。

2动态碰撞寻路算法

2.1 物理碰撞模型

由于静态寻路算法，只考虑到场景中静止不动的物体。因此，需要寻找一种方法能够解决场景中不断运动且会相互阻挡的物体。

对于运动的阻挡物，无法事先对其进行静态分析与建模。因此考虑引入物理系统中的碰撞检测来解决动态阻挡物的寻路问题。

首先，对场景中所有角色创建二维空间中的物理碰撞模型，如图7所示。NPC角色可以使用圆来表示碰撞模型，墙体使用三角形来表示碰撞模型。

物理系统以每秒20帧的频率检测所有碰撞模型之间的碰撞检测，由于不存在高速运动的阻挡物，因此当两个物理碰撞体边缘相接触时就可以立刻检测到。

2.2 盘绕算法

当角色A和角色B相向而行时，在发生碰撞的那一帧，采用如下盘绕算法来处理动态角色间的穿插问题。

对角色A，假设当前行进方向初始角度为d=d0设置盘绕角度a，初始a=10;

（1）计算d的顺时针盘绕方向d1=d+a，计算d的逆时针盘绕方向d2=d-a;

（2）分别沿d1和d2方向进行移动预测，判断是否与角色B碰撞;

（3）如果d1方向可行，则使d=d1;如果d2方向可行，则使d=d2;如果d1和d2方向都不可行a+=10，跳转1;

（4）移动一帧，使d = d向初始方向d0偏移10;

（5）判断是否仍然与角色B发生碰撞。是，跳转1;否，退出盘绕状态，并重新计算静态路径。

图8展示了算法的流程图。

采用以上计算方法后，当角色在行进方向遇到阻挡物体时。会先小角度进行移动预判，判断对当前方向左右偏移是否可以移动;并不断循环放大尝试偏移角度，直到找到可以行走的角度。

图9显示了角色A在遇到角色B的阻挡后，使用盘绕算法的行进路径。可以看到角色A的行进路径不会和B发生穿插，成功绕过B角色。

给角色添加物理碰撞范围，并且每帧进行物理碰撞检测，能够及时检测到物理模型之间的碰撞和穿插。然后再针对两物理模型之间的碰撞接触点，进行盘绕算法，使角色的移动方向避开下一帧可能发生碰撞的方向[1]。

使用这样的算法，不但很好地解决了NPC角色这种动态对象的寻路问题，针对静态场景也能够有明显的优化效果。

静态寻路算法的路径并没有考虑到角色半径的问题，因此当角色沿路径移动到墙角处时会发生明显的穿插现象。结合了基于物理碰撞的盘绕算法后，角色在经过墙角时能够动态绕开墙体。图10左图显示了静态寻路算法的路径，有明显的穿插现象;右图显示结合了碰撞算法后，可以成功避开与墙体的穿插。

3动态物理寻路算法

3.1 对象穿插

对于相互没有穿插的对象，以上算法能够很好地解决对象之间在寻路移动过程中的相互穿插现象。但是在实际项目中，有时会出现两个对象已经穿插在一起的情况。

比如，一个可以自动开关的门，门打开时NPC站在门中间，然后门自动关上。这时NPC就会仍然站在门中间，NPC和门互相穿插。而且在这种情况下，NPC已经站在了一个不可移动的区域中，即使生成了寻路网格，NPC也会由于起点不在寻路网格的任何一个三角形中而无法找到一条可达路径。

因此针对这种情况，需要结合物理系统中的运动学部分来优化NPC的寻路系统。

3.2 排斥速度

优化方案希望能够将已经穿插的两个对象能够相互挤开，因此这里引入真实物理系统中的排斥力概念。

真实物理系统中的排斥力会根据两个物理对象穿插的距离计算排斥力大小，并且涉及复杂的力学计算，但是在寻路系统中这样的表现并不好。因此我们只使用排斥力的方向，在方向上设定一个固定的移动速度。

图11显示了两个圆形碰撞体穿插时，互相给对方施加一个反向的排斥移动速度。和三个圆形碰撞体穿插时相互施加排斥移动速度。

需要注意的是，在通常的2D物理引擎中（比如box2d），当一个碰撞体与三个及以上的碰撞体发生碰撞时，需要积分计算，而电脑只能通过多次循环计算碰撞点所产生的合力方向来模拟积分过程。这个计算过程非常消耗算力，并且合力计算结果的精确性依赖于循环次数[2]。当循环次数较少且碰撞体较多时，仍然会发生穿插现象。而且较大的计算量对于MMO类游戏的服务器也会造成非常大的性能压力。

因此在这里的寻路算法中简化了这种复杂情况的计算。当一个碰撞对象受到3个及以上的碰撞体碰撞时，在计算过程中以任意一个力的方向为x轴，建立笛卡尔坐标系统。只要在x、y轴上出现相反方向的力，则将此方向上的力归零。如图12所示，A受到3个方向的力，且3个力在x、y轴上的投影都存在相反的情况。因此就不对A物体施加排斥速度。

采用这种算法上的优化后，大量碰撞物体聚集在一起时，会使边缘的碰撞对象逐步被挤开;腾出空间后，中间的碰撞对象再逐步疏散开。这样就能在性能和表现上取得平衡。

在对物理系统中碰撞与运动学部分进行简化和调整后，也能够完美解决由于多碰撞点需要积分计算而导致的不精确性[3]。可以完美的避免角色被大量其他角色推挤时，可能被挤进墙里的现象。

图13显示了在实际项目中大量角色聚集在一起时的寻路位移情况。其中绿色圈为玩家角色，红色圈为NPC角色。可以看到虽然大量红色NPC角色聚集在一起并且相互紧贴，但并没有发生明显的穿插现象。而且也完全不会出现穿插到墙体中的情況。

4结束语

经典的静态寻路算法奠定了寻路算法的基础，但是针对游戏项目中复杂多变的环境和需求，并不能达到令人满意的效果。

因此本文阐述了在实际项目中经过实践摸索后，总结的一种适合大量动态物体的寻路算法，将物理系统中的碰撞系统与运动学部分进行简化与调整，再结合静态寻路算法，能够达到令人满意的表现效果。对于MMO类服务器计算压力较大的环境也能很好的适用。

随着技术的发展，用户对游戏品质要求的提高，未来对寻路算法的要求会越来越高。本文所阐述的是一种经过实际项目验证的方法，对于其他类型的项目也有较好的参考价值。

参考文献

[1] Mark DeLoura.游戏编程精粹1[M].北京：人民邮电出版社，2004： 271-275.

[2] Siu-Wing Cheng.Delaunay Mesh Generation[M]. Chapman and Hall/CRC 2012：26-27.

[3] 陈文登.Box 2D 物理游戏编程[M].北京：科学出版社，2015：50.