关于寻路算法的一些思考（1）：A*算法介绍
英文原文： Amit’s Thoughts on Pathfinding
物体的移动算法似乎显得很简单，然而寻路规划问题却十分复杂。考虑下面这个例子：
这个单位的初始位置在地图的下方，想要到达地图的顶部。如果物体所能侦测到的地方（粉色部分所示）并没有障碍，那么物体就会直接向上走到它的目 标位置。但在距离顶端较近的位置时，物体侦测到了障碍，因而改变了方向。该物体将不得不行进一个“U”形的路径绕过障碍物（如红色路径所示）。通过对比可 知，寻路系统能够通过搜索一个更大的范围（如蓝色区域所示），并寻找一个更短的路线（如蓝色路径所示），使物体避免绕这条由凹陷障碍物造成的远路。
当然，可以通过改进物体的移动算法解决上图所示的陷阱。即要么避免在地图上创建有凹陷的物体，要么标记整个凹陷物体的整个凸包为危险区域（即除非目标在该区域内，否则避免进入该区域），如下图所示：
而寻路系统则会让路径的决定提前，而不是像上图一样，物体直到移动到最后一刻才发现问题所在。对于“改进物体移动算法”和“使用寻路系统规划路 径”两种方式有以下的折中：规划路径一般来说更慢，但效果更好；改进移动算法则会快一些，但有时候会卡住。如果游戏地图经常改变，那么路径规划的方式可能 就意义不大了。我建议两者都使用：在更大的尺度、缓慢变换的地图和更长的路径上进行寻路规划，而对于局部区域、快速更改的地图和短的路径则使用改进的物体 移动算法。
算法
普通教科书上的寻路算法往往只应用在数学意义上的“图”上，即由顶点集合和边集合互相连接组成的结构。因此我们需要将一个栅格化的游戏地图转化为一个“图”：地图上的每一格可以作为一个顶点，而相邻的格子则各有一条边，如图所示：
我们只考虑二维网格。如果你没有关于图的背景知识，可以参见此链接。之后我会讨论如何在游戏世界中创建其他类型的图。
大部分在 AI 和算法领域的寻路算法都是针对作为数学结构的“图”本身，而并非针对这种网格化游戏地图。我们希望寻找一种能利用游戏地图自身特征的方法。其实有些在二维 网格图中我们认为是常识的事情，一些在普通图上使用的寻路算法本身可能并没有考虑到，例如如果两个物体距离较远，那么可能从一个物体到另一个物体的移动的 时间和路径会较长（当然，假设空间中没有虫洞存在）。对于方向来说，如果方向是朝东，那么最优路径的路径也应当是大体往东走，而不是向西去。在网格中还可 以从对称中获取信息，即先向北再向西，大部分情况下和先向西再向北等价。这些额外的信息可以让寻路算法更加快速。
Dijkstra 算法和最好优先搜索(best-first search)
Dijkstra 算法简单说来，就是从起始点访问其他临近节点，并将该节点加入待检查节点集合中，使用松弛算法更新待检查节点的路径长度值。只要图不存在负权值的 边，Dijkstra 算法能够确保找到最短路径。在下面的图中，粉色的方格为起始点，蓝紫色的方格为目标点，青绿色的方格则为 Dijkstra 算法所扫描的节点。淡色的节点是距离起始点较远的节点。
贪心最好优先搜索算法大体与之类似，不同的是该算法对目标点的距离有一个估计值（启发值）。该算法并不在待检查节点集合中选取距离起始点近的节 点进行下一步的计算，而是选择距离目标点近的节点。贪心最好优先搜索算法并不能保证寻找到最优路径，然而却能大大提高寻路速度，因为它使用了启发式方法引 导了路径的走向。举例来说，如果目标节点在起始点的南方，那么贪心最好优先搜索算法会将注意力集中在向南的路径上。下图中的黄色节点指示了具有高启发值的 节点（即到目标节点可能花费较大的节点），而黑色则是低启发值的节点（即到目标节点的花费较小的节点）。下图说明了相比于 Dijkstra 算法，贪心最好优先算法能够更加快速地寻路。
然而上述的例子仅仅是最简单的：即地图上没有障碍物。考虑前文中我们曾经提到的凹陷障碍物，Dijkstra 算法仍然能够寻找到最短路径：
贪心最好优先算法虽然做了较少的计算，但却并不能找到一条较好的路径。
问题在于最好优先搜索算法的贪心属性。由于算法仅仅考虑从目前节点到最终节点的花费，而忽略之前路径已经进行的耗费，因此即使在路径可能错误的情况下仍然要移动物体。
1968 年提出的A*算法结合了贪心最好优先搜索算法和 Dijsktra 算法的优点。A*算法不仅拥有发式算法的快速，同时，A*算法建立在启发式之上，能够保证在启发值无法保证最优的情况下，生成确定的最短路径。
A*算法
下面我们主要讨论A*算法。A*是目前最流行的寻路算法，因为它十分灵活，能够被应用于各种需要寻路的场景中。
与 Dijkstra 算法相似的是，A*算法也能保证找到最短路径。同时A*算法也像贪心最好优先搜索算法一样，使用一种启发值对算法进行引导。在刚才的简单寻路问题中，它能够像贪心最好优先搜索算法一样快：
而在后面的具有凹陷障碍物的地图中，A*算法也能够找到与 Dijkstra 算法所找到的相同的最短路径。
该算法的秘诀在于，它结合了 Dijkstra 算法使用的节点信息（倾向于距离起点较近的节点），以及贪心最好优先搜索算法的信息（倾向于距离目标较近的节点）。之后在讨论A*算法时，我们使用 g(n)表示从起点到任意节点n的路径花费，h(n)表示从节点n到目标节点路径花费的估计值（启发值）。在上面的图中，黄色体现了节点距离目标较远，而 青色体现了节点距离起点较远。A*算法在物体移动的同时平衡这两者的值。定义f(n)=g(n) +h(n)，A*算法将每次检测具有最小f(n)值的节点。