Unreal Engine 3 中改进NavigationMesh质量的尝试

文章目的

本文旨在分享本人项目在使用 Unreal Engine 3 的 NavigationMesh 时遇到的问题及解决方法，期望能为其他使用该系统的开发者提供参考，减少他们走弯路的可能性。此外，由于 Unreal 4 采用了一套类似的 NavigationMesh 生成方案，本文最终的解决方法在 Unreal 4 中同样适用。

NavigationMesh 简单介绍

NavigationMesh 本质上是对游戏内 AI 可运动空间的一种描述，它通过连通图来组织整个结构。如下图所示，分别为 Unreal Engine 中的地图俯视图和绿色的 NavMesh 俯视图。可以看到，场景被离散地划分成了许多连通区域，这些连通区域相互连接，形成了整个地图的空间 Graph 描述。

在运行时，AI 实体在运动过程中会通过 Graph 上的 Search 算法（如最常用的 Path Finding 算法 A*），找到各种满足约束条件的路径（即需要经过区域的邻接边列表）。随后，依据这些路径生成目标点（Path Smooth 过程），并驱动物理层使 AI 实体朝着目标点移动（Path Following 过程）。由此可见，NavMesh 是整个 AI 系统的基础，其质量直接决定了 AI 的所有行为是否稳定。

项目中遇到的问题及解决尝试

Unreal 自带的 NavMesh 生成结果

Unreal 自带了一套 NavMesh 生成算法 [①]，用于自动化构建 NavMesh。然而，生成的结果在很多地方未能根据碰撞情况清晰地描述 AI 的可行走区域，这导致寻路底层不够健壮，上层 AI 逻辑无法良好表现，AI 卡死在某些区域的情况十分常见。

阅读生成算法的尝试

为了改进 NavMesh 生成结果，我们尝试查找相关论文并阅读生成算法。但遇到的问题是，除了官方的一篇介绍外，几乎没有其他相关论文。虽然有一些论文提到了 Unreal 自带的 NavMesh Generator 存在的一系列问题 [②]，但在尝试修改时，我们遇到了诸多困难。底层代码量（class UnNavigationMesh）非常大，且软件工程架构不佳，存在各种魔数、超长函数，缺乏模块化和注释。我们花费了半个多月的时间进行运算流程可视化和代码阅读，但整体进度缓慢。经过程序组内协商，我们认为这样做的性价比极低，最终放弃了这一尝试。

早期，我们只能在 AI 上层加入检测异常卡死状态的逻辑，从结果端来规避问题。

建立 AI 关卡规范和算法参数调节

由于在算法方面无法进行修改，我们只能让地图结构适应算法结构，避免出现导致 NavMesh 生成问题的关卡结构。具体采用的方法如下：

• 调节生成参数：整体效果并不理想，因为参数调节依赖于对算法的深入理解，且参数之间存在内在耦合，调节难度较大。
• 建立 AI 关卡规范：并非所有玩家能玩的地图都适合 AI 行走，需要根据经验建立相应的规范。
• 增加碰撞层：在地图中增加只影响 NavMesh 生成的碰撞层，排除难以解决的区域，在游戏实际运行时不加载该层。这种方法部分解耦了关卡碰撞和 NavMesh 生成，使 NavMesh 具有一定的可定制性。
• 修改关卡物件碰撞：尝试修改 NavMesh 构建时出问题区域的关卡物件碰撞，以定位生成问题。

通过上述方法，我们能够解决（准确地说是规避）许多生成问题。但不难发现，这种基于经验的方法几乎每一步都需要程序和关卡双方的参与，效率较低。

下面展示了当时解决生成问题的一种方法。第一张图是错误的 NavMesh，可以看到楼梯拐角处不规整；第二张图是根据算法出错部分添加碰撞体积，改变 NavMesh 生成结果；第三张图是改进后的生成结果，可以看到楼梯接缝处不规整的生成结果变得平整了许多。

新 NavMesh 生成方法的引入（Recast）

在 Unreal 后期版本的更新中，原有的生成算法被抛弃，引入了一种新的 NavMesh 生成方法——一个名为 Recast [③] 的开源工程。与原来的 NavMesh 相比，Recast 具有更快的生成速度和更好的生成结果。

然而，即使采用了新的算法，由于其本身固有的缺陷，仍然存在不少问题。例如，如下图所示的屋顶结构无法正常生成 NavMesh。这实际上是因为 NavMesh 生成进入了碰撞的内部，导致通过 NavMesh 计算产生的路径点在碰撞内部，AI 永远无法到达，从而卡死。

在尝试解决 Recast 这些问题时，我们发现 Recast 只有通过代码注释生成的 Doxygen API 文档，没有算法与设计文档，无法直接解决问题。当时 Recast 的 GoogleGroup 也没有相关问题的讨论。从论文方面来看，Recast 是作者在测试了当时一些生成算法后确定的方法，在学术领域并没有对应的方法 [④]。后来，我们找到一个名为 critterAI 的研究 Recast 的开源项目，该项目列举了整个算法流程 [⑤]，并将这些缺陷一一列举出来 [⑥]，但有些是算法的固有缺陷，难以解决。我们也曾做过一些修改尝试 [⑦]，但 Recast 缺少文档的问题再次凸显，复杂的数据结构在短期内也难以改进。

更麻烦的是，UE 自带的生成算法对屋顶的处理结果与 Recast 各有优劣。

因此，当时针对 NavMesh 的策略是：

• 关卡规范约束：通过关卡规范约束关卡，并添加碰撞层局部修改生成结果。
• 开放参数并调节：在 UE 内开放 Recast 的所有参数，结合 critterAI 的文档快速调节参数。
• 程序介入检查：程序介入检查生成问题。

NavMesh 的编辑功能

这个功能我们很早就有想法，但一直没有找到很好的解决思路。直到最近，随着对整个引擎和 Navigation 系统的深入阅读和理解，我们才实现了这个流程。下面是具体的思考流程：

• 直接编辑尝试：最早我们尝试让 Editor 直接编辑 NavMesh，但发现 Unreal Editor 不能直接编辑 NavMesh（class UNavigationMeshBase），只能直接编辑 BSP（class UModel）、Terrain 等。如果直接在 Unreal 里添加新的编辑 NavMesh 的流程（EditorMode），工作量巨大。
• 转换格式尝试：接着我们尝试将 NavMesh 转换成其他编辑器可编辑的格式。但发现 Unreal 存在的函数只有 BSP->StaticMesh、StaticMesh->BSP、StaticMesh->NavMesh 这三个接口，缺少 NavMesh 直接转 BSP 的流程，也缺少 NavMesh 间接通过 StaticMesh 转换 BSP 的第四个接口。而且这些接口散布在代码的各个地方，有些还未被引擎引用，具体使用时还需要确保互相转换的正确性。
• 导入外部 NavMesh 方案：最终我们确定了导入外部 NavMesh 的方案。StaticMesh->NavMesh 直接接口实际上意味着让美术编辑 NavMesh 并导入。我们一方面简化了工作流，让关卡美术同学直接将 ASE 文件按规范命名放入地图文件夹即可导入；另一方面进行了导入后的数据加工，使导入的 NavMesh 可直接使用。
• 导出 NavMesh 方案：由于关卡同学反馈直接制作 NavMesh 耗时过长，我们编写了一个导出器（UExporter），将 Recast 生成的 NavMesh（UNavigationMeshBase）导出为最简单的 Obj 格式，导出信息包括顶点和面信息。这样可以让算法生成大致的结果，关卡同学只需修改出问题的部分。
• 标记问题区域：在编辑出问题的区域时，需要确定哪些区域存在问题。UE 的 Navigation 系统在运行时，Navigation 系统（Path Finding、Path Smoothing）和物理层（Path Following）共同决定了寻路结果，因此不能单独检测某一环来确定问题。我们结合 UE 自带的游戏内信息统计系统，编写了高逻辑帧率的测试关卡，快速标记问题区域。

下面展示了从检测出问题区域（红色 X）、导出（Obj 文件）、编辑（3Dmax）再导入（ASE 文件）的整个流程。

另外，现阶段项目的关卡同学仍在寻找时间改进我们地图的 NavMesh，后续测试遇到的问题和解决方案将不断补充。不过在实施这个方案之前，我们在 3dmax 内编辑的 Mesh 导入并驱动 AI 运动进行了测试，结果显示没有问题，因此我们认为后续问题应该不会太多。

现阶段的方案

目前，我们采用的方案是：Recast 的 NavMesh 生成系统 + 快速迭代编辑的 NavMesh = 质量更好的 Navigation 底层。

总结

回顾整个过程，我们发现解决方案本身并不复杂，但找到合适的解决途径却耗费了大量时间。我从接触 AI 系统到现在断断续续快一年了，最近才找到较好的方法。主要原因有以下几点：一是 NavMesh 生成领域尝试了多种算法（如 UE、Recast 等），但学术界的方法未在 UE 中采用，工业界的这些算法又缺乏相关文档，难以改进；二是 Unreal Navigation 相关代码繁杂细碎，主干之外有大量代码，且缺少底层设计文档，软件工程架构不如 Rendering、Object、Collision 等其他模块清晰；三是需要对 Editor、Navigation、Collision 等模块有更深入的认知才能进行修改，我经过近一年对更多模块的阅读和接触才找到修改途径。

[①] Unreal Developer Network, “Navigation mesh reference”, http://udn.epicgames.com/Three/NavigationMeshReference.html [②] ANAVMG: AUTOMATIC GENERATION OF SUBOPTIMAL NAVMESHES FOR 3D VIRTUAL ENVIRONMENTS [③] https://github.com/memononen/recastnavigation [④] Navigation Meshes and Real-Time Dynamic Planning for Virtual Worlds [⑤] http://critterai.org/projects/nmgen_study/ [⑥] http://critterai.org/projects/nmgen_study/issues.html [⑦] https://udn.unrealengine.com/questions/184825/why-not-use-detailmesh-of-recast-for-navigationmes.html 来源：腾讯网