如何使 A *寻路适应 2D 网格平台：理论

首先算法是基于 2D 网格的，寻路使用进过改造的 a* 算法。

知识准备

a* 寻路算法（不熟悉的强烈建议先去熟悉一下https://blog.csdn.net/zhulichen/article/details/78786493
优先级队列 https://www.cnblogs.com/yangecnu/p/Introduce-Priority-Queue-And-Heap-Sort.html

规则定义

寻路算法只能通过上下左右的方式移动单元格，不能斜线移动单元格。

定义角色跳跃高度为三个单元格，以下是一种最大距离的跳跃路径示例。

当然角色也是垂直向上跳跃3格单元格。

用跳转值表示跳转路径

首先我们定义角色在地面的跳转值为永远都为0，也就是说只要角色的下一个单元格为地面，那么角色在当前的跳转值就是0

当前的角色的跳转值为偶数
1. 角色可以上/下/左/右移动(前提是没有大于最大跳跃值)
  1. 情况1：角色处于上升（上/左/右）
  2. 情况2：角色处于下落（下/左/右）
2. 下一步左/右移动，跳转值+1
3. 下一步上/下移动，跳转值+2
当前的角色的跳转值为奇数
1. 角色只能上/下移
  1. 情况1：角色处于上升（上）
  2. 情况1：角色处于下落（下）
2. 下一步上/下移动跳转值+1
当角色头顶的单元格为障碍（当前（5,5），下个单元格（5,6）为障碍物 maxCharacterJumpHeight = 3 角色最大跳转值
1. 当前的角色单元格的 x 坐标！=下一个移动单元格坐标跳转值定义为 jumpValue = max(maxCharacterJumpHeight * 2 + 1, jumpLength + 1）
2. 如果相等 jumpValue = max(maxCharacterJumpHeight * 2, jumpLength + 2)

如何确定下一个移动单元格？

我们使用的是 A*算法进行寻路，唯一不同的 G 值得计算方式不一样。因此我们最终要计算出来的就是 G 值。

这里的下一个移动的单元格不是角色真正移动的单元格，而是角色上下左右的单元格。通过上面的规则计算从起点移动到指定方格的移动代价，

H 值使用哈曼顿计算，这样有个 G 和 H 我们就可以计算每个单元格的 F 值。

如果觉得跳跃值为3，那么它的最大跳跃值为3*2

一些示例

这是一个更复杂的案例：

以下是跳数值的计算方法：

从地面开始：跳跃值为0。
水平跳转：将跳转值增加1，因此跳转值为1。
垂直跳转：将跳转值增加到下一个偶数：2。
垂直跳转：将跳跃值增加到下一个偶数：4。
水平跳跃：将跳跃值增加1 ; 跳跃值现在是5。
垂直跳转：将值增加到下一个偶数：6。（角色不能再向上移动，因此只有左，右和底节点可用。）
水平下降：将跳跃值增加1; 跳跃值现在是7。
垂直下降：将跳跃值增加到下一个偶数：8。
垂直下降：将值增加到下一个偶数：10。
垂直落下：因为角色现在在地上。将跳转值设置为0

情景分析

位置（3,1）处的绿色单元是字符; 位置（2,5）处的蓝色单元格是目标。让我们绘制一条 A *算法可以先选择尝试达到目标的路线。

由于角色的最大跳转值是6，所以角色无法到达(2,5)，但是我们可以发现还有另外一条更好路可以走

正如你所看到的，跳到角色右侧的区块允许它跳得足够高以达到目标！但是，这里有一个很大的问题......

很可能，算法将采用的第一条路线是我们检查的第一条路线。在获取之后，算法将不会走得太远，并且将最终返回节点（3,2）。然后它可以搜索节点（4,2），（4,3），（3,3） （再次），（3,4） （再次），（3,5），最后搜索目标单元格，（2），5）。

在 A *算法的基本版本中，如果已经访问过一个节点，那么我们不需要再次处理它。但是，在这个版本中，我们这样做。这是因为节点不仅仅由 x 坐标和 y 坐标区分，而且还由跳跃值区分。

在我们的第一次尝试找到一个路径，在节点跳跃值（3,3） 是4 ; 在我们的第二次尝试中，它是3。因为在第二次尝试中，该单元格的跳跃值较小，这意味着我们可能会比第一次尝试时更高。

这基本上意味着，节点（3,3）具有的跳跃值4是一个不同的节点以比该节点（3，3）用的跳跃值3。网格基本上需要在某些坐标处变为三维以适应这些差异，如下所示：