我正在寻找一种可视化数据的方式，算法中需要用到与A*路径查找99%相同的内容，但我无法完全理解它。我知道这将是一个相当简单的修改。（特定成本而不是最小成本）
基本上，我需要在X步内绘制从点A到点B的路径（2D网格，没有对角线）。
例如，如果起点和终点紧挨着，并且我需要路径为3步，则会有一个小循环。 （移动：向上，向右，向下）。
这个算法有已知的名称吗？还是使用它的人很少见？
我目前正在考虑修改此AS3库，因为它似乎非常快速，看起来也很干净简单：http://www.dauntless.be/astar/
任何建议/帮助都将不胜感激...
约翰
我喜欢这个问题——它很有趣。
我不确定如何编写代码，但这些只是我脑海中的想法。
基本上，你在处理曼哈顿距离，因为你没有使用对角线。因此，你需要知道最短路径并从中推导出来。如果你特定的成本小于你的曼哈顿距离，那么路径是不可能的。如果它相等，理想路径就是你最短的可能路径。
一旦你超出了这个范围，事情就会变得有点棘手，因为你有多种解决问题的方法。你可能能够采用暴力方法得到一个答案，但我不知道是否有一种非幼稚的方法来做到这一点。（注意，这些只是我脑海中的想法，所以...）
同时请注意，在某些情况下，由于使用曼哈顿距离，可能没有解决方案！例如，如果您有一个6x6的网格，起点在一个角落，终点在对角线的另一端，您可以在10步内到达终点，但不能在11步内到达（因为您必须回头）。我确定有一个规则，但我得推导一下。（再次强调，这只是我的初步想法。）（编辑：我意识到了这一点——实际上并不是一个规则，但您特定的成本不能介于最短路径距离和第二短路径距离之间。在曼哈顿网格中，第二短路径应该是n+2，我相信。）所以基本上...我认为可以编写类似的东西，但我认为您不能轻松地计算它，而不检查很多可能性。您可以通过规则优化特定情况，但是一旦您做到了这一点，我认为您就被卡住了。
不过还是试试吧。听起来很有趣！
< p > < em > < strong > 第二次编辑： 我刚刚意识到...由于曼哈顿距离，您的路径成本将始终增加两个单位。这意味着只要您知道最短距离，就可以进行更多优化；您的特定成本必须是2的倍数，再加上您的最短距离。在算法术语中，您的特定成本将为2n + 最短距离。 < p > < em > 不过，从这一点开始，你得硬着头皮去尝试。 < p > < em > 希望这有所帮助。 第三次编辑（也希望是最后一次）：我可能有点过于追求完美（而且我可能比其他人更早就发现了这个问题），但事实如下。如果你知道你的具体成本，以及你最短路径的距离，你实际上可以将两者之间的差异除以二，以确定你的路径需要多少个循环。循环可以“堆叠”（我的意思是，你可以开始一个循环，并继续走一段路程；这是“折返”），因此你甚至可以通过仅检查具有特定数量循环的路径来进一步优化。然而，到这个时候，你基本上已经找到了通向终节点的可能路径（假设障碍物不会阻挡你找到的所有可能路径）。因此，暴力搜索只是为了避免任何障碍。我希望这样讲清楚了。A*算法本身无法实现此功能。我建议使用Dijkstra算法，通过暴力搜索所有可能的路径（从最短路径开始），直到找到符合条件的路径为止。我真的想不出更简单的方法，因为可能有任意数量的路径满足这个条件（包括0条路径）。
首先，你需要明白这不是一个简单的问题，因此你在这里找不到完美的答案，但你会找到一些好的想法。
问题固有的第一件事就是由于无法沿着对角线移动，所以有些代价值是不可能达到的。我假设网格中存在不能通过的障碍块，如果不是这种情况，那么A*算法不是一个好的起点。
你的问题需要更多的澄清，但我会提供我发现的两种可能性的答案：
没有重复节点的路径:
修改A*算法使其持续运行，直到找到直接等于或高于所需成本的路径。将其作为路径使用，因为没有其他方法可以获得另一条路径。
存在重复节点的路径
找到基本A*算法的最短路径，然后如果它小于所需的成本，通过来回移动（前进和后退加2到成本）或将简单步骤转化为循环（每个循环加2到成本）增加成本。
