“直接上代码”这话我写算法笔记的时候常说。很多朋友学A*算法一开始就被“启发函数”“开闭列表”“路径回溯”这些术语劝退了翻了几篇理论文章脑子里记住了公式手却写不出一行能跑的代码。所以这篇我不按套路讲直接从一份能跑的 A*核心实现讲起把代码拆开揉碎讲清楚每个变量、每个判断为什么存在。A*算法解决的是最经典的路径规划问题在网格或地图上从起点到终点找一条代价最小的路径。游戏里的自动寻路、机器人导航、地图应用的路径规划底层几乎都是它。标题里“传统”两个字很关键意思是先掌握最经典、最通用的一套实现它不依赖任何花哨优化但恰恰是后面所有高级变体的地基。文章适合三类人准备算法面试的、做游戏开发或机器人路径规划的、以及那些“原理都懂但一到写代码就卡壳”的人。看完你不仅能跑通代码还能自己改参数、换启发函数、解决实际寻路问题。1. A*在求什么先看懂核心思路1.1 为什么A*能比BFS和Dijkstra“更聪明”地找路最早学搜索算法大家先接触的是 BFS。BFS 在网格里像水波扩散一圈一圈往外搜一定能找到最短路径但问题是它不知道目标在哪边把整个区域往外推。Dijkstra 比 BFS 聪明一点它按“从起点走过来的累计代价”扩展同样没有方向感只是从“圈数”变成了“代价层”。A* 多了一个东西对“距离终点还有多远”的估计也就是启发函数。搜索时不再只按“已经走了多远”排队而是按“已经走的 估计还要走的”排队。这个估计让 A* 像手里拿着一张地图在找人而不是蒙着眼睛一遍遍扫。举个例子你在商场找出口。BFS 是从入口开始把每个店铺都问一遍Dijkstra 是沿着走过的路不断找最短的走法A* 是你一边走一边看出口指示牌优先走向看起来离出口最近的方向走错了再回头。这个例子包含一个容易被忽略的要点A* 不是完全不探索其他方向它只是优先探索最有希望的区域万一启发函数给的信息不准它照样会改道。1.2 f g hA*最核心的公式三个字母的含义很简单g从起点到当前节点的真实代价。h从当前节点到终点的估计代价叫启发值。fg 和 h 的和也就是当前节点在待搜索队列里的优先级。A* 每一步都从 open list 里取出 f 最小的节点来扩展直到取出的节点是终点为止。这里必须补一个关键概念h 函数要“不虚报”术语叫可采纳性。意思是 h 对剩余距离的估计不能超过真实距离。只要 h 不高估A* 找到的就是最优路径。如果 h 高估就好比把“看起来很近”当成“真的很近”省略了本该检查的区域路径就可能不是最短的。主流程可以压缩成一个骨架后面所有代码都是在给这几行填空open 优先队列初始放入起点 while open 不为空: cur open 中 f 最小的节点 if cur 是终点: 回溯路径 将 cur 标记为已扩展 for 每个合法邻居 nxt: if nxt 从未被记录 或 新路径代价更小: 计算 nxt.f把 nxt 放入 open2. 代码之前的三个关键设计决策2.1 地图与节点网格问题怎么抽象网格地图用二维数组表示0是可通行1是障碍物。坐标用(x, y)表示x是行、y是列。节点不需要存整张地图只关心当前走到的格子。Node 类字段需要四样东西坐标x, y累计代价g总代价f父节点指针parent。parent是回溯路径用的。class Node: __slots__ (x, y, g, f, parent) def __init__(self, x, y, g, f, parent): self.x x self.y y self.g g self.f f self.parent parent为什么路径要靠parent回溯因为 A* 是前向搜索找到终点后只有通过 parent 链一路回退到起点才能拿到完整路径。如果只记录“访问过”不记录 parent最后只能回答“能不能到”回答不了“怎么走”。2.2 open list为什么必须用优先队列open list 是待考察节点的集合。如果每次从数组里线性查找 f 最小的节点扩展 N 个节点的总复杂度是 O(N²)地图一大就完蛋。用二叉堆优先队列能把“取最小”变成 O(log N)。Python 里直接用heapqC 里用std::priority_queue。但 C 的priority_queue默认是最大堆存 f 时要么用greater比较器要么把 f 取负值入堆。这是面试高频考点也是新手很容易搞反的地方。还有一个特别容易踩的细节heapq里不能直接存 Node 对象。因为 Python 比较元组时如果 f 相同会继续比较下一个元素这时就会去比较 Node 对象不仅可能抛异常还可能因为对象没有定义而报错。正确的做法是存(f, counter, node)其中counter是一个全局递增的序号。open_heap [] counter 0 heapq.heappush(open_heap, (start_node.f, counter, start_node)) counter 1counter有两个作用一是保证元组比较永远不会走到 Node 对象二是当 f 相同时先入堆的节点先出堆防止搜索在图内原地打转。2.3 避免重复扩展closed set 与 g_score教科书常说两个列表open list 和 closed list。closed 表示“这个点已经扩展过了”不再处理。工程实现里我更喜欢再加一个g_score字典记录每个格子当前已知的最小 g 值。原因很简单同一个节点可能被多条路径到达会入堆两次、三次甚至更多次。弹出时如果发现当前节点的 g 已经比g_score记录的大说明这条记录是旧数据直接扔掉。这种写法的好处是不需要去 open 链表中搜索节点再更新代码简洁也不容易错。if (cur.x, cur.y) in closed_set: continue if cur.g g_score.get((cur.x, cur.y), float(inf)): continueclosed_set负责避免重复扩展g_score负责丢弃过期的堆条目。两者配合才算把经典 A* 的“两列表”思想用工程方式落地。很多人只写 closed 不写 g_score结果在某些地图上会得到一条绕远的路径后面我会专门说这个坑。3. 核心代码逐行讲a_star 主函数3.1 完整可运行的A*核心实现下面这份代码可以直接复制运行我把启发函数和主循环写在了一起。import heapq import math class Node: __slots__ (x, y, g, f, parent) def __init__(self, x, y, g, f, parent): self.x x self.y y self.g g self.f f self.parent parent def heuristic(x1, y1, x2, y2, methoddiagonal): dx abs(x1 - x2) dy abs(y1 - y2) if method manhattan: return dx dy if method euclidean: return math.hypot(dx, dy) # diagonal8方向网格上最贴合实际的对角线距离 return max(dx, dy) (math.sqrt(2.0) - 1.0) * min(dx, dy) def astar(grid, start, goal, methoddiagonal, weight1.0): rows, cols len(grid), len(grid[0]) sx, sy start gx, gy goal # 起点和终点合法性检查 if grid[sx][sy] 1 or grid[gx][gy] 1: return None, 0 g_score {(sx, sy): 0.0} closed_set set() start_node Node( sx, sy, 0.0, weight * heuristic(sx, sy, gx, gy, method), None ) open_heap [] counter 0 heapq.heappush(open_heap, (start_node.f, counter, start_node)) counter 1 while open_heap: f, _, cur heapq.heappop(open_heap) if (cur.x, cur.y) in closed_set: continue if cur.g g_score.get((cur.x, cur.y), float(inf)): continue closed_set.add((cur.x, cur.y)) if (cur.x, cur.y) (gx, gy): path [] while cur is not None: path.append((cur.x, cur.y)) cur cur.parent return path[::-1], len(closed_set) # 根据方法决定是否允许8方向移动 neighbors [(1, 0), (-1, 0), (0, 1), (0, -1)] if method in (diagonal, euclidean): neighbors [(1, 1), (1, -1), (-1, 1), (-1, -1)] for dx, dy in neighbors: nx, ny cur.x dx, cur.y dy if nx 0 or nx rows or ny 0 or ny cols: continue if grid[nx][ny] 1: continue # 斜向移动时禁止穿墙 if dx ! 0 and dy ! 0: if grid[cur.x dx][cur.y] 1 or grid[cur.x][cur.y dy] 1: continue move_cost math.hypot(dx, dy) tentative_g cur.g move_cost if tentative_g g_score.get((nx, ny), float(inf)): h heuristic(nx, ny, gx, gy, method) child Node(nx, ny, tentative_g, tentative_g weight * h, cur) g_score[(nx, ny)] tentative_g heapq.heappush(open_heap, (child.f, counter, child)) counter 1 return None, len(closed_set)3.2 代码里几个关键分支的含义第一个关键分支是“过期条目跳过”。前面说过同一个格子可能因为多条路径被反复入堆。堆里弹出的节点如果它的 g 已经大于当前记录的g_score说明这是一条旧路径生成的节点直接跳过。如果只看closed_set不看 g_score就可能用旧路径覆盖新路径导致最终路径不是最优。第二个关键分支是“斜向禁止穿墙”。当dx和dy都不为 0 时从(cur.x, cur.y)走到(cur.xdx, cur.ydy)要经过两个相邻格子。如果这两个格子里有一个是墙那条斜线实际上是从墙角“挤”过去的视觉上就是穿墙。对于游戏角色或机器人这是不合法路径。所以必须检查if grid[cur.x dx][cur.y] 1 or grid[cur.x][cur.y dy] 1: continue第三个关键分支是“松弛更新”也就是tentative_g g_score.get(...)。这个思想来自 Dijkstra只有当找到一条通往邻居的更短路径时才更新邻居的代价、创建新节点并入堆。如果新路径更长什么都不做。这样保证每个格子保存的始终是当前已知最短的 g 值。路径回溯部分不需要递归用 while 从终点一路 parent 回到起点再反转列表。返回的第二个值是len(closed_set)也就是实际扩展了多少个格子这个值在后面对比启发函数时会很有用。4. 跑通它地图、可视化与启发函数对比4.1 造一张带墙的地图把路径打出来光看代码不够要跑起来。下面这张 10×10 地图放了两堵墙一堵横在第三行另一堵在右下角专门逼着路径绕行。grid [ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 1, 1, 1, 0, 0, 0], [0, 0, 0, 1, 1, 1, 1, 0, 0, 0], [0, 0, 0, 1, 1, 1, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], ] start (0, 0) goal (9, 9) path, explored astar(grid, start, goal, methoddiagonal) print(扩展节点数:, explored) print(路径长度:, len(path) - 1)再写一个简单的渲染函数把路径直接画到屏幕上def render(grid, path, start, goal): rows, cols len(grid), len(grid[0]) out [[. for _ in range(cols)] for _ in range(rows)] for i in range(rows): for j in range(cols): if grid[i][j] 1: out[i][j] # for x, y in path: out[x][y] * out[start[0]][start[1]] S out[goal[0]][goal[1]] G for row in out: print( .join(row))拿 diagonal 方法跑我这边输出的路径大概是这样的右侧绕行穿过第一堵墙的缺口再贴着右下墙绕到终点S . . . . . . . . . . * . . . . . . . . . . * * * * * * * * . # # # # # # # # * . . . . . . . . . * . . . . . . . . . * . . . # # # # . . * . . . # # # # . . * . . . # # # # . . * . . . . . . . . . G*就是路径#是墙。可以看到路径从第二行水平走到最右侧再从右侧缺口下去最后贴着右下角墙的外侧到达终点完全没穿墙。4.2 三种启发函数实测对比同样一张地图把method分别换成manhattan、diagonal、euclidean结果差异非常大。这里提醒一句manhattan模式下代码只允许 4 方向移动diagonal和euclidean允许 8 方向移动这是配套的。启发函数移动方向是否保证最优扩展节点量曼哈顿距离4方向是中等搜索区域呈菱形扩散对角线距离8方向是最少最贴合8方向网格欧几里得距离8方向是最多低估剩余距离导致过度探索很多人觉得欧几里得距离算的是直线距离应该最“准”。问题在于网格里实际移动距离不是连续的走一格是 1斜走一格是 √2而欧几里得距离计算的是两点之间的直线严重低于真实绕行距离。h 低估太多A* 就会认为大量方向都“看起来很近”结果把地图上很多无关区域也搜了。换个角度理解启发函数越贴近真实代价搜索方向感越强越低估扩展节点越多。如果 h 高估又会牺牲最优性。所以选启发函数的本质是“选一个最能反映你移动代价的估计函数”。8 方向移动最理想的是对角线距离公式4 方向移动最理想的是曼哈顿距离。4.3 工程提速weighted A* 和它的代价当你在真实项目里跑 A*往往不需要绝对的“最短路径”只需要一条“看起来合理”的路径。这时候可以给 h 乘一个权重w 1也就是f g w * h这叫 Weighted A*。w 越大搜索越倾向于直奔终点扩展节点越少速度越快但路径可能越差。w 1 时保证最优w 2 到 3 时路径通常只长一点点扩展节点能少一个量级游戏行业里甚至有人用 w 10。我上面的代码里已经预留了weight参数跑的时候直接传weight2.0就能体验。有一类场景尤其适合地图超大、对路径要求不高、帧率敏感的时候加权 A* 是性价比最高的方案。先保证能实时算出来再考虑要不要优化。5. 常见问题与排查实录5.1 问题速查表现象可能原因解决办法路径只有一两格就结束终点判断或起点终点传反了检查(cur.x, cur.y)与 goal 的比较搜索很长时间跑不完启发函数低估严重、地图过大换成更贴合的启发函数或使用 weighted A*路径斜着穿过墙角没做对角线穿墙检查增加grid[cur.xdx][cur.y]与grid[cur.x][cur.ydy]判断路径能到终点但绕远没有做 g 值松弛更新用tentative_g g_score.get(...)判断后再入堆起点或终点在障碍物里地图数据问题初始化前检查grid[sx][sy]和grid[gx][gy]同样的地图跑出不同结果heap 中 Node 对象比较有问题入堆统一用(f, counter, node)三元组5.2 三个我真实踩过的坑第一个坑用欧几里得距离当启发函数只开 4 方向结果搜索范围大得离谱。当时做的是 30×30 网格的课程设计地图不算大但 A* 几乎把整张图都扩展了界面肉眼可见地卡。后来把启发函数换成曼哈顿距离扩展节点数直接降了一个量级。这个教训就是启发函数必须和移动方式匹配。第二个坑允许 8 方向移动但没做穿墙检查。跑出来的路径看着很离谱角色斜着从两堵墙的夹角“挤”了过去在地图上一画就是一条斜穿墙角的直线。最初我以为是小路径误差后来放大地图才发现是规则漏洞。第三个坑早期版本只维护了 visited 集合没有维护g_score。路径能跑到终点但比最优路线长了一到两格。排查了很久才发现有一个格子被第一次访问时的路径记录固定了后面发现更短路径时没有更新导致后续所有节点的 g 值都偏大。从那以后我写 A* 一定会带上g_score松弛更新。6. 从这份代码到面试和工程6.1 面试官看A*会问什么A* 是算法岗高频题面试官一般从三个层次问。第一层是概念A* 和 Dijkstra 的区别是什么可以回答 A* 是 Dijkstra 在加了启发函数 h 之后的特例当 h 恒为 0 时A* 就退化成了 Dijkstra。第二层是正确性为什么 h 可采纳就能保证最优可以从反证法讲如果算法结束时找到的路径不是最优必然在某一刻 open list 中存在一个节点它的 f 值小于终点路径的真实代价而可采纳的 h 保证了这条路径上的 f 值不会被高估矛盾。不需要背太复杂的证明但要把可采纳性这个关键词讲清楚。第三层是手写实现写 A* 时先把 Node 定义和启发函数写好再写主循环。代码里出现(f, counter, node)这种细节往往是加分项因为它说明你真的写过、踩过堆排序元组比较的坑。面试还得准备一个扩展问题地图上会有动态障碍物A* 该怎么处理老实说标准 A* 不适合动态环境真正做机器人路径规划的会用 D* Lite 或 LPA*。能说出这几个名字说明你不是只会背模板。6.2 网格A*之后还能往哪走传统 A* 在网格地图上是一个非常好的起点但性能上限不高。地图一旦到几百乘几百普通 A* 就开始吃力这时候常用方向有这几个。JPS跳点搜索利用网格寻路的对称性把大量冗余节点直接跳过只扩展关键转折点。和 A* 配合使用在开阔地图上能提速几十倍甚至上百倍是 2D 网格寻路的事实标准。HPA层级 A**把地图切成多个区块先在高层规划区块路径再在低层规划具体移动路线。适合超大型地图。路径平滑A* 给的是网格路径角色走起来会一卡一卡的。拿到路径后可以用线性插值、拉普拉斯平滑或者 Catmull-Rom 样条把它变成平滑的曲线这是从“能走到”到“走得好看”的关键一步。代码层面也可以直接扩展给每个格子加不同的通行代价草地代价 1、沼泽代价 3、道路代价 0.5只需要把move_cost从固定值改成查表读取代码框架完全不用动。这就是传统核心实现的意义它是后面一切骚操作的底座。最后说点我自己的体会。写 A* 这件事最忌讳的是把代码背下来。我记得最开始搞懂这套算法时把几个参数来回改故意把 h 高估、把穿墙检查删掉、把 g_score 注释掉反复观察路径变化才真正明白每个设计在防什么。这篇核心实现给你的是一个能跑的起点建议你也拿地图折腾一遍跑通之后再往里面加东西。到那时候再看 JPS、看 LPA*你会比直接啃论文轻松得多。