Unreal Engine 导航网格寻路算法概述

目录

1. 导航网格寻路 —— 导航寻路和传统路点寻路比较
2. 导航网格寻路 —— 寻路方法
3. 导航网格寻路 —— 生成导航网格需要的几何知识
4. 导航网格寻路 —— 生成导航网格
5. 导航网格寻路 —— 生成网格的一些补充
6. 导航网格寻路 —— A*寻路实现细节
7. 导航网格寻路 —— 一些优化

1. 导航网格寻路 -- 介绍

传统路点寻路与导航网格寻路对比

传统路点寻路和导航网格寻路各有特点，以下是传统路点寻路存在的不足之处：

• 效率问题：一些复杂的游戏地图需要的路点数量过于庞大，例如柱角拐弯较多的地方，这会大大降低寻路算法的效率。而导航网格对于同样的地形，其多边形数量能保持在较少的水平。
• 路径规划：路点寻路即使在直线线路上没有阻挡，有时也会使角色走折线路径。而导航网格寻路可以保证直线行走。例如，在A点和B点之间的路径，路点寻路可能会产生“Z”字型路径，而导航网格寻路则能产生直线路径。
• 路径平滑：路点寻路路径在拐弯处不能进行路径平滑，而导航网格可以通过曲线来平滑路径，只要保证该曲线在导航网格内即可。例如，红线表示路径寻路的路线，蓝线表示导航网格通过曲线平滑的路线。
• 动态阻挡处理：路点寻路数据不包含任何地形外的物体数据，所以路点寻路系统在处理动态阻挡时修改路径很困难。而导航网格包含地形信息，能够知道网格内哪些区域有动态阻挡物体，通过射线投射能够方便地动态修改行走路线。当遇到动态阻挡时，路点寻路可能陷入困境，而导航网格能在导航网格内找到可通行的折线路径。
• 角色适应性：路径点寻路不能根据不同的寻路角色来改变路径（例如不同角色有不同的包围盒），而导航网格可以处理这种情况。例如，在拐角处，路点寻路的路径可能只适合一个人通过，对于坦克则无法通行；而导航网格能根据人和坦克的包围盒信息，计算出符合对应角色的路径。
• 地形附加信息：路点寻路不能保存地形的附加信息，如地表高度、地面特征（水面、沙地等）。例如，游戏中的角色在走到沙地上时会降低移动速度，或走在斜坡上时人物会发生倾斜等，路点寻路无法处理这些情况。

导航网格寻路内容包含两部分：一是导航网格的生成，二是在生成的导航网格基础上，使用一定的算法进行自动寻路。导航网格的生成涉及较多几何知识，将在后面详细讲解，下面先介绍其寻路算法。

寻路算法

使用A*寻路算法寻找导航网格路径列表（一个多边形列表）

对于已经生成导航网格的地图，深红色区域为阻挡，浅红色区域为可行走的导航网格。若A为起始点，B为终点，需要在所有导航网格中找到一条最优的可行网格路径。有很多算法可以实现这一目标，最经典的是A算法。关于A算法，网上有很多详细材料说明，本专题栏也会单独转载一篇老外写的译文资料。UE3中使用的就是A算法来得到导航网格路径，例如图中紫色网格即为A算法得到的一条导航网格路径列表。

由导航网格路径列表得到具体的路径点表

这里介绍使用“拐点法”来找到路径点列表。假设有5个凸多边形组成的导航网格，多边形外部的区域为不可行走区域，current为起点，goal为终点。从图中可以看出最短路径为图中红线，蓝色圈出的点为需要找出的点。所有多边形顶点均按逆时针方向存储（这些均在生成导航网格时处理）。具体步骤如下：

1. 显示各区域之间的入口，即多边形的临边。每个临边均为起点穿出该多边形区域的边，以下称该边为穿出边。
2. 找到起始点所在的多边形和穿出边的两个端点，由起点连接两个端点，形成两个线段lineLeft和lineRight。绿色圈表示左点，红色表示右点（左点、右点是根据多边形顶点保存顺序而来）。
3. 继续找到下一个穿出边的两个端点，判断新的左点是否在lineLeft和lineRight之间，如果在，则更新lineLeft为起点到新左点的线段。同样处理新穿出边的右点。
4. 继续判断下一个穿出边的两个端点，若新的左点在lineLeft和lineRight的外面，则不更新线段；若新的右点在两条直线之间，则更新lineRight。
5. 继续循环判断下一个穿出边的两个端点，若该穿出边的两个端点都在lineRight的右侧，表示lineRight的终点即为路径的一个拐角点。
6. 循环以上步骤，即可找到从起点到终点的一条完整路径。

3. 导航网格寻路 – 生成导航网格需要的一些几何知识

在介绍导航网格生成算法之前，先了解一些涉及到的计算几何知识。这里只罗列出结论，详细的证明过程可参考相关书籍。

矢量加减法

设二维矢量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 = x1y2 - x2y1，其结果是一个标量。显然有性质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边：假设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. 选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中。

4. 导航网格寻路 -- 生成导航网格

假设上图是一个游戏地图，红色区域是不可行走的区域，浅灰色区域是可行走区域。要在游戏中实现nav寻路，必须将可行走区域转化为nav网格并保存为一种固定形式的数据，例如浅红色的三角形。nav网格必须是凸多边形，这里使用三角形，当然也可以使用四边形。下面介绍一种任意多边形的三角化算法，该算法来自论文《平面多边形域的快速约束 三角化》，作者：曾薇 孟祥旭 杨承磊 杨义军。详细内容请参考该论文。

相关定义

• 可见点：称点p3为直线p1p2的可见点，其必须满足下面三个条件：
• p3在边p1p2的右侧（顶点顺序为顺时针）。
• p3与p1可见，即p1p3不与任何一个约束边相交。
• p3与p2可见。
• DT点：在一个约束Delaunay三角形中，其中与一条边相对的顶点称为该边的DT点。

确定DT点的过程

1. 构造Δp1p2p3的外接圆C（p1，p2，p3）及其网格包围盒B（C（p1，p2，p3））。
2. 依次访问网格包围盒内的每个网格单元：对未作当前趟数标记的网格单元进行搜索，并将其标记为当前趟数。若某个网格单元中存在可见点p，并且∠p1pp2 > ∠p1p3p2，则令p3 = p1，转Step1；否则，转Step3。
3. 若当前网格包围盒内所有网格单元都已被标记为当前趟数，也即C（p1，p2，p3）内无可见点，则p3为p1p2的DT点。

生成Delaunay三角网格算法

1. 取任意一条外边界边p1p2。
2. 计算DT点p3，构成约束Delaunay三角形Δp1p2p3。
3. 如果新生成的边p1p3不是约束边，若已经在堆栈中，则将其从中删除；否则，将其放入堆栈；类似地，可处理p3p2。
4. 若堆栈不空，则从中取出一条边，转Step3；否则，算法停止。

5. 导航网格寻路 -- 生成网格的一些补充

如果你实现了上一章提到的代码，会发现对于两种情况会出现问题：两个区域有相交的情况和多边形本身有自交。在这两种情况下，前面给出的代码均会产生错误的结果。对于两个多边形相交，可以在生成网格之前先合并多边形。

6. 导航网格寻路 -- A*寻路的实现细节

前面已经介绍了寻路的方法，现在给出一个实现。在使用A*算法寻找网格路径时，对于三角形网格，路径线进入三角形的边称为穿入边，路径线出去的边称为穿出边。每个三角形的花费（g值）采用穿入边和穿出边的中点的距离，至于估价函数（h值）使用该三角形的中心点（3个顶点的平均值）到路径终点的x和y方向的距离。

7. 导航网格寻路 -- 一些优化

在实际寻路中，可能会出现路径偏差的问题。例如，最优路径应该是从上面绕过中间阻挡区，而实际寻路产生的路径却是下面。这是由于在网格面积过大或有某边长度过长时，A*算法中的花费是计算网格的两边中点距离，而不是实际的路径长度，所以产生的路径偏差较大。因此，在一般的网格生成算法中都会加入网格最小面积和最大面积的限制，如果生成的网格小于最小面积则抛弃，如果大于最大面积则拆分。

此外，一般地图中可能会产生孤岛。例如，两个阻挡区域交叉，合并后在中间深红色区域产生孤岛。按照上面介绍的剪裁算法，中间孤岛多边形会以逆时针方向存储（其他顺时针），因此在这一步能够判断出是否生成孤岛。对于生成的孤岛，如果游戏允许人物可以通过瞬移等方式进入孤岛，那么孤岛也需要生成导航网格，不过孤岛的导航网格和其他区域的网格最好能分成不同区域，这样在寻路时就可以优化（起点和终点不在同区域，可直接确定为不能通过）。