这篇文章，首先会介绍什么是导航网格，它在 3D 游戏中起到了什么样的作用。然后会介绍目前导航寻路最常用的第三方开源库
RecastNavigation。接下来，就是重点讲怎样利用 RecastNavigation 来生成导航网格，并且利用这些导航网格来进行寻路。最后，会讲到 RecastNavigation 的局限性。
什么是导航网格？
导航网格（Navigation Mesh），也俗称行走面，是一种用于在复杂空间中导航寻路、标记哪些地方可行走的多边形网格数据结构。很多时候，它会被用于承载更多的功能，比如标识该位置的地形、该位置角色应该采用什么动作（行走、游泳、攀爬）。
一个导航网格是由多个凸多边形（Convex Polygon, Poly Mesh）组成的。为了避免混淆，下文这种专属名词都会用英文单词代替。Poly Mesh 有些时候也会简称为 Poly，即上图中的一个个色块部分。注意，这里的 Poly 专门指的是导航网格的组成单位。在导航网格中的寻路是以 Poly 为单位的。在同个 Poly 中的两点，在忽略地形高度的情况下， 是可以直线到达的；如果两个点位于不同的 Poly，那么就会利用导航网格 + 寻路算法（比如A*算法）算出需要经过的 Poly，再算出具体路径。
在 Unity 中，有提供专门的工具集 NavMesh 用于寻路导航。但这套工具有个最大的问题就是算法、数据格式不开源，导致了游戏服务端是无法使用，无法和客户端保持一致的导航寻路逻辑。因此，在实际 MMORPG 开发中，一般会使用其他寻路方案。
RecastNavigation
目前游戏最常用的导航寻路开源库应该就是 RecastNavigation 了。坊间传说 Unity、Unreal 底层其实也是用的这个库。最初版的作者 Mikko Mononen 多年前曾经是 Crytek工作室 的 AI 工程师。大名鼎鼎的 CryEngine、孤岛惊魂 就都是 Crytek 工作室开发的。出了 RecastNavigation 之后，这哥们后来又被 Unity 招安了。
RecastNavigation 是一个的导航寻路工具集，它包括了几个子集：
- Recast：负责根据提供的模型生成导航网格。
- Detour：利用导航网格做寻路操作。这里的导航网格可以是 Recast 生成的，也可以是其他工具生成的。
- DetourCrowd：提供了群体寻路行为的功能。
- Recast Demo：一个很完善的 Demo，基本上将 Recast 、 Detour 提供的功能都很好地展现了出来。弄懂了这个 Demo 的功能，基本也就了解了 RecastNavigation 究竟可以干什么事。
接下来，会重点讲导航网格的生成和如何利用导航网格进行寻路。
导航网格的生成
导航网格的生成依赖于场景模型的设计，有手动生成，有自动生成，有两种方式相结合的方式。如果场景简单，那么可以由场景设计师在构造场景模型时，手动拉一个场景的导航网格。但对于大规模复杂的场景，一般会让设计师剔除大量不可能到达的建筑、装饰物，做出一个简化的逻辑面模型，再根据这个模型去自动化生成导航网格。
Recast 库就是专门用于自动化生成导航网格的。有一个文章系列 Study: Navigation Mesh Generation，图文并茂详细地介绍了 Recast 生成导航网格的过程，非常推荐阅读。我在这里就根据这个系列，简要地罗列一下导航网格生成的相关概念和流程。
导航网格的生成会分为下面几个步骤：
- 场景模型体素化（Voxelization），或者叫“栅格化”（Rasterization）。
- 过滤出可行走面（Walkable Suface）
- 生成 Region
- 生成 Contour（边缘）
- 生成 Poly Mesh
- 生成 Detailed Mesh
第一步，体素化。顾名思义，就是将整个场景模型，都转化为体素（voxel）。
这一步处理和 GPU 渲染管线的光栅化流程概念是一样的，都是将矢量的模型信息（三角形），转化为点阵信息（像素或者体素）。开个脑洞， 假设将来有个全息显示器，可以在一个空间内渲染出制定的模型内容，渲染的最基本单位是体素而不是像素。那么到时的“显卡”很可能就是采取类似的模型体素化过程。
第二步，根据哪些体素顶部有足够的空间可供行走，以及根据设置的参数，剔除过滤掉一些不符合要求的体素，初步计算出行走面。
第三步，生成 Region。根据计算出来的行走面，使用特定算法，将这些可行走面切分为一个个尽量大的、连续的、不重叠的、中间没有“洞”的“区域”，这个区域就叫 Region。由于不重叠，也就不再需要高度信息，因此在这一步就把问题从三维空间转换到了二维空间。这一步的算法，Recast 提供了三种算法：
- 分水岭算法（Watershed partitioning）：最经典、效果最好，但处理比较慢，一般用于离线处理。
- Monotone partioning：最快且可以保证生成的是不重叠、没有洞的 Region，但是生成的 Region 可能会又细又长，效果不好。
- [Layer partitoining][Layer partitoining]：速度、效果都介乎分水岭算法和 Monotone partioning 之间，比较依赖于初始数据。
Region 虽然是不重叠且没有洞的区域，但仍然有可能是凹多边形，无法保证 Region 内任意两点在二维平面可以直线到达。因此，接下来的步骤，就是为了将每个 Region 拆分为多个凸多边形。
第四步，生成 Contour。
在这一步中，根据体素化信息和 Region，首先构建出描绘 Region 的 Detailed Contours（精确轮廓）。由于 Detailed Contour 以体素为单位构建边缘的，因此是锯齿状的。
接着，再将 Detailed Contours 简化为 Simplified Contours（简化轮廓），方便后面的做三角形化（Triangulation）。在这一步之后，体素化数据就不再会被使用了。
第五步，生成 Polygon Mesh。
由于大多数算法处理需要基于凸多边形，因此这一步就是将 Simplified Contours 切分为多个凸多边形。凸多边形在代码中会简称为 Polygon 或 Poly。
在一个 Polygon 中，任意两个点在二维平面内都是可以直线到达的。因此，Polygon 是 Detour 的基本寻路单元。
第六步，就是把 Polygon 继续做三角形化，生成了 Detailed Mesh。
如果把场景的拓扑结构看成一个无向图，其中每个 Polygon 是一个顶点。那么 Polygon 只是在拓扑结构上解决了寻路问题，但是为了在具体寻路过程中，让角色更加贴合地面地行走，需要一些更精确的地形信息（比如高度）。因此还需要将 Polygon 拆分为更贴近地表形状的 Detailed Mesh。
至此，导航网格的生成就结束了，Poly Mesh 和 Detailed Mesh 是最终需要的数据，需要存盘。其他都是属于中间数据，是可以被释放掉的。在实际应用中，可能会保存某些中间数据（比如体素化数据），做其它的用途。
利用导航网格做寻路
有了 Poly Mesh 和 Detailed Mesh 之后，使用 Detour 寻路就变得很简单了。构建一个 dtNavMeshQuery 实例，既可支持在 Poly Mesh 颗粒度的寻路，返回结果是路径途径的 Poly 数组；也可以支持在 Detailed Mesh 寻路，返回的是一个坐标点数组形式的路径。
RecastNavigation 的局限性
在 RecastNavigation 中，一个用于寻路的单位称为 Agent（代理）。 作者 Mikko Mononen 曾经在 RecastNavigation 的 Google 讨论组中提到项目的一些设计前提：
- 假设 Agent 都是在地面行走且收到重力影响的。
- 假设 Agent 始终保持直立姿态的，即垂直于重力方向。
Agent 不能飞，甚至不能跳。即使“走”在一些斜坡上，也始终应该是直立姿态，而不能是垂直于地表（即地表法线方向）。有了这些设计前提，才可以更方便地简化体素化时的数据结构，简化 Walking Surface 的计算生成。
因此，现在国产武侠类 MMORPG 里大行其道的轻功、甚至御剑飞行，是无法只单纯依赖 RecastNavigation 的数据去实现的。特别是对于某些具有层次错落结构的地形，就非常容易出现掉到两片导航网格的夹缝里的情况。这类机制的实现需要其他场景数据的支持。
而像《塞尔达传说：旷野之息》的爬山、《忍者龙剑传》的踩墙这种机制，则会在生成导航网格的阶段就会遇到麻烦。因为设计前提2的存在，RecastNavigation 是无法对与地面夹角小于或等于90°的墙面生成导航网格的。因此需要从另外的机制、设计上去规避或处理。不过，貌似 Unity 2017 已经可以支持了在各种角度的墙面生成导航网格了：Ceiling and Wall Navigation in Unity3D。
RecastNavigation 的另外的一个局限性则是，对于开放地图并不友好。如果需要判断远距离的两个点是否互相可到达，则需要将这个范围内的所有导航网格加载完，才可计算出路径，才可以判断是否可达到。即，“计算A点是否可走到B点” 和 “计算从A点到B点的具体路径”，这两个问题是等价的。因此，当长距离寻路时，玩家如果中途取消，则后续路径的计算量就会被浪费。
基于这一点，下一篇我们就来聊聊《游戏的寻路导航2：开放地图的导航》。
