一、两个问题

在Unity中，想要完成自动寻路，需要以下解决两个问题。

1.如何根据当前的level，找到目的地（how to reason about the level to find the destination）

2.如何到达该目的地（how to move there）

第一个问题是全局（globally）,静态的，需要计算整个Scene；

第二个问题是局部（locally）,动态的，需要实时考虑当前agent的移动方向与如何避免和其他agents发生碰撞，从而从出发点到达目的地

二、四个组成

Unity的Navigation System由以下四个内容组成，NavMesh, NavMesh Agent, NavMesh Obstacle, Off-Mesh Link

下面依次介绍这四个组成

1.NavMesh:NavMesh是一个数据结构，其中存储了若干凸多边形（Convex Ploygon）与各个多边形之间的相邻关系。用来表示一个Walkable Surface（表示对象的中心可以walk的地区）

2.NavMesh Agent:NavMeshAgent是一个Component,用来避开动态障碍和其他Agent

3.NavMesh Obstacle：是一个Component，用来描述可移动的障碍

4.Off-Mesh Link：是一个Component，用来描述无法再Walkable Surface中表示的捷径（传送点），如开门，跳过fence或ditch

三、寻路步骤

//问题一

将场景光栅化成体素（Voxel）->从中提取出walkable surface ->创建NavMesh（Bake NavMesh）

//问题二

->将start/dest position分别映射到对应的Polygon->利用A*算法，从start polygon开始搜索知道dest polygon，并获得一连串polygons，即corridor（a sequence polygons called corridor）->然后沿着走廊（corridor）的角落走到dest，同时避开其他agents和moving obstacle

PS:steering logic取决于dest方位与desired speed，如果按照原来的speed会与其他agent或者moving obstacle发生碰撞，那么会改变speed

四、实现Navigation与个组成的参数设置

1.Build NavMesh（Bake）：

①打开Window->Navigation

②选择所有需要被标记为Navigation Static的对象（Collect all Game Object as marked as Navigation Static，即地形）

③check on Navigation Static

④调整Bake设置

⑤Bake

                         （图一）                                                         （图二）

属性设置：

图一属性

Navigation Static:标记选择的对象为Navigation Static

Generate OffMeshLink：自动生成OffMeshLink

PS:如果创建的Link与预期的有所出入，那么可以适当加大Distance和Height

Navigation Area：选择生成Mesh的Area Type（下面讲解）

图二属性：

前四个用来表示walkable surface的范围（属性的含义就按照字面意思理解就可）

Drop Height和Jump Distance：用来决定自动生成OffMeshLink的条件，当高低小于Drop Height或者跨度小于Jump Distance时，会自动生成OffMeshLink

Manual Voxel Size(手动改变体素尺寸):默认情况下，Unity自动设置体素尺寸，保持每一个agent radius与三个体素对应。可以将这个属性视为Mesh的精准度，当体素越小，那么Mesh就越精准，也就越耗时。一般情况下，无需修改这个属性，有两种情况例外，请自行查看手册。

Min Region Area:规定最小的walkable surface Region area，如果某一Region的面积小值，那么会被剔除（视为non-walkable）.如果某一Region处于多块tile的交界处，即使它的面积小于此规定值，那么它也不会被剔除。因为Bake是按tile并行计算的，剔除是在计算时进行的，所以计算时只知道此region在某块tile的面积小于area无法确定所有tile上的面积和小于最小值，所以无法剔除。

Height Mesh:为了准确地放置角色。因为NavMesh是Walkable surface的近似平面，因此可能会将部分地表特色平整化。如一阶一阶的楼梯，可能在NavMesh中就用一个平滑的斜坡表示。这样如果某个对象上台阶就好像是飘上去得（没有准确地放在台阶上），缺乏真实感。如果开启Height Mesh，那么角色会沿着台阶一级一级上去。

2.Create NavMesh Agent

                      （图三）                                                      （图四）

Agent Size属性：

因为Agent由一个直立的圆柱体来表示，所依前两个属性用来描述此圆柱体的尺寸。

第三个属性（Base Offset）用来表示这个圆柱体底边中心与这个对象中心的偏差，来决定圆柱体上下的平移。

Steering属性：

前三个分别是，速度，角速度和加速度

Stopping Distance:表示距目的地多远时停下来

Auto Braking:表示会不会在接近目的地时，自动刹车（减速） PS：如果在实现巡逻效果时，要关闭自动刹车功能。

Obstacle Avoidance属性：

Quality：表示障碍躲避的品质，如果场景中有多个agent，那么可以适当使用低品质的躲避来保证效率。如果使用None，那么不会进行障碍躲避，就按照普通碰撞来处理。

Priority：表示优先级，如果优先级高（数值小）的话，那么表明此agent身份高贵，别的agent会尽力避免障碍它。

Path Finding属性:

Auto Traverse Off Mesh Link:表示是否开启自动通过OffMeshLink，如果开启的话，那么使用默认的方式完成转移（飘过去），如果关闭的话，那么需要动画系统提供一个转移动画，否则不会发生转移。

Auto Repath：当到达死胡同时，会不会重新寻路。如果无法到达目的地，那么会到一个离目的地最近的位置。

Area Mask：可以行走的Area Type

3.Create Navmesh Obstacle（可选）

                       （图五）

Nav Mesh Obstacle用来表示可移动障碍

Shape:表示障碍的形状，有Box和Capsule。每种Shape对应尺寸设置的参数。

Carve的含义：在NavMesh上刻出一块区域（Hole）

当Carve属性关闭时，表示这个障碍物不会Carve NavMesh，那么这个Obstacle就被单纯地视为Obstacle，类似于Collider。所以agent可能会无法找到正确的path，因为path被Obstacle阻塞，但是agent认为此路可通。通常用于一直在移动的对象，如Vehicle和Character。

当Carve属性开启时，表示这个Obstacle可能会Carve NavMesh。

　　当移动距离超过Move Threshold时，视为已移动；当静止时间超过Time To Stationary时，视为静止。

　　当Carve Only Stationary关闭时，那么无论当此Obstacle运动或静止时，其都会Carve NavMesh。所以会在运动过程中和静止时，更新NavMesh。通常用于大型，慢速的障碍物如，tank（对于步兵来说是运动中的障碍物）

　　当Carve Only Stationary开启时，那么当此Obstacle移动时，Carve Hole会被remove。Agent会使用collision Avoidance来避开它，但是不会绕着它安排路径。（While the obstacle is moving, the agents will avoid it using the collision avoidance, but will not plan paths around it.）当此Obstace静止时，会Carving被再次更新。此模式通常是最合适的选择，特别是当障碍被物理引擎控制的时候。

4.Create Off-Mesh Link（可选）

                       （图六）

此Component可以赋给任意对象，并使用两个对象表示传输点

Start End表示两个传送点

Cost Override：如果为负值，那么使用Area Type的Cost；如果为正值，那么使用此Cost

Bi Directional：开启为双向传输，关闭只能从Start到End

Activated：开启关闭Link

Auto Update Position：开启时，当传输点移动时，Link也会随之移动；关闭时，当传输点移动时，Link保持不变

Navigation Area：标记Area Type

PS：当Link存在时，但是角色无法通过次Link，有以下两个原因：1）角色的Mesh Mask屏蔽了此Link的Area Type 2）Link端点之间没有连接好，可能某个端点太高或太低，在图中可以看到端点上没有圆圈，Link箭头fade

五、Navigation Area Type 和 Cost 和 Area Mask

每个Area有个与之对应的Type和Cost值

Cost值可以看作，在此Area上进行的困难程度。

当寻路时，如果有存在条路径，那么会选择总开销最小的那条路径。

总开销 = Σdistance * cost （每小段路径的距离乘上cost值之和）

                               （图七）

可以在图七所示面板设置全局的Area Cost，也可以在Script中设置不同Agent的不同Cost值。Area Mask也可在全局设置或在Script中设置。

PS：Cost值的设定其实很难影响到结果路径的选择，特别是当路径很长时。Cost值可以视为Hint，例如如果不太希望角色经常使用OffMeshLink那么可以加大Link的Cost值。

注：不同场景之间的NavMesh可以用Link来连接，具体查阅官方手册

六、具体寻路实现

1.移动到指定目的地：在script中设置agent的dest属性为目的地的position

2.移动到鼠标点击的位置：当鼠标点击时，利用Raycast获取鼠标在屏幕上的二维点对应的3D坐标

3.多点巡逻：关闭刹车，if(remainingDistance<0.5f){gotoNextPoint();}

Unity Manual —— Navigation and Pathfinding