Navigation System In Unity

时间仓促，大部分采用google机器翻译来不及全部校对翻译成中文资料 本篇作为笔记。感兴趣的可以看下。这篇是记录Unity3D寻路的官方文档阅读体验。

The Navigation System allows you to create characters which can navigate the game world. It gives your characters the ability to understand that they need to take stairs to reach second floor, or to jump to get over a ditch. The Unity NavMesh system consists of the following pieces:

Unity3d的寻路系统大概有下面几个部分：

NavMesh（导航网格的缩写）是描述游戏世界的步行表面的数据结构，并且允许从游戏世界中的一个步行位置到另一个步行路径找到路径。 数据结构是烘焙的网格里获取的。

NavMesh (short for Navigation Mesh) is a data structure which describes the walkable surfaces of the game world and allows to find path from one walkable location to another in the game world. The data structure is built, or baked, automatically from your level geometry.

NavMesh Agent组件帮助您创建角色，在向目标移动时避开彼此。Agent使用NavMesh理解游戏世界，他们知道如何避免彼此以及移动障碍物。
离网链接组件允许您合并无法使用可走行的曲面表示的导航快捷方式。 例如，跳过沟渠或栅栏，或者在走过它之前打开门，都可以被描述为“Off-mesh”链接。

NavMesh Agent component help you to create characters which avoid each other while moving towards their goal. Agents reason about the game world using the NavMesh and they know how to avoid each other as well as moving obstacles.
Off-Mesh Link component allows you to incorporate navigation shortcuts which cannot be represented using a walkable surface. For example, jumping over a ditch or a fence, or opening a door before walking through it, can be all described as Off-mesh links.

NavMesh障碍组件允许您描述Agent在航行世界时应避免的移动障碍。 物理系统控制的一个桶或一个箱子是一个障碍的好例子。 当障碍物移动时，障碍物尽力避开它，但是一旦障碍物变得静止，它将在导航网上挖一个洞，使得障碍物可以改变它们的路径来绕过障碍物，或者如果障碍物妨碍路径 方式，Agent可以找到不同的路线。

NavMesh Obstacle component allows you to describe moving obstacles the agents should avoid while navigating the world. A barrel or a crate controlled by the physics system is a good example of an obstacle. While the obstacle is moving the agents do their best to avoid it, but once the obstacle becomes stationary it will carve a hole in the navmesh so that the agents can change their paths to steer around it, or if the stationary obstacle is blocking the path way, the agents can find a different route.

Inner Workings of the Navigation System / Navigation的工作原理

当你想智能地移动你的游戏中的角色（或者在AI圈子中被称为Agent）时，你必须解决两个问题：如何推理关卡以找到目的地，然后如何移动到那里。 这两个问题紧密结合在一起，但性质却截然不同。 关于层次的推理问题更加全局化和静态化，因为它考虑了整个场景。 移动到目的地更具局部性和动态性，只考虑移动的方向，以及如何防止与其他移动Agent发生冲突。

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.

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

The navigation system needs its own data to represent the walkable areas in a game scene. The walkable areas define the places in the scene where the agent can stand and move. In Unity the agents are described as cylinders. The walkable area is built automatically from the geometry in the scene by testing the locations where the agent can stand. Then the locations are connected to a surface laying on top of the scene geometry. This surface is called the navigation mesh (NavMesh for short).

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

The NavMesh stores this surface as convex polygons. Convex polygons are a useful representation, since we know that there are no obstructions between any two points inside a polygon. In addition to the polygon boundaries, we store information about which polygons are neighbours to each other. This allows us to reason about the whole walkable area.

要查找场景中两个位置之间的路径，我们首先需要将起始位置和目标位置映射到最近的多边形。 然后我们从开始位置开始搜索，访问所有邻居，直到到达目的地多边形。 跟踪访问的多边形允许我们找到从开始到目的地的多边形序列。 寻找路径的常见算法是Unity *使用的A *（发音为“A star”）。

To find path between two locations in the scene, we first need to map the start and destination locations to their nearest polygons. Then we start searching from the start location, visiting all the neighbours until we reach the destination polygon. Tracing the visited polygons allows us to find the sequence of polygons which will lead from the start to the destination. A common algorithm to find the path is A* (pronounced “A star”), which is what Unity uses.

描述从开始到目的地多边形路径的多边形序列称为走廊。 Agent将通过总是转向走廊的下一个可见角落而到达目的地。 如果你有一个简单的游戏，只有一个Agent在场景中移动，那么一次性找到走廊的所有角落并使角色沿连接角的线段移动是很好的。

The sequence of polygons which describe the path from the start to the destination polygon is called a corridor. The agent will reach the destination by always steering towards the next visible corner of the corridor. If you have a simple game where only one agent moves in the scene, it is fine to find all the corners of the corridor in one swoop and animate the character to move along the line segments connecting the corners.

在处理同时移动的多个Agent时，他们需要在避开对方时偏离原来的路径。 尝试使用由线段组成的路径来纠正这种偏差变得非常困难且容易出错。

When dealing with multiple agents moving at the same time, they will need to deviate from the original path when avoiding each other. Trying to correct such deviations using a path consisting of line segments soon becomes very difficult and error prone.

由于每个框架内的Agent移动都很小，所以我们可以利用多边形的连通性来固定走廊，我们需要绕行。 然后我们很快找到下一个可见的角落转向。
Since the agent movement in each frame is quite small, we can use the connectivity of the polygons to fix up the corridor in case we need to take a little detour. Then we quickly find the next visible corner to steer towards.

Avoiding Obstacles / 规避障碍

转向逻辑取下一个角的位置，并根据这个数字找出到达目的地所需的方向和速度（或速度）。 使用所需的速度移动Agent可能会导致与其他Agent发生冲突。

The steering logic takes the position of the next corner and based on that figures out a desired direction and speed (or velocity) needed to reach the destination. Using the desired velocity to move the agent can lead to collision with other agents.

障碍规避选择新的速度，该速度在向期望的方向移动和防止将来与其他Agent和导航网格的边缘的碰撞之间平衡。 Unity使用交互的度障碍（RVO）来预测和防止碰撞。
Obstacle avoidance chooses a new velocity which balances between moving in the desired direction and preventing future collisions with other agents and edges of the navigation mesh. Unity is using reciprocal velocity obstacles (RVO) to predict and prevent collisions.

Moving the Agent / 移动Agent

最后在转向和避障后计算最终速度。 在Unity中，Agent使用简单的动态模型进行模拟，该模型还考虑了加速度，以便更自然，更流畅地移动。
Finally after steering and obstacle avoidance the final velocity is calculated. In Unity the agents are simulated using a simple dynamic model, which also takes into account acceleration to allow more natural and smooth movement.

在这个阶段，可以将模拟Agent的速度提供给Mecanim动画系统，以移动角色，或者让导航系统处理。
At this stage it is possible to feed the velocity from the simulated agent to the Mecanim animation system to move the character, or let the navigation system take care of that.

一旦使用任一方法移动Agent，模拟的Agent位置将被移动，并被限制在NavMesh内。 这最后一小步对于强大的导航非常重要。
Once the agent has been moved using either method, the simulated agent location is moved and constrained to NavMesh. This last small step is important for robust navigation.

Global and Local

关于导航最重要的事情之一是全局导航和本地导航之间的区别。

One of the most important things to understand about navigation is the difference between global and local navigation.

全局导航是用来查找全局各地的走廊。 在全局范围内寻找路径是一项代价高昂的操作，需要相当多的处理能力和内存。

Global navigation is used to find the corridor across the world. Finding a path across the world is a costly operation requiring quite a lot of processing power and memory.

描述路径的多边形的线性列表是用于转向的灵活的数据结构，并且可以随着Agent的位置移动而在本地调整。 本地(Local)导航试图找出如何有效地移动到下一个角落，而不会与其他Agent或移动对象发生冲突。

The linear list of polygons describing the path is a flexible data structure for steering, and it can be locally adjusted as the agent’s position moves. Local navigation tries to figure out how to efficiently move towards the next corner without colliding with other agents or moving objects.

Two Cases for Obstacles / 两个障碍案例

导航的许多应用需要其他类型的障碍，而不仅仅是其他Agent。 这些可能是射击游戏或车辆中常见的箱子和桶。 障碍物可以通过局部避障或全局寻路来处理。

Many applications of navigation require other types of obstacles rather than just other agents. These could be the usual crates and barrels in a shooter game, or vehicles. The obstacles can be handled using local obstacle avoidance or global pathfinding.

当障碍物移动时，最好使用避免局部障碍物来处理。 这样Agent可以预测性地避免障碍。 当障碍物静止时，可以考虑阻挡所有Agent人的路径，障碍物应该影响全局导航，即导航网格。

When an obstacle is moving, it is best handled using local obstacles avoidance. This way the agent can predictively avoid the obstacle. When the obstacle becomes stationary, and can be considered to block the path of all agents, the obstacles should affect the global navigation, that is, the navigation mesh.

改变NavMesh被称为雕刻(carving)。 该过程检测障碍物的哪些部分接触NavMesh并将孔雕刻到NavMesh中。 这在计算上是昂贵的操作，这又是另一个令人信服的原因，为什么移动障碍物应该使用避免碰撞来处理。

Changing the NavMesh is called carving. The process detects which parts of the obstacle touches the NavMesh and carves holes into the NavMesh. This is computationally expensive operation, which is yet another compelling reason, why moving obstacles should be handled using collision avoidance.

Describing Off-mesh Links / 关于Off-mesh（跨网格链接）

NavMesh多边形之间的连接使用路径查找系统内的链接进行描述。 有时需要让Agent人跨越不可行走的地方，例如跳过围栏或穿过关闭的门。 这些案件需要知道行动的地点。

The connections between the NavMesh polygons are described using links inside the pathfinding system. Sometimes it is necessary to let the agent to 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.

这些动作可以使用Off-Mesh链接进行注释，通过指定的链接告诉探路者路线存在。 这个链接可以在路径后面访问，并且可以执行特殊的动作。

These actions can be annotated using Off-Mesh 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.