立即注册，结交更多朋友，享受更多功能^_^
您需要登录才能下载或查看。 还没有帐户？立即注册
在制作游戏时，您是否想创建一些怪物或游戏主角并让他们移动到特定位置并避开墙壁和障碍物？
如果是这样，请查看本教程，我们将展示如何使用 A-Star 寻路算法来实现它！
网上有很多关于 A-star 寻路算法的文章，但大多数都是针对已经了解基本原理的高级开发人员。
本教程将从最基本的原理开始。 我们将通过大量的插图和例子一步步解释A星寻路算法。
无论您使用什么编程语言或操作平台，您都会发现本教程很有帮助，因为它在非编程语言级别解释了算法的原理。 稍后会有教程展示如何在游戏中实现A星算法。
现在找到获取含咖啡因饮料和美味小吃的最短路径并开始吧！ :]
一只寻路猫
让我们想象一个游戏，其中一只猫想要找到通往骨头的路。
“为什么猫想要一根骨头？！” 你可能在想。 在这个游戏中，是一只狡猾的猫想要捡起骨头送给狗，以防止他被咬死！
现在想象一下下图中的猫想要找到到达骨头的最短路径：
不幸的是，猫无法从当前位置直接走到骨头位置，因为有一堵墙挡住了去路，而且它并不是游戏中的鬼猫！
游戏中的猫也很懒，他总是想找到最短的路径，这样回家探望女朋友时就不会太累:-)
但是我们如何编写一个算法来计算猫将走哪条路径呢？ A星算法救了我们！
简化搜索区域
寻路的第一步是将其简化为易于控制的搜索区域。
如何处理取决于游戏。 例如，我们可以将搜索区域划分为像素，但对于我们的基于块的游戏来说，这种粒度太高（不必要）。
相反，我们使用立方体（正方形）作为寻路算法的单位。 其他形状类型也是可能的（例如三角形或六边形），但正方形是最简单且最适合我们的需求的。
这样划分，我们的搜索区域就可以简单地用一个地图大小的二维数组来表示。 所以如果是一个25*25的正方形地图，我们的搜索区域将是一个由625个正方形组成的数组。 如果我们将地图划分为像素，那么搜索区域就是 640,000 个正方形的数组（一个正方形为 32*32 像素）！
现在，我们将当前区域划分为多个正方形来表示搜索空间（在这个简单的示例中，7*6 个正方形 = 42 个正方形）：
打开并列出
现在我们已经创建了一个简单的搜索区域，让我们讨论一下 A-star 算法的工作原理。
除了懒之外，我们的猫记忆力也不好，所以他需要两个列表：
考虑寻找最短路径的所有块的记录（称为开放列表）
被记录并且不会被再次考虑的块（成为列表）
猫首先将当前位置添加到列表中（我们将此起始点称为“A”）。 然后，将与其当前位置相邻的所有可通过的小方块添加到打开列表中。
下图是猫在某个位置时的场景（绿色代表打开列表）：
现在猫需要确定这些选项中哪一个是最短路径，但它如何选择呢？
在A星寻路算法中，每个块都被赋予一个总和值，称为路径增量。 让我们看看它是如何工作的！
路径增量
我们将为每个块赋予一个 G+H 总和值：
您可能还对“移动量”感兴趣。 在游戏中，概念很简单——只是方块的数量。
但是，您可以在游戏过程中调整该值。 例如：
就这样了——现在让我们详细介绍一下如何计算 G 和 H 值。
关于G值
G是从起点A到当前方块的移动量（在本游戏中为方块数）。
为了计算 G 的值，我们需要从它的前一个（前一个方块）中取出它并加 1。 因此，每个块的G值代表从A点到该块形成的路径的总移动量。
例如，下图显示了通往不同骨骼的两条路径，每个方块都标有其 G 值：
关于H值
H值是从当前块到终点的估计移动量（在本游戏中为块数）。
运动估计越接近真实值，最终路径就越准确。 如果估计不起作用，则生成的路径可能不是最短的（但可能很接近）。 这个主题相对复杂，因此我们不会在本教程中介绍它，但我在教程末尾提供了一个网络链接，对其进行了很好的解释。
为了简单起见，我们将使用“曼哈顿距离法”（也称为“曼哈顿距离”或“城市街区距离”），该方法仅计算距 B 点的距离，省略剩余的水平和垂直方块。 障碍物的数量或不同的土地类型。
例如，下图展示了利用“城市街区距离”来估计不同起点到终点的H（黑色文字）的值：
一星算法
现在您已经知道如何计算每个平方的总和（我们称之为 F，等于 G+H），让我们看看 A-star 算法是如何工作的。
猫会重复以下步骤来找到最短路径：
如果您对它的工作原理仍然有点困惑，请不要担心 - 我们将通过示例逐步引导您了解它的工作原理！
猫路
让我们看一个懒猫到达骨头的旅程的例子。
在下图中，我列出了公式 F = G + H 中的每个值，基于：
同时，箭头指示到达相应方块的移动方向。
最后，在每一步，红色方块代表列表，绿色方块代表打开列表。
好的，让我们开始吧！
第一步，猫会确定相对于起始位置（A点）的相邻方格，计算它们的F和值，然后将它们添加到open列表中：
您将看到每个方格都列出了一个 H 值（两个是 6，一个是 4）。 我建议根据“城市街区距离”计算街区的相对值，并确保您了解其工作原理。
另请注意，F 值（左上角）是 G（左下）值和 H（右下）值之和。
第二步，猫选择F和最小的方格，将其添加到列表中，然后检索其相邻方格的关联值。
现在你会看到增量最小的块是F值为4的块。猫尝试将所有相邻的块添加到打开列表中（然后计算它们的总和），但猫自己的块无法添加（因为它已经被添加到列表中）或者它是一个墙块（因为它无法访问）。
请注意，添加到打开列表中的两个新块的 G 值增加了 1，因为它们现在距离起点有 2 个块。 您可能需要再次计算“城市街区距离”，以确保您了解每个新街区的 H 值。
第三步，我们再次选择F和值最小的方格（5），继续重复前面的步骤：
现在，只有一个可能的块被添加到打开列表中，因为关闭列表中已经存在一个相邻块，另外两个是墙块。
步骤 4. 现在我们遇到了一个有趣的情况。 正如您之前看到的，有 4 个带有 F 且值为 7 的方格 - 我们该怎么办？ ！
可以使用多种解决方案，但最简单（最快）的方法是继续跟踪最近添加到打开列表中的块。 现在继续沿着最近添加的块前进。
这次有两个可以通过的相邻块，我们仍然像以前一样计算它们的和。
步骤5：然后我们选择总和值最小的方格（7），继续重复前面的步骤：
我们已经接近终点了！
第6步，你现在已经训练好了！ 我打赌你可以猜到下一步是这样的：
我们快要结束了，但是这次您会看到我们有两条到达骨骼的最短路径可供选择：
在我们的示例中，有两条最短路径：
这与我们选择哪一个无关，这取决于代码。
选择哪一个并不重要，现在是时候用代码实际实现它了。
第七步，让我们重复从其中一个方块开始的步骤：
啊哈，骨头在开放列表中！
步骤 8. 现在目标块位于打开列表中，算法会将其添加到列表中：
然后算法所要做的就是返回并计算最终路径！
一只有远见的猫
在上面的例子中，我们看到，当猫寻找最短路径时，它通常会选择更好的方格（位于其未来最短路径上的方格）——就好像它是一只有先见之明的猫一样！
但是，如果猫是盲人并且总是选择添加到其列表中的第一个方块，会发生什么呢？
下图显示了搜索过程中将使用的所有块。 你会看到猫尝试了更多的方块，但它仍然找到最短路径（不是前一条，而是另一条等效路径）：
图中的红色方块并不代表最短路径，它们只是代表在某个时刻被选为“S”的方块。
我建议您查看上图并尝试以下步骤。 无论这次你看到哪个相邻街区，都选择“最差”的路线。 你会发现你终于找到了最短路径！
所以你可以看到，沿着“错误”的方格走是没有问题的，经过多次重复尝试后你仍然会找到最短路径。
所以在我们的实现中，我们会按照下面的算法将区块添加到open链表中：
以下为原路线返回示意图：
最短路径是从终点出发，逐步返回起点而形成的（例如：在终点处我们可以看到箭头指向右侧，因此该块的前一个块在其左侧）。
