Unreal Engine 3导航网格寻路算法概述
目录：
1， 导航网格寻路 —— 导航寻路和传统路点寻路比较
2， 导航网格寻路 —— 寻路方法
3， 导航网格寻路 —— 生成导航网格需要的几何知识
4， 导航网格寻路 —— 生成导航网格
5， 导航网格寻路 —— 生成网格的一些补充
6， 导航网格寻路 —— A*寻路实现细节
7， 导航网格寻路 —— 一些优化
1，导航网格寻路 -- 介绍
传统路点寻路截图
下图是一个寻路路点的截图
导航网格寻路截图
下图是一个导航网格截图
路点寻路和导航网格的比较，具有的不足之处：
1. 一些复杂的游戏地图需要的路点数量过于庞大，比如柱角拐弯较多的地方，这样将会大大降低寻路算法的效率。而导航网格多边形数量对于同样的地形则能保持比较少的数量水平。
路点所需要路点数：
导航网格所需要的多边形数：
显然，导航网格需要的多边形数大大降低。
2. 路点寻路即使在直线线路上没有阻挡，有时也会使角色走折线路径。而导航路径寻路，则可以保证直线行走。
如下图A点和B点之间的路径
路点寻路如下图（产生了”Z”字型寻路路径）
导航网格寻路如下图（产生了直线寻路路径）
3. 路点寻路路径在拐弯处不能进行路径平滑，而导航网格则可以通过曲线来平滑路径，只要保证该曲线在导航网格内即可。
如下所示，红线是路径寻路的路线，蓝线是导航网格通过曲线平滑的路线。
4. 路点寻路数据不包含任何地形外的物体数据，所以路点寻路系统在处理动态阻挡的时候去修改路径是很困难的。而导航网格包含地形信息，能够知道网格内哪些区域有动态阻挡物体，通过射线投射能够方便地动态修改行走路线。
路点寻路在遇到动态阻挡的情况
导航网格遇到动态阻挡的情况，能够在导航网格内找到可通行的一条折线路径。
5. 路径点寻路不能根据不同的寻路角色来改变路径（例如不同角色有不同的包围盒），而导航网格则可以处理这种情况。
下图是寻路路点在拐角处的情形，该路径能够保证一个人顺利拐弯，但对于一辆坦克却无能为力，因为坦克的包围盒半径通过该路点时要撞上阻挡物。
下图是导航网格的情况，这时人和坦克能够根据包围盒信息，通过导航网格计算出两条符合对应角色的路径。
6. 不能保存地形的附加信息，如地表高度、地面特征（水面、沙地等）
比如一个游戏中的角色在走到沙地上时会降低移动速度，或走在一个斜坡上时人物会发生倾斜等。
导航网格寻路内容包含两部分：一是，导航网格的生成。二是，在生成的导航网格基础上，使用一定的算法进行自动寻路
导航网格的生成涉及较多几何知识，放到后面详细讲解，先来说说它的寻路算法
一. 使用A*寻路算法寻找导航网格路径列表（一个多边形列表）
下图是一个已经生成导航网格的地图，深红色为阻挡，浅红色为可行走的导航网格。
下图A为起始点，B为终点，需要在所有导航网格中找到一条最优的可行网格路径，可以有很多算法，最经典的是A*算法，对于A*算法网上有很多详细材料说明，本专题栏也会单独转载一篇老外写的译文资料，这里就不多说了。UE3中使用的就是A*算法来得到导航网格路径，如图所示的紫色网格即为A*算法得到的一条导航网格路径列表。
二. 由导航网格路径列表得到具体的路径点表
这里介绍使用“拐点法”来找到路径点列表
下图的5个凸多边形是已经生成的导航网格，多边形外部的区域为不可行走区域，current为起点，goal为终点，从图中就可以看出最短路径为图中红线，蓝色圈出的点为我们需要找出的点。所有多边形顶点均按逆时针方向存储（这些均在生成导航网格时处理，以后会讲到）。
（1）下图显示出各区域之间的入口，即多边形的临边。由图中可以看出每个临边均为起点穿出该多边形区域的边，故以下称该边为穿出边。
（2）首先找到起始点所在的多边形和穿出边的两个端点，由起点连接两个端点，形成两个线段lineLeft 和lineRight。如下图。绿色圈表示左点，红色表示右点（左点、右点是根据多边形顶点保存顺序而来）。
（3）继续找到下一个穿出边的两个端点，判断新的左点是否在lineLeft 和lineRigh之间，如果在，则更新lineLeft为起点到新左点的线段。
同样处理新穿出边的右点，如下图
该步最后得到两个新的线段，如下图。
（4） 继续判断下一个穿出边的两个端点，如下图，新的左点在lineLeft和lineRight的外面，则不更新线段。
下图说明新的右点在两条直线之间，更新lineRight。
该步最后得到两个新的线段，如下图。
（5） 继续循环判断下一个穿出边的两个端点，该穿出边的两个端点都在lineRight的右侧，表示lineRight的终点即为路径的一个拐角点。
（6） 循环以上步骤都可以找到从起点到终点的一条完整路径。
在继续下面的导航网格生成算法之前，先介绍一下涉及到的计算几何知识。这里只罗列出结论，要详细了解证明过程可以去参考相关的书籍。
矢量加减法：
设二维矢量P = ( x1, y1 )，Q = ( x2 , y2 )，则矢量加法定义为： P + Q = ( x1 + x2 , y1 + y2 )，同样的，矢量减法定义为： P - Q = ( x1 - x2 , y1 - y2 )。显然有性质 P + Q = Q + P，P - Q = - ( Q - P )。
·矢量叉积
设矢量P = ( x1, y1 )，Q = ( x2, y2 )，则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积，即：P × Q = x1*y2 - x2*y1，其结果是一个标量。显然有性质 P ×Q = - ( Q × P ) 和 P × ( - Q ) = - ( P × Q )。
· 折线段的拐向判断：
折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段p0p1和p1p2，通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐向：
若(p2 - p0) × (p1 - p0) > 0,则p0p1在p1点拐向右侧后得到p1p2。
若(p2 - p0) × (p1 - p0) < 0,则p0p1在p1点拐向左侧后得到p1p2。
若(p2 - p0) × (p1 - p0) = 0,则p0、p1、p2三点共线。
· 判断两线段是否相交：
我们分两步确定两条线段是否相交：
(1)快速排斥试验
设以线段 P1P2 为对角线的矩形为R， 设以线段 Q1Q2 为对角线的矩形为T，如果R和T不相交，显然两线段不会相交。
(2)跨立试验
如果两线段相交，则两线段必然相互跨立对方。若P1P2跨立Q1Q2 ，则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧，即( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0。上式可改写成( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0。当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时，说明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共线，但是因为已经通过快速排斥试验，所以 P1 一定在线段 Q1Q2上；同理，( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。所以判断P1P2跨立Q1Q2的依据是：( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) ×( P2 - Q1 ) >= 0。同理判断Q1Q2跨立P1P2的依据是：( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 )× ( Q2 - P1 ) >= 0。
·凸多边形
假设我们在一个多边形上(包括多边形的边界及边界围封的范围)任意取两点并以一条线段连结该两点，如果线段上的每一点均在该多边形上，那么我们便说这个多边形是凸的。
· 凸包
给定平面上的一个(有限)点集(即一组点)，这个点集的凸包就是包含点集中所有点的最小面积的凸多边形。
·点在凸多边形中的判断
假设多边形是凸的，而且顶点p0,p1,...,pn按顺时针方向排列，则点在多边形任意一边 pi-1, pi的右面。
· Voronoi图及对偶图
·Delaunay三角剖分
注（Delaunay三角剖分即狄洛尼三角剖分）
实际中运用的最多的三角剖分是Delaunay三角剖分，它是一种特殊的三角剖分。先从Delaunay边说起：
【定义】Delaunay边：假设E中的一条边e（两个端点为a,b），e若满足下列条件，则称之为Delaunay边：存在一个圆经过a,b两点，圆内(注意是圆内，圆上最多三点共圆)不含点集V中任何其他的点，这一特性又称空圆特性。【定义】Delaunay三角剖分：如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分。
以下是Delaunay剖分所具备的优异特性：
1、最接近：以最近临的三点形成三角形，且各线段(三角形的边)皆不相交。
2、唯一性：不论从区域何处开始构建，最终都将得到一致的结果。
3、最优性：任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那么两个三角形六个内角中最小的角度不会变大。
4、最规则：如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大。
5、区域性：新增、删除、移动某一个顶点时只会影响临近的三角形。
6、具有凸多边形的外壳：三角网最外层的边界形成一个凸多边形的外壳。
· 多边形裁剪
Weiler-Athenton算法
–主多边形：被裁剪多边形，记为A
–裁剪多边形：裁剪窗口，记为B
多边形顶点的排列顺序（使多边形区域位于有向边的左侧 ）外环：逆时针 ；内环：顺时针
主多边形和裁剪多边形把二维平面分成两部分。
内裁剪：A∩B
外裁剪：A-B
裁剪结果区域的边界由A的部分边界和B的部分边界两部分构成，并且在交点处边界发生交替，即由A的边界转至B的边界，或由B的边界转至A的边界。
如果主多边形与裁剪多边形有交点，则交点成对出现，它们被分为如下两类：
进点：主多边形边界由此进入裁剪多边形内 如，I1,I3, I5, I7, I9, I11
出点：主多边形边界由此离开裁剪多边形区域. 如， I0,I2, I4, I6, I8, I10
算法步骤
(1)建立空的裁剪结果多边形的顶点表．
(2)选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中．
假设上图是一个游戏地图，红色的区域是不可行走的区域，浅灰色区域是可行走区域，要想在游戏中实现nav寻路，必须将可行走区域转化为nav网格并保存为一种固定形式的数据，如下图浅红色的三角形。
nav网格必须是凸多边形，这里使用三角型，当然也可以使用4边形。下面介绍一种任意多边形的三角化算法。算法来自论文《平面多边形域的快速约束 三角化》作者：曾薇 孟祥旭 杨承磊杨义军。详细内容请参考该论文。
先来看几个定义：
A. 我们称点 p3 为直线 p1p2 的可见点，其必须满足下面三个条件：
（1） p3 在边 p1p2 的右侧 (顶点顺序为顺时针)；
（2） p3 与 p1 可见，即 p1p3 不与任何一个约束边相交；
（3） p3 与 p2 可见
B. DT点
在一个约束Delaunay三角形中，其中与一条边相对的顶点称为该边的DT点。
确定 DT 点的过程如下：
Step1. 构造 Δp1p2p3 的外接圆 C（p1，p2，p3）及其网格包围盒 B（C（p1，p2，p3））
Step2. 依次访问网格包围盒内的每个网格单元：
对未作当前趟数标记的网格单元进行搜索，并将其标记为当前趟数
若某个网格单元中存在可见点 p, 并且 ∠p1pp2 > ∠p1p3p2，则令 p3=p1，转Step1；否则，转Step3.
Step3. 若当前网格包围盒内所有网格单元都已被标记为当前趟数，也即C（p1，p2，p3）内无可见点，则 p3 为的 p1p2 的 DT 点
生成Delaunay三角网格算法如下：
Step2. 取任意一条外边界边 p1p2 .
Step3. 计算 DT 点 p3，构成约束 Delaunay 三角形 Δp1p2p3 .
Step4. 如果新生成的边 p1p3 不是约束边，若已经在堆栈中，则将其从中删除；否则，将其放入堆栈；类似地，可处理 p3p2 .
Step5. 若堆栈不空，则从中取出一条边，转Step3；否则，算法停止 .
如果你也实现了上一章提到的代码，不难发现对下图的两种情况会出现问题
左面的是两个区域有相交的情况，右面的是多边形本身有自交，在这两种情况下，前面给出的代码均会产生错误的结果。
对于两个多边形相交，可以在生成网格之前先合并多边形，合并后如图
前面已经介绍了寻路的方法，现在给出我的一个实现。
A*寻找网格路径
A*算法就不说了，网上很多，这里只说下三角形网格如何使用A*算法，如下图，绿色直线代表最终路径和方向，路径线进入三角形的边称为穿入边，路径线出去的边称为穿出边。每个三角形的花费（g值）采用穿入边和穿出边的中点的距离（图中红线），至于估价函数（h值）使用该三角形的中心点（3个顶点的平均值）到路径终点的x和y方向的距离。
看下图，最优路径应该是从上面绕过中间阻挡区，而实际寻路产生的路径确是下面。这是由于，在网格面积过大或有某边长度过长时，由于a*中的花费是计算网格的两边中点距离而不实际的路径长度，所以产生的路径偏差较大。所以在一般的网格生成算法中都会加入网格最小面积和最大面积的限制，如果生成的网格小于最小面积时则抛弃，如果大于最大面积则拆分。
一般地图中都会产生孤岛，如下图，两个阻挡区域交叉，合并后在中间深红色区域产生孤岛。按照上面介绍的剪裁算法，中间孤岛多边形会以逆时针方向存储（其他顺时针），因此在这一步能够判断出是否生成孤岛。对于生成的孤岛，如果游戏允许人物可以通过瞬移等方式进入孤岛，那么孤岛也需要生成导航网格，不过孤岛的导航网格和其他区域的网格最好能分成不同区域，这样在寻路时就可以优化（起点和终点不在同区域，可直接确定为不能通过）。
