I was very curious about the heuristics used, when a while back we got routes from the same starting location near Santa Rosa, to two different campgrounds in Yosemite National Park. These different destinations produced quite different routes (via I-580 or CA-12) despite the fact that both routes converged for the last 100 miles (along CA-120) before diverging again by a few miles at the end. This was quite repeatable. The two routes were up to 50 miles apart for around 100 miles, but the distances/times were pretty close to each other as you would expect.

唉，我无法重现——算法肯定已经改变了。但这让我对算法很好奇。我所能推测的是，有一些方向修剪，恰好对从远处看的目的地之间的微小角度差异非常敏感，或者有不同的最终目的地选择的预先计算的片段。

我知道OP里的地图是怎么回事了:

用指定的中间点来观察路线:由于那条路不直，这条路线略微向后走。

如果他们的算法不会回溯，它就看不到更短的路线。

像Dijkstra算法这样的图算法将无法工作，因为图是巨大的。

这个论点并不一定成立，因为Dijkstra通常不会查看完整的图，而只是一个非常小的子集(图的互联性越好，这个子集就越小)。

对于行为良好的图，Dijkstra实际上可能表现得相当好。另一方面，通过仔细的参数化，A*总是表现得一样好，甚至更好。您是否已经尝试过它对数据的处理方式?

也就是说，我也很有兴趣听听其他人的经历。当然，像谷歌Map搜索这样的突出例子是特别有趣的。我可以想象类似于有向近邻启发式的东西。

我有点惊讶这里没有提到Floyd Warshall的算法。这个算法很像Dijkstra算法。它还有一个很好的特性，那就是它允许你计算，只要你想继续允许更多的中间顶点。因此，它自然会很快找到使用州际公路或高速公路的路线。

Probably similar to the answer on pre-computed routes between major locations and layered maps, but my understanding is that in games, to speed up A*, you have a map that is very coarse for macro navigation, and a fine-grained map for navigation to the boundary of macro directions. So you have 2 small paths to calculate, and hence your search space is much much smaller than simply doing a single path to the destination. And if you're in the business of doing this a lot, you'd have a lot of that data pre-computed so at least part of the search is a search for pre-computed data, rather than a search for a path.

地图从不考虑整个地图。 我猜是:- 1. 根据你的位置，它们加载一个地方和那个地方的地标。 2. 当你搜索目的地时，他们会加载地图的另一部分，然后用两个地方做一个图，然后应用最短路径算法。

此外，还有一个重要的技术动态规划，我怀疑是用在最短路径的计算。你也可以参考一下。