学习首页/图算法/A* 寻路交互演示 · JavaScript

代码与动画 A STAR PATHFINDING

A* 寻路.

按已走步数与到终点的估计步数之和，选择下一格进行扩展。

四方向移动 · 每步成本 1曼哈顿距离启发式线性选择候选格

原理与执行逻辑

用 f = g + h 评估候选格：g 是已知的起点到该格路径成本，h 是该格到终点的估计成本。优先扩展 f 最小的候选，更新邻格距离与前驱。

执行步骤

  1. 起点以 g = 0 加入候选集，使用曼哈顿距离计算 h。
  2. 选出 f 最小的格子，若为终点则沿前驱还原路径。
  3. 将当前格移入已确定集合，检查四方向可通行邻格。
  4. 发现更小的 g 时更新距离与前驱并加入候选；候选耗尽则无路径。

关键理解

四方向、每步成本 1 时，曼哈顿距离不会高估且满足一致性，所以已确定格无需重开。障碍会增加实际路程，h 仍只作为估计。

简短示例

从 (0,0) 到 (2,2)，起点 h = 4；走到 (0,1) 后 g = 1、h = 3、f = 4。遇到障碍时实际路径可能超过 4 步。

代码与执行动画

STEP 0 / 63
A* 寻路
function astar(grid) {  const rows = grid.length, cols = grid[0].length, goal = rows * cols - 1;  const h = v => rows - 1 - Math.floor(v / cols) + cols - 1 - v % cols;  const open = new Set([0]), closed = new Set(), previous = new Map(), g = new Map([[0, 0]]);  while (open.size) {    const node = [...open].sort((a, b) => g.get(a) + h(a) - g.get(b) - h(b))[0];    if (node === goal) {      const path = []; for (let v = goal; v !== undefined; v = previous.get(v)) path.push(v);      return path.reverse();    }    open.delete(node); closed.add(node);    const r = Math.floor(node / cols), c = node % cols;    for (const [nr, nc] of [[r-1,c], [r+1,c], [r,c-1], [r,c+1]]) {      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] === '#') continue;      const next = nr * cols + nc;      if (closed.has(next)) continue;      const candidate = g.get(node) + 1;      if (candidate < (g.get(next) ?? Infinity)) {        g.set(next, candidate); previous.set(next, node); open.add(next);      }    }  }  return [];}
24 行 · 0 个片段标记
Sg0 h8·····###····#··#·······G
当前数据正在操作已访问 / 命中标记 / 指针
0

初始化起点

格内数字是 f = g + h，格下显示 g 与 h；粉色候选等待扩展，绿色格已确定。

配置演示数据

应用后重新生成执行过程，可单步观察结果。

实现说明

A* 寻路的操作规则

S 为左上角起点，G 为右下角终点，# 为障碍。f = g + h，曼哈顿距离在本模型中满足一致性；已确定格无需重开。线性候选扫描的最坏时间 O(V²)，空间 O(V)。

对应题目与扩展练习

观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。