虚幻引擎3中的NavMesh寻路介绍

发表于2015-12-25

寻路是游戏AI的一个基础组成部分。基本目标是给定一个起始点和目标点，生成一条个体可以到达的路径。目前通常有这么几类常用的寻路方法：基于路点（PathNode），基于导航网格（Navigation Mesh，简称NavMesh），基于势力场（Potential Field）。目前游戏使用NavMesh寻路居多。本文主要介绍虚幻引擎3（UDK）中NavMesh相关实现。

NavMesh的原理大致是：将场景可行走部分剖分成若干相邻凸多边形，这些多边形将场景表示成了图状结构。图的节点表示开放区域，在区域内部任意点都可以直线可达。连接节点的边表示两个联通区域直接可达。一般来说区域都是双向联通的，然而也有某些特殊的区域是单向联通的，比如可以跳下却无法爬上的坡。在这个图状结构上可以使用各种图搜索算法去寻找联通路径。NavMesh其实并不能确保找到绝对最短路径，然而它有诸多的优点。相比路点的方法，NavMesh寻路可以避免产生Z字折线路径，可以很好的支持动态障碍物，并可以确保达到场景中存在NavMesh的任意区域。

虚幻引擎3中的NavMesh寻路介绍

使用NavMesh进行寻路需要解决两个问题：一部分是如何生成NavMesh，另外一个是如何使用NavMesh寻路。我们首先看一下UDK中的NavMesh生成算法。UDK中的大部分Navmesh是离线生成的，其使用的算法经历了两个阶段。最初使用了一套自己研发的NavMesh生成算法，大致思想是先把Mesh先splitting，然后再进行Merge，具体算法流程见【1】。然而这套算法存在某些明显的缺陷，尤其是在斜坡的区域，经常出现浮空和畸形。在2012年2月的版本之后，UDK合入了Recast中间件【2】替换了原来的算法，显著提高了NavMesh生成的质量。在最新的虚幻4引擎里，NavMesh生成也同样使用的是Recast，可以看出Recast的可靠及稳定性。Recast算法原理比较复杂，这里有一个详细的介绍【3】，感兴趣可以研究下。UDK里面除了调用Recast生成NavMesh之外，还对NavMesh做了一些补充：1、使用摆放在地图中的PathObject对NavMesh做补充和修改，例如可以添加自定义的Jump Link让AI可以在某些地图跳上去。2、生成Obstacle Mesh。ObstacleMesh有点类似Collision Mesh，不过比较粗糙，主要用在寻路检测，比如判断一个目标是否直接可达，直接对ObstacleMesh进行射线检测就可以得到结果，可以直接略过寻路计算【4】。3、生成场景的高低层的DropDown Edge，这些DropDown Edge让AI寻路能考虑寻路过程中跳下的可能性，让AI在这些场景中看起来不那么蠢。然而这个特性似乎有蛮多bug的，我修复了相关问题并梳理了一遍流程，有兴趣可以看下我的下篇文章。

虚幻引擎3中的NavMesh寻路介绍
PathObject示例

虚幻引擎3中的NavMesh寻路介绍

Obstacle Mesh示例（红色的边）

虚幻引擎3中的NavMesh寻路介绍

Drop Down Edge示例（浅蓝色的箭头）

除了离线NavMesh生成之外，在某些情况NavMesh是需要运行时生成的，比如场景中动态出现了一个障碍物阻挡AI寻路。UDK里面提供了NavMeshObstacle来解决这个问题【5】，原理大致是使用NavMeshObstacle的边界动态对NavMesh进行Splitting，如下图所示。
虚幻引擎3中的NavMesh寻路介绍
NavMesh Obstacle

使用NavMesh寻路是游戏中动态完成的。相比虚幻4则直接采用了Recast自带的Detour解决方案【2】，UDK中这套算法是自己实现的，是一个很好的学习例子。使用NavMesh寻路主要有两个步骤，一个是生成联通多边形链表，一个是从列表中找到最优路径，如下图所示，首先需要找到褐色的联通多边形，然后找到虚线所示的最优路径。

虚幻引擎3中的NavMesh寻路介绍

生成联通多边形是一个典型的图搜索问题，一般使用的是A*算法【6】。学术界还提出了许多对A*进行优化的算法，比如可以D*减少物体移动过程中路径的重复计算，HPA*优化多个个体同时寻路的开销。UDK里面用的是最简单的A*，精简伪代码大致如下：

虚幻引擎3中的NavMesh寻路介绍

UDK里面对算法中的搜索截止条件和添加邻边这两个步骤进行了模块化，并提供了NavMeshConstraint和GoalEvalutor自定义这两个步骤丰富AI的表现【7】。例如，修改NavMeshConstraint可以让AI有意地避开某些物体，修改GoalEvalutor可以搜索指定点一定距离外的一个多边形，可以让AI进行游荡、逃避等特殊的寻路操作。

生成联通多边形之后，另外一个问题就是从联通中找到最优路径。解决这个问题一般采用的是Funnel Algorithm【8】。Funnel中文里是漏斗的意思，这个词比较形象的概括了这个算法。首先把漏斗的出口设置为起始点（图A）。对于要穿过的每条边，依次不断缩小开口张角（图B-E）。如果张角闭合了，那么找到当前边的拐点，并重新设置为漏斗的起始点（图F-G）。
虚幻引擎3中的NavMesh寻路介绍

事实上UDK用的并不是Funnel算法，而是一个比较冷门的StringPull算法，模拟拉绳子的过程寻找最优路径，对穿越的每条边都去寻找一下最近的点。个人感觉这个算法其实复杂度更高一些。求生之路里面还提出一种Reactive Path Following的策略，也非常值得参考。原理是每次只进行部分的路径计算，优势在于节省计算开销同时让AI表现更自然【9】。

在确定路径之后，接下来要做的就是让AI不断运动到所找到路径中的下一个中间点。然而这也并非一件容易的事情。对于一些特殊的边，AI需要进行一些操作才可以到达下一个区域，比如需要爬墙、跳跃等。还有种种因素经常会影响到AI不能到达目标点，比如多个AI之间一般都存在flocking群体行为来保证个体不发生重合，这里面会不断对AI的运动速度进行修正。另外，AI在快要到达目标时一般推荐的是进行减速操作以便能够比较准确地到达目标，然而UDK里面也并没有这么做。这些因素都经常导致AI偏离需要重新计算路径。

接下来我们看一下虚幻脚本里面使用NavMesh寻路的一般步骤：
虚幻引擎3中的NavMesh寻路介绍

最后谈谈UE3寻路的一些坑：
1. 半径较大的物体在拐角会卡住，大致看了一下。原因是引擎只在NavMesh生成的时候考虑PathWidth，而寻路过程中其实没有进行相应处理。

2.如果自己或目标一不小心在NavMesh之外，那么寻路会直接失败，必须要特殊处理。另外计算路径的函数容错性不高，经常发生寻路失败。