导航系统的内部工作原理

When you want to intelligently move characters in your game (or agents as they are called in AI circles), you have to solve two problems: how to reason about the level to find the destination, then how to move there. These two problems are tightly coupled, but quite different in nature. The problem of reasoning about the level is more global and static, in that it takes into account the whole scene. Moving to the destination is more local and dynamic, it only considers the direction to move and how to prevent collisions with other moving agents.

可行走区域

导航系统需要自己的数据来表示游戏场景中的可行走区域。可行走区域定义了代理可在场景中站立和移动的位置。在 Unity 中，代理被描述为圆柱体。可行走区域是通过测试代理可站立的位置从场景中的几何体自动构建的。然后，这些位置连接到场景几何体之上覆盖的表面。该表面称为导航网格（简称 NavMesh）。

导航网格将该表面存储为凸多边形。凸多边形是一种有用的表示，因为我们知道多边形内的任意两点之间没有障碍物。除了多边形边界之外，我们还存储有关哪些多边形彼此相邻的信息。这使我们能够推断整个可行走区域。

寻路

要寻找场景中两个位置之间的路径，我们首先需要将起始位置和目标位置映射到各自最近的多边形。然后，我们从起始位置开始搜索，访问所有邻居，直到我们到达目标多边形。通过跟踪被访问的多边形，我们可以找出从起点到目标的多边形序列。一种寻路的常用算法是 A*（发音为“A star”），这也是 Unity 使用的算法。

跟随路径

描述从起点到目标多边形的路径的多边形序列称为“走廊”(corridor)。代理将始终朝着走廊的下一个可见拐角移动，直至到达目标。如果一个简单游戏只有一个代理在场景中移动，可一次性找出走廊的所有拐角，并推动角色沿着连接拐角的线段移动。

在多个代理同时移动的情况下，它们需要在避开彼此时偏离原始路径。试图使用由线段组成的路径来纠正这种偏差很快变得非常困难并且容易出错。

由于每一帧中的代理移动距离非常小，我们可以使用多边形的连接来修复走廊，以防我们需要稍微绕道而行。然后，我们快速找到下一个需要抵达的可见拐角。

躲避障碍物

转向逻辑将采用下一个拐角的位置并基于该位置计算出到达目标所需的方向和速度。使用所需的速度移动代理可能会导致与其他代理发生碰撞。

障碍躲避系统将选择新的速度，该速度可平衡“代理在所需方向上移动”和“防止未来与其他代理及导航网格边缘发生碰撞”这两个问题。Unity 采用倒数速度障碍物 (RVO) 来预测和防止碰撞。

移动代理

最后在转向和障碍躲避之后计算最终速度。在 Unity 中使用简单的动态模型来模拟代理，该模型还考虑了加速度以实现更自然和平滑的移动。

在此阶段，您可以将速度从模拟的代理提供给动画系统，从而使用根运动移动角色，或让导航系统处理该问题。

使用任一方法移动代理后，模拟代理位置将移动并约束到导航网格。最后这一小步对于实现强大的导航功能非常重要。

全局和局部

关于导航需要了解的最重要事项之一是全局和局部导航之间的区别。

全局导航用于在整个世界中寻找走廊。在整个世界中寻路是一项代价高昂的操作，需要相当多的处理能力和内存。

描述路径的多边形的线性列表是用于转向的灵活数据结构，并可在代理的位置移动时进行局部调整。局部导航试图确定如何有效移动到下一个拐角而不与其他代理或移动对象发生碰撞。

障碍物的两种情况

许多导航应用需要其他类型的障碍物而不仅仅是其他代理。这些障碍物可能是射击游戏中的常规板条箱和木桶，或者是车辆。可使用局部障碍躲避或全局寻路功能来应对障碍物。

当障碍物为移动状态时，最好使用局部障碍躲避功能进行处理。这样，代理可预测性地避开障碍物。当障碍物变为静止状态并可认为其阻挡了所有代理的路径时，障碍物应该影响全局导航，即导航网格。

更改导航网格称为“雕刻”(carving)。该过程将检测障碍物的哪些部分会接触导航网格并在导航网格中雕刻孔洞。此操作的计算成本十分高昂，因此这也是应该使用碰撞躲避功能来处理移动障碍物的另一个充分理由。

Local collision avoidance can be often used to steer around sparsely scattered obstacles too. Since the algorithm is local, it will only consider the next immediate collisions, and cannot steer around traps or handle cases where an obstacle blocks a path. These cases can be solved using carving.

Describing OffMesh Links

The connections between the NavMesh polygons are described using links inside the pathfinding system. Sometimes it is necessary to let the agent navigate across places which are not walkable, for example, jumping over a fence, or traversing through a closed door. These cases need to know the location of the action.

These actions can be annotated using OffMesh Links which tell the pathfinder that a route exists through the specified link. This link can be later accessed when following the path, and the special action can be executed.