Unreal Engine 3 中改进NavigationMesh质量的尝试
这篇文章的目的
主要想写一下自己的项目在使用Unreal Engine 3的NavigationMesh中遇到的问题和解决方法，希望其他用到这个系统的人少走些弯路。另外由于Unreal 4用的是一套NavigationMesh生成方案，最终的解决方法其实Unreal 4也是适用的。
NavigationMesh简单介绍
本质上是对游戏内AI可运动空间的描述，通过连通图组织整个结构。如下图所示分别为Unreal Engine中的地图俯视图和绿色的NavMesh俯视图，可以看到场景被离散划分成了很多连通区域，连通区域连接在一起形成整个地图的空间Graph描述。
运行时，AI实体运动过程中通过Graph上的Search算法（Path Finding,最常用的A*），找到各种满足约束的路径（需要经过区域的邻接边列表），其后依据路径生成目标点（Path Smooth过程），驱动物理层让AI实体走向实体目标点(Path Following过程)。由此，NavMesh其实是整个AI系统的基础，NavMesh的质量直接决定了AI的一切行为是否稳定。
项目中遇到问题以及解决尝试
Unreal自带的NavMesh生成结果
Unreal自带有一套NavMesh生成算法[①]，用于自动化NavMesh构建。但是生成的结果有很多地方并没有按照碰撞清晰的描述AI的可行走区域，造成的结果寻路底层的不健壮，导致上层AI逻辑无法很好表现，AI卡死在某些区域很常见。如下图所示
阅读生成算法的尝试
尝试去找论文和阅读生成算法，做出改进。遇到的问题是没有相关论文只有官方一篇介绍，也有一些论文中提到Unreal自带的NavMesh Generator的一系列问题[②]。但是在尝试修改时遇到不少问题，底层代码量（class UnNavigationMesh）非常大但是软件工程架构并不好，各种魔数、超长函数缺乏模块化、缺少注释。用了半个多月时间做运算流程可视化和阅读代码，但是整体进度缓慢，程序组内大家协商后感觉性价比非常低放弃。
最终，早期只能在AI上层加入检测异常卡死状态的逻辑，从结果端去规避问题。
建立AI关卡规范和算法参数调节
后来，因为在算法方面无法做出修改，只能让地图结构适应算法结构，避免造成NavMesh生成问题的关卡结构。下面是采用的方法：
调节生成参数，不过整体效果并不好，因为参数调节依赖于对算法深入理解。而且由于参数间有内在的耦合，并不好调节。
根据经验建立AI关卡规范，并不是所有玩家能玩的地图都适合AI行走。
在地图增加只影响NavMesh生成的碰撞层，排除掉难以解决区域，在游戏实际运行时不加载这个层。这个方法部分解耦了关卡碰撞和NavMesh生成，一定的NavMesh可定制性。
修改NavMesh构建时出问题区域的关卡物件碰撞，尝试去定位生成问题。
有了上面的方法，能解决，准确说是规避掉了很多生成问题。但是不难发现，这种基于经验的方法基本每一步都需要程序和关卡双方的参与，效率可想而知。
下面所示是当时解决生成问题的方法中的一种。第一张图是错误的NavMesh，可以看到楼梯拐角处不规整的样子，第二张图是根据算法出错部分添加碰撞体积，改变NavMesh生成结果，第三张图是改进之后的生成结果，可以看到楼梯接缝处不规整的生成结果平整了许多。
新NavMesh生成方法的引入（Recast）
Unreal后期版本的更新中，抛弃了原有的生成算法，引入了新的NavMesh生成方法，一个叫Recast[③]的开源工程。Recast相对于原来的NavMesh，有了更快的生成速度和更好的生成结果。
下图所示第一个是Unreal自带生成算法导致的，第二个是Recast的生成结果。
但是即使用了新的算法，由于新的算法本身固有的缺陷，还是有不少的问题。如下图所示的屋顶结构不能正常生成NavMesh。这个实际上是NavMesh生成进入了碰撞的内部，这样造成的结果是通过NavMesh计算产生的路径点在碰撞内部，AI永远不可能到达而卡死。
在尝试解决Recast这些问题的时候，由于Recast只有Doxygen通过代码注释生成API文档，没有算法与设计文档无法直面解决，当时Recast的GoogleGroup也没有相关问题。论文方面Recast是作者测试了当时一些生成算法之后自己确定的方法，在学术领域并没有对应方法[④]。后来找到一个名为critterAI的研究Recast的开源项目，整个算法流程被列举出来了[⑤]，这些缺陷在这个研究Recast的项目中被一一列举出来[⑥]，但是无奈有些是算法固有缺陷。当时也做过一些修改尝试[⑦]，但是Recast缺少文档的问题再次暴露出来，复杂的数据结构短期内也改进不了。
更折腾的事情是，下图是UE自带的生成算法对屋顶的处理结果。有些地方Recast好过UE自带算法，有些地方UE自带算法好过Recast。。。
因此，当时针对NavMesh的策略是：
关卡规范约束关卡，添加碰撞层局部修改生成结果
在UE内开放出来Recast的所有参数，结合critterAI的文档快速调节参数
程序介入检查生成问题
下图所示是当时把Recast能开放的参数全部开放了
NavMesh的编辑功能
这个功能很早就想到了，但是一直没有太好的解决思路，直到最近对整个引擎和Navigation系统阅读和理解更深入了，才实现了这个流程。下面是思考流程：
最早尝试去让Editor直接编辑NavMesh。最后发现，Unreal Editor不能直接编辑NavMesh（class UNavigationMeshBase），只能直接编辑BSP（class UModel）、Terrain这些，如果直接在Unreal里新添加编辑NavMesh的流程（EditorMode）是很大的工作量。
其次尝试转换成其他编辑器可编辑格式。发现，Unreal存在的函数只有BSP->StaticMesh、StaticMesh->BSP、StaticMesh->NavMesh这三个接口，缺少NavMesh直接转BSP的流程，也缺少NavMesh间接通过StaticMesh转换BSP的第四个接口。再者这些接口散布在代码各个地方、有些还没有被引擎引用，具体用起来还要确保互相转换正确性没问题。
确定导入外部NavMesh方案。StaticMesh->NavMesh直接接口实际上的意思是让美术编辑NavMesh并导入了，我这边一方面简化了工作流，让关卡美术同学直接把ASE文件按规范命名放入地图文件夹即可导入，另一方面做了导入后的数据加工，导入即可直接使用。
确定导出NavMesh方案。关卡同学反应，直接制作NavMesh还是太耗时，就写了个导出器（UExporter）把Recast的生成NavMesh（UNavigationMeshBase）导出，导出格式方面选择了最简单的Obj，导出信息包括顶点和面信息。这样让算法生成大致的结果，关卡同学只用修改出问题的部分。
标记NavMesh问题区域标记。上一步提到的编辑出问题区域，下一个问题就是确定哪个区域出问题。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 VIRTUALENVIRONMENTS
[③]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