actionscript-3 - 在 X 步中找到从点 A 到 B 的路径。 (一个*左右)

Question

我目前正在研究一种可视化数据的方法，该算法的一部分需要与 A* 路径查找 99% 相同的东西，但我无法完全理解它。我知道这将是一个相当简单的修改。 (特定成本而不是最低成本)

基本上我需要绘制一条从点 A 到点 B 的路径(二维网格，无对角线)，步数为 X。

例如如果起点和终点彼此相邻并且我需要路径为 3 步，那么它会有一个小循环。 (移动:向上、向右、向下)。

这个算法是否有一个已知的名称，或者这种算法的使用是否非常罕见？

我目前正在查看这个 AS3 Librbay 进行修改，因为它显然非常快并且对我来说看起来干净简单: http://www.dauntless.be/astar/

非常感谢任何建议/帮助...

约翰

Answer 1

我喜欢这个问题 - 它很有趣。

我不确定我该如何编写代码，但这些只是我脑海中浮现的想法。

基本上，您正在处理 Manhattan distance在这里，因为您没有使用对角线。因此，您需要知道最短的可能路径并从那里得出。如果您的特定成本小于您的曼哈顿距离，则该路径是不可能的。如果相等，则理想路径就是最短的可能路径。

一旦你超出了这个范围，事情就会变得有点棘手，因为你有多种解决问题的方法。您也许可以暴力破解答案，但我不知道是否有一种非天真的方法可以做到这一点。 (不过请注意，这些只是我脑海中的想法，所以...)

另请注意，在某些情况下，不会有解决方案，因为您使用的是曼哈顿距离!例如，如果你有一个 6x6 的网格，起点在一个角，终点在对角，你可以在 10 步而不是 11 步结束到终点(因为你必须自己加倍)。这有一个规则，我敢肯定，但我必须得出它。 (再次，超出我的想象。)(编辑:我意识到这一点 - 这本身并不是真正的规则，但您的特定成本不能落在最短路径距离和第二个路径距离之间最短路径距离。在曼哈顿网格中，第二短路径应该是 n+2，我相信。)

所以基本上...我认为可以这样写，但我不认为不检查很多可能性就可以轻松计算它。您可以通过规则优化特定情况，但一旦您这样做了，我认为您就陷入困境了。

尽管如此，请尝试一下。听起来很有趣!

第二次编辑:我刚刚意识到....您的路径成本将始终增加两倍(同样，由于曼哈顿距离)。这意味着只要知道最短距离就可以多优化一点；您的具体费用必须是 2 的倍数加上您的最短距离。用算法术语来说，您的特定成本 = 2n + 最短距离。

不过，在这之后，您将不得不对其进行暴力破解。

希望这对您有所帮助。

第三次编辑(希望是最后一次):我在这里可能有点迂腐(而且我可能正在弄清楚其他人在我之前已经弄清楚了什么)但是这是交易。如果您知道您的特定成本，并且您知道您的最短路径距离，您实际上可以取两者之间的差值并除以二来计算出您的路径中需要多少个环路。循环可以“堆叠”(我的意思是，您可以开始一个循环，并继续一段距离；这是“加倍返回”)，因此您可以通过仅检查路径来进一步优化具有特定数量的循环。然而，此时，您几乎已经找到了通往末端节点的可能路径(假设障碍物没有阻挡您找到的所有可能路径)。因此，只有在避免任何障碍时才需要暴力破解。我希望这是有道理的。