javascript - 2个坐标之间的最短路径，通过一组坐标 - Javascript

Question

我需要编写一个 JavaScript 算法来找到 2 个坐标之间的最短路径。我研究过使用一些路径查找算法，例如 A* 算法。

然而，我的应用程序的不同之处在于我知道路径可以采用的所有坐标。

例如，在下图中，绿色方 block 是起点坐标，红色方 block 是终点坐标。每个黑色方 block 所代表的坐标将存储在一个数组(或其他数据结构)中。

所以我需要从绿色方 block 到红色方 block 的最短路径，但它只能通过一个黑色方 block 才能到达那里。我还会使用 A* 算法来实现吗？

Answer 1

是的，您可以使用 A*。您将计算从每个黑色坐标到红色方 block 的距离(移动次数)。然后你得到一个图形结构，你可以从哪个方 block 移动到哪个方 block ，并且该图中的每个节点都存储到红色方 block 的距离。然后将 A* 应用于该图并获得最短路径。

编辑

对于 A*，您需要一个启发式算法，它会告诉您哪个节点更接近端点。计算黑色区域和红色区域之间的“空中距离”可为您提供每个区域的启发式方法。然后你做 A*，这基本上是带有启发式的 Dijkstra 算法。在您的示例中，如果左上角为 (x = 0, y = 0)，红色为 (14, 7)，绿色为 (0, 1)，则绿色和红色区域之间的空气距离为ABS(14 - 0) + ABS(7 - 1) = 20。所以很容易从坐标计算。