distance - A* 曼哈顿距离

Question

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

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

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

Answer 1

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

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

Answer 2

With the manhattan distance the first one is a shortest path. It simply counts the number of horizontal and vertical steps taken. If you want something that looks more like a shortest path in the euclidian distance you can try changing your algorithm so that when it has the choice to move horizontally or vertically at one point it chooses the horizontal one if the horizontal distance is bigger than the vertical one and vice versa.

Answer 3

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

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

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

最后一行：Blocked Point------------->Goal

连接所有线路，您将获得更短的最短路径。您可以再次执行，但反向执行以增加另一个准确性，因此视线将从目标开始直到开始。