掌握 A* 搜索算法:通过交互式迷宫游戏可视化路径规划
使用迷宫游戏理解 A* 寻路算法
准备好了吗?让我们开始一场有趣的迷宫游戏:
迷宫挑战
- 你需要在网格地图上找到一条从起点(蓝色)到终点(绿色)的路径
- 规则:
- 蓝色方块表示你当前的位置
- 白色格子是可以行走的空地
- 黑色格子是不能穿越的墙壁
- 目标:用最少的步数到达终点
尝试找到最少步数的路径来进入下一关!
找到路径了吗?需要几步?现在让我们来看看 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*,需用到两个列表:
- 开放列表(Open List):存放等待处理的节点。
- 关闭列表(Closed List):存放已处理过的节点,避免重复探索。
节点(Node):在迷宫网格中,每个可行走的格子都可以看作一个节点。每个节点至少需要存储以下信息:
- 位置(x, y)坐标
- g-score(从起点到此节点的成本)
- h-score(此节点到终点的预估成本)
- f-score(g+h)
- from(记录从哪个节点过来,用于最终重建路径)
A* 算法的步骤
- 初始化:
- 将起点节点加入开放列表
- 起点的 g=0(因为还没走过任何路径),h 为起点到终点的曼哈顿距离,f=g+h
- 所有其他节点的 g、f 初始化为 -1(未确定)
- 选择当前节点:
- 从开放列表中选取 f-score 最低的节点作为当前节点。
- 起初,只有起点在开放列表中,因此当前节点是起点
- 检查是否到达终点
- 如果当前节点是终点,那么已经找到最优路径,退出循环
- 扩展邻居节点:
- 对当前节点的每一个可通行的相邻节点(上下左右)进行处理
- 计算邻居的新 g-score(=当前节点的 g+1)
- 若邻居不在开放列表,或通过当前节点到邻居的路径更优(g更低),则更新邻居的 g、h、f 和 from,确保记录最佳路径
- 对当前节点的每一个可通行的相邻节点(上下左右)进行处理
- 更新列表:
- 将当前节点从开放列表移除,加入关闭列表
- 从开放列表中继续选择下一个 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* 的理解。