理论解析：如何让A*寻路算法适应2D网格平台游戏

本文是系列教程“如何让A*寻路算法适应基于2D网格实现的平台游戏”的第一部分。这个系列教程共有６个部分，作者Daniel Branicki详细解释为什么以及该如何修改A*寻路算法来适应基于2D网格实现的平台游戏。

基于网格的寻路算法在游戏中工作的非常好，角色可以沿着x轴和y轴自由的移动。但是把这种寻路系统推广到平台游戏的时候遇到的问题是沿着y轴的移动是严重受限的，因为平台游戏需要模拟存在重力的情况。

在这个教程中，我将大概描述下如何修改标准的A*寻路算法来在模拟重力限制的平台游戏上正常工作。（在接下来的部分，我将逐步通过编程来演示算法）。修改后的A*寻路算法可以用来创建一个跟随玩家的有人工智能的机器人角色，或者用来指引玩家该如何到达他们的目的地等等。

在这篇文章里，我将假设你已经很熟悉A＊寻路算法了，但是如果并不是这样，你还需要了解下这个技术的话，这里有一篇很棒的适合初学者的文章：Patrick Lester的“给初学者看的A＊寻路“（ A* Pathfinding forBeginners）。

演示

你可以玩下Unity开发的演示demo，或者WebGL版本的演示demo（大小64MB），在演示中可以看到最终的结果。演示中的操作包括使用WASD键来移动角色，在地图的一个点上左键单击可以用来找到一条你可以沿着到达那里的路径，用右键单击一个单元格可以切换那个点的地面。

在这个系列的最后，我们还将向游戏里面添加单向平台功能，通过拓展代码来处理不同大小的角色，并且将编码一个可以自动沿路径行走的机器人。请在Unity开发的demo中查看这个效果（Demo）或者在100MB+的WebGL版本看下效果（DEMO）。

定义整体的规则

在我们对A*寻路算法进行修改之前，我们需要清楚的定义路径将采用什么形式来定义。

角色可以做什么事情？

比方说，我们的角色可以占用一个单元格，可以跳三个格子高。

我们不会允许我们的角色沿着单元格的对角线移动，因为我们不想让角色穿越有障碍物的地面。（也就是说，我们不会允许角色仅仅穿越单元格的四个角，包括从上方、下方、左边、右边）。要移动到对角相邻的单元格时，角色必须先向上或者向下穿过一个单元格，然后再向左或者向右穿过一个单元格。

因为角色的跳跃高度是三个单元格高，那么每当它跳跃以后，在它已经向上穿过三个单元格以后，就不应该再能向上穿越任何单元格了，但是它仍然应该能向着两边移动。

基于这些规则，这里有一个角色在最大高度跳跃下可以走的路径的例子。


当然，角色可以沿直线垂直向上跳，或者在向上跳的过程中加上向左或者向右的移动。但是这个例子显示了一种我们在用网格进行路径计算的时候需要接受的近似。

用跳跃值来表示跳跃路径

路径上的每个单元格都将记录跳跃高度的数据，所以我们的算法可以用来检测玩家是否还能跳的更高或者必须开始下落。

让我们从给每个单元格的跳跃值加1开始，只要跳跃还在继续，我们就给经过的每个格子的跳跃值加1。当然，当角色在地面的时候，跳跃值为0。

下面就是把规则应用到之前的最大高度跳跃后的结果：


跳跃值为6的单元格是路径的最高点。这是有意义的，因为跳跃值等于角色最大跳跃高度的2倍，这意味着在这个例子里角色垂直穿过一个单元格和水平穿过一个单元格是依次发生的。

请注意，如果角色垂直向上跳，我们将对每个单元格的跳跃值进行依次加一，那么这个机制就不会起作用了，因为最高的单元格的跳跃值是3。

让我们来修改下规则，只要是角色向上移动的时候，都把通过的单元格的跳跃值提高到下一个偶数。如果当前单元格的跳跃值是偶数，那么角色可以向左、向右、向下移动（还可以向上移动，只要当前单元格的跳跃值还不是6），当前单元格的跳跃值是奇数，那么角色只能向上或是向下移动（到底是向上还是向下移动取决于角色是否到达跳跃的最高点，也就是是否有单元格的跳跃值等于6）。

下面是一个垂直向上跳看起来的样子：


这是一个更加复杂的情况：


这里是跳跃值如何计算出来的过程:

从站在地面上开始：单元格的跳跃值为0.

水平跳跃：对单元格的跳跃值加一，所以单元格的跳跃值现在是1。

垂直跳跃：增加单元格的跳跃值到下一个偶数：2。

垂直跳跃：增加单元格的跳跃值到下一个偶数：4。

水平跳跃：对单元格的跳跃值加一，所以单元格的跳跃值现在是5。

垂直跳跃：增加单元格的跳跃值到下一个偶数：6。（角色不能再向上移动了，所以只有左边、右边和下方的节点可以到达）。

水平下降：对单元格的跳跃值加一，所以单元格的跳跃值现在是7。

垂直下降：增加单元格的跳跃值到下一个偶数：8。

垂直下降：增加单元格的跳跃值到下一个偶数：10.

垂直下降：因为角色现在是在地面上，所以单元格的跳跃值现在是0。

正如你所看到的，通过在单元格记录这样的数字以后，我们可以很精确的知道角色什么时候能够到达它们的最大高度：就是那个跳跃值等于角色最大跳跃高度2倍的单元格。如果当前单元格的跳跃值比角色最大跳跃高度2倍小，那么角色就还能继续向上移动。否则，我们就要忽略那些位于角色垂直上方的节点。

添加坐标

既然我们对角色在网格中能做的移动方式已经有了一定的认识，现在让我们考虑以下设置：


位于位置（3，1）的绿色单元格就是角色，位于位置(2，5)的蓝色单元格就是目的地。让我们根据A＊寻路算法来绘制一条路径，A*寻路算法将会首先尝试下最短路径是否可行。


单元格右上角的黄色数字是单元格的跳跃值。正如你所看到的，通过一个向上垂直跳跃，角色可以跳三个单元格高，但是最多也就3个单元格这么高了，没法再跳的高一点。这没有办法到达目标点。

我们可能需要更多的运气才能发现另外一条路径，所以让我们从头开始搜索，这次以节点(3，2)作为起点开始搜索。


正如你看到的那样，角色如果先跳到角色右边的障碍物上，然后从那起跳将允许角色跳的足够高到够到目标点!但是，这里面有一个大问题。。。

在所有的可能性中，算法会把连接两点的最短路径找出来作为第一条路径来判断是否可行。在对连接两点的最短路径检测之后，算法不会有太大的进展，并最终将回到节点(3 2)。然后它会进行一个搜索，从（3，2）->(4,2) ->(4,3) ->(3,3)(上次的路径也有这个点) ->(3,4)(上次的路径也有这个点) ->(3，5)，最后到达目标点(2,5)

在A*寻路算法的基础版本中，如果一个节点已经被搜索过一次了，那么我们在后面的搜索中就无需再次处理这个节点了。但是在我们的A＊寻路算法版本中，我们确实再次对搜索过的节点进行处理了。这是因为节点并非完全由x和y坐标进行辨别，还通过了跳跃值进行控制。（这就是前面说的大问题）。

在我们第一次试图找到一条路径的尝试中，节点（3，3）的跳跃值是4。在我们第二次试图找到一条路径的尝试中，节点（3，3）的跳跃值是3。因为在第二次找到路径的尝试里面，这个节点的跳跃值更小，这意味着角色从这个节点出发可以到达比第一次尝试更高的位置。

这基本上意味着跳跃值为4的节点（3，3）和跳跃值为3的节点（3，3）其实是不同的节点。网格为了适应这些差异性需要加入某个坐标来让自己变成三维空间的网格，比如这样：


我们不能简单的把节点（3，3）的跳跃值直接从4变成3，因为某些路径可能会重复使用同一个节点多次。如果我们只是简单粗暴的覆盖了节点之前的跳跃值，那么这显然会打断最终结果的结算，没有办法找到一个到达终点的路径。

如果修改玩家的最大跳跃高度让第一条路径能够到达目标点，其实我们也会遇到同样的问题。如果我们把某个节点的跳跃值用另外一个更小的跳跃值进行覆盖，那么我们就没办法通过节点值的记录复原完整的路径。（也就是虽然我们找到了一条路径到达目标点，但是当我们到达目标点以后，我们没有办法回溯出原始路径来）。

使用网格寻路的优点和缺点

请记住，这是使用基于网格的寻路算法的优缺点。理论上来说，你的游戏和关卡并不一定是这样的。

优点

在基于瓦片的游戏中真的工作的很好。

扩展了基本的A *寻路算法，所以你不需要针对飞行和陆地行走角色分别实现两套完全不同的寻路算法。

在动态地形上工作的很好，不需要一个非常复杂的节点重建过程。

缺点

不够精确：最小距离是一个单元格的大小。

需要对每个地图或者关卡都使用网格表示。

• 引擎和物理需求
• 玩家自由度 vs 算法自由度
  

有一点非常重要，就是角色至少要拥有算法期望的移动自由度，最好比算法期望的还要多一点。

由于网格的离散特性和网格的单元格是有大小的，让人物运动完全匹配算法的约束并不是一个可行的方法。所以我们应该通过算法来找到一条路径如果这条路径存在的话，然后需要你构建物理部分来具体按照路径来移动，这样构建出来的物理系统对我们这样的游戏来说才是可行的。

我在这个教程中使用的方法是让算法适应游戏的物理部分，而不是相反。

算法可能会在边界情况时候发生一些问题，这些问题主要是因为算法期待的玩家移动自由度可能与游戏中真实的玩家移动自由度不是完全匹配。

如果角色移动方面的自由度超出算法的预期会怎么样？

比方说人工智能部分允许角色可以跳6个单元格高，但是游戏的物理部分允许角色可以跳7个单元格高。如果存在一条最快路径，但是要求角色能够跳的更高（也就是要求角色跳7个单元格高那么高才能走这条路径），那么机器人就会忽略这条路径，选择一条更保守的路径，它会觉得要求跳的更高的路径是不可能的。

如果只有那条角色能够跳的更高的路径能到达目标点，而其他路径都倒不了，那么寻路单元就会认为那个目标点不可到达。

如果算法期望的角色移动自由度超出角色实际拥有的移动自动度怎么办？

但是如果反过来，算法认为角色能跳7个单元格高，但是游戏的物理部分只允许角色可以跳6个单元格高，那么机器人就可能沿着一条错误的路径前进，落入一个地方它没有办法出来，或者会再次尝试寻路得到一个同样错误的结果，变成死循环。

（针对这两个问题，最好让游戏的物理部分让角色拥有比算法期待的更多的自由度。）

解决这些问题

确保这个算法总是正确的第一种方法是不让玩家可以修改关卡布局。在这种情况下，你只需要确保你设计或者生成的任何地形能与寻路AI一起良好工作就可以了。

解决这些问题的第二种方案是调整算法、物理或者两个一起调整，来确保算法和物理相匹配。正如我前面提到的，这并不意味着他们需要完全匹配。举个例子来说，如果算法认为角色可以跳5个单元格那么高，那么让角色实际可以跳5.5个单元格那么高也是没问题的。（与算法不同，游戏的物理部分可以使用浮点数。）

依据游戏的不同，AI机器人不能找到存在的路径也许并不是一个很大的问题。它可能就是简单的放弃然后回到出发点，或者就是简单的坐下并等待玩家。

结论

到现在为止，你该对如何让A*算法能够适应平台游戏有一些比较成熟的概念性理解了。在这个教程的下个部分，我们将把这些理解具体化，通过修改一个已存在的A＊算法来把它加入到游戏里！

相关阅读：游戏中常用的寻路算法的分享（1）：A*算法介绍

via：GAD