A *曼哈顿距离

我搜索了A * I的算法/伪代码，然后对它进行编码。我用曼哈顿距离h（n）。（F（N）= G（N）+ H（N））这是结果，A *曼哈顿距离

时有没有墙挡住了路这总是发生，但是当我放了很多看起来它走的是最短的路。这是最短的路吗？我的意思是为什么它不是这样的下面？

这一个也是A *曼哈顿，他们有相同的大小（19x19）。这是从http://qiao.github.com/PathFinding.js/visual/

2012-06-15 Zik

umm它的距离相同，33个立方体...除非我算错了。 –

因为你不能走对角线，你不会比第一个例子更短。你可以得到很多其他的方式（比如第二种），它们的距离相同，但看起来更短，但不是。你总是必须通过16个方块向右和16个方向（对于你给出的例子）。 – Nobody

啊所以还有其他最短路径。 – Zik

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

提示：从源到目标单元格的每条路径仅使用Von Neumann neighborhood（即，不对角线走向），并且不会向“错误”方向迈出一步（即，永远不会走到您的示例中）具有相同的曼哈顿距离。所以，如果你在纽约，无论你走到曼哈顿某个特定地点的哪个十字路口都没关系:)

2012-06-15 07:57:29 gexicide

那么第一个仍然是最短路径之一？ – Zik

当然可以。两条路径都是可能的正确答案。 – gexicide

曼哈顿距离第一个是最短路径。它仅计算所采取的水平和垂直步数。如果你想在欧几里德距离看起来更像是最短路径的东西，你可以尝试改变你的算法，这样当它有一个水平或垂直移动的选择时，如果水平距离大于垂直距离一个，反之亦然。

2012-06-15 08:05:03

啊，好吧。谢谢！ :) – Zik

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

第一线：开始---------> S + N（前阻塞点）

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

最后一行：阻塞点------------->目标

连接所有线路和你有一个更短的最短路径。您可以再次执行，但反过来又添加了另一个准确度，所以视线将从目标开始直到开始。

2015-03-17 16:03:26

回答