交错等轴投影路径规划器

Question

我有一个问题，尝试在交错等角地图上实现路径查找系统。我阅读了A*算法，并尝试看看它如何在等角地图上呈现，结果带我来到这里。

所以问题在于这里（对于廉价的显示，我很抱歉）。

因此，我目前位于绿色瓷砖（2,3）上，并尝试找到通往红色瓷砖（3,1）的路径。

基于A*算法，我尝试计算相邻瓷砖的F值（仅对这3个瓷砖执行此操作）。如图所示，（2,1）的F值低于（2,2），这是所有问题的根源，j+2和j-2的对角瓷砖几乎每次都会比“逻辑”选择具有较低的F值。因此，它将走向（2,1），而不是（2,2）。

我该如何解决这个问题？有人能给我一些提示应该做什么吗？

- Sandu Cezar

---

你如何计算G和H？哦，根据给定的值，看起来你的H不是可接受的。从(2,2)到(3,1)应该需要10步，但你说需要20步（即你高估了）。 - Bernhard Barker

我计算(x1,y1)和(x2,y2)之间的距离，方法如下：H = (Math.Abs(x2-x1) + Math.Abs(y2-y1)) * 10。至于G，我对于直线路径使用10，对于对角线路径使用14。 - Sandu Cezar

Answer 1

根据给定的值，看起来你的H值不是可允许的。由于从（2,3）到（2,2）需要10步，我假设从（2,2）到（3,1）也需要10步，但是你的H值是20（即你高估了）。

一个可能的H值是直接距离到目标点（可以是曼哈顿距离或欧几里得距离之类的）。

在我们的第一步中，我们探索所有邻居节点。我们的G值为：（G=绿色，R=红色）。

    14
  10  10
14   R  14
  10  10
G   14

让我们将H视为类似于曼哈顿距离，其中14是对角线跳跃，10是移动到直接相邻的位置。对于这个示例，这实际上是完美的启发式方法，因为它与实际距离完全相同。但一旦路径中有障碍物，情况将会不同。

然后，我们得到了H值：

    34
  24  30
14   R  34
  10  24
G   14

因此，我们的F值（= G + H）为：

    48
  34  40
28   R  48
  20  34
G   28

然后您找到最小值，即20，探索它的（未探索的）邻居并找到最小值，这将是此案例中的目标。

请注意，很容易犯一个错误，即一旦其中一个邻居是目标而不是我们当前正在探索的节点，就停止。如果我们这样做，可接受的启发式算法不能保证我们会找到通往目标的最优路径。

- Bernhard Barker

---

如何识别对角跳跃？ - Sandu Cezar

@SanduCezar 我不确定，你的坐标系是如何工作的？ 如果 (1,5) 是 (2,5)，那么看起来有 2 行在相同的 x 坐标上。 这似乎有点复杂，至少计算不会那么直接。 作为一个更容易的选项，只需将当前的 H 除以 2 即可（即乘以 5 而不是 10），尽管这样做会更糟糕——达到结果需要更长的时间。 - Bernhard Barker

哦，对不起。看来我犯了个错误，抱歉再次造成困惑。是的，你是正确的，应该是(2,5)，而不是(1,5)。 - Sandu Cezar