unity3d NavMesh 判断是否到目标

在实现 Unity3D NavMesh 判断是否到达目标这一功能时，我采用寻路方法来实现，具体实现步骤如下：

底层 C# NavMesh 寻路的必要性

以 Unity3D 引擎为例，编写一个底层 C# NavMesh 寻路程序。由于 Unity3D 自带的 NavMesh 寻路功能在某些情况下难以很好地融入游戏项目，因此重写 NavMesh 寻路是一个可行的解决方案。NavMesh 在众多游戏中应用广泛，在不同的框架下都能发挥出色的性能。与传统的 A* 寻路算法相比，NavMesh 不仅减少了内存占用，加快了寻路速度，还能加入寻路角色的宽高限制以及动态物体寻路等功能，基本能适应大多数项目复杂多变的需求。

NavMesh 实现过程详解

1. 理解 NavMesh 核心算法

NavMesh 的核心算法是用三角形替代传统寻路中的方格，并通过计算拐点来优化寻路路径，而非合并路径直线。

对比 NavMesh 寻路和传统的方格寻路（此处可插入图 1 NavMesh 寻路和图 2 传统的方格寻路），可以明显看出两者的差异。NavMesh 以三角形作为寻路块，而传统寻路以方格为寻路块。尽管两者都使用 A* 寻路算法，但网格生成方式的不同，导致在大范围寻路时，其效率和要求也有所不同。

2. NavMesh 寻路中的路径优化之拐点计算

在 NavMesh 中，比较常用的路径优化方法是光照射线法，关于光照射线法的详细内容可参考：光照射线法详细内容。

拐点计算优化路径的核心是在到达目的地所需经过的一系列三角形中，计算出最简洁的移动方式。其核心算法是：从当前点到另一个三角形中的点之间的线段，与这条线段相交的线段全部是路径所穿越的线段，这些交点即为拐点。找出所有的拐点，并确定一条最长的拐点路径，该拐点所在位置就是最佳的拐点位置。

3. NavMesh 类设计详解

这里仅设计 2D 寻路，对于 3D 方向的寻路，实际上可以用 2D 寻路来替代，在 Unity3D NavMesh 判断是否到达目标时同样适用。

所有类都位于同一命名空间 NavMesh 内：

namespace NavMesh
{
// 三角形基础类
class Triangle { }
// 寻路三角形类 (继承 Triangle)
class NavTriangle : Triangle { }
// 线段类
class Line2D { }
// 多边形类
class Polygon { }
// 寻路主算法类
class Seeker { }
}

4. 建立 MESH 三角形网格

在寻路前，需要建立 MESH 三角形网格，这是 NAV_MESH 的关键步骤之一。具体步骤如下：

1. 确定可行走范围：首先画出一个范围来明确可行走区域。
2. 添加不可行走范围：在可行走范围内添加不可行走的区域。
3. 用多边形表示范围：使用多个多边形 Polygon 来表示上述范围，即一个大的可行走 Polygon 内包含若干个小的不可行走的 Polygon。

根据这些多边形的各个顶点来生成三角形网格，三角形网格的生成算法如下：

• Step 1：用可行走 Polygon 的任意一条边作为起点，将其推入堆栈列表，然后进入 Step 2。
• Step 2：从堆栈中推出一条边，在所有三角形中计算出该边的 DT 点，构成约束 Delaunay 三角形，进入 Step 3。如果没有 DT 点，则重复 Step 2，直到堆栈为空，结束整个程序。
• Step 3：将所构成的三角形的另外两条边进行如下处理：检查堆栈中是否已存在该边，如果存在则删除，不存在则加入到堆栈中。

生成 mesh 后的示例图（绿色为多边形边框，蓝色为寻路路径，红色为编辑器选中的多边形）。

以下是生成导航网格的核心源码：

/// <summary>
/// 创建导航网格
/// </summary>
/// <param name="polyAll">所有阻挡区域</param>
/// <param name="triAll">输出的导航网格</param>
/// <returns></returns>
public NavResCode CreateNavMesh(List<Polygon> polyAll, ref int id, int groupid, ref List<Triangle> triAll)
{
triAll.Clear();
List<Line2D> allLines = new List<Line2D>(); // 线段堆栈
// Step1 保存顶点和边
NavResCode initRes = InitData(polyAll);
if (initRes != NavResCode.Success)
return initRes;
int lastNeighborId = -1;
Triangle lastTri = null;
// Step2. 遍历边界边作为起点
{
Line2D sEdge = startEdge;
allLines.Add(sEdge);
Line2D edge = null;
do
{
// Step3. 选出计算出边的 DT 点，构成约束 Delaunay 三角形
edge = allLines[allLines.Count - 1];
allLines.Remove(edge);
Vector2 dtPoint;
bool isFindDt = FindDT(edge, out dtPoint);
if (!isFindDt)
continue;
Line2D lAD = new Line2D(edge.GetStartPoint(), dtPoint);
Line2D lDB = new Line2D(dtPoint, edge.GetEndPoint());
// 创建三角形
Triangle delaunayTri = new Triangle(edge.GetStartPoint(), edge.GetEndPoint(), dtPoint, id++, groupid);
// 保存邻居节点
// if (lastNeighborId != -1)
// {
//     delaunayTri.SetNeighbor(lastNeighborId);
//     if(lastTri != null)
//         lastTri.SetNeighbor(delaunayTri.ID);
// }
// save result triangle
triAll.Add(delaunayTri);
// 保存上一次的 id 和三角形
lastNeighborId = delaunayTri.GetID();
lastTri = delaunayTri;
int lineIndex;
// Step4. 检测刚创建的的线段 ad,db；如果如果它们不是约束边
// 并且在线段堆栈中，则将其删除，如果不在其中，那么将其放入
if (!Line2D.CheckLineIn(allEdges, lAD, out lineIndex))
{
if (!Line2D.CheckLineIn(allLines, lAD, out lineIndex))
allLines.Add(lAD);
else
allLines.RemoveAt(lineIndex);
}
if (!Line2D.CheckLineIn(allEdges, lDB, out lineIndex))
{
if (!Line2D.CheckLineIn(allLines, lDB, out lineIndex))
allLines.Add(lDB);
else
allLines.RemoveAt(lineIndex);
}
// Step5. 如果堆栈不为空，则转到第 Step3. 否则结束循环
} while (allLines.Count > 0);
}
// 计算邻接边和每边中点距离
for (int i = 0; i < triAll.Count; i++)
{
Triangle tri = triAll[i];
//// 计算每个三角形每边中点距离
//tri.calcWallDistance();
// 计算邻居边
for (int j = 0; j < triAll.Count; j++)
{
Triangle triNext = triAll[j];
if (tri.GetID() == triNext.GetID())
continue;
int result = tri.isNeighbor(triNext);
if (result != -1)
{
tri.SetNeighbor(result, triNext.GetID());
}
}
}
return NavResCode.Success;
}

5. 计算 DT 点的说明

• Step 1：构造三角形的外接圆，以及外接圆的包围盒。
• Step 2：依次访问网格包围盒内的每个网格单元。若某个网格单元中存在可见点 p，并且 ∠p1pp2 > ∠p1p3p2，则令 p3 = p，转 Step 1；否则，转 Step 3。
• Step 3：若当前网格包围盒内所有网格单元都已被处理完，即 C（p1，p2，p3）内无可见点，则 p3 为 p1p2 的 DT 点。

以下是计算 DT 点的核心源码：

/// <summary>
/// 找到指定边的约束边 DT
/// </summary>
/// <param name="line"></param>
/// <returns></returns>
private bool FindDT(Line2D line, out Vector2 dtPoint)
{
dtPoint = new Vector2();
if (line == null)
return false;
Vector2 ptA = line.GetStartPoint();
Vector2 ptB = line.GetEndPoint();
List<Vector2> visiblePnts = new List<Vector2>();
foreach (Vector2 point in allPoints)
{
if (IsPointVisibleOfLine(line, point))
visiblePnts.Add(point);
}
if (visiblePnts.Count == 0)
return false;
bool bContinue = false;
dtPoint = visiblePnts[0];
do
{
bContinue = false;
// Step1. 构造三角形的外接圆，以及外接圆的包围盒
Circle circle = NMath.CreateCircle(ptA, ptB, dtPoint);
Rect boundBox = NMath.GetCircleBoundBox(circle);
// Step2. 依次访问网格包围盒内的每个网格单元：
// 若某个网格单元中存在可见点 p, 并且 ∠p1pp2 > ∠p1p3p2，则令 p3=p，转 Step1；
// 否则，转 Step3.
float angOld = (float)Math.Abs(NMath.LineRadian(ptA, dtPoint, ptB));
foreach (Vector2 pnt in visiblePnts)
{
if (pnt == ptA || pnt == ptB || pnt == dtPoint)
continue;
if (!boundBox.Contains(pnt))
continue;
float angNew = (float)Math.Abs(NMath.LineRadian(ptA, pnt, ptB));
if (angNew > angOld)
{
dtPoint = pnt;
bContinue = true;
break;
}
}
// false 转 Step3
} while (bContinue);
// Step3. 若当前网格包围盒内所有网格单元都已被处理完，
// 也即 C（p1，p2，p3）内无可见点，则 p3 为的 p1p2 的 DT 点
return true;
}

通过以上步骤，我们可以实现一个较为完整的 Unity3D NavMesh 寻路系统，进而实现判断是否到达目标的功能。