我需要编写一个 JavaScript 算法来找到两个坐标之间的最短路径。我研究过使用一些路线查找算法，例如 A* 算法。
然而，我的应用程序的不同之处在于我知道路径可以采用的所有坐标。
例如，在下图中，绿色方 block 是起始位置坐标，红色方 block 是结束位置坐标。每个黑色方 block 代表的坐标将存储在一个数组(或其他数据结构)中。
所以我需要从绿色方 block 到红色方 block 的最短路径，但它只能穿过黑色方 block 才能到达那里。我还会使用 A* 算法来实现这个吗？
最佳答案
是的，您可以使用 A*。您将计算从每个黑色坐标到红色方 block 的距离(移动次数)。然后你得到一个图形结构，你可以从哪个方 block 移动到哪个方 block ，并且该图中的每个节点都存储了到红色方 block 的距离。然后将 A* 应用于该图并获得最短路径。
编辑
对于 A*，您需要一个启发式方法，告诉您哪个节点更接近端点。计算黑色字段和红色字段之间的“空气距离”可以为每个字段提供此启发式。然后你做 A*，这基本上是带有启发式的 Dijkstra 算法。在您的示例中，如果左上角为 (x = 0, y = 0)，红色为 (14, 7)，绿色为 (0, 1)，则绿色和红色字段之间的空气距离为ABS(14 - 0) + ABS(7 - 1) = 20。所以根据坐标计算起来非常容易。
关于javascript - 通过一组坐标，两个坐标之间的最短路径 - Javascript，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40992807/