两种常见搜索技术

给定一个瓦片网格、起始位置 a 和结束位置 b，搜索算法计算从 a 到 b 的路径。算法通过在 a 创建节点、把与 a 相邻的节点添加到待探索瓦片列表（称为前沿）、把节点更新为前沿中最好的瓦片，并重复这个过程直到节点到达 b 来做到这一点。不同搜索算法用成本、启发式或两者兼有来选择最佳节点。

例如，Dijkstra 算法根据瓦片与 a 节点的距离计算成本，选择成本最低的瓦片。想象一个 a 在中间的空二维网格。在遵循 Dijkstra 算法的搜索中，前沿会围绕 a 呈圆形扩展，直到 b 位于圆边，如图 11-4 所示。

贪婪最佳优先搜索算法不按节点与起始点的距离优先级排序，而是用启发式估计前沿中节点到 b 的距离。算法然后选择估计距离最短的节点。想象这个算法在之前相同的网格中；前沿会是一条几乎直接从 a 到 b 的线，如图 11-5 所示。

瓦片成本更高。