1. 先把 A* 摆到桌面上它到底比 Dijkstra 多算了什么我第一次真正把 A* 用进项目里是在一个网格地图的寻路模块上。当时用最朴素的广度优先搜索跑一张两百乘两百的地图单次寻路要几十毫秒单位一多就直接把帧率拖垮。换成 A* 之后同样一张图、同样的起点终点扩展的节点数从几万个掉到几百个耗时降到了毫秒级。但紧接着问题就来了路径偶尔会绕远有时候还会贴着墙根走出一条特别难看的折线甚至在某些地图上干脆找不到路。这些问题逼着我把 A* 从会写推到写对也让我意识到——这个算法的代码量不大真正的门槛全在细节里。A* 属于启发式图搜索解决的是在一张带权图上从起点找到一条到终点代价最小的路径这个问题。它的适用面比很多人想的宽游戏里的单位寻路、机器人室内导航、仓储 AGV 的调度路线、地图软件的分段规划甚至一些排程和拼图类问题底层都能套进同一个框架。适合读这篇内容的人大概是两类一类是刚接触寻路、能照着教程写出一个能跑的版本但不知道为什么这么写、出了问题不知道从哪查的人另一类是用过现成库但遇到大地图卡顿、路径质量差、动态障碍处理不了想回头把原理捋清楚的人。下面我按原理—启发函数—数据结构—地图细节—工程优化—踩坑排查这条线把我在实际项目里积累的东西摊开讲。1.1 一次寻路要被反复计算的三个数字A* 的全部逻辑浓缩起来就是一个公式f(n) g(n) h(n)。这三个量各有明确含义但新手最容易混淆的是它们各自代表事实还是猜测。g(n)是从起点走到当前节点 n 已经付出的实际代价它是确凿的、可累加的。比如在地图上直走一格代价是 1斜走一格代价是 1.414走了五步就是这五步的和。g 值只增不减而且随着搜索推进会被不断修正——如果后来发现了一条更便宜的走法n 的 g 就要更新成更小的那个值。h(n)是从当前节点 n 到终点还需要付出多少代价的估计。注意是估计不是真实值。我们不可能在搜索到一半时就知道剩下的路到底多长否则就不用搜了。h 的作用是给搜索一个方向感让它优先去探索那些看起来离终点更近的节点。f(n)则是这两者的和代表如果我从起点出发、经过 n 走到终点总共大概要花多少代价。A* 每次从待探索集合里挑出 f 最小的节点展开本质上是在赌f 最小的那条路最有可能就是最优解。用一个生活化的类比你要从城市一头开到另一头g 是你油表上已经掉下去的那部分h 是你打开导航看到的距目的地还有多少公里。你不可能精确知道前面会不会堵车但根据距离做个估计总比闭着眼睛一条街一条街地试要高效得多。而这个估计准不准就直接决定了你是在高效赶路还是在瞎绕。1.2 有方向和没方向差的是几个数量级的枚举量理解 A* 价值的最快方式是拿它和最笨的 Dijkstra 对比。Dijkstra 的选点规则是每次挑当前累计代价 g 最小的节点展开。它完全不看终点在哪从起点像水波一样均匀地向四周扩散直到波纹碰到终点为止。在一张没有障碍的 100×100 网格上从左上角走到右下角Dijkstra 大致要扩展到接近一万个格子——因为波纹必须铺满整个圆半径才够得着对角。而 A* 在 h 选得合理的情况下只会沿着起点到终点的一条带状区域推进扩展节点数通常在几百这个量级。两者相差二三十倍地图越大、维度越高这个差距越夸张。之所以能省下这么多根本原因在于 h 提供了方向偏置。搜索算法本质上是在一个巨大的候选集合里做取舍而 Dijkstra 对每个候选一视同仁因为它没有任何信息判断哪个更有希望。h 相当于给每个候选打了一个前景分让搜索把有限的算力优先投给前景好的那些。这里有个容易被忽略的点h 并不会改变搜索的正确性它只改变搜索的顺序。只要 h 满足特定条件下面马上讲A* 最终找到的路径和 Dijkstra 找到的是一模一样的只是走的路子更直。反过来说如果 h 提供的信息是错的那 A* 就会朝着错误的方向狂奔最后要么找到一条明显更长的路要么彻底错过最优解。这就是为什么很多实现能跑但结果不对问题几乎都出在 h 上。1.3 可采纳与一致h 必须守的两条硬规矩h 不是随便拍脑袋写个函数就行它必须满足两个性质这两个性质决定了 A* 的理论保证。第一个叫可采纳性admissibility对任意节点 nh(n) 都不能超过从 n 到终点的真实最小代价也就是h(n) ≤ h*(n)。通俗说h 只能是往少了估绝不能往多了估。只要满足这一条A* 就保证能找到全局最优路径。原因很直观如果 h 从不夸大剩余代价那么当终点被弹出时它的 f 值就等于真实总代价任何其他还没探索的路径的 f 值都不可能比它更小因为它们至少也要花这么多所以终点一定是最优的。第二个叫一致性consistency也叫单调性对任意相邻节点 n 和 n必须满足h(n) ≤ c(n, n) h(n)其中 c 是这两点之间的实际边代价。这条规矩的直观含义是从 n 到终点的估计代价不应该比先走一步到 n、再从 n 估计还要大——否则就出现了绕一步反而更近的悖论。一致性是可采纳性的加强版满足一致性的 h 一定可采纳反之不成立。这两条性质在实践中带来一个非常实际的差别满足一致性的 h每个节点最多只需要被展开一次。因为一旦某个节点被弹出并放入闭表它的 g 值就不会再被改小了——任何后续路径到达它的代价都会更大。而如果 h 只是可采纳但不一致就可能出现节点已经处理完了后来发现一条更便宜的路能到它的情况这时候必须允许把它从闭表里重新捞出来再算一遍否则结果就是错的。很多实现里那个让人困惑的 reopen 逻辑根子就在这里。举个具体的例子。在四方向网格只能上下左右走每步代价 1上用曼哈顿距离h |dx| |dy|作为启发函数它是既可采纳又一致的。在八方向网格允许斜走直走代价 1、斜走代价 √2上用欧几里得距离h √(dx² dy²)是可采纳的但由于它总是低估因为实际只能走格点走不出直线扩展的节点会比理论最优多一些。这时候如果换成对角线距离估计会更紧扩展更少。这些选择背后都是同一件事h 越接近真实代价搜索越聚焦h 越保守搜索越铺开但保证最优。2. 启发函数怎么选h 的精度直接决定 A* 是利器还是拖累如果只能给一条关于 A* 的实操建议我会说把八成精力花在 h 上。因为 g 的计算是确定的、机械的而 h 的设计充满了取舍。同一个地图换一个 h性能可能差十倍路径质量也可能天差地别。我在项目里见过最典型的错误是直接抄了一个欧几里得距离的 h然后地图是四方向移动的——结果就是 h 严重低估A* 退化得几乎和 Dijkstra 一样慢团队还以为地图太大算法不行。2.1 三种距离度量各自对应什么样的移动规则选 h 的第一步是先搞清楚你的地图允许怎么移动。移动规则决定了两点之间的最短可能距离是什么形状而 h 就应该用那个形状去估。移动规则允许方向单步代价推荐的 h说明四方向上下左右统一为 1曼哈顿距离 dx八方向斜走同价八个方向斜走也按 1切比雪夫距离 max(dx八方向斜走加价八个方向直走 1、斜走 √2对角线距离见下方公式这是最紧的估计任意方向无限制实际欧氏距离欧几里得距离√(dx² dy²)连续空间、无人机、机器人常用对角线距离的公式是h (dx dy) (√2 - 2) × min(dx, dy)。推导思路很简单先尽可能多地走斜线走min(dx, dy)步剩下的差值只能靠直走补齐走|dx - dy|步。所以总代价是min × √2 |dx - dy| × 1整理一下就是上面的形式。这个估计在八方向加价的地图上是最紧的既不夸大也不过分保守。在实际代码里我强烈建议把代价整数化。直走记 10斜走记 14√2 的近似曼哈顿距离就变成10 × (dx dy)对角线距离变成14 × min 10 × (|dx - dy|)。这样做的好处不只是省浮点运算——更重要的是避免了浮点相等比较带来的各种诡异 bug。闭表判定、f 值比较、g 值更新全都变成整数比较行为确定调试时打印出来也一目了然。2.2 h 高估之后路径会以什么方式变差可采纳性这条线一旦越过去A* 就不再保证最优了。但有意思的是它依然能返回一条路而且往往看起来还挺合理这就特别容易骗过人。举个我实际遇到过的场景。一张地图上有个大块的凹形障碍起点在凹口左边终点在凹口右边。绕开障碍需要先往回走几步再绕过去多花大概 8 步。如果用了一个略微高估的 h比如把欧几里得距离乘了 1.1那么在凹口附近绕路方向的节点 f 值会比看起来直线更近的方向大搜索就优先往凹口里钻。钻进去发现走不通再回退但此时已经浪费了大量扩展。最终它确实找到了路但那条路比最优解长了整整 8 步而且在一个实时性要求高的场景里这次的搜索耗时也是最优情况的好几倍。这种现象在业内有个说法叫被启发函数带偏。它的危险之处在于在小地图、简单障碍上几乎测不出来一旦地图变复杂就开始偶发而这类偶发问题最难定位。所以我的做法是在开发阶段给 h 加一个断言如果 h 函数被单独调用时返回的值大于沿无障碍直线走到终点的最小可能代价就直接报错。这个检查很便宜但能在早期把绝大多数 h 设计错误拦下来。顺带说一个反直觉的点h 高估导致的问题不只是路径变长还包括搜索时间反而变长。因为被带偏的方向往往通向死路进去之后要回退回退就意味着把之前跳过的那些节点重新捡起来算实际扩展量可能比用保守 h 还多。我就见过一个版本把 h 乘了 1.5 想加速结果平均耗时涨了三成查了半天才发现是这个原因。2.3 用权重给 h 松绑速度与最优之间的滑杆如果业务场景并不强求绝对最优只要求看起来合理且快那有一个非常实用的手段给 h 加权重。把选点规则从f g h改成f g w × h其中 w ≥ 1。w 等于 1 时就是标准 A*保证最优w 越大搜索越贪婪越倾向于朝终点方向猛冲扩展节点越少、速度越快但路径可能变长。这个技巧在业界被称为加权 A*思想来源是ε-可采纳的概念——理论上可以保证找到的路径代价不超过最优解的 w 倍。这个滑杆在实际项目里非常好用因为不同场景对路径质量的要求差别巨大。一个玩家操控的角色路径稍微绕一格根本看不出来但一个需要精确对齐的机械臂路径偏差就是事故。所以我通常会按用途分档w 1.0离线规划、需要严格最优的场合。w 1.2 ~ 1.5常规实时寻路肉眼几乎看不出差别速度提升明显。w 2.0 以上大批量单位同时寻路、或者只需要一个大致方向的时候。还有一个更巧妙的用法是动态权重搜索早期用大的 w 快速逼近终点区域等到当前节点离终点足够近比如 h 小于某个阈值时把 w 降回 1 做一次精细搜索。这样既有早期的速度又能保证末端路径质量。这个思路在很多实时策略类项目里是标配实现成本也就是加一个判断值得一试。不过要提醒一句加权之后之前提到的一致性保证每节点只扩展一次就可能不成立了因为 w 改变了 f 的相对大小关系。如果用了动态权重闭表的 reopen 逻辑一定要留着不然会出现路径突然断掉或者绕大圈的情况。3. 待探索集合不是随便一个容器优先队列、重复入队与延迟删除把公式想明白之后下一个决定性能的地方就是数据结构。A* 每一轮要做的事情非常固定从待探索集合通常叫 open 表里取出 f 最小的节点展开它的邻居把邻居塞回去。所以 open 表的核心操作就是插入和取最小这天然指向优先队列。我见过不少教学实现用数组或者链表维护 open 表每次线性扫描找最小值。在小数据量下没问题但节点数上千之后这个线性扫描就成了整个算法的瓶颈——因为 A* 的循环次数和 open 表大小是同一量级的整体复杂度会被拖到 O(n²)。3.1 二叉堆够不够用什么规模该换标准答案是用二叉堆插入和弹出都是 O(log n)绝大多数场景足够。用现成的语言库就行比如 C 的std::priority_queue、Python 的heapq、Java 的PriorityQueue。需要注意方向大部分堆实现是大顶堆而我们要取 f 最小值所以要么取负值存进去要么自己写比较器。堆有个绕不开的短板它不支持高效地降低某个已存在元素的键值。而 A* 里恰恰需要这个操作——当我们发现一条更便宜的路径到达节点 n 时n 的 g 变小了f 也跟着变小理论上应该更新它在堆里的位置。工程上有两条路。第一条是自己实现一个带索引的堆额外维护节点 → 堆内下标的映射支持 decrease-key复杂度 O(log n)。这条路性能最好但代码量和出错概率都上去了尤其是下标维护那一块写错一次能调半天。第二条路更常见叫懒惰删除不更新堆里的旧元素而是直接再插入一条新的记录旧记录留在堆里当僵尸。弹出时检查这个节点是不是已经被处理过或者这条记录的 f 值是不是已经过期是就跳过。这样堆里可能堆积多条同节点的记录内存占用变大但每次操作仍然是 O(log n)而且代码极其简单。我的经验是在节点规模不超过十万、且每个节点最多被更新几次的情况下懒惰删除完全够用没必要上带索引的堆。只有在极端场景下比如超大地图、节点被反复更新几十次才值得上索引堆。再往上如果代价是小范围整数比如直走 10、斜走 14 这种可以用桶队列也叫 Dial 算法替代堆把优先级按代价值分桶取最小值时顺序扫描桶即可复杂度接近 O(1)。这个技巧在几十万节点的地图上能带来明显收益代价是需要预先知道代价的上界内存开销也大一截。3.2 一个节点被多次发现g 更新和重开的判定逻辑这是 A* 实现里最容易写错的地方也是路径看起来对但莫名绕远的头号元凶。搜索过程中同一个节点很可能被多个邻居反复发现。每次发现时都要做一次判断新的路径代价g(邻居) 边代价是不是比它现有的 g 更小更小就更新 g、把父指针指向当前节点、重新入队不更小就直接丢弃。这个逻辑本身很直白问题出在节点已经进了闭表之后又被发现更便宜的路径这种情况。如果 h 满足一致性这种情况理论上不会发生所以很多实现干脆不做处理。但现实里 h 常常只是可采纳而不一致比如用了动态权重、或者 h 函数写得不够严谨再加上浮点误差闭表里的节点被翻案是真实会发生的。这时候如果不处理就会出现某段路径的父指针指向了一个已经被认为已完成的节点而那个节点到起点的实际代价比记录的大最终回溯出来的路径代价和实际不符表现出来就是路径图上看着通实际走起来绕。我的处理原则是默认允许重开。具体做法是弹出节点时先检查它是否在闭表中如果在比较堆里这条记录的 g 和闭表里记的 g如果堆里的更小就把它从闭表移除、重新处理。这段逻辑只多几行判断但能挡掉一大批疑难杂症。当然代价是极端情况下扩展量会增加所以我会加一个扩展次数的上限做兜底超过就返回当前最优解并打日志——总比死循环强。3.3 闭表的粒度决定状态空间有多大初学者容易把闭表里存的是格子坐标当成理所当然。这在纯网格寻路里是对的但一旦你的移动规则里加入了别的维度坐标就不够了。举个典型例子如果你的单位有朝向转身需要额外代价那么在 (5, 5) 面朝北和在 (5, 5) 面朝东是两个完全不同的状态代价不同、后续可达的邻居也不同。这时候状态键必须是(x, y, direction)这样的组合。同理如果移动带速度或者惯性速度也得进键。一旦状态维度上去状态空间就是指数级的。我做过一个带朝向的版本地图是 200×200加上四个朝向状态数直接变成十六万内存和耗时都翻了四倍。这种情况下有几个缓解手段一是精简朝向比如只区分八个方向而不是连续角度二是合并等价状态比如面朝北和面朝南在某些规则下代价相同就可以合并三是改用其他搜索形式比如把状态空间压缩成稀疏图只保留关键节点。还有个小细节闭表用哈希表还是数组。如果状态空间是规整的比如就是网格用一维数组按下标索引最快内存也可控如果状态是稀疏的、或者维度不固定那哈希表更合适。哈希表的开销不小每个条目几十字节几十万状态就是几十兆移动端项目要留意这一点。4. 网格地图上的隐性成本斜走代价、穿角规则与地形权重前面讲的都是图层面的东西。但绝大多数实际项目用的是网格地图而网格有自己的物理约束这些约束如果不在代价函数里体现A* 算出来的路径就会违反现实规则——最典型的就是斜着穿过两堵墙的夹角。4.1 允许斜走之后代价不能再按 1 来算假设你的地图允许八个方向移动每步代价都设成 1。看起来简单但算出来的路径会明显偏爱斜线因为斜着走一步在坐标上同时推进了 x 和 y效率是直走的两倍而收费却一样。结果就是路径变成一条锯齿状的斜线实际移动距离比直走 必要的斜走要长视觉上也很怪。正确做法是让代价反映真实的几何距离直走代价 1斜走代价 √2。整数化之后就是 10 和 14。这个比例必须和 h 函数保持一致否则就会出现g 按 √2 算、h 按切比雪夫算这种错配导致 h 系统性低估或者高估。我在排查一个路径问题时就发现过 g 用 14、h 用 10 的情况结果在地图某些区域h 的估计比 g 的实际推进还大直接违反了可采纳性路径质量一塌糊涂。还有个变体是斜走代价略高于 √2比如设成 15 而不是 14。这在某些游戏里是有意为之目的是让单位更倾向于走直线看起来更自然。这种做法会牺牲一点最优性但对观感的提升往往值得。这个取舍没有标准答案取决于你的产品更看重什么。4.2 穿角问题和贴墙走的丑陋路径所谓穿角是指两个障碍物在斜对角上相邻中间只有一个格子的缝隙。如果允许斜走A* 会毫不犹豫地从那条缝里斜穿过去——在纯数学的图模型里没问题但在有体积的实体上这等于从两堵墙的夹缝里挤过去物理上不可能视觉上也很假。解决方式有两种。一种是硬禁止在判断某个斜向邻居是否可走时额外检查它相邻的两个直向格子是否都可通行只要有一个是障碍就禁止斜走。这个规则严格、安全但会让路径在拐角处多一些直角看起来稍微僵一点。另一种是软惩罚允许斜穿但在代价上加一个惩罚值比如 5。这样大部分情况下 A* 会主动避开穿角只有在绕路代价明显更大时才会选择穿过去。这个方案更灵活适合那些偶尔穿一下也能接受的场景。与该不该穿角密切相关的是路径的贴墙倾向。默认的 A* 在等代价路径之间没有任何偏好它找到的往往是那条紧贴障碍物边缘的路线。玩家看到的感受就是这个单位怎么老是贴着墙根蹭。缓解手段是在 g 里加一个贴近惩罚如果某个格子的四邻里有障碍物代价加一个小量比如 1。这个改动很小但路径会明显往通道中间靠视觉上舒服很多。我在一个塔防类项目里加过这个惩罚反馈里单位走路很怪的抱怨基本消失了。4.3 地形代价不能只加在 g 上h 也得跟着调整真实地图很少是均匀的。草地、泥地、道路、浅水通行代价各不相同。把地形代价加进 g 是很自然的每走一步代价按目标格子的地形系数算。但这里有个特别隐蔽的坑——h 的基准必须跟着变。举个例子。如果地图上最便宜的地形代价是 0.6道路而你仍然用每步 1去估 h那 h 就高估了破坏了可采纳性路径会变差。反过来如果地图上所有格子代价都 ≥ 1你用 1 去估是安全的。所以规则是h 里用的最小步进代价必须是全图所有地形的代价下界。我在一个项目里就栽过这个跟头。地图上加了传送带地形代价是 0.3但 h 还是按 1 估。结果 A* 在一些本来应该走传送带的场景里选择了看起来更短但实际更慢的直路。后来把 h 的基准降到 0.3路径立刻正常了。代价是扩展节点数变多因为 h 变保守了——但这是必要的交换正确性优先于速度。如果地形非常不均匀还有一个折中方案h 用平均代价估同时接受轻微的高估。这在很多实际产品里是可接受的因为路径质量下降的幅度很小而速度提升明显。关键是要清楚自己在做什么并且用真实数据验证过影响而不是稀里糊涂地就用了。5. 从能跑到跑得快跳点搜索、分层规划与增量重算一个正确实现的 A*在中等规模的网格上表现通常还不错。但只要地图继续变大、单位继续变多就一定会撞到性能墙。这时候考验的就是工程优化能力了。优化方向大致有三类我按改动成本从低到高排列。5.1 跳点搜索省掉的到底是什么跳点搜索JPS是针对均匀代价网格的一个经典加速方法思路非常巧妙在开阔区域里很多路径是对称的、等价的那我们就没有必要逐个格子去展开它们。具体说在一大片空地上从起点到终点有无数条等价的走法它们的代价完全一样。标准 A* 会把这些路径上的节点全都展开一遍或者说展开其中很大一部分因为它们 f 值都相同、都有可能是最优解的一部分。跳点搜索的做法是只沿着必要的方向一路跳过去跳过中间那些不需要转弯的点直到遇到一个强制邻居——也就是那种如果我不在这里转弯就会绕更远的节点。只有这些跳点才进入 open 表。效果有多明显在一张大部分是空地的地图上跳点搜索的扩展节点数常常只有标准 A* 的几十分之一速度快一个数量级。这个提升在实时代码里是很有分量的。但它有明确的适用边界只在所有格子代价相同、移动规则统一的情况下成立。一旦你的地图有了地形代价差异对称性就被打破了跳点搜索的剪枝逻辑不再正确。所以如果你的项目需要地形代价这条路基本走不通。另外实现复杂度也高不少尤其是强制邻居的判定涉及大量边界情况写错一个条件就会漏掉路径。我的建议是除非确实卡在性能上否则先别上跳点搜索先把标准 A调优到位再说。*5.2 分层和预计算大地图的另一条路当单张地图大到连优化后的 A* 都吃力时另一个思路是降低搜索的粒度也就是分层。典型做法是把地图切成若干个区块比如每 16×16 格一个块预先算好每个区块边界上那些出入口之间的最短路径和代价。寻路时先在区块图这一层做一次粗粒度的 A*得到一条穿过哪些块、从哪个口进出的路线然后再在每一段内部做细粒度的寻路。这就是分层路径规划的基本形式。这么做的好处是搜索规模从全图格子数降到区块数量级直接降了两三个数量级。代价是需要预处理的时间和内存以及路径质量会略微下降——因为粗粒度那层只考虑块间的路径可能错过一些跨块的巧妙捷径。预计算还有一个变体是缓存把常用的起终点对之间的路径存起来下次同样或相近的请求直接复用。这在那些大量单位从固定几个出生点涌向固定几个目标点的场景里特别有效。实现上要注意缓存失效——地图一变所有涉及该区域的缓存都要作废否则单位会往已经不存在的路上走。5.3 动态障碍全量重算是最贵的做法静态地图好办麻烦的是障碍会变化——门开了关了、建筑被摧毁了、其他单位临时占位。最粗暴的做法是障碍一变就整条路径重算但这在很多场景下代价太高尤其是当变化只影响路径上很小的一段时。比较实用的做法是分段重算先判断变化点是否落在当前路径上如果不在什么都不用做如果在只从变化点附近的一个安全点开始重新规划到终点前面已经走过的那段保留。这个思路实现简单效果也好是我在多数项目里的默认选择。更激进的方案是增量搜索算法它们的核心思想是复用上一次搜索留下的信息只更新受影响的那些节点的 g 值。这类算法在机器人领域用得比较多因为机器人是一边走一边感知的环境信息持续更新全量重算完全跟不上。但它们的实现复杂度明显更高状态维护、传播逻辑都容易出错而且对图的规模有要求。我的看法是如果只是游戏或模拟场景里的偶尔变化分段重算足够了只有在真的需要高频、连续重规划的场景才值得投入去搞增量算法。另外还有一个容易忽略的点重规划不必追求每一帧都做。给每个单位一个下次可以重规划的时间点错峰执行能极大平滑 CPU 峰值。我在一个单位数量上千的项目里加了这个限制帧率的抖动立刻改善了很多。6. 我实际踩过的坑以及一条可复用的排查链路最后这部分是我这些年调试 A* 相关问题时总结出来的东西。比起原理这些更像是血泪经验因为 A* 的问题往往不报错、不崩溃只是结果不对非常考验排查思路。6.1 路径绕远时按这个顺序查最省时间遇到路径能走通但明显不是最短的情况我现在会按固定顺序查基本能在十分钟内定位。第一步看 h 有没有高估。在代码里临时加一段检查对搜索到的每个节点比较 h 值和沿无障碍直线的最小可能代价如果 h 更大就打印出来。这一步能揪出绝大多数问题包括地形基准设错、距离度量选错、坐标系搞混。第二步看 g 的累加对不对。打印一条完整路径上每一步的边代价人工核对。常见错误包括斜走按 1 算应该是 1.414 或 14、地形系数乘在了源格子而不是目标格子、以及某些方向的代价表填错了顺序。第三步看闭表判定。如果闭表是用节点是否访问过这种粗粒度判断而没有比较 g 值那么先到达的路径哪怕更贵也会被保留。改成只有更便宜才更新再试。第四步看坐标转换。这一步听起来很蠢但真的高频。地图数据是按行存的map[row][col]而寻路代码里习惯用(x, y)如果哪个地方把行列搞反了表现出来的就是路径在某些区域莫名其妙地绕因为它在另一个方向的地图上找路。我至少遇到过三次这个问题每次都是查了半天算法最后发现是两行代码的顺序写反了。第五步看穿角规则和贴墙惩罚有没有互相打架。如果既禁止穿角又加了贴墙惩罚某些狭窄地形里可能出现所有路都被重罚导致 A* 选了一条远路。这时候打印一下几条候选路径的代价明细问题一目了然。6.2 并发寻路时的性能塌方往往不在算法本身有一类性能问题特别有迷惑性单次寻路测下来很快但一上量就卡得不行。这时候罪魁祸首通常不是 A* 的复杂度而是内存分配。A* 每次搜索都要开几个容器open 堆、闭表、g 值表、父指针表。如果每次寻路都重新 new 一遍在大地图上这几个结构加起来可能是几百 KB 到几 MB。一帧内如果有几十个单位同时寻路就是几十 MB 的分配和释放垃圾回收直接被打爆。解决办法是对象池预分配几套工作缓冲区寻路开始时清空复用结束后归还。清空的方式也有讲究——如果是数组用版本号标记比逐个清零快得多每个格子存一个stamp本次搜索的编号和 stamp 不同就视为未访问避免了 O(n) 的清零开销。这个小技巧在地图上万时能带来成倍的提升。还有一个点是限制每帧的寻路预算。不要在一帧里把所有请求都处理完而是排个队列每帧只处理固定数量或者固定时间片内的请求。剩下的下帧继续。这样最坏情况下的帧时间可控玩家感受到的是有些单位反应慢半拍而不是整个游戏卡住。6.3 那些不报错但会让结果出错的边界情况最后列几个我在实际项目里真实遇到过、而且都属于不崩溃但结果错的边界情况写实现的时候值得挨个过一遍。起点就是终点。如果没做特判搜索会正常进行但因为 h 是 0可能一路扩散出去才停白费算力。加一行判断直接返回空路径。起点或终点落在障碍上。这时候搜索永远找不到终点会一直跑到 open 表空了才返回失败。如果地图很大这一次就是几秒钟的卡顿。正确做法是在入口处校验不合法立刻返回。终点不可达。和上一条类似但更隐蔽——因为地图看起来是通的只是被某个封闭区域围住了。这时候 A* 会把整个可达区域全搜一遍。应对办法是加扩展上限或者做一次快速的连通性预检查。浮点相等比较。如果代价用了浮点那么新 g 是否更小的判断在极端情况下会因为精度问题反复横跳导致同一节点被反复更新甚至出现震荡。这是整数化代价最实在的好处之一能彻底避免这类问题。父指针成环。如果 g 更新逻辑写错可能出现 A 的父是 B、B 的父又是 A 的情况。回溯路径时就会死循环。加一个步数上限做保护同时在开发期打印路径长度做断言能及早发现。这些东西单看每一条都很小但组合起来就是一个能跑但不可靠的实现。我的习惯是每写完一个寻路模块就拿一张构造好的极端地图——包含死角、窄缝、孤立区域、起终点重合——跑一遍把上面这些情况全过一遍。花半小时做这件事能省掉后面几天的 debug。我个人在实际操作中的体会是A* 这个算法最迷人的地方在于它的透明度每一个决策都能追溯到那三个数字上出了问题也一定能从 g、h、闭表、代价函数这几个地方找到原因。它不像那些黑盒式的算法调不动就只能换。所以每当我看到有人抱怨寻路不准我的第一反应从来不是换算法而是把中间过程打印出来看一眼——十有八九答案就在那几行数字里。 
长河君 · 2026/10/31 17:04:04 · 阅读 1.2k A*寻路算法实战：启发函数、优先队列与工程优化
1. 先把 A* 摆到桌面上它到底比 Dijkstra 多算了什么我第一次真正把 A* 用进项目里是在一个网格地图的寻路模块上。当时用最朴素的广度优先搜索跑一张两百乘两百的地图单次寻路要几十毫秒单位一多就直接把帧率拖垮。换成 A* 之后同样一张图、同样的起点终点扩展的节点数从几万个掉到几百个耗时降到了毫秒级。但紧接着问题就来了路径偶尔会绕远有时候还会贴着墙根走出一条特别难看的折线甚至在某些地图上干脆找不到路。这些问题逼着我把 A* 从会写推到写对也让我意识到——这个算法的代码量不大真正的门槛全在细节里。A* 属于启发式图搜索解决的是在一张带权图上从起点找到一条到终点代价最小的路径这个问题。它的适用面比很多人想的宽游戏里的单位寻路、机器人室内导航、仓储 AGV 的调度路线、地图软件的分段规划甚至一些排程和拼图类问题底层都能套进同一个框架。适合读这篇内容的人大概是两类一类是刚接触寻路、能照着教程写出一个能跑的版本但不知道为什么这么写、出了问题不知道从哪查的人另一类是用过现成库但遇到大地图卡顿、路径质量差、动态障碍处理不了想回头把原理捋清楚的人。下面我按原理—启发函数—数据结构—地图细节—工程优化—踩坑排查这条线把我在实际项目里积累的东西摊开讲。1.1 一次寻路要被反复计算的三个数字A* 的全部逻辑浓缩起来就是一个公式f(n) g(n) h(n)。这三个量各有明确含义但新手最容易混淆的是它们各自代表事实还是猜测。g(n)是从起点走到当前节点 n 已经付出的实际代价它是确凿的、可累加的。比如在地图上直走一格代价是 1斜走一格代价是 1.414走了五步就是这五步的和。g 值只增不减而且随着搜索推进会被不断修正——如果后来发现了一条更便宜的走法n 的 g 就要更新成更小的那个值。h(n)是从当前节点 n 到终点还需要付出多少代价的估计。注意是估计不是真实值。我们不可能在搜索到一半时就知道剩下的路到底多长否则就不用搜了。h 的作用是给搜索一个方向感让它优先去探索那些看起来离终点更近的节点。f(n)则是这两者的和代表如果我从起点出发、经过 n 走到终点总共大概要花多少代价。A* 每次从待探索集合里挑出 f 最小的节点展开本质上是在赌f 最小的那条路最有可能就是最优解。用一个生活化的类比你要从城市一头开到另一头g 是你油表上已经掉下去的那部分h 是你打开导航看到的距目的地还有多少公里。你不可能精确知道前面会不会堵车但根据距离做个估计总比闭着眼睛一条街一条街地试要高效得多。而这个估计准不准就直接决定了你是在高效赶路还是在瞎绕。1.2 有方向和没方向差的是几个数量级的枚举量理解 A* 价值的最快方式是拿它和最笨的 Dijkstra 对比。Dijkstra 的选点规则是每次挑当前累计代价 g 最小的节点展开。它完全不看终点在哪从起点像水波一样均匀地向四周扩散直到波纹碰到终点为止。在一张没有障碍的 100×100 网格上从左上角走到右下角Dijkstra 大致要扩展到接近一万个格子——因为波纹必须铺满整个圆半径才够得着对角。而 A* 在 h 选得合理的情况下只会沿着起点到终点的一条带状区域推进扩展节点数通常在几百这个量级。两者相差二三十倍地图越大、维度越高这个差距越夸张。之所以能省下这么多根本原因在于 h 提供了方向偏置。搜索算法本质上是在一个巨大的候选集合里做取舍而 Dijkstra 对每个候选一视同仁因为它没有任何信息判断哪个更有希望。h 相当于给每个候选打了一个前景分让搜索把有限的算力优先投给前景好的那些。这里有个容易被忽略的点h 并不会改变搜索的正确性它只改变搜索的顺序。只要 h 满足特定条件下面马上讲A* 最终找到的路径和 Dijkstra 找到的是一模一样的只是走的路子更直。反过来说如果 h 提供的信息是错的那 A* 就会朝着错误的方向狂奔最后要么找到一条明显更长的路要么彻底错过最优解。这就是为什么很多实现能跑但结果不对问题几乎都出在 h 上。1.3 可采纳与一致h 必须守的两条硬规矩h 不是随便拍脑袋写个函数就行它必须满足两个性质这两个性质决定了 A* 的理论保证。第一个叫可采纳性admissibility对任意节点 nh(n) 都不能超过从 n 到终点的真实最小代价也就是h(n) ≤ h*(n)。通俗说h 只能是往少了估绝不能往多了估。只要满足这一条A* 就保证能找到全局最优路径。原因很直观如果 h 从不夸大剩余代价那么当终点被弹出时它的 f 值就等于真实总代价任何其他还没探索的路径的 f 值都不可能比它更小因为它们至少也要花这么多所以终点一定是最优的。第二个叫一致性consistency也叫单调性对任意相邻节点 n 和 n必须满足h(n) ≤ c(n, n) h(n)其中 c 是这两点之间的实际边代价。这条规矩的直观含义是从 n 到终点的估计代价不应该比先走一步到 n、再从 n 估计还要大——否则就出现了绕一步反而更近的悖论。一致性是可采纳性的加强版满足一致性的 h 一定可采纳反之不成立。这两条性质在实践中带来一个非常实际的差别满足一致性的 h每个节点最多只需要被展开一次。因为一旦某个节点被弹出并放入闭表它的 g 值就不会再被改小了——任何后续路径到达它的代价都会更大。而如果 h 只是可采纳但不一致就可能出现节点已经处理完了后来发现一条更便宜的路能到它的情况这时候必须允许把它从闭表里重新捞出来再算一遍否则结果就是错的。很多实现里那个让人困惑的 reopen 逻辑根子就在这里。举个具体的例子。在四方向网格只能上下左右走每步代价 1上用曼哈顿距离h |dx| |dy|作为启发函数它是既可采纳又一致的。在八方向网格允许斜走直走代价 1、斜走代价 √2上用欧几里得距离h √(dx² dy²)是可采纳的但由于它总是低估因为实际只能走格点走不出直线扩展的节点会比理论最优多一些。这时候如果换成对角线距离估计会更紧扩展更少。这些选择背后都是同一件事h 越接近真实代价搜索越聚焦h 越保守搜索越铺开但保证最优。2. 启发函数怎么选h 的精度直接决定 A* 是利器还是拖累如果只能给一条关于 A* 的实操建议我会说把八成精力花在 h 上。因为 g 的计算是确定的、机械的而 h 的设计充满了取舍。同一个地图换一个 h性能可能差十倍路径质量也可能天差地别。我在项目里见过最典型的错误是直接抄了一个欧几里得距离的 h然后地图是四方向移动的——结果就是 h 严重低估A* 退化得几乎和 Dijkstra 一样慢团队还以为地图太大算法不行。2.1 三种距离度量各自对应什么样的移动规则选 h 的第一步是先搞清楚你的地图允许怎么移动。移动规则决定了两点之间的最短可能距离是什么形状而 h 就应该用那个形状去估。移动规则允许方向单步代价推荐的 h说明四方向上下左右统一为 1曼哈顿距离 dx八方向斜走同价八个方向斜走也按 1切比雪夫距离 max(dx八方向斜走加价八个方向直走 1、斜走 √2对角线距离见下方公式这是最紧的估计任意方向无限制实际欧氏距离欧几里得距离√(dx² dy²)连续空间、无人机、机器人常用对角线距离的公式是h (dx dy) (√2 - 2) × min(dx, dy)。推导思路很简单先尽可能多地走斜线走min(dx, dy)步剩下的差值只能靠直走补齐走|dx - dy|步。所以总代价是min × √2 |dx - dy| × 1整理一下就是上面的形式。这个估计在八方向加价的地图上是最紧的既不夸大也不过分保守。在实际代码里我强烈建议把代价整数化。直走记 10斜走记 14√2 的近似曼哈顿距离就变成10 × (dx dy)对角线距离变成14 × min 10 × (|dx - dy|)。这样做的好处不只是省浮点运算——更重要的是避免了浮点相等比较带来的各种诡异 bug。闭表判定、f 值比较、g 值更新全都变成整数比较行为确定调试时打印出来也一目了然。2.2 h 高估之后路径会以什么方式变差可采纳性这条线一旦越过去A* 就不再保证最优了。但有意思的是它依然能返回一条路而且往往看起来还挺合理这就特别容易骗过人。举个我实际遇到过的场景。一张地图上有个大块的凹形障碍起点在凹口左边终点在凹口右边。绕开障碍需要先往回走几步再绕过去多花大概 8 步。如果用了一个略微高估的 h比如把欧几里得距离乘了 1.1那么在凹口附近绕路方向的节点 f 值会比看起来直线更近的方向大搜索就优先往凹口里钻。钻进去发现走不通再回退但此时已经浪费了大量扩展。最终它确实找到了路但那条路比最优解长了整整 8 步而且在一个实时性要求高的场景里这次的搜索耗时也是最优情况的好几倍。这种现象在业内有个说法叫被启发函数带偏。它的危险之处在于在小地图、简单障碍上几乎测不出来一旦地图变复杂就开始偶发而这类偶发问题最难定位。所以我的做法是在开发阶段给 h 加一个断言如果 h 函数被单独调用时返回的值大于沿无障碍直线走到终点的最小可能代价就直接报错。这个检查很便宜但能在早期把绝大多数 h 设计错误拦下来。顺带说一个反直觉的点h 高估导致的问题不只是路径变长还包括搜索时间反而变长。因为被带偏的方向往往通向死路进去之后要回退回退就意味着把之前跳过的那些节点重新捡起来算实际扩展量可能比用保守 h 还多。我就见过一个版本把 h 乘了 1.5 想加速结果平均耗时涨了三成查了半天才发现是这个原因。2.3 用权重给 h 松绑速度与最优之间的滑杆如果业务场景并不强求绝对最优只要求看起来合理且快那有一个非常实用的手段给 h 加权重。把选点规则从f g h改成f g w × h其中 w ≥ 1。w 等于 1 时就是标准 A*保证最优w 越大搜索越贪婪越倾向于朝终点方向猛冲扩展节点越少、速度越快但路径可能变长。这个技巧在业界被称为加权 A*思想来源是ε-可采纳的概念——理论上可以保证找到的路径代价不超过最优解的 w 倍。这个滑杆在实际项目里非常好用因为不同场景对路径质量的要求差别巨大。一个玩家操控的角色路径稍微绕一格根本看不出来但一个需要精确对齐的机械臂路径偏差就是事故。所以我通常会按用途分档w 1.0离线规划、需要严格最优的场合。w 1.2 ~ 1.5常规实时寻路肉眼几乎看不出差别速度提升明显。w 2.0 以上大批量单位同时寻路、或者只需要一个大致方向的时候。还有一个更巧妙的用法是动态权重搜索早期用大的 w 快速逼近终点区域等到当前节点离终点足够近比如 h 小于某个阈值时把 w 降回 1 做一次精细搜索。这样既有早期的速度又能保证末端路径质量。这个思路在很多实时策略类项目里是标配实现成本也就是加一个判断值得一试。不过要提醒一句加权之后之前提到的一致性保证每节点只扩展一次就可能不成立了因为 w 改变了 f 的相对大小关系。如果用了动态权重闭表的 reopen 逻辑一定要留着不然会出现路径突然断掉或者绕大圈的情况。3. 待探索集合不是随便一个容器优先队列、重复入队与延迟删除把公式想明白之后下一个决定性能的地方就是数据结构。A* 每一轮要做的事情非常固定从待探索集合通常叫 open 表里取出 f 最小的节点展开它的邻居把邻居塞回去。所以 open 表的核心操作就是插入和取最小这天然指向优先队列。我见过不少教学实现用数组或者链表维护 open 表每次线性扫描找最小值。在小数据量下没问题但节点数上千之后这个线性扫描就成了整个算法的瓶颈——因为 A* 的循环次数和 open 表大小是同一量级的整体复杂度会被拖到 O(n²)。3.1 二叉堆够不够用什么规模该换标准答案是用二叉堆插入和弹出都是 O(log n)绝大多数场景足够。用现成的语言库就行比如 C 的std::priority_queue、Python 的heapq、Java 的PriorityQueue。需要注意方向大部分堆实现是大顶堆而我们要取 f 最小值所以要么取负值存进去要么自己写比较器。堆有个绕不开的短板它不支持高效地降低某个已存在元素的键值。而 A* 里恰恰需要这个操作——当我们发现一条更便宜的路径到达节点 n 时n 的 g 变小了f 也跟着变小理论上应该更新它在堆里的位置。工程上有两条路。第一条是自己实现一个带索引的堆额外维护节点 → 堆内下标的映射支持 decrease-key复杂度 O(log n)。这条路性能最好但代码量和出错概率都上去了尤其是下标维护那一块写错一次能调半天。第二条路更常见叫懒惰删除不更新堆里的旧元素而是直接再插入一条新的记录旧记录留在堆里当僵尸。弹出时检查这个节点是不是已经被处理过或者这条记录的 f 值是不是已经过期是就跳过。这样堆里可能堆积多条同节点的记录内存占用变大但每次操作仍然是 O(log n)而且代码极其简单。我的经验是在节点规模不超过十万、且每个节点最多被更新几次的情况下懒惰删除完全够用没必要上带索引的堆。只有在极端场景下比如超大地图、节点被反复更新几十次才值得上索引堆。再往上如果代价是小范围整数比如直走 10、斜走 14 这种可以用桶队列也叫 Dial 算法替代堆把优先级按代价值分桶取最小值时顺序扫描桶即可复杂度接近 O(1)。这个技巧在几十万节点的地图上能带来明显收益代价是需要预先知道代价的上界内存开销也大一截。3.2 一个节点被多次发现g 更新和重开的判定逻辑这是 A* 实现里最容易写错的地方也是路径看起来对但莫名绕远的头号元凶。搜索过程中同一个节点很可能被多个邻居反复发现。每次发现时都要做一次判断新的路径代价g(邻居) 边代价是不是比它现有的 g 更小更小就更新 g、把父指针指向当前节点、重新入队不更小就直接丢弃。这个逻辑本身很直白问题出在节点已经进了闭表之后又被发现更便宜的路径这种情况。如果 h 满足一致性这种情况理论上不会发生所以很多实现干脆不做处理。但现实里 h 常常只是可采纳而不一致比如用了动态权重、或者 h 函数写得不够严谨再加上浮点误差闭表里的节点被翻案是真实会发生的。这时候如果不处理就会出现某段路径的父指针指向了一个已经被认为已完成的节点而那个节点到起点的实际代价比记录的大最终回溯出来的路径代价和实际不符表现出来就是路径图上看着通实际走起来绕。我的处理原则是默认允许重开。具体做法是弹出节点时先检查它是否在闭表中如果在比较堆里这条记录的 g 和闭表里记的 g如果堆里的更小就把它从闭表移除、重新处理。这段逻辑只多几行判断但能挡掉一大批疑难杂症。当然代价是极端情况下扩展量会增加所以我会加一个扩展次数的上限做兜底超过就返回当前最优解并打日志——总比死循环强。3.3 闭表的粒度决定状态空间有多大初学者容易把闭表里存的是格子坐标当成理所当然。这在纯网格寻路里是对的但一旦你的移动规则里加入了别的维度坐标就不够了。举个典型例子如果你的单位有朝向转身需要额外代价那么在 (5, 5) 面朝北和在 (5, 5) 面朝东是两个完全不同的状态代价不同、后续可达的邻居也不同。这时候状态键必须是(x, y, direction)这样的组合。同理如果移动带速度或者惯性速度也得进键。一旦状态维度上去状态空间就是指数级的。我做过一个带朝向的版本地图是 200×200加上四个朝向状态数直接变成十六万内存和耗时都翻了四倍。这种情况下有几个缓解手段一是精简朝向比如只区分八个方向而不是连续角度二是合并等价状态比如面朝北和面朝南在某些规则下代价相同就可以合并三是改用其他搜索形式比如把状态空间压缩成稀疏图只保留关键节点。还有个小细节闭表用哈希表还是数组。如果状态空间是规整的比如就是网格用一维数组按下标索引最快内存也可控如果状态是稀疏的、或者维度不固定那哈希表更合适。哈希表的开销不小每个条目几十字节几十万状态就是几十兆移动端项目要留意这一点。4. 网格地图上的隐性成本斜走代价、穿角规则与地形权重前面讲的都是图层面的东西。但绝大多数实际项目用的是网格地图而网格有自己的物理约束这些约束如果不在代价函数里体现A* 算出来的路径就会违反现实规则——最典型的就是斜着穿过两堵墙的夹角。4.1 允许斜走之后代价不能再按 1 来算假设你的地图允许八个方向移动每步代价都设成 1。看起来简单但算出来的路径会明显偏爱斜线因为斜着走一步在坐标上同时推进了 x 和 y效率是直走的两倍而收费却一样。结果就是路径变成一条锯齿状的斜线实际移动距离比直走 必要的斜走要长视觉上也很怪。正确做法是让代价反映真实的几何距离直走代价 1斜走代价 √2。整数化之后就是 10 和 14。这个比例必须和 h 函数保持一致否则就会出现g 按 √2 算、h 按切比雪夫算这种错配导致 h 系统性低估或者高估。我在排查一个路径问题时就发现过 g 用 14、h 用 10 的情况结果在地图某些区域h 的估计比 g 的实际推进还大直接违反了可采纳性路径质量一塌糊涂。还有个变体是斜走代价略高于 √2比如设成 15 而不是 14。这在某些游戏里是有意为之目的是让单位更倾向于走直线看起来更自然。这种做法会牺牲一点最优性但对观感的提升往往值得。这个取舍没有标准答案取决于你的产品更看重什么。4.2 穿角问题和贴墙走的丑陋路径所谓穿角是指两个障碍物在斜对角上相邻中间只有一个格子的缝隙。如果允许斜走A* 会毫不犹豫地从那条缝里斜穿过去——在纯数学的图模型里没问题但在有体积的实体上这等于从两堵墙的夹缝里挤过去物理上不可能视觉上也很假。解决方式有两种。一种是硬禁止在判断某个斜向邻居是否可走时额外检查它相邻的两个直向格子是否都可通行只要有一个是障碍就禁止斜走。这个规则严格、安全但会让路径在拐角处多一些直角看起来稍微僵一点。另一种是软惩罚允许斜穿但在代价上加一个惩罚值比如 5。这样大部分情况下 A* 会主动避开穿角只有在绕路代价明显更大时才会选择穿过去。这个方案更灵活适合那些偶尔穿一下也能接受的场景。与该不该穿角密切相关的是路径的贴墙倾向。默认的 A* 在等代价路径之间没有任何偏好它找到的往往是那条紧贴障碍物边缘的路线。玩家看到的感受就是这个单位怎么老是贴着墙根蹭。缓解手段是在 g 里加一个贴近惩罚如果某个格子的四邻里有障碍物代价加一个小量比如 1。这个改动很小但路径会明显往通道中间靠视觉上舒服很多。我在一个塔防类项目里加过这个惩罚反馈里单位走路很怪的抱怨基本消失了。4.3 地形代价不能只加在 g 上h 也得跟着调整真实地图很少是均匀的。草地、泥地、道路、浅水通行代价各不相同。把地形代价加进 g 是很自然的每走一步代价按目标格子的地形系数算。但这里有个特别隐蔽的坑——h 的基准必须跟着变。举个例子。如果地图上最便宜的地形代价是 0.6道路而你仍然用每步 1去估 h那 h 就高估了破坏了可采纳性路径会变差。反过来如果地图上所有格子代价都 ≥ 1你用 1 去估是安全的。所以规则是h 里用的最小步进代价必须是全图所有地形的代价下界。我在一个项目里就栽过这个跟头。地图上加了传送带地形代价是 0.3但 h 还是按 1 估。结果 A* 在一些本来应该走传送带的场景里选择了看起来更短但实际更慢的直路。后来把 h 的基准降到 0.3路径立刻正常了。代价是扩展节点数变多因为 h 变保守了——但这是必要的交换正确性优先于速度。如果地形非常不均匀还有一个折中方案h 用平均代价估同时接受轻微的高估。这在很多实际产品里是可接受的因为路径质量下降的幅度很小而速度提升明显。关键是要清楚自己在做什么并且用真实数据验证过影响而不是稀里糊涂地就用了。5. 从能跑到跑得快跳点搜索、分层规划与增量重算一个正确实现的 A*在中等规模的网格上表现通常还不错。但只要地图继续变大、单位继续变多就一定会撞到性能墙。这时候考验的就是工程优化能力了。优化方向大致有三类我按改动成本从低到高排列。5.1 跳点搜索省掉的到底是什么跳点搜索JPS是针对均匀代价网格的一个经典加速方法思路非常巧妙在开阔区域里很多路径是对称的、等价的那我们就没有必要逐个格子去展开它们。具体说在一大片空地上从起点到终点有无数条等价的走法它们的代价完全一样。标准 A* 会把这些路径上的节点全都展开一遍或者说展开其中很大一部分因为它们 f 值都相同、都有可能是最优解的一部分。跳点搜索的做法是只沿着必要的方向一路跳过去跳过中间那些不需要转弯的点直到遇到一个强制邻居——也就是那种如果我不在这里转弯就会绕更远的节点。只有这些跳点才进入 open 表。效果有多明显在一张大部分是空地的地图上跳点搜索的扩展节点数常常只有标准 A* 的几十分之一速度快一个数量级。这个提升在实时代码里是很有分量的。但它有明确的适用边界只在所有格子代价相同、移动规则统一的情况下成立。一旦你的地图有了地形代价差异对称性就被打破了跳点搜索的剪枝逻辑不再正确。所以如果你的项目需要地形代价这条路基本走不通。另外实现复杂度也高不少尤其是强制邻居的判定涉及大量边界情况写错一个条件就会漏掉路径。我的建议是除非确实卡在性能上否则先别上跳点搜索先把标准 A调优到位再说。*5.2 分层和预计算大地图的另一条路当单张地图大到连优化后的 A* 都吃力时另一个思路是降低搜索的粒度也就是分层。典型做法是把地图切成若干个区块比如每 16×16 格一个块预先算好每个区块边界上那些出入口之间的最短路径和代价。寻路时先在区块图这一层做一次粗粒度的 A*得到一条穿过哪些块、从哪个口进出的路线然后再在每一段内部做细粒度的寻路。这就是分层路径规划的基本形式。这么做的好处是搜索规模从全图格子数降到区块数量级直接降了两三个数量级。代价是需要预处理的时间和内存以及路径质量会略微下降——因为粗粒度那层只考虑块间的路径可能错过一些跨块的巧妙捷径。预计算还有一个变体是缓存把常用的起终点对之间的路径存起来下次同样或相近的请求直接复用。这在那些大量单位从固定几个出生点涌向固定几个目标点的场景里特别有效。实现上要注意缓存失效——地图一变所有涉及该区域的缓存都要作废否则单位会往已经不存在的路上走。5.3 动态障碍全量重算是最贵的做法静态地图好办麻烦的是障碍会变化——门开了关了、建筑被摧毁了、其他单位临时占位。最粗暴的做法是障碍一变就整条路径重算但这在很多场景下代价太高尤其是当变化只影响路径上很小的一段时。比较实用的做法是分段重算先判断变化点是否落在当前路径上如果不在什么都不用做如果在只从变化点附近的一个安全点开始重新规划到终点前面已经走过的那段保留。这个思路实现简单效果也好是我在多数项目里的默认选择。更激进的方案是增量搜索算法它们的核心思想是复用上一次搜索留下的信息只更新受影响的那些节点的 g 值。这类算法在机器人领域用得比较多因为机器人是一边走一边感知的环境信息持续更新全量重算完全跟不上。但它们的实现复杂度明显更高状态维护、传播逻辑都容易出错而且对图的规模有要求。我的看法是如果只是游戏或模拟场景里的偶尔变化分段重算足够了只有在真的需要高频、连续重规划的场景才值得投入去搞增量算法。另外还有一个容易忽略的点重规划不必追求每一帧都做。给每个单位一个下次可以重规划的时间点错峰执行能极大平滑 CPU 峰值。我在一个单位数量上千的项目里加了这个限制帧率的抖动立刻改善了很多。6. 我实际踩过的坑以及一条可复用的排查链路最后这部分是我这些年调试 A* 相关问题时总结出来的东西。比起原理这些更像是血泪经验因为 A* 的问题往往不报错、不崩溃只是结果不对非常考验排查思路。6.1 路径绕远时按这个顺序查最省时间遇到路径能走通但明显不是最短的情况我现在会按固定顺序查基本能在十分钟内定位。第一步看 h 有没有高估。在代码里临时加一段检查对搜索到的每个节点比较 h 值和沿无障碍直线的最小可能代价如果 h 更大就打印出来。这一步能揪出绝大多数问题包括地形基准设错、距离度量选错、坐标系搞混。第二步看 g 的累加对不对。打印一条完整路径上每一步的边代价人工核对。常见错误包括斜走按 1 算应该是 1.414 或 14、地形系数乘在了源格子而不是目标格子、以及某些方向的代价表填错了顺序。第三步看闭表判定。如果闭表是用节点是否访问过这种粗粒度判断而没有比较 g 值那么先到达的路径哪怕更贵也会被保留。改成只有更便宜才更新再试。第四步看坐标转换。这一步听起来很蠢但真的高频。地图数据是按行存的map[row][col]而寻路代码里习惯用(x, y)如果哪个地方把行列搞反了表现出来的就是路径在某些区域莫名其妙地绕因为它在另一个方向的地图上找路。我至少遇到过三次这个问题每次都是查了半天算法最后发现是两行代码的顺序写反了。第五步看穿角规则和贴墙惩罚有没有互相打架。如果既禁止穿角又加了贴墙惩罚某些狭窄地形里可能出现所有路都被重罚导致 A* 选了一条远路。这时候打印一下几条候选路径的代价明细问题一目了然。6.2 并发寻路时的性能塌方往往不在算法本身有一类性能问题特别有迷惑性单次寻路测下来很快但一上量就卡得不行。这时候罪魁祸首通常不是 A* 的复杂度而是内存分配。A* 每次搜索都要开几个容器open 堆、闭表、g 值表、父指针表。如果每次寻路都重新 new 一遍在大地图上这几个结构加起来可能是几百 KB 到几 MB。一帧内如果有几十个单位同时寻路就是几十 MB 的分配和释放垃圾回收直接被打爆。解决办法是对象池预分配几套工作缓冲区寻路开始时清空复用结束后归还。清空的方式也有讲究——如果是数组用版本号标记比逐个清零快得多每个格子存一个stamp本次搜索的编号和 stamp 不同就视为未访问避免了 O(n) 的清零开销。这个小技巧在地图上万时能带来成倍的提升。还有一个点是限制每帧的寻路预算。不要在一帧里把所有请求都处理完而是排个队列每帧只处理固定数量或者固定时间片内的请求。剩下的下帧继续。这样最坏情况下的帧时间可控玩家感受到的是有些单位反应慢半拍而不是整个游戏卡住。6.3 那些不报错但会让结果出错的边界情况最后列几个我在实际项目里真实遇到过、而且都属于不崩溃但结果错的边界情况写实现的时候值得挨个过一遍。起点就是终点。如果没做特判搜索会正常进行但因为 h 是 0可能一路扩散出去才停白费算力。加一行判断直接返回空路径。起点或终点落在障碍上。这时候搜索永远找不到终点会一直跑到 open 表空了才返回失败。如果地图很大这一次就是几秒钟的卡顿。正确做法是在入口处校验不合法立刻返回。终点不可达。和上一条类似但更隐蔽——因为地图看起来是通的只是被某个封闭区域围住了。这时候 A* 会把整个可达区域全搜一遍。应对办法是加扩展上限或者做一次快速的连通性预检查。浮点相等比较。如果代价用了浮点那么新 g 是否更小的判断在极端情况下会因为精度问题反复横跳导致同一节点被反复更新甚至出现震荡。这是整数化代价最实在的好处之一能彻底避免这类问题。父指针成环。如果 g 更新逻辑写错可能出现 A 的父是 B、B 的父又是 A 的情况。回溯路径时就会死循环。加一个步数上限做保护同时在开发期打印路径长度做断言能及早发现。这些东西单看每一条都很小但组合起来就是一个能跑但不可靠的实现。我的习惯是每写完一个寻路模块就拿一张构造好的极端地图——包含死角、窄缝、孤立区域、起终点重合——跑一遍把上面这些情况全过一遍。花半小时做这件事能省掉后面几天的 debug。我个人在实际操作中的体会是A* 这个算法最迷人的地方在于它的透明度每一个决策都能追溯到那三个数字上出了问题也一定能从 g、h、闭表、代价函数这几个地方找到原因。它不像那些黑盒式的算法调不动就只能换。所以每当我看到有人抱怨寻路不准我的第一反应从来不是换算法而是把中间过程打印出来看一眼——十有八九答案就在那几行数字里。