导航与寻路

导航和寻路是两个联系紧密的概念，但它们并不完全相同，导航往往指代一整套的功能，而寻路是一个相对单一的算法问题。

对导航功能而言，最重要的自然是数据结构，这是导航机制的基础；实践中的导航数据可能有多种不同的储存方式，最基础和最常见的一种当属网格式导航数据。

这种导航数据常见于Tile-based地图，根据地图区块信息得出指定坐标的区块是否可以通行，所有可通行的区块合在一起便是完整的导航数据。

此外还有路点网，通过预先设定好的一系列路点两两相连构成一个完全图，储存在合适的数据结构中即可。

而寻路算法的实现细节会因为导航数据的不同而出现变化，同样的算法思路在不同的数据结构下会有不同的写法。

网格式导航数据通常来说会以矩阵的形式储存

而路点则常见使用和邻接表类似的数据结构

  // 网格矩阵
  int[,] naviData;
  // 邻接表
  public struct GraphNode {
      public int nodeIndex;
      public int nodeInfo;
      public GraphNode nextNode;
  }
  public GraphNode[] adjList;
  // 路点网
  public struct Waypoint {
      public string pid;
      public int pInfo;
      public HashSet<string> pConnect;
  }
  public Dictionary<string, Waypoint> waypointMap;

最短路径算法

最短路径算法是图算法中的一类，它们专注于寻找指定图中两点间的最短路径，其中最基础的几种算法分别为遍历搜索算法，Floyd算法和Dijkstra算法。

遍历搜索算法

图的遍历搜索分为深度优先和广度优先两种方式，它们的运行过程略有区别，但本质上都是在遍历图中的每个节点和每条边。

深度优先搜索，即在搜索时先沿着一个方向搜索到结束，再返回一步继续搜索，该算法有递归和迭代两个版本的实现。

深度优先搜索的迭代版本使用堆栈作为节点搜索的缓存结构，每当遇到新节点时，将其所有邻接压入堆栈即可，每次迭代从堆栈中弹出一个节点进行访问。

广度优先搜索，即在搜索时先搜索完当前节点的所有邻接节点之后才尝试搜索下一层级，该算法同样有递归和迭代两个版本的实现。

广度优先搜索的迭代版本使用队列作为节点搜索的缓存结构，每当遇到新节点时，将其所有邻接加入队列即可，每次迭代从队列中取出一个节点进行访问。

Floyd算法

Floyd算法是一种基于动态规划的最短路径算法，它能在一次运行中找到图内所有节点对的最短路径，其算法思想是许多离线寻路算法的基础。

Floyd算法的状态转移方程如下

  path[i,j] = min{path[i,k] + path[k,j], path[i,j]}
  // 其中path[i,j]表示i到j的最短距离，k则是在穷举i,j之间的断点

具体实现代码

  // 该示例采用邻接矩阵表示图，因此二维数组的两个维度有相同的尺寸
  int vertCount;
  int[,] map;
  int[,] path;
  int[,] distance;

  void Floyd_Path() {
      // 初始化花费和路径矩阵
      for(int v = 0; v < vertCount; v++) {
          for(int w = 0; w < vertCount; w++) {
              distance[v,w] = map[v,w];
              path[v,w] = w;
          }
      }
      for(int k = 0; k < vertCount; k++) { // 第一层循环，断点位置
          for(int v = 0; v < vertCount; v++) { // 第二层循环，起点位置
              for(int w = 0; w < vertCount; w++) { // 第三层循环，终点位置
                  if(distance[v,w] > distance[v,k] + distance[k,w]) {
                      // 找到更小花费的路径
                      distance[v,w] = distance[v,k] + distance[k,w];
                      path[v,w] = path[v,k];
                  }
              }
          }
      }
  }

弗洛伊德算法通过一个O(n^3)复杂度的过程将图中任意两点间的最短路径找出并保存下来，可以用于离线的导航数据预处理，为在线导航过程提供最短路径依据。

Dijkstra算法

Dijkstra算法，也称迪杰斯特拉算法，是一套用于计算图中单一起点到各个目标点最短路径的算法，采取了贪心策略。

具体实现代码

  // 此处同样采用邻接矩阵的表示方法
  int vertCount;
  int[,] map;
  int[] path;
  int[] distance;

  void Dijkstra_Path(int src) {
      int[] step = new int[vertCount];
      for(int i = 0; i < vertCount; i++) {
          step[i] = 0;
          distance[i] = map[src,i];
          path[i] = 0;
      }
      distance[src] = 0;
      step[src] = 1;
      int mp = 0;
      for(int v = 0; v < vertCount; v++) {
          int min = int.MaxValue;
          // 初始化路径和花费记录数组
          for(int w = 0; w < vertCount; w++) {
              if(step[w] == 0) {
                  if(distance[w] < min) {
                      mp = w;
                      min = distance[w];
                  }
              }
          }
          step[mp] = 1; // 记录当前访问过的点
          // 更新路径的花费
          for(int w = 0; w < vertCount; w++) {
              if(step[w] == 0 && (min + map[mp, w]) < distance[w]) {
                  distance[w] = min + map[mp, w];
                  path[w] = mp; // 记录各个最短路径上存在的顶点
              }
          }
      }
  }

启发式搜索算法

所谓的启发式搜索算法是指和传统的寻路算法比起来，它引入了一些额外的信息作为“启发”来构造最优路径，比如引入一个路径花费的参考函数，用它来指导每一步搜索时如何选择子节点。

这种引入额外“启发信息”的做法即是“启发式搜索”的名称来源，同时由于使用了额外信息，这种寻路算法往往能在性能和空间消耗方面获得较好的成果。

一种比较常见的启发式搜索算法是“A星”算法，作为人工智能领域的基础算法之一，“A星”算法利用一个数学意义上的“估值函数”来指导每一步搜索时的节点选择方案，保证了能在相对较低的时间内找到最优路径。

A星算法的基本思路是一种“走一步看一步”的做法，从起点出发，同时朝所有可能的方向进行搜索，将能抵达的所有子节点连同抵达它们的花费一起记录下来，然后再从记录里获取下一个节点重复搜索过程。

而其中最重要的地方就在于“记录所有子节点以及抵达它们的花费”以及“选取下一个节点”这两个步骤，前者需要根据地图导航数据实时得出两个节点之间的行动花费，而且需要随时更新已经被记录的节点信息。

后者则需要“估值函数”参与运算，通过比较所有节点到达终点的“估值花费”来确定下一步该从哪个子节点开始进行搜索。

A星算法有较好的普适性，它既可以对导航网格或者邻接矩阵一类数据结构进行搜索，也可以用于路点网或者多边形网格寻路，需要做的只是基于项目的导航数据建立合适的节点数据结构。

示例代码如下

  // 导航数据节点，需要预先配置好
  public class TBaseNavNode {
      public string NodeIdentifier { get; private set; }
      public Vector2Int nodeCoordinate;
      public int nodeTileReference;
      // 0-正上，1-右上，2-正右，3-右下，4-正下，5-左下，6-正左，7-左上
      public string[] nodeAdjacent;

      public static string CompileID(int x, int y) {
          return $"[{x},{y}]";
      }
  }

  // 导航中间路径表示单元，仅用作寻路
  public class PathUnit {
      public string nodeIdentifier;
      public string parentIdentifier;
      public float unitPrice;
  }

  protected Dictionary<string, TBaseNavNode> nodeSet; // 导航数据
  protected Dictionary<string, PathUnit> openSet; // 寻路的Open列表
  protected Dictionary<string, PathUnit> closeSet; // 寻路的Close列表

  public List<Vector2> FindPath(Vector2Int src, Vector2Int dest) {
      string srcIdentifier = TBaseNavNode.CompileID(src.x, src.y);
      string destIdentifier = TBaseNavNode.CompileID(dest.x, dest.y);
      List<Vector2> result = new List<Vector2>();
      if (nodeSet.Count > 2) {
          Dictionary<string, PathUnit> record = AStarFindPath(srcIdentifier, destIdentifier);
          // 算法的结果是路径链条，需要转化为坐标点列表
          string cursor = destIdentifier;
          while (cursor != null) {
              result.Insert(0, nodeSet[cursor]);
              cursor = record[cursor].parentIdentifier;
          }
      } else {
          result.Add(nodeSet[srcIdentifier]);
          result.Add(nodeSet[destIdentifier]);
      }
      return result;
  }

  protected Dictionary<string, PathUnit> AStarFindPath(string src, string dest) {
      Dictionary<string, PathUnit> pathRecord = new Dictionary<string, PathUnit>();
      openSet.Clear();
      closeSet.Clear();
      PathUnit srcUnit = new PathUnit();
      srcUnit.nodeIdentifier = src;
      srcUnit.parentIdentifier = null;
      srcUnit.unitPrice = 0;
      PathUnit cursor = srcUnit;
      pathRecord[src] = srcUnit;
      openSet[src] = srcUnit;
      // 持续循环直到发现终点或者找不到下一个搜索点为止
      while (openSet.Count > 0 && !openSet.ContainsKey(dest)) {
          openSet.Remove(cursor.nodeIdentifier);
          closeSet[cursor.nodeIdentifier] = cursor;
          TBaseNavNode node = nodeSet[cursor.nodeIdentifier];
          for (int i = 0; i < node.nodeAdjacent.Length; i++) {
              if (node.nodeAdjacent[i] != null) {
                  TBaseNavNode adjNode = nodeSet[node.nodeAdjacent[i]];
                  if (openSet.ContainsKey(adjNode.NodeIdentifier)) {
                      // open表里已经有这个节点了，尝试更新
                      PathUnit openUnit = openSet[adjNode.NodeIdentifier];
                      float price = GetNodePrice(node, adjNode);
                      if (cursor.unitPrice + price < openUnit.unitPrice) {
                          openUnit.parentIdentifier = cursor.parentIdentifier;
                          openUnit.unitPrice = cursor.unitPrice + price;
                      }
                  } else if (!closeSet.ContainsKey(adjNode.NodeIdentifier)) {
                      // open表里没有，close表里也没有，新建一个
                      PathUnit openUnit = new PathUnit();
                      openUnit.nodeIdentifier = adjNode.NodeIdentifier;
                      openUnit.parentIdentifier = node.NodeIdentifier;
                      openUnit.unitPrice = cursor.unitPrice + GetNodePrice(node, adjNode);
                      openSet[openUnit.nodeIdentifier] = openUnit;
                      pathRecord[openUnit.nodeIdentifier] = openUnit;
                  }
              }
          }
          // 从Open列表中找出“最合适”的下一个节点
          float minPrice = float.MaxValue;
          foreach (PathUnit unit in openSet.Values) {
              // 通过估值函数确定最优选择
              float estimatePrice = GetEstimateDistance(nodeSet[unit.nodeIdentifier], nodeSet[dest]);
              if (unit.unitPrice + estimatePrice < minPrice) {
                  minPrice = unit.unitPrice + estimatePrice;
                  cursor = unit;
              }
          }
      }
      return pathRecord;
  }

  // 估值函数
  protected float GetEstimateDistance(TBaseNavNode node, TBaseNavNode dest) {
      Vector2Int delta = dest.nodeCoordinate - node.nodeCoordinate;
      return (Mathf.Abs(delta.x) + Mathf.Abs(delta.y));
  }

  // 花费计算
  protected float GetNodePrice(TBaseNavNode node, TBaseNavNode dest) {
      Vector2Int delta = dest.nodeCoordinate - node.nodeCoordinate;
      return delta.magnitude;
  }

以上示例中的A星算法基于经过预处理后的导航网格数据，使用几何距离作为花费参考，曼哈顿距离作为估值函数。

可以很明显看出，算法中的一大性能瓶颈就在“选择下一个最优子节点”的步骤，示例里使用的是暴力搜索，直接遍历整个Open列表，性能开销很大。

一种可行的优化方案是将其替换为最小堆或者优先队列实现，每次取出估值花费最小的一个节点即可，堆的调整过程复杂度为O(LogN)因此会节约不少性能。

A星算法作为启发式搜索算法里的重要一员，广泛应用在游戏开发以及人工智能等方面，它的搜索思想也可以进行拓展，以适应更加苛刻的性能需求环境。

题外话：多边形网格A星寻路

前文提到A星算法的普适性很强，网格导航可以使用，路点网也可以，而一种相对比较复杂的多边形网格寻路同样可以使用它。

所谓的多边形网格寻路是指将任意形状的表面进行凸多边形划分，然后储存下每个多边形的顶点信息并据此进行寻路与导航，可以算是3D游戏导航的基础思想，而且同时也能应用于2D平面。

要实现这样的寻路算法首先需要确定一套导航数据的表达形式，多边形划分的算法有成熟的代码可用，大部分情况下都是划分为多个三角面，而如何储存这些三角面就是影响算法的重点了。

一种可行的方法是为每个三角形储存三个顶点，三条边的中点以及整个三角形的几何中心，通过预编译以及去重之后，完成划分的三角形就能被转化为一个巨大的点集，此后只要使用合适的估值函数进行A星寻路即可在任意平面或者非平面上找到路径了。

在这个过程中有一个细节需要注意，多边形网格寻路和路点网寻路非常相似，都会面临着选择的起点和终点和储存的节点并不重合的情况，因此需要一种方法来确定距离起点和终点最近且最合适作为寻路节点的点位。

如果遍历所有节点去寻找最近的那个，性能开销显然过大，一种相对更加合适的方案是预先将所有顶点划分到不同的“区块”内，比如按照8的倍数划分坐标轴，将所有节点按坐标位置划分到特定的区块内，并为每个区块设定编号，提供确定某个点位于哪个区块的检测方法。

搜索时便能先找到起点和终点所在的区块，然后在区块内寻找距离最近的点，找不到则扩大搜索范围至周围八个区块重复执行即可。

A星算法的特化，JSP寻路算法

JSP寻路算法，又称跳跃搜索寻路算法，同样是启发式搜索算法的一员，其算法思路和A星算法一脉相承，但通过灵活运用网格导航数据的特殊性以及多种多样的预处理机制，JSP算法能获得比A星算法强数十乃至数百倍的性能优势。

需要注意的是，JSP算法通常而言仅针对网格式导航数据，其跳跃搜索的效率便是以网格数据为基础实现的。

作为A星算法的特化，JSP寻路算法的基本思路也是走一步看一步，根据当前路径的花费以及估值函数的运算结果选择一个当前最优的搜索方向。

但和A星算法中将每一步的邻接节点都加入搜索列表不同的是，JSP算法试图将尽可能少的节点添加到搜索列表，从而达到降低性能开销的目的，为了做到这一点，JSP算法引入了一个新的概念，即跳跃点，Jump Point。

所谓的跳跃点是指满足一定条件的节点，在JSP中通常仅指代网格点。

一个跳跃点至少需要满足以下任意一个条件

1. 它自身为起点或者终点
2. 它自身具有至少一个强制邻居
3. 从它开始朝四个直线方向搜索时至少发现了一个确定的跳跃点

这里提到了JSP算法中的一个重要概念，即强制邻居，所谓强制邻居是指当到达某个网格点的最短路径必然经过另一个点时，前者便为后者的强制邻居。

以下图为例

如果寻路时的搜索方向是从8号点位到5号点位，那么考察4号点位是否可以通行，如果不可通行则1号点位必然为5号点位的强制邻居；考察6号点位，如果6号点位不可通行则3号点位必然为5号点位的强制邻居。

水平方向搜索时也类似，如下图

如果寻路方向是从4号点位到五号点位，则考察2号和8号点位是否可以通行，并由此判定3号和9号点位是否为强制邻居。

由此可知，在行动方向确定的前提下，想要到达B点则必然会经过A点时便称B点为A点的强制邻居，表示它们在寻路时可以被看成是相邻节点参与运算。

在确定了检测跳跃点的规则之后，JSP算法便可以开始运行了，最简单的JSP算法是从起点开始，朝多个方向迭代搜索跳跃点，当找到任何可用跳跃点时将其加入搜索列表，然后结束当前节点的搜素，取出下一个节点重复执行，直到发现终点为止。

这个流程和A星算法非常相似，最大的不同在于JSP算法仅添加跳跃点到搜索列表。

相关的示例代码如下

  /// <summary>
  /// 导航信标节点结构
  /// </summary>
  public class NaviUnit {

      public int xCoord;
      public int yCoord;
      public float uCost;
      public int uValue;
      public NaviUnit parentUnit;

      public string id {
          get {
              return $"[{xCoord},{yCoord}]";
          }
      }

      public NaviUnit(int x, int y) {
          xCoord = x;
          yCoord = y;
      }
  }

  /// <summary>
  /// 寻路请求
  /// </summary>
  public class PathFindingRequest {

      public int xStart;
      public int yStart;
      public int xFinish;
      public int yFinish;
      // 其它数据
      public PathFindingRequest(int xStart, int yStart, int xFinish, int yFinish) {
          this.xStart = xStart;
          this.yStart = yStart;
          this.xFinish = xFinish;
          this.yFinish = yFinish;
      }
  }

  /// <summary>
  /// 寻路方法，接受一个请求作为输入，返回路径上的各点坐标
  /// </summary>
  public List<Vector3> FindPath(PathFindingRequest request) {
      NaviUnit dstUnit = JSPFunction(request);
      List<Vector3> result = new List<Vector3>();
      if (dstUnit != null) {
          NaviUnit cusor = dstUnit;
          while (cusor != null) {
              Vector3 point = new Vector3(cusor.xCoord + 0.5f, cusor.yCoord + 0.5f);
              result.Insert(0, point);
              cusor = cusor.parentUnit;
          }
      } else {
          result.Add(new Vector3(request.xStart, request.yStart, 0f));
          result.Add(new Vector3(request.xFinish, request.yFinish, 0f));
      }
      return result;
  }

  /// <summary>
  /// JSP算法执行过程
  /// </summary>
  public NaviUnit JSPFunction(PathFindingRequest request) {
      openSet.Clear();
      closeSet.Clear();
      unitQueue.Clear();
      if (IsWalkable(request.xFinish, request.yFinish)) {
          NaviUnit srcUnit = new NaviUnit(request.xStart, request.yStart);
          srcUnit.uCost = 0;
          openSet[srcUnit.id] = srcUnit;
          string dst = StageNaviCell.CompileID(request.xFinish, request.yFinish);
          NaviUnit cusor = srcUnit;
          searchQueue.Clear();
          while (openSet.Count > 0 && !openSet.ContainsKey(dst)) {
              openSet.Remove(cusor.id);
              closeSet[cusor.id] = cusor;
              searchQueue.Enqueue(new Vector2Int(0, 0));
              // 此处用队列迭代来处理多方向搜索跳跃点的问题，也可以考虑使用递归
              while (searchQueue.Count > 0) {
                  Vector2Int offset = searchQueue.Dequeue();
                  if (offset.x > 0) {
                      if (offset.y > 0) {
                          // 右上，只查两个方向
                          bool hasPoint = false;
                          hasPoint |= CheckInDirection(cusor, offset, 0, 1, request);
                          hasPoint |= CheckInDirection(cusor, offset, 1, 0, request);
                          if (!hasPoint) {
                              // 没有新增节点，继续搜索
                              CheckSearchOffset(cusor, offset.x + 1, offset.y + 1);
                          }
                      } else if (offset.y < 0) {
                          // 右下，只查两个方向
                          bool hasPoint = false;
                          hasPoint |= CheckInDirection(cusor, offset, 0, -1, request);
                          hasPoint |= CheckInDirection(cusor, offset, 1, 0, request);
                          if (!hasPoint) {
                              // 没有新增节点，继续搜索
                              CheckSearchOffset(cusor, offset.x + 1, offset.y - 1);
                          }
                      }
                  } else if (offset.x < 0) {
                      if (offset.y > 0) {
                          // 左上，只查两个方向
                          bool hasPoint = false;
                          hasPoint |= CheckInDirection(cusor, offset, 0, 1, request);
                          hasPoint |= CheckInDirection(cusor, offset, -1, 0, request);
                          if (!hasPoint) {
                              // 没有新增节点，继续搜索
                              CheckSearchOffset(cusor, offset.x - 1, offset.y + 1);
                          }
                      } else if (offset.y < 0) {
                          // 左下，只查两个方向
                          bool hasPoint = false;
                          hasPoint |= CheckInDirection(cusor, offset, 0, -1, request);
                          hasPoint |= CheckInDirection(cusor, offset, -1, 0, request);
                          if (!hasPoint) {
                              // 没有新增节点，继续搜索
                              CheckSearchOffset(cusor, offset.x - 1, offset.y - 1);
                          }
                      }
                  } else {
                      if (offset.y == 0) {
                          // 这里是特殊情况，即当前点位的搜索，根据cusor的方向进行
                          CheckAndInsertJumpPoint(cusor, request);
                          if (cusor.parentUnit == null) {
                              // 起点没有方向，所以就是四个方向全部加入
                              bool hasPoint = false;
                              hasPoint |= SearchInDirection(cusor, Vector2Int.zero, 0, 1, request);
                              hasPoint |= SearchInDirection(cusor, Vector2Int.zero, 1, 0, request);
                              hasPoint |= SearchInDirection(cusor, Vector2Int.zero, 0, -1, request);
                              hasPoint |= SearchInDirection(cusor, Vector2Int.zero, -1, 0, request);
                              if (!hasPoint) {
                                  // 搜不到任何跳点
                                  for (int x = -1; x <= 1; x += 2) {
                                      for (int y = -1; y <= 1; y += 2) {
                                          CheckSearchOffset(cusor, x, y);
                                      }
                                  }
                              }
                          } else {
                              // 存在方向性的跳点，则根据来源确定搜索方向
                              bool hasPoint = false;
                              int xDir = Mathf.Clamp(cusor.xCoord - cusor.parentUnit.xCoord, -1, 1);
                              int yDir = Mathf.Clamp(cusor.yCoord - cusor.parentUnit.yCoord, -1, 1);
                              if (xDir != 0 && yDir != 0) {
                                  // 斜向
                                  hasPoint |= SearchInDirection(cusor, offset, xDir, 0, request);
                                  hasPoint |= SearchInDirection(cusor, offset, 0, yDir, request);
                                  if (!hasPoint) {
                                      CheckSearchOffset(cusor, xDir, yDir);
                                      CheckSearchOffset(cusor, -xDir, yDir);
                                      CheckSearchOffset(cusor, xDir, -yDir);
                                  }
                              } else if (xDir == 0) {
                                  // 纵向
                                  hasPoint |= SearchInDirection(cusor, offset, 1, 0, request);
                                  hasPoint |= SearchInDirection(cusor, offset, 0, yDir, request);
                                  hasPoint |= SearchInDirection(cusor, offset, -1, 0, request);
                                  if (!hasPoint) {
                                      CheckSearchOffset(cusor, -1, yDir);
                                      CheckSearchOffset(cusor, 1, yDir);
                                  }
                              } else if (yDir == 0) {
                                  // 横向
                                  hasPoint |= SearchInDirection(cusor, offset, 0, 1, request);
                                  hasPoint |= SearchInDirection(cusor, offset, xDir, 0, request);
                                  hasPoint |= SearchInDirection(cusor, offset, 0, -1, request);
                                  if (!hasPoint) {
                                      CheckSearchOffset(cusor, xDir, 1);
                                      CheckSearchOffset(cusor, xDir, -1);
                                  }
                              }
                          }
                      }
                  }
              }
              // 从OpenSet中搜索一个最合适的跳点做下次搜索
              float minCost = float.MaxValue;
              foreach (string id in openSet.Keys) {
                  NaviUnit unit = openSet[id];
                  float estimateCost = GetEstimateCost(id, dst);
                  if (unit.uCost + estimateCost < minCost) {
                      minCost = unit.uCost + estimateCost;
                      cusor = unit;
                  }
              }
          }
          return openSet.TryGetElement(dst);
      }
      return null;
  }

  /// <summary>
  /// 在指定方向上检查跳跃点，如果搜到了就将搜索起点看做跳跃点加入集合
  /// </summary>
  public bool CheckInDirection(NaviUnit cusor, Vector2Int offset, int xDir, int yDir, PathFindingRequest request) {
      string jp = SearchJumpPoint(cusor.xCoord + offset.x, cusor.yCoord + offset.y, xDir, yDir, request.xFinish, request.yFinish);
      if (!string.IsNullOrEmpty(jp)) {
          // 发现任何跳点都可以直接添加Offset位置
          return CheckNaviUnit(offset, cusor, request);
      }
      return false;
  }

  /// <summary>
  /// 在指定方向上搜索跳跃点，搜到之后直接添加到搜索列表中
  /// </summary>
  public bool SearchInDirection(NaviUnit cusor, Vector2Int offset, int xDir, int yDir, PathFindingRequest request) {
      string jp = SearchJumpPoint(cusor.xCoord + offset.x, cusor.yCoord + offset.y, xDir, yDir, request.xFinish, request.yFinish);
      if (!string.IsNullOrEmpty(jp)) {
          // 发现任何跳点都可以直接添加
          return CheckNaviUnit(jp, cusor, request);
      }
      return false;
  }

  /// <summary>
  /// 限制斜角穿越的情况发生，如果允许斜角穿越则不需要进行检查
  /// </summary>
  public void CheckSearchOffset(NaviUnit cusor, int xOffset, int yOffset) {
      Vector2Int offset = new Vector2Int(xOffset, yOffset);
      // 在这里查看一次是否有斜角穿越
      int xDir = Mathf.Clamp(xOffset, -1, 1);
      int yDir = Mathf.Clamp(yOffset, -1, 1);
      bool left = IsWalkable(cusor.xCoord + xOffset - xDir, cusor.yCoord + yOffset);
      bool right = IsWalkable(cusor.xCoord + xOffset, cusor.yCoord + yOffset - yDir);
      if (left && right && IsWalkable(cusor.xCoord + offset.x, cusor.yCoord + offset.y)) {
          searchQueue.Enqueue(offset);
      }
  }

  /// <summary>
  /// 检查特定导航信标节点
  /// </summary>
  public bool CheckNaviUnit(string id, NaviUnit cusor, PathFindingRequest request) {
      bool result = false;
      if (openSet.ContainsKey(id)) {
          // Open表里发现已经存在，则尝试更新
          NaviUnit openUnit = openSet[id];
          float cost = GetPathCost(cusor.id, id);
          if (cusor.uCost + cost < openUnit.uCost) {
              openUnit.parentUnit = cusor;
              openUnit.uCost = cusor.uCost + cost;
          }
      } else if (!closeSet.ContainsKey(id)) {
          // Open表里没有，Close表里也没有，那么就该新建一个
          string dst = StageNaviCell.CompileID(request.xFinish, request.yFinish);
          StageNaviCell cell = mapData.mapNavigate[id];
          NaviUnit openUnit = new NaviUnit(cell.xCoord, cell.yCoord);
          float cost = GetPathCost(cusor.id, id);
          openUnit.parentUnit = cusor;
          openUnit.uCost = cusor.uCost + cost;
          openSet[id] = openUnit;
          float estCost = GetEstimateCost(id, dst);
          result = true;
      }
      return result;
  }

  /// <summary>
  /// 检查特定导航信标节点
  /// </summary>
  public bool CheckNaviUnit(Vector2Int offset, NaviUnit cusor, PathFindingRequest request) {
      string id = StageNaviCell.CompileID(cusor.xCoord + offset.x, cusor.yCoord + offset.y);
      return CheckNaviUnit(id, cusor, request);
  }

  /// <summary>
  /// 获取路径花费
  /// </summary>
  public float GetPathCost(string src, string dst) {
      StageNaviCell srcCell = mapData.mapNavigate[src];
      StageNaviCell dstCell = mapData.mapNavigate[dst];
      int xDelta = dstCell.xCoord - srcCell.xCoord;
      int yDelta = dstCell.yCoord - srcCell.yCoord;
      return Mathf.Sqrt(xDelta * xDelta + yDelta * yDelta);
  }

  /// <summary>
  /// 估值函数
  /// </summary>
  public float GetEstimateCost(string src, string dst) {
      StageNaviCell srcCell = mapData.mapNavigate[src];
      StageNaviCell dstCell = mapData.mapNavigate[dst];
      return Mathf.Abs(dstCell.xCoord - srcCell.xCoord) + Mathf.Abs(dstCell.yCoord - srcCell.yCoord);
  }

  /// <summary>
  /// 跳跃点搜索
  /// </summary>
  public string SearchJumpPoint(int xSrc, int ySrc, int xDir, int yDir, int xEnd, int yEnd) {
      if (xDir != 0 && yDir != 0) {
          // 斜向搜索，只前进一步
          if (CheckJumpPoint(xSrc + xDir, ySrc + yDir, xDir, yDir, xEnd, yEnd)) {
              // 搜到跳点，返回ID
              return StageNaviCell.CompileID(xSrc + xDir, ySrc + yDir);
          }
      } else {
          // 横向或者纵向搜索，一直向前
          int step = 1;
          if (xDir != 0) {
              // 横向
              while (IsWalkable(xSrc + xDir * step, ySrc)) {
                  if (CheckJumpPoint(xSrc + xDir * step, ySrc, xDir, yDir, xEnd, yEnd)) {
                      // 找到了一个跳点，返回ID
                      return StageNaviCell.CompileID(xSrc + xDir * step, ySrc);
                  }
                  step++;
              }
          } else {
              // 纵向
              while (IsWalkable(xSrc, ySrc + yDir * step)) {
                  if (CheckJumpPoint(xSrc, ySrc + yDir * step, xDir, yDir, xEnd, yEnd)) {
                      // 找到了一个跳点，返回ID
                      return StageNaviCell.CompileID(xSrc, ySrc + yDir * step);
                  }
                  step++;
              }
          }
      }
      return string.Empty;
  }

  /// <summary>
  /// 对当前节点进行判定
  /// </summary>
  public void CheckAndInsertJumpPoint(NaviUnit cusor, PathFindingRequest request) {
      if (cusor.parentUnit != null) {
          // 当前点有父亲，那么就通过这个来确定搜索方向
          int xCoord = cusor.xCoord;
          int yCoord = cusor.yCoord;
          int xDir = Mathf.Clamp(cusor.xCoord - cusor.parentUnit.xCoord, -1, 1);
          int yDir = Mathf.Clamp(cusor.yCoord - cusor.parentUnit.yCoord, -1, 1);
          // 然后找一次强迫邻居
          if (xDir != 0 && yDir != 0) {
              // 斜向移动
              bool forward = IsWalkable(xCoord, yCoord + yDir);
              bool right = IsWalkable(xCoord + xDir, yCoord);
              bool back = IsWalkable(xCoord, yCoord - yDir);
              bool left = IsWalkable(xCoord - xDir, yCoord);
              if (!left && forward) {
                  if (IsWalkable(xCoord - xDir, yCoord + yDir)) {
                      string naviID = StageNaviCell.CompileID(xCoord, yCoord + yDir);
                      CheckNaviUnit(naviID, cusor, request);
                  }
              }
              if (!back && right) {
                  if (IsWalkable(xCoord + xDir, yCoord - yDir)) {
                      string naviID = StageNaviCell.CompileID(xCoord + xDir, yCoord);
                      CheckNaviUnit(naviID, cusor, request);
                  }
              }
          } else {
              if (xDir == 0) {
                  // 纵向移动
                  bool forward = IsWalkable(xCoord, yCoord + yDir);
                  if (forward) {
                      if (!IsWalkable(xCoord + 1, yCoord) && IsWalkable(xCoord + 1, yCoord + yDir)) {
                          string naviID = StageNaviCell.CompileID(xCoord, yCoord + yDir);
                          CheckNaviUnit(naviID, cusor, request);
                      }
                      if (!IsWalkable(xCoord - 1, yCoord) && IsWalkable(xCoord - 1, yCoord + yDir)) {
                          string naviID = StageNaviCell.CompileID(xCoord, yCoord + yDir);
                          CheckNaviUnit(naviID, cusor, request);
                      }
                  }
              } else {
                  // 横向移动
                  bool right = IsWalkable(xCoord + xDir, yCoord);
                  if (right) {
                      if (!IsWalkable(xCoord, yCoord + 1) && IsWalkable(xCoord + xDir, yCoord + 1)) {
                          string naviID = StageNaviCell.CompileID(xCoord + xDir, yCoord);
                          CheckNaviUnit(naviID, cusor, request);
                      }
                      if (!IsWalkable(xCoord, yCoord - 1) && IsWalkable(xCoord + xDir, yCoord - 1)) {
                          string naviID = StageNaviCell.CompileID(xCoord + xDir, yCoord);
                          CheckNaviUnit(naviID, cusor, request);
                      }
                  }
              }
          }
      }
  }

  /// <summary>
  /// 检查指定位置是否为跳跃点
  /// </summary>
  public bool CheckJumpPoint(int xCoord, int yCoord, int xDir, int yDir, int xEnd, int yEnd) {
      if (xCoord == xEnd && yCoord == yEnd) {
          return true; // 终点必然是跳点
      } else {
          if (xDir != 0 && yDir != 0) {
              // 斜向移动
              bool forward = IsWalkable(xCoord, yCoord + yDir);
              bool right = IsWalkable(xCoord + xDir, yCoord);
              bool back = IsWalkable(xCoord, yCoord - yDir);
              bool left = IsWalkable(xCoord - xDir, yCoord);
              if (!left && forward) {
                  if (IsWalkable(xCoord - xDir, yCoord + yDir)) {
                      return true;
                  }
              }
              if (!back && right) {
                  if (IsWalkable(xCoord + xDir, yCoord - yDir)) {
                      return true;
                  }
              }
          } else {
              if (xDir == 0) {
                  // 纵向移动
                  bool forward = IsWalkable(xCoord, yCoord + yDir);
                  if (forward) {
                      if (!IsWalkable(xCoord + 1, yCoord) && IsWalkable(xCoord + 1, yCoord + yDir)) {
                          return true;
                      }
                      if (!IsWalkable(xCoord - 1, yCoord) && IsWalkable(xCoord - 1, yCoord + yDir)) {
                          return true;
                      }
                  }
              } else {
                  // 横向移动
                  bool right = IsWalkable(xCoord + xDir, yCoord);
                  if (right) {
                      if (!IsWalkable(xCoord, yCoord + 1) && IsWalkable(xCoord + xDir, yCoord + 1)) {
                          return true;
                      }
                      if (!IsWalkable(xCoord, yCoord - 1) && IsWalkable(xCoord + xDir, yCoord - 1)) {
                          return true;
                      }
                  }
              }
          }
          return false;
      }
  }

  /// <summary>
  /// 是否可以通行
  /// </summary>
  public bool IsWalkable(int x, int y) {
      string naviID = StageNaviCell.CompileID(x, y);
      return mapData.mapNavigate.ContainsKey(naviID);
  }

如代码所示便可实现JSP寻路算法，其中值得优化的地方在于从OpenSet中选取新的搜索节点时采用了暴力搜索的方法，如果考虑使用堆结构或者优先队列实现，则可以将这个选取节点的时间开销压低。

示例代码中采用了迭代的方式来搜索跳跃点，实际使用中也可以考虑递归方法，但需要注意递归的深度，对于规模较大的地图可能会因为递归深度过大导致栈溢出，因此要根据实际情况限制其递归深度。

JSP算法作为A星的一个特化，它的思想并不能直接适用于非网格寻路的场景，而且有许多针对JSP算法的数据结构和预处理优化都仅针对网格导航数据，这一点需要特别注意的。

延伸：基于向量场的寻路思想

所谓的基于向量场的寻路是一种非常有针对性的的寻路思想，以泛洪算法为基础，得出指定起点和终点间的向量场，然后跟随着向量场中每个点位的方向即可抵达终点。

从原理可以看出，这种算法并不能直接适用于在线寻路的场景，因为每次改变起点和终点时都要重新计算整个向量场，开销非常巨大。

但这种思想却能应用在一些起点和终点相对固定甚至完全不发生改变的地方，比如说让敌人持续不断地朝一个目标发起攻击，通过预先计算好的向量场便能让整个场景中任意位置的敌人了解自己当前应该朝哪个方向走。

而且不需要做任何实时寻路，因为向量场已经算好了。

向量场的寻路思想或许能作为特殊情况下寻路方案的一种补充和提示。

总结

寻路算法和导航方案是许多游戏中相当重要的组成部分，因此了解并实践多种多样的寻路方法和导航方案能大大丰富开发者的问题解决工具箱。

而且游戏中的寻路并非是个苛刻的最短路径计算问题，而更可能是一个富有弹性的资源规划问题，在这方面必须根据实际需求来决定采用何种方案，甚至是多种方案的混合使用。