带启发式的 A* 网格寻路

功能说明

该示例在字符网格中寻找起点到终点的最短路径，井号表示墙，其余字符可通行。它使用 A* 搜索，综合已走步数 g 与到终点的曼哈顿距离 h 选择下一个节点，通常比广度优先搜索扩展更少节点。返回值是包含起点与终点的坐标数组，无法到达时返回 null。

关键代码

findPath 先校验网格非空、每行等长且起点终点可通行。开放表用 Map 保存候选点与 f 值，每轮线性扫描选出最小 f 的节点；代价表记录 g 值，cameFrom 记录前驱，closed 避免重复处理。扩展四方向邻居时跳过墙、越界与已结算节点，只有更小的 g 才更新并重新入表。命中终点后用 keyOf 与 parsePoint 在字符串坐标和元组之间转换并回溯路径。

使用注意

启发函数使用曼哈顿距离，只适用于四方向、单位代价的网格；若允许斜走应改用切比雪夫或欧几里得距离。开放表用线性扫描选择最小值，复杂网格上应换成优先队列。封闭集合会阻止找到更优路径的情况在一致性启发下不会发生，但自定义启发时需谨慎。网格是只读的，函数不会修改输入。

验证方式

在带墙的迷宫中断言返回路径首尾正确且每一步都相邻、可通行。构造被墙完全包围的空地，断言返回 null。测试起点或终点落在墙上、网格不等长、空网格分别抛 RangeError。再检查路径长度与手工计算的最短步数一致。

代码示例

export type GridPoint = readonly [row: number, column: number];

interface OpenEntry {
  readonly point: GridPoint;
  readonly score: number;
}

export function findPath(grid: readonly string[], start: GridPoint, goal: GridPoint): GridPoint[] | null {
  if (!Array.isArray(grid) || grid.length === 0) throw new RangeError("grid must be a non-empty array");
  const width = grid[0]?.length ?? 0;
  if (width === 0) throw new RangeError("grid rows must not be empty");
  for (const row of grid) {
    if (typeof row !== "string" || row.length !== width) {
      throw new RangeError("grid must be rectangular");
    }
  }
  if (!isWalkable(grid, start)) throw new RangeError("start is blocked or out of bounds");
  if (!isWalkable(grid, goal)) throw new RangeError("goal is blocked or out of bounds");

  const startKey = keyOf(start);
  const goalKey = keyOf(goal);
  const open = new Map<string, OpenEntry>([[startKey, { point: start, score: heuristic(start, goal) }]]);
  const cameFrom = new Map<string, string>();
  const cost = new Map<string, number>([[startKey, 0]]);
  const closed = new Set<string>();

  while (open.size > 0) {
    let currentKey: string | null = null;
    let currentEntry: OpenEntry | null = null;
    for (const [candidateKey, candidate] of open) {
      if (currentEntry === null || candidate.score < currentEntry.score) {
        currentKey = candidateKey;
        currentEntry = candidate;
      }
    }
    if (currentKey === null || currentEntry === null) break;
    open.delete(currentKey);
    if (closed.has(currentKey)) continue;
    closed.add(currentKey);

    if (currentKey === goalKey) {
      return reconstruct(cameFrom, currentKey).map(parsePoint);
    }

    const baseCost = cost.get(currentKey) ?? 0;
    for (const neighbor of neighbors(currentEntry.point)) {
      if (!isWalkable(grid, neighbor)) continue;
      const neighborKey = keyOf(neighbor);
      if (closed.has(neighborKey)) continue;
      const tentative = baseCost + 1;
      if (tentative >= (cost.get(neighborKey) ?? Number.POSITIVE_INFINITY)) continue;
      cost.set(neighborKey, tentative);
      cameFrom.set(neighborKey, currentKey);
      open.set(neighborKey, { point: neighbor, score: tentative + heuristic(neighbor, goal) });
    }
  }
  return null;
}

function isWalkable(grid: readonly string[], point: GridPoint): boolean {
  const [row, column] = point;
  if (!Number.isInteger(row) || !Number.isInteger(column)) return false;
  if (row < 0 || row >= grid.length) return false;
  const line = grid[row];
  if (line === undefined) return false;
  if (column < 0 || column >= line.length) return false;
  return line[column] !== "#";
}

function heuristic(point: GridPoint, goal: GridPoint): number {
  return Math.abs(point[0] - goal[0]) + Math.abs(point[1] - goal[1]);
}

function neighbors(point: GridPoint): GridPoint[] {
  const [row, column] = point;
  return [
    [row - 1, column],
    [row + 1, column],
    [row, column - 1],
    [row, column + 1],
  ];
}

function keyOf(point: GridPoint): string {
  return `${point[0]},${point[1]}`;
}

function parsePoint(key: string): GridPoint {
  const [row, column] = key.split(",");
  return [Number(row), Number(column)];
}

function reconstruct(cameFrom: ReadonlyMap<string, string>, goalKey: string): string[] {
  const keys = [goalKey];
  let cursor = cameFrom.get(goalKey);
  while (cursor !== undefined) {
    keys.push(cursor);
    cursor = cameFrom.get(cursor);
  }
  return keys.reverse();
}

const maze = [
  "S....",
  ".###.",
  ".#.#.",
  ".#.#.",
  ".###.",
  "....G",
];
console.log(findPath(maze, [0, 0], [5, 4]));
console.log(findPath(maze, [0, 0], [2, 2]));