A*算法介绍

单个物体的移动似乎很容易。 寻路很复杂。 为什么要烦恼寻找路径？ 考虑以下情况：

该单位最初位于地图的底部，并希望到达顶部。 它扫描的区域中没有任何东西（以粉红色显示）表示该装置不应向上移动，因此它继续前进。 在顶部附近，它会检测到障碍物并改变方向。 然后它沿着红色路径绕过“U”形障碍物。 相比之下，探路者将扫描更大的区域（以浅蓝色显示），但发现较短的路径（蓝色），从不将该单元送入凹形障碍物。

但是，您可以扩展移动算法以解决上面显示的陷阱问题。 要么避免产生凹陷的障碍物，要么将它们的凸包标记为危险（只有在目标位于内部时才进入）：

探路者让你提前计划，而不是等到最后一刻发现有问题。 在计划与寻路器之间以及与运动算法作出反应之间存在权衡。 规划通常较慢，但效果更好; 运动通常更快，但可能会卡住。 如果游戏世界经常变化，那么提前计划就不那么有价值了。 我建议同时使用：寻找大图片，缓慢改变障碍物和长路径; 和局部区域的运动，快速变化和短路径。

Algorithms

计算机科学教科书中的寻路算法在数学意义上的图形上工作 - 一组边缘连接它们。 平铺的游戏地图可以被视为图形，其中每个图块是顶点，并且在彼此相邻的图块之间绘制边缘：

现在，我将假设我们正在使用二维网格。如果您之前没有使用图表，请参阅此入门手册。稍后，我将讨论如何从游戏世界中构建其他类型的图形。

来自AI或算法研究的大多数寻路算法都是针对任意图形而不是基于网格的游戏而设计的。我们想找到一些可以利用游戏地图性质的东西。我们认为有些事情是常识，但算法并不理解。我们对距离有所了解：一般来说，当两个东西相距较远时，假设没有虫洞，则需要更长时间才能从一个移动到另一个。我们对方向有所了解：如果您的目的地在东方，那么走向东方比走向西方更有可能找到最佳路径。在网格上，我们知道关于对称性的东西：大多数时候，向北移动然后向东移动与向东移动然后向北移动相同。这些附加信息可以帮助我们更快地运行寻路算法。

Dijkstra’s Algorithm and Best-First-Search

Dijkstra的算法通过从对象的起点开始访问图中的顶点来工作。 然后，它重复检查最近的尚未检查的顶点，将其顶点添加到要检查的顶点集。 它从起点向外扩展，直到达到目标。 Dijkstra的算法保证找到从起点到目标的最短路径，只要没有边缘具有负成本。 （我写的是“最短路径”，因为通常存在多个等效短路径。）在下图中，粉红色方块是起点，蓝色方块是目标，蓝绿色区域显示Dijkstra算法扫描的区域。 最轻的蓝绿色区域距离起点最远，因此形成了探索的“前沿”：

Greedy Best-First-Search算法以类似的方式工作，除了它有一些估计（称为启发式），距目标的任何顶点有多远。 它不是选择最接近起点的顶点，而是选择最接近目标的顶点。 贪心Best-First-Search无法保证找到最短的路径。 然而，它比Dijkstra算法运行得快得多，因为它使用启发式函数非常快速地引导它朝向目标。 例如，如果目标位于起始位置的南边，则Greedy Best-First-Search将倾向于关注向南的路径。 在下图中，黄色表示具有高启发式值（达到目标的高成本）的节点，黑色表示具有低启发式值的节点（达到目标的低成本）。 它表明，与Dijkstra的算法相比，Greedy Best-First-Search可以非常快速地找到路径：

然而，这两个例子都说明了最简单的情况 - 当地图没有障碍物时，最短路径确实是一条直线。 让我们考虑上一节中描述的凹陷障碍。 Dijkstra的算法更加努力，但保证找到最短的路径：

另一方面，贪婪的Best-First-Search做的工作较少，但其路径显然不太好：

麻烦的是贪婪的Best-First-Search是“贪婪的”，并试图朝着目标前进，即使它不是正确的道路。 因为它只考虑到达目标的成本而忽略了到目前为止的路径成本，所以即使它所使用的路径变得非常长，它也会继续前进。

将两者中最好的结合起来不是很好吗？ A *是在1968年开发的，用于结合启发式方法，如Greedy Best-First-Search和Dijsktra算法等形式方法。 这有点不寻常，因为启发式方法通常会为您提供一种解决问题的近似方法，而无法保证您获得最佳答案。 但是，A *建立在启发式的基础之上，虽然启发式本身并不能保证，但A *可以保证最短的路径。

The A* Algorithm

我将专注于A *算法。 A *是最常用的寻路选择，因为它非常灵活，可以在各种环境中使用。

A *就像Dijkstra的算法一样，它可以用来找到最短的路径。 A *就像Greedy Best-First-Search一样，它可以使用启发式来指导自己。 在简单的情况下，它与Greedy Best-First-Search一样快：

在具有凹陷障碍物的示例中，A *找到与Dijkstra算法找到的路径一样好的路径：

它成功的秘诀在于它结合了Dijkstra算法使用的信息（支持接近起点的顶点）和Greedy Best-First-Search使用的信息（支持接近目标的顶点）。在谈论A *时使用的标准术语中，g（n）表示从起点到任何顶点n的路径的精确成本，而h（n）表示从顶点n到目标的启发式估计成本。在上图中，黄色（h）表示远离目标的顶点，而蓝绿色（g）表示远离起点的顶点。 A *在从起点移动到目标时平衡两者。每次通过主循环，它检查具有最低f（n）= g（n）+ h（n）的顶点n。

本文的其余部分将探讨启发式设计，实现，地图表示以及与在游戏中使用寻路的相关的各种其他主题。有些部分很发达，有些则相当不完整。