五种寻路算法交互实验
从家走到咖啡店，有一条直穿泥地的小路，也有一条绕过街角的干净人行道。前者步数少，后者可能更省力。
计算机替角色找路时，也会遇到类似的问题：先往哪里探索？遇到墙怎么办？什么时候能确定这条路线已经足够好？我们说的“最短”，究竟是步数最少，还是总代价最低？
接着迷宫与地牢实验室和排序算法实验室，这次做一个可以亲手画地图的寻路 Demo。墙、泥地、起点、终点都能修改；每次运行，浏览器会根据当前地图重新计算搜索过程。
动手体验寻路
下面是一张 13 × 9 的小地图。S 是起点，G 是终点，数字 5 表示泥地：走入这格需要花 5 点代价，普通空地只花 1 点。
先点击“看结果”，再切换到 Dijkstra 或 A*，重新看结果。地图保持不变，路线却会发生变化。
这张图的中间一行，相当于：
1 | S → 5 → 5 → 5 → 5 → 5 → 5 → 5 → 5 → 5 → G |
直走共 10 步，经过 9 格泥地，再走入终点，总代价是 9 × 5 + 1 = 46。从上方或下方绕开这排泥地，要多走两步，但每一步都在普通空地上，总代价只有 12。起点本身不收费。
| 本页示例的结果 | 路线步数 | 总代价 |
|---|---|---|
| BFS、DFS、贪心最佳优先 | 10 | 46 |
| Dijkstra、A* | 12 | 12 |
这是这张固定地图、四方向移动、泥地代价为 5 时，本页实现的结果。换地图或规则后，数字会变化；DFS 也不会在所有地图上都给出和 BFS 一样的路线。
试着展开“实验参数”，把泥地代价调成 1。现在每一步一样贵，直走重新变得划算。再调到 2，看 Dijkstra 和 A* 是否已经决定绕路。
读懂搜索过程
图中的蓝色格子是已发现、等待检查的位置，青色是已检查的位置，黄框标出当前正在检查的格子。找到终点后，黄色连线才表示最终路线。S、G 和泥地数字会一直保留。
搜索过程是在比较候选位置，并不代表游戏角色已经把所有有颜色的地方都走了一遍。角色真正要走的，是最后选出来的路线。
“下一步”检查一个格子；“上一步”和进度条可以回看。自动运行只是替你连续点击下一步，随时能暂停，也可以点“重跑此图”从头观察。你还可以：
| 想做的实验 | 操作 |
|---|---|
| 自己设计障碍 | 选“画墙”后点击或拖动；“擦除”恢复空地 |
| 改变走路成本 | 选“铺泥地”，再调整泥地代价 |
| 移动两端 | 选“S 起点”或“G 终点”，点击新位置 |
| 生成新地图 | 选择随机障碍或迷宫，输入种子后重新生成 |
| 对照同一张图 | 直接切换算法，或展开“五种算法一起对照” |
| 让朋友重做实验 | 点击“分享”，链接会保存手绘地图、起终点与规则 |
修改地图或通行规则后，旧搜索会清除，等待重新开始。换算法保留地图；改地图大小、选择新示例或重新生成，会替换地图。随机图不保证连通，终点被围住时，正确结果就是“无路可走”。
BFS 广度优先：逐层探索
往平静的水面丢一颗石子，波纹先到近处，再到远处。BFS（Breadth-First Search）也从起点开始，先看一步能到哪里，再看两步、三步能到哪里。
它手里有一条队列：新发现的位置排到队尾，每次取走队首。先发现的先检查，所以还没看完“走两步能到的地方”时，不会先跳去检查“走三步才到的地方”。
1 | 第 0 层：起点 |
在每次移动都算一步的网格里，这个顺序保证 BFS 找到步数最少的路线。普林斯顿《Algorithms》的无向图章节也用队列逐层搜索来说明 BFS 的最短路径性质。
但 BFS 的队列不会因为一格泥地更贵，就把它排到后面。所以在开头的示例中，它正确地找到了 10 步路线，却没有替我们节省总路费。
试一试： 打开绕墙地图上的 BFS。看搜索区域如何绕过墙底的缺口，再向另一侧扩散。暂时忘记公式，只看这圈“水波”。
DFS 深度优先：沿分支深入
想象带着线团进入岔路：先挑一条路往里走，遇到尽头，再回来尝试其他分支。DFS（Depth-First Search）体现的就是这种优先深入的思路。
本页用一个栈存放待检查的位置：后放进去的先取出来。只需改变取出顺序，搜索的样子就从“铺开一圈圈水波”变成了“沿分支深入”。普林斯顿的图搜索说明将 DFS 用于访问可达顶点，并记录可返回的路径。
这里的实现会在格子首次入栈时标记它，记下来自哪里，之后不重复入栈。这是迭代式的深度探索；待检查格子和前驱树的细节不必与递归写法完全相同。为便于重复比较，方向顺序固定，优先往右深入。
DFS 可以判断这张有限地图上的终点是否可达，但它不保证步数最少，也不保证代价最低。先找到一条路，和找到最好的路，是两件不同的事。
试一试： 打开空白地图上的 DFS，把 G 移到 S 上方的空地。明明两端很近，它却可能先沿着偏好的方向绕一大圈。
还有个有趣的对照：在本页生成的迷宫中，四方向移动时两点之间只有一条通路。不同算法最后可能给出同一路线，但途中检查了多少格子，仍然很不一样。
Dijkstra：按代价探索
现在给旅行者一本账本。每发现一个位置，就记下“从起点到这里，目前知道的最低路费”，把它叫作 g。
Dijkstra 不再只按排队先后来取位置，而是每次挑 g 最小的那个。如果后来发现一条更便宜的来路，就更新账本，同时修改“从哪里走到这里”的记录。这个更新动作常叫作“松弛”，可以直接理解为：发现便宜路线，就改账。
例如，某个格子原本要花 9 点才能到达；新检查的邻居只花了 4 点，再走一步进入它花 1 点。于是 4 + 1 = 5 比 9 更便宜，这个格子的记录就改成 5。
当所有边的代价非负时，Dijkstra 每次取出的最低代价格子，其最低代价可以确定下来。本页的空地、泥地和斜走代价都为正，满足这个条件。相关原理见普林斯顿的最短路径章节。
这里有一个容易忽略的时刻：终点被取出来检查时才停止，不能刚发现终点就宣布结束。 终点初次进入待检查区域时，可能还存在一条没有探索完的便宜路线。
在泥地示例里，Dijkstra 愿意多走两步，就是因为它比较的是路费账本。它并不知道终点在哪个方向，所以也可能检查不少与目标方向无关、但到达成本较低的格子。
贪心最佳优先：接近终点
如果把账本换成一张只指示目标距离的地图，就得到另一种思路：优先检查看起来离终点最近的位置。
这个估计值叫 h。例如，在只能上下左右移动时，某格与终点横着相差 4 格、竖着相差 3 格，那么忽略障碍估计还要走 4 + 3 = 7 步。这叫曼哈顿距离。
贪心最佳优先搜索只用 h 排序。它可能很快朝目标推进，但估计时没有看到墙，也没把已经花掉的路费算进去。直线方向上隔着一片昂贵泥地，它也可能毫不犹豫地往前找。
试一试： 在泥地捷径上运行贪心搜索。它只检查少量格子就到达 G，却付出了 46 点代价。少检查几个格子，不等于找到了更好的路线。
g 和 h 的区别，以及这种只追逐估计距离的搜索方式，可以在 Red Blob Games 的A* 原理演示中继续对照。这里的地图、实现和实验数据则由本页独立生成。
A*：结合代价与估计
A* 把账本和地图放到一起：
1 | g：从起点到这里，已知的最低代价 |
每次选择 f 最小的位置。它既不会像贪心那样忘记已经花掉的路费，也能利用目标方向，使探索更有针对性。
假设两个候选格子：甲的 g = 4、h = 8，乙的 g = 7、h = 3。甲目前花得少，但估计全程为 12；乙虽然已经花了 7，估计全程却只要 10。A* 会优先检查乙。
不过，h 不是随便猜得越大胆越好。要保证最优，启发式需要满足相应条件；像本页这样关闭已检查节点、不重新打开的实现，使用一致的启发式可以保证正确性。直观地说，从相邻格往目标迈一步，估计距离的下降不能超过这一步的真实代价。
本页按最低地形代价 1 来估计，忽略墙和泥地额外成本：四方向使用曼哈顿距离；八方向使用适合直走与斜走的距离。两者都不高估，并与当前规则一致，因此本页 A* 能找到最低总代价路线。启发式与移动方式的配合可参考 Red Blob Games 的实现说明。
最值得动手的一项： 在 A* 参数中选择“h = 0”。公式变成 f = g，它就成了 Dijkstra。地图完全不动，对比“已检查格数”，便能看见启发式为这张图提供了多少帮助。
开头的固定泥地示例中，本页 A* 检查 13 格，Dijkstra 检查 69 格，两者都得到代价 12 的路线。这是该地图及当前并列优先级规则下的结果，不意味着 A* 在每张地图上都严格少检查，也不代表真实耗时一定按格数成比例。
斜向移动的代价
参数可以从四方向改成八方向。本页规定直走长度为 1，斜走长度为 √2 ≈ 1.414，再乘以走入地形的代价。因此，斜着走入代价 5 的泥地，一步花费 5 × √2。
这带来两个需要说清楚的细节。
首先，即使全是普通空地，直走与斜走的代价也不相同。BFS 依然能最小化移动次数，但不能再据此保证几何路程或总代价最小。
其次，斜走不能穿墙角。如果右侧或下侧有墙，就不能直接从当前格斜着进入右下角。这能避免角色从两个障碍之间挤过去；生成、手绘地图和五种算法共用同一条规则。
对于八方向的距离估计，设横向差为 dx、纵向差为 dy，可以先斜走较小的那部分，再直走剩下的距离：
1 | h = min(dx, dy) × √2 + |dx - dy| |
例如横差 4、竖差 3，忽略障碍时可以斜走 3 次、直走 1 次，估计为 3√2 + 1。本页会自动切换这个估计，不需要手动修改公式。
五种算法对比
| 算法 | 优先检查谁 | 本页能保证什么 |
|---|---|---|
| BFS | 最早进入队列的格子 | 移动步数最少；每条边等代价时，总代价也最低 |
| DFS | 栈顶、最近加入的分支 | 判断可达性；不保证最短或最低代价 |
| Dijkstra | 已知到达代价 g 最小的格子 | 在本页正代价规则下，总代价最低 |
| 贪心最佳优先 | 估计剩余距离 h 最小的格子 | 不保证最短或最低代价 |
| A* | g + h 最小的格子 | 在本页匹配且一致的启发式下，总代价最低 |
把格子看作顶点、允许的移动看作边，这些方法就不只属于迷宫：它们也是图搜索。网格只是让“顶点、边、代价”变得能直接画出来。实际应用可能还要处理连续地形、角色体积、动态障碍或多角色避让，那些需要在寻路模型上继续补充规则。
实验表格展示的是最终路线步数、总代价和已检查格数。前两项描述路线，后一项帮助观察探索范围。播放速度只是阅读节奏；本页为回看保存的快照，也不是算法自身所需的全部存储模型。
不妨最后亲手画一个小实验：先用一面墙挡住目标，再留一个远处的缺口；把缺口附近铺上泥地，慢慢调高代价。观察每种算法先看哪里、何时转向，以及它最终愿意走哪条路。参数一变，课本上的名字就变成了可以看见、可以重复验证的选择过程。