A* 曼哈顿距离

Question

我搜索了 A* 的算法/伪代码，我按照它进行编码。我使用曼哈顿距离作为 h(n)。 ( f(n) = g(n) + h(n) ) 这就是结果

_{（来源：uploadir.com）}

当没有墙壁挡路时，这种情况总是会发生，但是当我放置很多墙壁时，它似乎走的是最短路径。这是最短路径吗？我的意思是为什么它不像下面这个？
_{（来源：uploadir.com）}

这也是 A* 曼哈顿，它们的尺寸相同（19x19）。这是来自http://qiao.github.com/PathFinding.js/visual/

Answer 1

两条路径的曼哈顿距离相同。因此，选择哪条路径取决于实现。要了解为什么选择这个特定部分，我们必须查看这个特定 A* 实现的代码。

提示：从源到目标单元的每条路径仅使用冯·诺依曼邻域（即，不沿对角线行走）并且不会向“错误”方向迈出一步（即，永远不会在你的方向上走或左走）示例）具有相同的曼哈顿距离。所以，如果你在纽约，无论你走哪个十字路口到达曼哈顿的某个地方都没关系:)

Answer 2

对于曼哈顿距离，第一条是最短路径。它只是计算所采取的水平和垂直步数。如果您想要看起来更像欧几里德距离中的最短路径的东西，您可以尝试更改您的算法，以便当它可以选择在某一点水平或垂直移动时，如果水平距离大于垂直距离，它会选择水平距离一，反之亦然。

Answer 3

您需要从起点到每个点（曼哈顿/A*结果）投射一条视线（毕达哥拉斯/欧几里德）直到完成。如果向某个点投射的线被障碍物阻挡/隐藏，则可以使用之前投射的点并从该阻挡点开始投射另一条线，然后向前直至完成。 阻挡点是指某个点被线段/线的初始点的视线隐藏。 所以就像：

第一行：开始--------->S+N(被阻挡点之前)

第二条/中线：阻挡点---------->S+N（在另一个阻挡点之前）再次重复（新线/线段），直到建立到目标的视线.

最后一行：封锁点------------->目标

连接所有线路，您就得到了一条更短的最短路径。 您可以再次执行，但相反可以增加另一个精度，因此视线将从目标开始，直到开始。