A *尋路 - 最接近不可行走的目的地

Question

我已經有了一個A *實現。問題是，如果您選擇一個不可行的目標，則不會返回路徑。我希望能夠得到我能得到的「最接近的」。

最好的選擇將是完全動態的（不僅僅是檢查目的地周圍的8個瓷磚來嘗試找到一個）。這樣，即使他們點擊了一個不可行的瓷磚包圍的不可行走的瓷磚，它仍然會盡可能地接近它。

Answer 1

你可以保留一個指針，它保存一個具有最小h值的瓦片，那麼如果沒有返回路徑，只需生成一個路徑到你所持有的瓦片。

Answer 2

儘管這裏提供的簡單答案可能足夠了，但我認爲這取決於您的遊戲類型以及您想要實現的目標。

例如，藉此球場（對不起，我再利用我曾經向您展示戰爭迷霧一樣的軟件:)）：

正如你所看到的，憤怒的雞阻止了左側和右側之間的路徑。憤怒的小雞可以是任何東西......如果它是一個靜態的障礙，那麼以最低的h node就足夠了，但如果它是一個動態物體（如鎖着的門，拉橋等等），下面的例子可能會有幫助你會發現你想如何解決你的問題。

如果我們爲我們的英雄目的地在另一側

我們需要考慮我們想要的路徑是，因爲我們顯然不能達到它。使用標準的試探像manhattan距離或euclidian距離，你會得到這樣的結果：

這可能是夠用了，但如果有任何我們的小英雄能與雞交互傳遞，這不是「T道理可言，你要的是這個

你怎麼能這樣做呢？那麼，一個簡單的方法就是找到hierarchical graphs。這聽起來很複雜，但事實並非如此。首先，你希望能夠建立一個新的，高層次的節點和邊緣，將包含多個網格節點（或其他表示，不會改變任何東西）的

正如你所看到的，我們現在有權利blue node和左red node。箭頭表示兩個節點之間的邊緣。如何建立你問這個圖？很簡單，只需從一個開放節點開始，展開所有鄰居並將它們添加到高級節點，完成後，打開可能會導致圖的另一部分並執行相同操作的動態節點。

現在，當您向我們的英雄的紅X的路徑，你首先要做的尋路的高層次...有沒有辦法從blue node到red node？是!通過雞。

您現在可以輕鬆知道如何通過轉到edge來導航藍色方面，這將允許您跨越，這是雞。

如果這只是一個普通的牆，你可以決定非常快，通過訪問一個節點，那是沒有辦法達到的另一邊，然後處理它，你想要的方式，有可能仍然執行A *並返回最低點h節點。