用地标改进 A star 寻路的启发函数
今天读到 redblobgames 写的关于如何改进寻路算法中启发式函数的文章 ，感觉很棒。我们可以用很简单的方法改进 A star 算法中的传统计算欧氏距离的方式实现启发函数的方法。
这意味着，可以直接利用之前写好的寻路模块 改变一下启发函数，就可以大幅提升性能。
A star 寻路算法，本质上是对 Dijkstra 算法的一种改进：即从一个端点扩展节点时不盲目的向外扩展，而是利用一个启发函数优先尝试最可能在最短路径上的邻接节点。启发函数设计的越好，每一步的估计都和正确路径一致，那么就越快。依靠启发函数的结果就能避开所有不必要的节点。
但是，启发函数的复杂度不能太高，最好是 O(1) 的。因为每一步都要调用一次，时间复杂度乘在整个运算过程中。这使得启发函数不能去探测远方的状态。通常我们用当前位置到目标点的直线距离作为启发值，这个值一定小于实际路径距离，这样才能保证按启发值得到的路径一定不会比真实路径更糟糕。但在有墙和复杂迷宫的地图中，它几乎难以起到正确的引导作用。
例如，当起点在一个房间中，目标点在东边，而房间的门在西边。采用这种启发函数，算法一定会向东尝试完几乎所有路径后，才会从西边的门出去。毕竟启发函数感知不到门的位置，房间内部的东侧距离目标点的直线距离一定更近。如果房间是密闭的那就更糟了，算法会尝试完房间内的每个位置才会停下来。
有没有什么简单的方法可以改进启发函数，让它可以识别出墙，却不增加时间复杂度呢？最简单的方法是用一个地标。
在现实里，如果一个人要从北京出发去广州某地，他肯定不会从出发点地开始用 A 星算法寻路。而是先去到广州再说，北京到广州的路径是事前就已知的。到了广州再找怎么去特定地点。广州作为一个区域比较抽象，但我们可以预算计算出到广州某距离地点（例如广州塔）的路线图。对于固定目的地，可以用 Dijkstra 算法计算出到地图每个点的最短路径图（ 流图 ），全部缓存下来。这样从任意点都可以用 O(1) 查询到如何去广州塔的当前移动方向。
当目的地离地标很近且当前位置离目的地很远时（从北京出发，还没进广州），按着去地标点的预设路径走一段肯定没错。直到离目的地比较近了（已经到了广州），就没必要按预设路径（去广州塔）行进了。
问题在于怎么确定离目标点比较近了？还是计算欧氏距离。
假设当前位置是 S（北京某地） ，目标点为 E （广州某地），地标点为 L （广州塔） 。这三个点可以构成一个三角形。因为三角形的任意两条边之和大于等于第三边，所以有 SE + EL >= SL 。也就是说在估价函数中，我们判断 SE 是不是大于等于 SL - EL ，即北京某地到广州某地的直线距离是不是小于等于出发地到广州塔的已知距离减去广州塔到目的地的已知距离。如果是，说明直线距离太短了，不值得按直线方向行进，应该遵循直接计算好的去广州塔的路径行进。反之，直线路径指向的方向可能是更有效的。
再看前面的房间例子：如果起点和东边的目的地之隔着一堵墙，直线距离为 1 ，但实际路径必须先绕向西侧的墙。而如果我们在目的地附近有一个预设的地标，距离目的地路程为 2，而当前位置到地标点的路程为 10 ；那么显然，从当前位置去目的地的最短路程不可能小于 10 - 2 = 8 。因为假设目的地就在去地标点的路径上，那么我们向地标行进，在剩下路程还有 2 的时候，就能抵达终点。这已经是最短路径，如果目的地偏离了这条路径，路程只能更远。
用地标的预设路程，可以更容易的排除目的地不可达的情况：如果我们可以去到地标，而地标到目的地不可达，那么目的地就不可达；同样，如果地标到目的地可达，而我们无法去到地标，目的地也不可达。如果目的地和当前位置都可以抵达地标，路径一定是存在的。只有当前位置和目的地都无法通向地标试，可达性才是未知的。
所以，我们在估价函数中，只要利用预算计算好的地标流图，就可以 O(1) 计算出是否可以复用到地标的流图给出预设方向，或是退化成传统以直线方向给出的估价值。
我们还可以多计算几个地标，比较它们哪个更有效：SL - EL 中较小的那个，决定采用到哪个地标的预设路径。地标可以是提前计算的，也可以是在多次寻路中生成的。可以想象成，如果我们没有去过广州，那么就先以一个离广州比较近的去过的地标，比如深圳为地标导引路径，一旦抵达目的地，就把新的这个目的地广州为地标记录下来，方便后续的寻路。