首先算法是基于 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:角色处于上升(上/左/右)
- 情况2:角色处于下落(下/左/右)
- 下一步左/右移动,跳转值+1
- 下一步上/下移动,跳转值+2
- 角色可以上/下/左/右移动(前提是没有大于最大跳跃值)
- 当前的角色的跳转值为奇数
- 角色只能上/下移
- 情况1:角色处于上升(上)
- 情况1:角色处于下落(下)
- 下一步上/下移动 跳转值+1
- 角色只能上/下移
- 当角色头顶的单元格为障碍(当前(5,5),下个单元格(5,6)为障碍物 maxCharacterJumpHeight = 3 角色最大跳转值
- 当前的角色单元格的 x 坐标!=下一个移动单元格坐标 跳转值定义为 jumpValue = max(maxCharacterJumpHeight * 2 + 1, jumpLength + 1)
- 如果相等 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* 算法不一样的地方,由于每个单元格可以被访问多次,我们需要对每个单元格创建一个数组来储存跳跃值。
谢谢分享,学习了
非常感谢~