A* 搜索算法：游戏和 AI 中的寻路

1. 什么是 A* 算法？

A*（发音为 "A-Star"）算法是一种图遍历和路径搜索算法，由于其完备性、最优性和最佳效率，在计算机科学中被广泛使用。它由斯坦福研究所的 Peter Hart, Nils Nilsson 和 Bertram Raphael 于 1968 年发明，最初旨在帮助 Shakey 机器人在房间内导航。

如今，A* 算法是路由和寻路的绝对行业标准。无论策略游戏中的角色是在网格上行走，还是 GPS 正在计算穿越全国的最快路线，A*（或其变体）都可能在承担繁重的工作。

2. Dijkstra 算法的问题

要了解为什么 A* 如此出色，我们必须首先了解它改进了什么。在 A* 之前，寻找最短路径的黄金标准是 Dijkstra 算法。

Dijkstra 算法保证能找到最短路径。然而，它从根本上说是“盲目”的。当你要求 Dijkstra 寻找从纽约到洛杉矶的路径时，它探索通向波士顿、迈阿密和芝加哥的道路的热情，与探索向西行驶的道路的热情一样高。它在一个完美的圆（或球体）中向外搜索，在所有方向上均等地搜索，直到它偶然遇到目标。

在一张大地图上，探索每一个可能的方向慢得令人难以置信，并且浪费了大量的处理能力。我们需要一种足够“聪明”的算法，知道目标在哪个方向，这样它就可以优先探索 朝向 目标的路径。

3. 秘诀：启发式方法 (f = g + h)

A* 通过引入启发式方法 (Heuristic) 来解决“盲目性”问题。启发式是一种有根据的猜测。在寻路中，它是一个估计节点距离最终目的地有多远的函数。

A* 为它发现的每个节点分配一个分数。分数最低的节点是它接下来要探索的节点。A* 的核心公式是：

• n 是图上当前正在评估的节点。
• g(n) 是 实际成本 (Exact Cost)。它是从起始节点到节点 n 的已知距离。（这正是 Dijkstra 使用的）。
• h(n) 是 启发式估计 (Heuristic Estimate)。它是从节点 n 到最终目标的估计距离。
• f(n) 是 总成本 (Total Cost)。这是 g 和 h 的总和。A* 总是优先处理 f 分数最低的节点。

通过添加 h(n) 组件，A* 就像被磁铁吸引一样被拉向目标。它将忽略与目标方向相反的路径，与 Dijkstra 算法相比，大大减少了搜索空间。

4. 选择正确的启发式方法

A* 的魔力完全取决于启发式函数 h(n) 的准确性。如果你的启发式方法高估了到目标的距离，A* 就不再能保证找到最短路径。如果它低估了距离，它就会变慢。因此，为你特定的游戏或地图选择正确的启发式方法至关重要。

曼哈顿距离 (适用于没有对角线的网格世界)

如果您的游戏使用网格（如吃豆人或传统的 roguelike），并且角色只能向上、向下、向左或向右移动，则应使用曼哈顿距离。它计算当前节点和目标之间水平和垂直块的总数。

function heuristic(node, goal) {
    return abs(node.x - goal.x) + abs(node.y - goal.y)
}

欧几里得距离 (适用于开放世界或任意角度移动)

如果角色可以在任何方向上移动（或者如果你在连续的地图上进行路由），你应该使用欧几里得距离。这是使用勾股定理计算的两点之间的直线“直线”距离。

function heuristic(node, goal) {
    return sqrt((node.x - goal.x)^2 + (node.y - goal.y)^2)
}

切比雪夫距离 (适用于有对角线的网格世界)

如果您的游戏使用网格但允许对角线移动（其中对角线移动的成本与直线移动的成本相同），您可以使用切比雪夫距离。它取水平或垂直差异的最大值。

function heuristic(node, goal) {
    return max(abs(node.x - goal.x), abs(node.y - goal.y))
}

5. A* 的逐步执行

以下正是该算法在执行过程中如何维护其状态和处理节点的：

1. 初始化： 创建两个集合：一个 OPEN 集合（要评估的节点）和一个 CLOSED 集合（已评估的节点）。将起始节点添加到 OPEN 集合。
2. 循环开始： 在 OPEN 集合中找到 f 成本最低的节点。我们称其为 Current（当前）节点。
3. 检查目标： 如果 Current 节点是目标，您就完成了！向后跟随父指针以重建路径。
4. 移动到 Closed： 从 OPEN 集合中删除 Current 节点，并将其添加到 CLOSED 集合中。
5. 扩展邻居： 查看 Current 节点的所有相邻邻居。对于每个邻居：
   • 如果邻居是障碍物（墙）或在 CLOSED 集合中，则忽略它。
   • 计算邻居的 g 成本（当前的 g + 到邻居的距离）。
   • 如果邻居不在 OPEN 集合中，则计算其 h 和 f 成本，将其父级设置为 Current，并将其添加到 OPEN 集合中。
   • 如果邻居已经在 OPEN 集合中，请检查这条到邻居的新路径是否更好（具有更低的 g 成本）。如果是，请更新其父级和 g 成本。
6. 重复： 循环回到第 2 步。如果 OPEN 集合变为空且尚未达到目标，则没有有效路径。

6. 游戏开发和 AI 中的实际应用

A* 是数字空间中移动的骨干。

• 实时战略 (RTS) 游戏： 当你在《星际争霸》或《帝国时代》中拖动选择 50 个单位并点击地图上的一个点时，A* 会计算出 50 条独立的路径，引导它们绕过建筑物、河流以及彼此。（通常利用诸如流场或分层 A* 等专业变体）。
• RPG 和潜行游戏： NPC 使用“NavMesh”（导航网格 - 一种可行走表面的简化图）上的 A* 来追逐玩家、在走廊中巡逻或寻找掩体。
• 机器人技术： 自动化仓库机器人（如亚马逊使用的机器人）使用 A* 在工厂车间导航，而不会与货架单元或其他机器人发生碰撞。
• GPS 导航： 虽然标准 A* 对于大陆地图来说太慢了，但修改版本（例如 ALT - 具有地标和三角不等式的 A*）用于快速计算最佳驾驶路线。