移动单个对象似乎很容易。寻路很复杂。为什么要麻烦寻路？
考虑以下情况：
该单位最初位于地图底部并希望到达顶部。它扫描的区域（以粉红色显示）中没有任何东西表明该单元不应向上移动，因此它会继续前进。在顶部附近，它检测到障碍物并改变方向。然后它沿着红色路径绕过“U”形障碍物。相比之下，探路者会扫描更大的区域（以浅蓝色显示），但会发现更短的路径（蓝色），永远不会将单位送入凹形障碍物。
但是，您可以扩展移动算法以解决上面显示的陷阱。要么避免创建凹形障碍物，要么将它们的凸形外壳标记为危险（仅当目标在内部时才进入）：
探路者让您提前计划，而不是等到最后一刻才发现问题。在使用探路者进行规划和使用运动算法做出反应之间需要进行权衡。计划通常较慢，但会产生更好的结果；移动通常更快，但可能会卡住。如果游戏世界经常变化，那么提前计划就没有那么重要了。我建议同时使用两者：大图寻路、缓慢变化的障碍物和长路径；和局部区域的移动、快速变化和短路径。
算法#
我已经写了这一页的更新版本，但没有写其余的页面。它有交互式图表和示例代码。
计算机科学教科书中的寻路算法处理数学意义上的图——一组顶点，边连接它们。一个平铺的游戏地图可以被认为是一个图，每个图块是一个顶点，边绘制在彼此相邻的图块之间：
现在，我假设我们使用的是二维网格。如果您以前没有使用过图表，请参阅此入门指南。稍后，我将讨论如何在您的游戏世界中构建其他类型的图表。
大多数来自 AI 或算法研究的寻路算法都是为任意图而不是基于网格的游戏而设计的。我们想找到可以利用游戏地图性质的东西。有些事情我们认为是常识，但算法不理解。我们对距离有一些了解：一般来说，当两个物体相距更远时，假设没有虫洞，从一个物体移动到另一个物体需要更长的时间。我们对方向有所了解：如果您的目的地是东边，那么向东步行比向西步行更有可能找到最佳路径。在网格上，我们对对称性有所了解：大多数情况下，先北后东与先东后北移动相同。这些附加信息可以帮助我们使寻路算法运行得更快。
Dijkstra 算法和最佳优先搜索#
Dijkstra 算法的工作原理是从对象的起点开始访问图中的顶点。然后它反复检查最近的尚未检查的顶点，将其顶点添加到要检查的顶点集中。它从起点向外扩展，直到到达目标。Dijkstra 算法可以保证找到从起点到目标的最短路径，只要所有边都没有负成本。（我写“最短路径”是因为通常有多个等效的短路径。）在下图中，粉红色方块是起点，蓝色方块是目标，青色区域显示 Dijkstra 算法扫描的区域。最浅的青色区域是离起点最远的区域，因此形成了探索的“前沿”：
Greedy Best-First-Search 算法以类似的方式工作，不同之处在于它对任何顶点距目标的距离有一些估计（称为启发式）。它不是选择离起点最近的顶点，而是选择离目标最近的顶点。贪婪的最佳优先搜索不是保证找到最短路径。但是，它比 Dijkstra 算法运行得快得多，因为它使用启发式函数非常快速地引导其朝着目标前进。例如，如果目标是起始位置的南边，Greedy Best-First-Search 将倾向于关注通往南边的路径。在下图中，黄色代表具有高启发值（达到目标的成本高）的节点，黑色代表具有低启发值（达到目标的成本低）的节点。它表明与 Dijkstra 算法相比，Greedy Best-First-Search 可以非常快速地找到路径：
然而，这两个例子都说明了最简单的情况——地图上没有障碍物，最短路径确实是一条直线。让我们考虑上一节中描述的凹形障碍物。Dijkstra 的算法工作更努力，但保证找到最短路径：
另一方面，Greedy Best-First-Search 做的工作较少，但它的路径显然没有那么好：
问题在于贪婪的最佳优先搜索是“贪婪的”，即使它不是正确的路径，也会试图朝着目标前进。由于它只考虑到达目标的成本，而忽略了到目前为止的路径成本，因此即使它所走的路径变得很长，它也会继续前进。
将两者的优点结合起来不是很好吗？A* 于 1968 年开发，结合了诸如贪心最佳优先搜索之类的启发式方法和 Dijsktra 算法之类的形式化方法。这有点不寻常，因为启发式方法通常会为您提供解决问题的近似方法，但不能保证您得到最佳答案。但是，A* 是建立在启发式之上的，虽然启发式本身并不能保证，但 A*可以保证最短路径。
A* 算法#
我将专注于A* 算法。A* 是最流行的寻路选择，因为它相当灵活，可以在广泛的上下文中使用。
A* 类似于 Dijkstra 算法，因为它可以用来寻找最短路径。A* 类似于 Greedy Best-First-Search，因为它可以使用启发式方法来引导自己。在简单的情况下，它与 Greedy Best-First-Search 一样快：
在具有凹形障碍物的示例中，A* 找到了与 Dijkstra 算法找到的路径一样好的路径：
其成功的秘诀在于它结合了 Dijkstra 算法使用的信息片段（偏好靠近起点的顶点）和贪婪最佳优先搜索使用的信息（偏好靠近目标的顶点）。在谈论 A* 时使用的标准术语中，g(n)表示从起点到任何顶点的路径的确切成本n，并h(n)表示从顶点到目标的启发式估计成本n。在上图中，黄色 ( h) 代表远离目标的顶点和青色 (g) 表示远离起点的顶点。A* 在从起点移动到目标时平衡了两者。每次通过主循环时，它都会检查n具有最低的顶点f(n) = g(n) + h(n)。
本文的其余部分将探讨启发式设计、实现、地图表示以及与在游戏中使用寻路相关的各种其他主题。有些部分发展得很好，而另一些则相当不完整。