使用迷宫游戏理解 A* 寻路算法

准备好了吗？让我们开始一场有趣的迷宫游戏：

1. 你需要在网格地图上找到一条从起点（蓝色）到终点（绿色）的路径
2. 规则：
   • 蓝色方块表示你当前的位置
   • 白色格子是可以行走的空地
   • 黑色格子是不能穿越的墙壁
3. 目标：用最少的步数到达终点

尝试找到最少步数的路径来进入下一关！

找到路径了吗？需要几步？现在让我们来看看 A* 算法是如何解决这个问题的。

引言

在游戏开发、导航系统和机器人路径规划中，我们常常需要寻找一条从起点到终点的最优路径。A* （A-Star）作为一种高效且通用的寻路算法，被广泛运用于此类问题。

对于初学者而言，光看算法原理并不够；你需要在实际场景下理解 A* 是如何运作的。本篇文章将借助一个具体的迷宫关卡示例（level1）来深入讲解 A* 的实现方法。我们将详细解释数据结构、算法步骤、关键代码段，并通过可视化帮助你轻松入门。

为什么选择 A* 算法？

A* 融合了 Dijkstra 算法的精确性与最佳优先搜索的启发性。它使用以下三个指标来评估节点：

• g-score：当前路径已花费的真实成本（距离、时间等）
• h-score（启发函数值）：从当前节点到目标节点的预估成本。常用曼哈顿距离等启发函数。
• f-score = g-score + h-score：总评估成本，用于决定下一个要探索的节点

通过 f-score，A* 能优先探索更有潜力接近目标的路径，从而减少无谓的搜索。

示例关卡说明

下方是 level1 的关卡数据。该关卡为 8x8 的网格，每个数字表示格子的类型：

• 蓝色方块表示你当前的位置
• 绿色方块表示终点
• 黑色方块表示墙壁
• 白色方块表示可以行走的空地

数据结构与算法流程

要实现 A*，需用到两个列表：

1. 开放列表（Open List）：存放等待处理的节点。
2. 关闭列表（Closed List）：存放已处理过的节点，避免重复探索。

节点（Node）：在迷宫网格中，每个可行走的格子都可以看作一个节点。每个节点至少需要存储以下信息：

• 位置（x, y）坐标
• g-score（从起点到此节点的成本）
• h-score（此节点到终点的预估成本）
• f-score（g+h）
• from（记录从哪个节点过来，用于最终重建路径）

A* 算法的步骤

1. 初始化：
   • 将起点节点加入开放列表
   • 起点的 g=0（因为还没走过任何路径），h 为起点到终点的曼哈顿距离，f=g+h
   • 所有其他节点的 g、f 初始化为 -1（未确定）
2. 选择当前节点：
   • 从开放列表中选取 f-score 最低的节点作为当前节点。
   • 起初，只有起点在开放列表中，因此当前节点是起点
3. 检查是否到达终点
   • 如果当前节点是终点，那么已经找到最优路径，退出循环
4. 扩展邻居节点：
   • 对当前节点的每一个可通行的相邻节点（上下左右）进行处理
     • 计算邻居的新 g-score（=当前节点的 g+1）
     • 若邻居不在开放列表，或通过当前节点到邻居的路径更优（g更低），则更新邻居的 g、h、f 和 from，确保记录最佳路径
5. 更新列表：
   • 将当前节点从开放列表移除，加入关闭列表
   • 从开放列表中继续选择下一个 f-score 最低的节点为当前节点，重复上述步骤，直到找到终点或开放列表为空

启发函数（Heuristic）

在方格地图中，使用的启发函数是曼哈顿距离，即：

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

其中 (x1, y1) 为当前节点位置，(x2, y2) 为终点位置。此距离能快速估计到终点的最短步数（忽略障碍）。

示例代码（TypeScript）

下面是简化的 A* 代码示例，通过注释帮助初学者理解每一步的逻辑。

interface Node {
  x: number;
  y: number;
  g: number;
  h: number;
  f: number;
  from?: Node;
  isWall: boolean;
}

function heuristic(a: Node, b: Node): number {
  return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}

function aStar(start: Node, goal: Node, grid: Node[][]): Node[] | null {
  const openList: Node[] = [];
  const closed: boolean[][] = Array.from({ length: grid.length }, () =>
    Array(grid[0].length).fill(false),
  );

  start.g = 0;
  start.h = heuristic(start, goal);
  start.f = start.g + start.h;

  openList.push(start);

  while (openList.length > 0) {
    // 1. 找到 f-score 最低的节点作为当前节点
    let current = openList[0];
    let currentIndex = 0;
    for (let i = 1; i < openList.length; i++) {
      if (openList[i].f < current.f) {
        current = openList[i];
        currentIndex = i;
      }
    }

    // 如果找到终点，重建路径
    if (current.x === goal.x && current.y === goal.y) {
      return reconstructPath(current);
    }

    // 将当前节点移出开放列表，加入关闭列表
    openList.splice(currentIndex, 1);
    closed[current.y][current.x] = true;

    // 获取邻居（上下左右）
    const neighbors = getNeighbors(current, grid);
    for (const neighbor of neighbors) {
      if (neighbor.isWall || closed[neighbor.y][neighbor.x]) continue;

      const tentativeG = current.g + 1;
      const inOpen = openList.includes(neighbor);

      // 如果邻居不在开放列表中，或这条路径更优
      if (!inOpen || tentativeG < neighbor.g) {
        neighbor.from = current;
        neighbor.g = tentativeG;
        neighbor.h = heuristic(neighbor, goal);
        neighbor.f = neighbor.g + neighbor.h;
        if (!inOpen) openList.push(neighbor);
      }
    }
  }

  return null; // 未找到路径
}

function reconstructPath(node: Node): Node[] {
  const path: Node[] = [];
  let current: Node | undefined = node;
  while (current) {
    path.push(current);
    current = current.from;
  }
  return path.reverse();
}

function getNeighbors(node: Node, grid: Node[][]): Node[] {
  const dirs = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  const neighbors: Node[] = [];
  for (const [dx, dy] of dirs) {
    const nx = node.x + dx;
    const ny = node.y + dy;
    if (ny >= 0 && ny < grid.length && nx >= 0 && nx < grid[0].length) {
      neighbors.push(grid[ny][nx]);
    }
  }
  return neighbors;
}

你可以用迷宫挑战中的调试模式观看算法的执行过程。在可视化界面中，你会看到：

• 黄色节点：开放列表中的候选点（等待探索）
• 蓝色节点：已访问并放入关闭列表的节点
• 悬停在节点上可查看 g、h、f 值和来源节点

通过单步执行，你可以看到算法是如何不断选择 f-score 最低的节点前进，遇到墙壁时绕道，直到最终找到通往终点的最优路径

优化与进阶

本示例中，我们使用普通数组作为开放列表，寻找最低 f-score 节点需要线性搜索。对于小地图，这足够简单直观。但在更大地图上，可考虑：

使用优先队列（Priority Queue）或二叉堆优化选点过程，提高算法效率。 尝试不同的启发函数（如欧几里得距离或自定义启发）以适应不同场景。 在大型场景中使用内存优化策略（如多级地图分块、预计算启发值）来提升运行速度。 当你掌握了这些基础知识和实现方法后，便可以轻松将 A* 应用于更复杂的项目中。

总结

通过本篇文章和所提供的关卡例子，你已经了解了 A* 算法的工作机制和基本实现过程。现在，不妨亲自动手编写代码，加深对 A* 的理解。