English
简体中文
如何使A *寻路适应2D网格平台：理论
首先算法是居于2d网格的，寻路使用进过改造的a*算法
知识准备
1.a*寻路算法（不熟悉的强烈建议先去熟悉一下）
https://blog.csdn.net/zhulichen/article/details/78786493
2.优先级队列
https://www.cnblogs.com/yangecnu/p/Introduce-Priority-Queue-And-Heap-Sort.html
规则定义
寻路算法只能通过上下左右的方式移动单元格，不能斜线移动单元格
定义角色跳跃高度为三个单元格，以下是一种最大距离的跳跃路径示例
当然角色也是垂直向上跳跃3格单元格
用跳转值表示跳转路径
首先我们定义角色在地面的跳转值为永远都为0，也就是说只要角色的下一个单元格为地面，那么角色在当前的跳转值就是0
一.当前的角色的跳转值为偶数
1.角色可以上/下/左/右移动(前提是没有大于最大跳跃值)
情况1：角色处于上升（上/左/右）
情况2：角色处于下落（下/左/右）
2.下一步左/右移动，跳转值+1
3.下一步上/下移动，跳转值+2
二.当前的角色的跳转值为奇数
1.角色只能上/下移动
情况1：角色处于上升（上）
情况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。网格基本上需要在某些坐标处变为三维以适应这些差异，如下所示：
这也是和a*算法不一样的地方，由于每个单元格可以被访问多次，我们需要对每个单元格创建一个数组来储存跳跃值。
参考地址：
近期喜欢的会员
