改进 A* 寻路的启发函数

2026 Jul，不过类似尝试自 2015 年起就做过多次

优化 A* 的时候，我们通常关注优先队列或地图表示，但常常忽略的是启发函数本身的改进。下面这个例子来自《龙腾世纪：起源》中的 Denerim 城镇。试着拖动起点和终点，看看 A* 是怎么工作的：

现在再把绿点移近紫点。当启发值 越来越接近真实距离 时，A* 需要探索的节点数会从 减少到 。蓝色区域就是省下来的部分。

在这篇文章里，我会介绍一种改进启发函数、从而加速 A* 的方法。文末会用真实游戏中的地图演示这个技巧。

 1  A* 怎么使用启发函数#

A* 用一个启发函数来引导它走向终点。我们可以把它想象成一股推着我们前进的风——启发函数把我们向东推，最短路径 也是向东：

但有时候它会把我们往错的方向推。最短路径明明向西，启发函数却把我们向东推：

启发函数方向指得对，A* 就跑得快；指错了，就会浪费时间。可它为什么会指错？因为常用的基于距离的启发函数根本不知道障碍墙的存在。

 2  完美启发函数#

理想情况下，我们想找到一种知道障碍墙存在、而且永远不会指错方向的启发函数：

我们能算出这个"完美"启发函数吗？能！

不过，完美启发函数依赖于具体的目标点和障碍墙布局。移动目标点 时，你会发现启发函数会变；而移动起点 时，它则不变。

如果目标点和障碍墙保持不变，可以直接用流场寻路（flow field pathfinding）。但一般来说目标点会变，所以就得为每个目标点重新算一个完美启发函数。每跑一次 A* 都重新算一遍太慢了，而要提前算好再存起来，数据量又太大，根本不现实。

如果我们能只计算一次启发式，然后在多次 A* 运行中（针对不同目标点）复用它，那就太好了。

 3  复用完美的启发式#

让我们计算到绿色 L 的完美启发式，我们称 L 为"地标"。这个启发式能复用到另一个目标点 X 吗？可以，但要看情况！移动起点 B 和地标 L，看看哪些紫色目标点会从中受益：

思路是这样的：如果我们已经知道从 B → L 的路径，那么沿途任何 X 点的最短路径也同时得到了：

把地标想象成远方的一个参照物。朋友告诉你"从你家 B 出发，朝埃菲尔铁塔 L 的方向一直走，走到 Daniel 家 X 就到了"。目标并不是到达地标本身；地标给的是一个方向，而真正要去的 Daniel 家正好在途中。

大多数目标点 X 都不在 B → L 这条路径上，但有时它们离这条路径很近：

但"近"到底是什么意思呢？我们可以用路径长度 cost(B, L) 来衡量。当两条路径几乎重合时，cost(B, L) 就接近 cost(B, X) + cost(X, L)。

在 A* 中，我们用启发式函数作为路径长度 cost(B, X) 的下界。三角不等式^[1] 指出，三角形任意两边之和总是不小于第三边。套用到有向图上，可以得到 cost(B, X) + cost(X, L) ≥ cost(B, L)。为了求下界，我们把它改写成 cost(B, X) ≥ cost(B, L) - cost(X, L)。

这就是本文的核心思想。预先算出到所有位置的距离是不现实的，但如果我们已经预先算出了到某个特定位置 L 的距离，就可以用它来估算到另一个位置 X 的距离。

一些学术论文称之为基于三角不等式的启发式；另一些论文则称之为"差分启发式"，因为它本质上取的是两个已计算距离之差。

 4  使用多个地标#

这个三角不等式有多常用呢？

这取决于它相对于路径 → 的位置：

	相对位置	地标是否有用？
之前		仅在无向图中
中间		没用
之后		有用

移动起点 和终点 ，看看地标在哪里会有帮助：

试着把地标 移到绿色阴影区域外面，你会发现启发函数和路径并不总是一致的。

由于地标需要处于终点 "之后"，单个地标并不能对所有路径都起作用。我们需要多个地标 L₁、L₂、L₃ 等等。每个地标都能给出一个启发函数的下界：

cost(B, X) ≥ cost(B, L₁) - cost(X, L₁)
cost(B, X) ≥ cost(B, L₂) - cost(X, L₂)
cost(B, X) ≥ cost(B, L₃) - cost(X, L₃)
…
cost(B, X) ≥ cost(B, Lₙ) - cost(X, Lₙ)

我们可以取这些值的 max()，选其中最高的界。在这张图里，把终点 移到紫色阴影区域，看看这些区域是怎么被地标改善的。然后再把它移到非阴影区域，看看在这些地方 A* 并不会更快。也可以试着移动起点 ，观察阴影区域如何也依赖于起点的位置。

 5  地标的放置#

最佳的地标位置取决于起点 以及终点 。我们希望地标处于终点 "之后"，但"之后"是相对的，取决于起点 和终点 的位置。

我们希望用地标来尽可能多地改善 (起点, 终点) 对。

先从单个地标开始。在这张地图上试着移动起点 、终点 和地标 ：

紫色阴影区域显示了地标能够起到帮助的终点位置。看起来地标能覆盖主要走廊，但覆盖不了侧边的房间。我们需要更多的地标：

现在地图的大部分都被紫色覆盖了。地标的数量和位置的选取 取决于具体项目。需要考虑：

• 所有路径出现的概率相同吗？比如在《矮人要塞》这样的殖民地建造游戏中，我们可能更关心从主基地出发或到达主基地的路径，而不关心从森林到矿坑的路径。
• 是否所有路径都具有同等的优化价值？比如当寻路限制了帧率时，我们更应该把精力放在那些计算耗时的长路径上，而不是短路径。
• 地图是静态的还是会动态变化？如果是静态的，我们可以花大量时间在地图编辑工具中预先算出最优地标。但如果是动态地图，或许应该用最近的几个目标点位置来决定新的地标位置。
  • 如果变化降低了某条边的代价，启发函数就会偶尔高估，A\* 在我们更新代价表之前会返回非最短路径——寻路更快但不再最优。例如：玩家砸开了一面墙，但单位不会立刻找到更短的路径。
  • 如果变化增大了某条边的代价，启发函数就会比预期偏低，A\* 在我们更新代价表之前需要多花一点时间——寻路保持最优但不够高效。例如：玩家加了一面墙，单位还以为那块区域可以走，结果只能绕道而行。
• 如果大量单位都在寻路前往相同的区域（比如矮人堡垒的餐厅），可以考虑移除最少被使用的地标，在公共区域附近新增一个。
• 地图是开放世界还是封闭场景？即时战略游戏和房间+走廊的地牢探险游戏在寻路上会有截然不同的诉求。
• Thomas Nobes 做了一个视频讲解^[2]，里面还有更多关于地标点放置的建议。

幸运的是，即便某个地标位置不够理想，它多少还是能起点作用，最差也不过是和普通 A\* 启发函数打个平手。

 6  自动放置#

虽说最佳地标位置因项目而异，但有一种与项目无关的通用算法：持续记录哪些位置对大量随机路径都有不错的效果。点这里试试，看看会算出什么地标位置：

(start animation)

结果通常（但不总是）落在地图的左上角——和我们直觉相符，地标就应该放在地图的边缘地带。

第二个地标要远离第一个地标，第三个要远离前两个，之后每加一个都要看它带来了多少新信息。已有两个地标时大致是这个过程：

(start animation)

它选的第三个地标总是离前两个远，但位置不一定每次都一样。

 7  实现#

这一页介绍的变化只涉及传给 A* 的启发函数，A* 本身不用动。

第一步是选地标。如果地图是提前确定的，可以在关卡编辑器里手工放；如果地图是程序化生成的，可以试试本页前面提到的随机地图分析法。页末列出的几篇论文还介绍了更复杂的地标放置算法。

然后是分析地图：分配一个二维数组 cost[nodeId][landmarkId]。

对每个地标，跑一遍 Dijkstra 算法。它本来是“单源最短路径”算法，但我们这里要的是单个终点而不是单个起点。在有向图中需要把所有边反向，在无向图中则直接用原图即可。把 cost[nodeId][landmarkId] 设为从 nodeId 到 landmarkId 的最短路径代价。如果所有边权都是 1，可以用广度优先搜索（BFS）代替 Dijkstra。

下面大致就是本页演示所用的代码（针对无向图）：

const L = [ /* 地标位置数组 */ ];
let L_cost = [ /* 按 nodeId 索引的数组，每个元素是按 landmarkId 索引的数组 */ ];
for (let landmarkId = 0; landmarkId < L.length; landmarkId++) {
    let output = dijkstraSearch(L[landmarkId]);
    for (let nodeId = 0; nodeId < graph.num_nodes; nodeId++) {
      L_cost[nodeId][landmarkId] = output.cost_so_far[nodeId];
    }
}

注意：代码量并不大，无非就是跑现有的算法（Dijkstra、A* 或 BFS），把结果存进数组。整个过程完全可以放到后台线程里执行。

最后是改造启发函数。以前是 distance(B, X)，比如：

function heuristicManhattan(a, z) {
    return Math.abs(a.x - z.x) + Math.abs(a.y - z.y);
}

每个地标 L_i 都能给出一个下界 cost(Lᵢ, X) - cost(Lᵢ, B)。我们取其中最大的那个：

function heuristicLandmark(B, X) {
    let h = heuristicManhattan(B, X); // 或任何基础启发函数
    for (let i = 0; i < L.length; i++) {
        let lowerBound = L_cost[B][i] - L_cost[X][i];
        lowerBound = Math.abs(lowerBound); // 无向图需要取绝对值
        if (lowerBound > h) { h = lowerBound; }
    }
    return h;
}

注意这部分代码并不多。它只是先运行原有的启发函数（通常是曼哈顿、切比雪夫或欧几里得距离），当地标构成较好的三角形时再把这个值适当提高。

A* 代码本身需要改吗？完全不用。

加速 A* 的方法有很多。我喜欢这个，是因为改动非常小。

 8  演示#

我在一些地图上测试了差分启发函数，包括《龙腾世纪》的几张地图（来自 movingai.com^[3]）、一个迷宫地图（同样来自 movingai.com）以及 Cogmind^[4]（地图由 Josh Ge 提供）。这些地图都是无向图（边是双向的），因此我使用的是差分启发函数的无向版本。

• 蓝色区域表示使用差分启发函数后不再需要搜索的部分，橙色区域则表示即使有了改进的启发函数仍需搜索的部分。
• 尝试移动起点 和终点 ，观察不同路径下的性能表现。

 8.1 龙腾世纪：圆塔#

初始路径的地标 位置并不理想，试着移动它看看。

 8.2 Cogmind，工厂 5#

下一个演示中，地标 所处的位置对搜索帮助不大，移动它们可以改善搜索效果。

蓝色区域是不再需要搜索的节点。蓝色越多越好。

地标 越靠近起点 而不是终点 时，帮助更大。当地标位于终点 "之外"时效果也更明显。随意移动起点 和终点 ，可以看到无论要找的是哪条路径，性能都有显著提升：

不过，要达到这个效果需要用很多路标点。我们可以做得更好：借助随机路径地图分析来挑选数量更少、位置更合理的路标点：

 8.3 迷宫#

在迷宫这类地图中，带距离启发式的 A* 表现尤其糟糕，但在这个例子里，只要四个路标点就能带来巨大的提升！然后反复点击 Random path。蓝色区域就是我们因为使用路标点而无需搜索的区域。另外可以切换双向搜索开关，看看它能带来多大的改善。

 8.4 龙腾世纪，洛瑟林#

这张地图有大片开阔区域，用路标点效果不错。

 8.5 Cogmind，Research 2#

这是 Cogmind 中的一张房型走廊地图。

 8.6 Cogmind，Factory 4#

又一张房型走廊地图，传统 Roguelike 地牢中很常见。

 9 延伸阅读#

本文讲的是如何在游戏地图中使用笛卡尔坐标来构建基于“路标”（landmark）节点（也叫“pivot”或“beacon”）的图启发式。我收集了一些参考资料，但并没有全部读完，所以有些内容可能理解有误。

• 2004 Computing the Shortest Path: A* Search Meets Graph Theory^[5]（Goldberg、Harrison）[镜像^[6]]。我就是从这篇论文里学到这个方法的。它把双向 A* 搜索和基于路标的启发式结合起来，用于道路网络。文中使用了“landmarks”和“triangle inequality”这两个术语。
• 1994 Routing information organization to support scalable interdomain routing with heterogeneous path requirements（Hotz）。[引用^[7]] 我在网上没找到原文，但这篇工作似乎最早把三角不等式与路标结合用于互联网路由。
• 2005 Approximate Distance Oracles（Thorup、Zwick）[镜像^[8]]。这篇理论论文讨论了一个更通用的问题：如何使用“距离预言机^[9]”来计算图中任意两个节点之间的近似距离。A* 中所需的启发式函数本质上就是一种近似距离。

反过来做也是可以的。许多图并不天然具有笛卡尔坐标，而即使有，基于距离的启发式也可能效果不佳。

• 2002 Predicting Internet Network Distance with Coordinates-Based Approaches^[10]（Ng、Zhang）[镜像^[11]]。该论文利用地标启发式为互联网路由网络中的节点赋予笛卡尔坐标，再以欧几里得距离作为启发式。这恰好与本文的做法相反——我们这里已有笛卡尔坐标，却希望改用地标启发式。
• 2011 Euclidean Heuristic Optimization^[12]（Rayner、Bowling、Sturvetant）针对游戏地图中距离启发式效果不佳的情况，将原有笛卡尔坐标变换为新的笛卡尔坐标，使得基于距离的启发式能够良好工作。

存储地标数据需要为每个节点保存一个数值。在典型的游戏地图中，相邻格子之间的这些数值往往非常接近。正如图像压缩利用相邻像素相似性那样，我们也可以利用相邻图节点值相近的特性来压缩地标数据：

• 2011 The Compressed Differential Heuristic^[13]（Goldenberg、Sturvetant、Felner、Schaeffer）——在相同存储空间下保存更多地标，可获得更好的启发式效果。该论文将"地标"称为"pivots"，将"基于地标的启发式"称为"差分启发式"。

本页使用的地标放置在路径的末端之后，布局是 →→。也有算法把地标放在路径的沿途，→→→→。这里不展开讨论这个话题，但如果你感兴趣，可以参考：

• 2008 年 Approximating Shortest Paths using Landmarks^[14]（Grant, Mould）。文中称之为 "landmarks"。
• 2014 年 Hub Labels: Theory and Practice^[15]（Delling, Goldberg, Savchensko, Werneck）。文中称之为 "hubs"，且路径上只用一个中间节点 B→L→X。
• 2009 年 Abstraction-Based Heuristics with True Distance Computations^[16]（Felner, Barer, Sturvetant, Schaeffer）。我认为这篇论文试图统一两类"地标"方法。B→X→L 被称为 "differential heuristic"，B→L→L→L→X 被称为 "canonical heuristic"，二者都归入 "true distance heuristics" 这个总称之下。

我在 2007 年第一次接触到这项技术，然后在 2015 年尝试把它写下来。当时我发现理解得还不够，没法讲清楚。此后在 2016、2018、2019、2022、2024 和 2026 年断断续续地学习过。这个页面也是写写停停、重启过很多次。到 2026 年，我觉得自己理解得够清楚了，于是写成了这一页。不过我还没在真实项目里实际使用过它。