纯前端实现 A* 寻路可视化：二叉堆、启发式设计与逐帧渲染

A* 是路径规划里最常被提起的算法之一，但真正动手写的时候，难点往往不在公式，而在几个工程细节：优先队列怎么选、启发式怎么调、搜索过程怎么画出来。这篇文章用一个纯前端的网格演示，把这三件事拆开讲清楚。

一、先把网格变成图

可视化里的地图就是一个二维数组，0 表示可走，1 表示障碍。每个格子是一个节点，四方向连通时最多有 4 条出边。为了不额外建图，我把邻居计算写成按需展开：

const DIRS_4 = [[1,0],[-1,0],[0,1],[0,-1]];

function neighbors(grid, x, y) {
  const out = [];
  for (const [dx, dy] of DIRS_4) {
    const nx = x + dx, ny = y + dy;
    if (nx < 0 || ny < 0) continue;
    if (nx >= grid.cols || ny >= grid.rows) continue;
    if (grid.cells[ny * grid.cols + nx] === 1) continue;
    out.push([nx, ny]);
  }
  return out;
}

用一维数组存格子，索引是 y * cols + x。这样做的好处不只是省内存，更重要的是让每个节点有稳定的整数 id，后面用数组做堆和访问标记都更方便。

二、开放集为什么用最小堆

A* 每一轮都要取出 f 值最小的节点。用数组线性扫描是 O(n)，网格一大就会明显卡顿；用二叉堆可以把取最小值和插入都压到 O(log n)。手写一个只支持 push / pop 的二叉堆，比引入优先队列库更轻：

class MinHeap {
  constructor() { this.a = []; }
  push(node) {
    const a = this.a;
    a.push(node);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p].f <= a[i].f) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop() {
    const a = this.a;
    const top = a[0];
    const last = a.pop();
    if (a.length) {
      a[0] = last;
      let i = 0;
      for (;;) {
        const l = i * 2 + 1, r = l + 1;
        let m = i;
        if (l < a.length && a[l].f < a[m].f) m = l;
        if (r < a.length && a[r].f < a[m].f) m = r;
        if (m === i) break;
        [a[m], a[i]] = [a[i], a[m]];
        i = m;
      }
    }
    return top;
  }
  get size() { return this.a.length; }
}

这里有意不做 decrease-key。节点被重新发现更短路径时，直接再 push 一份新记录，弹出时用「已访问」标记跳过旧记录。实现更简单，代价是堆里可能有重复项，但在网格规模下完全可以接受。

三、启发式的选择决定行为

四方向移动时用曼哈顿距离，八方向移动时用对角距离，这是最稳妥的默认值。启发式必须不高估真实代价，否则最优性不成立。一个常用的八方向写法是：

function octile(dx, dy) {
  const a = Math.abs(dx), b = Math.abs(dy);
  return (a + b) + (Math.SQRT2 - 2) * Math.min(a, b);
}

把启发式的权重调大（比如乘 1.2），搜索会更快，但路径可能不是最短的。做可视化时我留了一个滑杆，让读者亲眼看到「更快」和「更短」之间的取舍，比文字解释有效得多。

四、逐帧渲染：让搜索过程可见

最直接的做法是搜完再画，但那样只能看到结果。想看到扩张过程，就要把算法拆成可中断的状态机：每次主循环只扩展若干个节点，然后把当前开放集和闭集画出来。

function step(budget = 60) {
  let n = 0;
  while (open.size && n++ < budget) {
    const cur = open.pop();
    if (closed[cur.id]) continue;
    if (cur.id === goalId) return 'done';
    closed[cur.id] = 1;
    for (const [nx, ny] of neighbors(grid, cur.x, cur.y)) {
      const id = ny * grid.cols + nx;
      if (closed[id]) continue;
      const g = cur.g + 1;
      if (g < (best[id] ?? Infinity)) {
        best[id] = g;
        open.push({ id, x: nx, y: ny, g, f: g + h(nx, ny) });
      }
    }
  }
  return open.size ? 'running' : 'failed';
}

渲染层用 Canvas，每帧只重绘发生变化的格子。实测在 80×60 的网格上，把单帧预算控制在 60～120 个节点，画面既跟得上又不掉帧。如果把预算开到几千，虽然算得快，但视觉上就是「瞬间填满」，反而失去了演示意义。

五、几个容易踩的坑

闭集不等于访问过。节点进过开放集不代表已经确定最短距离，只有从堆里弹出时才应该标记为已确定。否则会把更好的路径挡掉。

浮点代价不要直接比相等。对角线代价是 √2，累加后会出现 3.9999999 和 4 的差异。比较时用「严格小于」更新，不要用相等判断。

八方向要考虑切角。允许斜穿两个障碍物的夹角，路径看起来会「穿墙」。要么禁止切角，要么在代价里加惩罚。

大网格少用对象。每个节点一个对象、再用 Map 索引，在几万格时垃圾回收压力很明显。用类型化数组存 g 值和标记位，性能会稳定很多。

六、小结

A* 本身不复杂，难的是把它做成一个「看得懂」的东西。把优先队列、启发式和渲染节奏分开处理，代码结构会清晰很多；把搜索拆成可中断的步骤，也给后面加动画、调速、单步调试留出了空间。如果你也在做类似的算法可视化，建议先把状态机写对，再考虑配色和动效。