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

作者:JamBob
2018-10-20
9 11 2

首先算法是基于 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. 角色可以上/下/左/右移动(前提是没有大于最大跳跃值)
      1. 情况1:角色处于上升(上/左/右)
      2. 情况2:角色处于下落(下/左/右)
    2. 下一步左/右移动,跳转值+1
    3. 下一步上/下移动,跳转值+2
  2. 当前的角色的跳转值为奇数
    1. 角色只能上/下移
      1. 情况1:角色处于上升(上)
      2. 情况1:角色处于下落(下)
    2. 下一步上/下移动 跳转值+1
  3. 当角色头顶的单元格为障碍(当前(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

一些示例

这是一个更复杂的案例:

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

  1. 从地面开始:跳跃值为0
  2. 水平跳转:将跳转值增加1,因此跳转值为1
  3. 垂直跳转:将跳转值增加到下一个偶数:2
  4. 垂直跳转:将跳跃值增加到下一个偶数:4
  5. 水平跳跃:将跳跃值增加1 跳跃值现在是5
  6. 垂直跳转:将值增加到下一个偶数:6。(角色不能再向上移动,因此只有左,右和底节点可用。)
  7. 水平下降:将跳跃值增加1; 跳跃值现在是7
  8. 垂直下降:将跳跃值增加到下一个偶数:8
  9. 垂直下降:将值增加到下一个偶数:10
  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* 算法不一样的地方,由于每个单元格可以被访问多次,我们需要对每个单元格创建一个数组来储存跳跃值。

参考地址

https://gamedevelopment.tutsplus.com/tutorials/how-to-adapt-a-pathfinding-to-a-2d-grid-based-platformer-theory--cms-24662

本文为用户投稿,不代表 indienova 观点。

近期点赞的会员

 分享这篇文章

您可能还会对这些文章感兴趣

参与此文章的讨论

  1. Demgel 2018-10-20

    谢谢分享,学习了

  2. CyclohexaneC6H12 2018-10-25

    非常感谢~

您需要登录或者注册后才能发表评论

登录/注册