障碍物如何干扰搜索

一旦向网格添加障碍物，算法行为差异就变得更清晰。例如，如果墙壁隔开 a 和 b，Dijkstra 算法总会找到最快的路径，但代价巨大。围绕 a 的圆形前沿半径将等于最终路径的长度；我们把这个半径叫 r。如果没有网格边界裁剪前沿，你可以粗略计算打开的节点数量，取半径为 r 的圆面积。如果绕墙路径是 50 个瓦片，算法会打开大约 7,854 个瓦片，如这个方程：π× 50² = 7,854。

同样场景下，贪婪最佳优先搜索会计算次优路径，但打开的瓦片少得多。前沿如何扩展不容易可视化，现在也不重要，所以我不会在这里深入。归根结底，这两种算法都不太适合寻路问题。最优路径慢，快路径不最优。

要快速计算最优路径，你需要把 Dijkstra 算法与贪婪最佳优先搜索融合。幸运的是，已经有人做到了，得到的算法是一个叫 A-star 搜索（通常简称 A*）的怪物。

A 用成本 g 和启发式 h 的和选择节点。这个结果和称为分数。简单来说，score = g + h。与 Dijkstra 算法一样，A 可以计算从 a 到 b 的最优路径，与贪婪最佳优先搜索一样，它可以相对快速地做到。