掌握 A* 搜索算法:通过交互式迷宫游戏可视化路径规划

6 min read
·

使用迷宫游戏理解 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 最低的节点前进,遇到墙壁时绕道,直到最终找到通往终点的最优路径

一张 8x8 网格迷宫的截图,其中蓝色方块表示玩家的起点位置,绿色方块表示终点位置,黑色方块为无法通行的墙壁,白色方块为可行走的空地。该图片用于演示 A* 寻路算法在该关卡中的路径规划过程

优化与进阶

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

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

总结

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