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

回答