导航网格或 navmesh是一种用于虚拟环境中路线规划的数据结构，在游戏开发中特别有用。 它由一组代表地图区域的凸多边形组成，多边形的边用额外的连接信息进行了注释，显示了游戏角色可以穿越的区域。

正如你在下图中看到的，导航网格提供了世界上障碍物的简化表示，允许路线规划算法快速有效地计算出最佳路径。

我不会在这篇文章中过多地谈论导航网格背后的理论，网络上有很多很好的资源； 维基百科条目是一个很好的起点。 相反，我将专注于构建导航网格的技术。

我也不打算谈论在运行时更新网格以适应动态障碍，尽管这可能是未来另一篇文章的主题。

我将使用的网格是一个2.5 D网格，这意味着它是一组由斜坡连接的平面二维网格：

这也支持遵循地形高度场轮廓的导航网格：

对于这个项目，我选择使用经典的多边形导航网格而不是更高级的 Explicit Corridor Maps。 尽管 ECM 有很多优点，但我想将额外的场景属性，例如旅行成本（道路和小径的旅行成本低于草地或雪地，因此在规划路线时更受角色青睐）嵌入到网格中。 不幸的是，ECM 方法将世界严格划分为“障碍”和“非障碍”，而没有规定“半障碍”。 另一方面，对多边形区域执行此操作相对简单。

构建网格的过程主要包括对多边形的布尔运算。 幸运的是，有许多出色的开源库可用于执行此类操作。

推荐： 使用 NSDT场景设计器 快速搭建 3D场景。

1、使用的库

该构建器使用了来自 npm 的许多开源库，但有三个包对完成这项工作特别重要：

• polygon-clipping 是一个用于对多边形进行高效布尔运算的库——并集、交集、差集等等。
• rbush 是 R-Trees 的一个实现，可以在 2D 空间内快速搜索对象。
• polygon-partition是一种将复杂的多边形分解成更小的凸多边形的算法。 请注意，我不得不分叉该库以对算法进行轻微调整 —原始库未处理的边缘情况，请参阅此 GitHub 问题了解详细信息。

接下来我们需要谈谈数据结构是如何组织的。

2、导航网格的数据结构

导航网格由一个名为 NavigationMesh 的 TypeScript 类表示。 这在运行时保存导航网格的表示，并由路线规划器使用。

构建网格的代码在另一个名为 NavigationMeshBuilder 的类中。 这个类会遍历游戏世界中的所有对象——地形、可行走表面、障碍物等等——并更新网格几何体。 请注意， NavigationMeshBuilder 可以在 Node.js 和浏览器中运行，这对于导航网格的离线计算很重要。

NavigationMesh 本质上是 NavRegions 的集合，以 R-Tree 组织。 每个 NavRegion 代表网格内的一个多边形区域。

该区域本身由一个边链表组成，表示多边形的边。 按照计算几何中使用的标准术语，这些称为 HalfEdge，因为它们存储单个顶点以及指向下一个 HalfEdge的指针。

export interface HalfEdge {
  next: HalfEdge;
  region: NavRegion;
  origin: NavVertex;
  connections: HalfEdge[];
}
export interface NavRegion extends BBox {
  surface?: SurfaceType;
  edges: HalfEdge; // Pointer to first edge in the list
  plane: Plane;
}

使用链表的原因是这使我们可以轻松地从任何边开始遍历多边形的边。 这在路线规划中很重要，因为可以从任何方向进入一个区域。

HalfEdge包含一个 conections列表，它是属于接触该边的相邻区域的边列表。

HalfEdge 包含一个指向 NavVertex 的指针，它是一个带有一些附加字段的 three.js 的 Vector3，包括使用该顶点的所有 HalfEdges 的列表。 请注意，顶点是共享对象— 也就是说，在相同位置具有顶点的两个不同区域将指向相同的 NavVertex。

NavRegion 本身有指向边链表的指针，以及一个表面类型（由路线规划器使用）和一个 three.js 平面 Plane对象。 Plane 对象表示多边形的平面表面，用于快速测试点是在 NavRegion 表面上方还是下方。

你可能会注意到 NavRegion 类型扩展了 BBox，它是一个 2D 包围框。 BBox 类型来自 RBush 包，并且是插入到 R-Tree 中的对象所必需的。

NavigationMeshBuilder 在构造期间也使用区域，但数据布局略有不同。 这样做的主要原因是用于操作多边形的开源库被设计为使用 2D 坐标，而不是 3D，并且不断地在两种格式之间来回转换是一件痛苦的事情。 因此， BuilderRegion 由一个二维多边形和一个 Plane 对象组成。 将 2D 坐标转换为 3D 只需将点垂直投影到平面上即可。

interface BuilderRegion extends BBox {
  surface?: SurfaceType;
  vertices: Pair[];
  holes?: Pair[][];
  minHeight: number;
  maxHeight: number;
  plane: Plane;
}

Pair 由 polygon-clipping 库定义，由 [number, number] 形式的二元组组成。 你可能会注意到这个结构也有一个 holes 字段。 这样做的原因是，在构建过程中，生成的多边形将是复杂的形状，可能是凹的也可能是凸的，并且可能包含孔洞。 只有在施工的后期阶段，这些区域才会被分割成没有孔洞的凹多边形。

3、导航网格的构建步骤

构建导航网格的步骤如下：

• 将游戏世界中的所有可行走表面作为多边形添加到网格中。
• 从网格中减去所有障碍物。
• 将位于同一平面且具有相同表面类型的相邻区域合并在一起。
• 将区域分割成凸多边形。
• 计算区域之间的连接。
• 清理所有未使用的顶点。
• 序列化并写入输出。

3.1 添加可行走表面

究竟什么构成可行走的表面将取决于你的游戏。 在我的例子中，这是基于物理对撞机对象——任何角度小于 45 度的固体顶面。

在导航网格构建期间，区域存储在构建器的 RBush 中。 更新网格的过程包括对每个多边形表面执行以下步骤：

• 计算要添加的多边形的二维顶点。
• 计算这些顶点的 2D 边界框。
• 计算新区域的平面，这可以在给定可行走表面的任意三个不共线的顶点的情况下完成。
• 调用 rbush.search(box) 查找与新多边形重叠的任何区域。
• 对于找到的每个重叠区域：如果现有区域在不同的平面上，则不要修改它，直接跳过它；如果现有区域具有相同的表面类型，则将其从 RBush 中移除，并使新区域成为两个区域的联合体；如果现有区域具有不同的表面类型，则从旧区域中减去新区域，将其剪掉；如果这导致边界框发生变化，则从 RBush 中删除旧区域并使用新边界重新添加它。
• 现在，将新多边形作为区域添加到 RBush。

3.2 从网格中剔除障碍物

此步骤与上一步类似，但有几个重要区别：

• 我们在网格中减去（切割孔）而不是添加新区域。
• 障碍物被“膨胀”了一个边缘，以解释角色具有非零半径的事实。 这也称为“Minskowski 和”。
• 需要考虑障碍物的高度，以及角色的高度。 障碍物将从沿该区域的运动将被障碍物阻挡的任何区域中减去。

请注意，对于这种类型的导航网格，角色的半径和高度被“烘焙”到网格几何体中。 这意味着网格仅适用于大小大致相同的角色。

3.3 合并相似区域

在前两个步骤中，将创建许多小区域。 我们可以将这些区域中的许多区域合并在一起，只要它们相邻、具有相同的表面类型并且在同一平面中即可。 该方法与步骤 1 中所做的非常相似：在矩形搜索区域中查询 RBush 的区域，然后将匹配的区域合并在一起。

但是，你可能希望对区域可以增长的大小设置限制。 在我的实施中，我将区域保持得相对较小（适合 4 米 x 4 米的区域）。 这样做的主要原因是它可以更容易地在运行时向导航网格添加动态障碍物——添加或移除的每个障碍物只需要更新网格的一小部分，而不是必须更新可能延伸很长时间的巨大多边形 距离。

3.4 将区域分割成凸多边形

在前面的步骤中创建的许多区域将具有复杂的形状。 我们可以使用 poly-partition 包将它们分成更小的凸区域。 对于每个区域：

• 首先，通过调用 removeHoles() 移除所有孔。 这不会影响形状，它只是将孔与外边缘连接起来。
• 现在调用 convexPartition() 生成一个凸多边形列表。

在此阶段，我还通过将所有 2D 坐标转换为 3D 坐标，将 BuilderRegion 转换为 NavRegion。

3.5 计算区域之间的连接。

乍一看，这一步似乎很简单——对于一个区域的每条边，寻找一个在相同顶点之间有一条边但方向相反的区域。 事实上，如果你按照标准的计算几何教科书进行操作，那将是执行此操作的正常方法。

然而，有一个问题： polygon-clipping 库喜欢通过删除冗余的共线顶点来优化多边形。

假设你有一个T形区域：

根据多边形生成和合并的顺序，你最终可能会得到两个没有共享顶点的独立矩形——因为顶部矩形中的额外顶点将被优化掉。

这就是为什么 HalfEdge 对象具有 connections列表而不是单个边引用的原因。 该列表是通过从附近区域中搜索共线和重叠的边缘来构建的。 为了提高效率，我们可以创建第二个 RBush 在此阶段存储 HalfEdges。

请注意，这种表示会使我们的路线规划器变得更复杂，但不会太多—这只是意味着我们必须更聪明地对待我们认为的“连接”。

根据你的偏好，你可能还想删除小的“孤岛”区域——即不与任何其他区域相连的区域。 由于没有连接，角色无法到达这些区域。 但是，将它们留在其中都没有真正的危害。

3.6 清理未使用的顶点

处理完所有区域后，你可能会发现自己有任何区域不再使用的额外顶点。 可以使用简单的标记清除垃圾收集算法来摆脱这些。

这也是为每个顶点分配唯一数字索引的好地方，当我们想要序列化导航网格并将其写入下一步中的文件时将需要它。

3.7 写入文件

你需要为导航网格定义某种序列化格式。 顶点是最简单的部分：你可以获取所有 { x, y, z } 坐标并将它们合并到一个数组中。 然后通过该数组的索引引用顶点。

无需序列化 RBush，因为当你将网格加载到你的游戏引擎中时再次构建它会非常快。 相反，你可以将区域列表写成一个对象数组。 每个对象都包含顶点列表（作为整数）和连接列表——尽管你也可以省略后一部分并在加载时重新计算连接。

此时，你将拥有一个包含导航网格的 JSON 对象。 你可以把它写成一个字符串，或者使用像 msgpack 这样的二进制编码。

4、导航网格的可视化

当然，导航网格生成器是一段复杂的代码，一路上你会遇到错误。 我建议使用测试驱动开发——使用 Jest 或你最喜欢的测试运行器编写一些简单的单元测试，然后让构建器通过这些测试。

此外，查看以 3D 方式呈现的网格可能非常有帮助。 为此，你可以创建一个叠加助手——一个将网格渲染为你的世界顶部的半透明叠加层的类。 本文开头显示的屏幕截图是使用该帮助程序创建的。

原文链接：
http://www.bimant.com/blog/three-js-navmesh-tutorial/