A* 寻路算法：启发式搜索与游戏导航

FreeGuideOnline 最新 2026-06-18

什么是 A* 寻路算法

A*（读作 A-Star）是一种在图形平面上，有多个节点的路径中，寻找最低通过代价的算法。它结合了 Dijkstra 算法 的可靠性与 最佳优先搜索（BFS） 的启发式速度，被广泛应用于游戏中的角色导航、机器人路径规划、地图路线计算等场景。

A* 的核心思想是：在搜索时，算法会同时考虑已走过的实际代价与预估到终点的剩余代价，从而更有方向性地逼近目标，避免无效的盲目搜索。

核心概念与代价函数

节点与代价

一个寻路网格通常由节点（格子或路点）构成。从一个节点移动到相邻节点需要付出代价，例如距离、时间、消耗等。

A* 为每个节点分配一个评估值 f(n)，其计算公式为：

f(n) = g(n) + h(n)
  • g(n)：从起点到当前节点 n 的实际代价（已走过的路程）。
  • h(n)：从当前节点 n 到终点的启发式预估代价（预计剩余路程）。这个函数必须由开发者针对应用场景设计。
  • f(n)：节点 n 的综合代价，算法每次都优先探索 f(n) 最小的节点。

如果 h(n) 永远不大于实际剩余代价（即满足容许性），则 A* 一定能找到最优路径；如果 h(n) 还满足三角形不等式（即一致性），搜索效率会进一步提高。

A* 算法步骤

下面以常见的二维网格（允许四方向或八方向移动）为例，说明 A* 的标准流程。

1. 初始化

  • 创建开放列表（Open List） 和关闭列表（Closed List）。
  • 将起点加入 Open List，设置 g=0，计算 h 和 f。
  • Closed List 为空。

2. 主循环

只要 Open List 不为空，重复以下步骤：

  1. 取出当前最优节点
    从 Open List 中找出 f(n) 最小的节点，记为 当前节点。若该节点正好是终点，则寻路成功，从终点回溯父节点生成路径。

  2. 移入 Closed List
    将当前节点从 Open List 中移除，加入 Closed List，表示该节点已处理完毕。

  3. 遍历邻居节点
    对当前节点的每个邻居节点执行：

    • 忽略不可通行的节点（例如障碍物）。
    • 若邻居已在 Closed List 中，跳过。
    • 计算从起点经当前节点到该邻居的新 g 值：tentative_g = g(current) + 从 current 到此邻居的移动代价。
    • 如果该邻居不在 Open List 中，则将其加入 Open List，设置其父节点为当前节点，并计算 g、h、f。
    • 如果该邻居已在 Open List 中，但新的 tentative_g 比其已有的 g 值更小，则更新该邻居的 g、f 值，并重新设置父节点。

3. 寻路失败

如果 Open List 为空仍未找到终点，说明起点与终点之间没有可达路径。

如何设计启发式函数 h(n)

启发函数的选择直接影响寻路性能与路径质量。以下为几种常见形式（均以网格为例，设当前节点坐标 (x1, y1)，终点坐标 (x2, y2)）。

曼哈顿距离（Manhattan Distance）

适用于仅允许四方向移动（上、下、左、右）的网格。

h = |x1 - x2| + |y1 - y2|

该启发式满足容许性，因为在不允许斜向移动时，实际最短路径长度不可能小于曼哈顿距离。

对角距离（Diagonal Distance）

适用于允许八个方向移动（含斜对角）的网格。

dx = |x1 - x2|
dy = |y1 - y2|
h = max(dx, dy) + (√2 - 1) * min(dx, dy)

或直接使用近似代价，如将斜向移动代价设为 14（√2≈1.414 的整数倍），直线代价 10：

h = 10 * (dx + dy) + (14 - 2*10) * min(dx, dy)

这也是一种常用且容许的启发式。

欧几里德距离（Euclidean Distance）

适用于可以任意方向移动的连续空间。

h = √((x1 - x2)² + (y1 - y2)²)

在网格寻路中直接使用平方根可能导致数值性能问题，且如果移动仅限于网格方向，它可能产生非最优路径（因为 h 可能高估剩余代价）。可以将其乘以一个系数使其更保守，或用平方形式（但平方形式不满足容许性）。

可视化实现示例（伪代码）

以下伪代码使用八方向移动、对角距离启发式，帮助理解程序结构。

function AStar(start, goal):
    openList = PriorityQueue()
    openList.add(start, f(start))
    cameFrom = empty map
    gScore[start] = 0

    while openList is not empty:
        current = openList.pop()   // 获取 f 值最小的节点
        if current == goal:
            return reconstructPath(cameFrom, current)

        for each neighbor in getNeighbors(current):
            if neighbor is not passable:
                continue
            tentative_g = gScore[current] + distance(current, neighbor)
            if neighbor not in gScore or tentative_g < gScore[neighbor]:
                gScore[neighbor] = tentative_g
                fScore = tentative_g + heuristic(neighbor, goal)
                openList.add(neighbor, fScore)
                cameFrom[neighbor] = current

    return failure

优化与常见问题

数据结构优化

  • 开放列表使用优先队列（最小堆） 可高效获取最小 f 值节点。
  • 为避免重复搜索，可配合使用哈希集快速判断节点是否在开放/关闭列表中。
  • 对于大型网格，使用分层寻路、导航网格（NavMesh） 或跳点搜索（JPS） 等进阶技术能够显著降低搜索空间。

启发式权重调整

在某些实时应用（如游戏）中，可以动态调整启发式以牺牲路径最优性换取速度：

f(n) = g(n) + w * h(n)
  • w = 1 时为标准 A*。
  • w > 1 会加快搜索速度，但可能得到次优路径。
  • w 非常大数据退化为贪心最佳优先搜索。
  • w = 0 退化为 Dijkstra 算法。

多种地形代价

当不同格子具有不同移动成本（例如沼泽、道路），可在 g(n) 计算时加权：移动代价 = 基础距离 × 地形权重。只要权重非负，算法仍然正确。

动态障碍与重寻路

若环境动态变化，可在障碍出现后执行增量寻路（如 D* Lite），或简单地在检测到路径受阻时重新运行 A*。

游戏导航中的实际应用

A* 不仅是独立算法，更是现代游戏 AI 的核心组件：

  • 路径平滑：A* 生成的路径往往紧贴网格，存在尖锐折角。可通过线平滑（Line of Sight 优化） 或 贝塞尔曲线 进一步美化轨迹。
  • 分层寻路：大地图先以粗略路径点寻路，再局部细化，避免节点爆炸。
  • 群体寻路：结合流场、转向行为等技术，使大量单位高效移动而不碰撞。

掌握 A* 的原理与调优技巧，你便能应对从 2D 回合制游戏到 3D 开放世界的各种导航挑战。