給出一個開始和目標，如何在導航網格中找到最短路徑？

我一派只得到錯誤的方法來估算G-值「關於導航網格A *算法」，類似這樣的給出一個開始和目標，如何在導航網格中找到最短路徑？

或本

通過總結藍色的長線段，我們得到的g值，但它被高估（g值應該被低估）。該算法將返回一條優化路徑，但不保證是最短路徑。

我能想到的唯一方法是繪製基於導航網格的可見性圖形，但這會花費太多的內存。

還有沒有其他的方法來計算在導航網最近的路？

2016-03-19 iouvxz

我認爲你應該更多地研究A *算法，特別是它做出了什麼假設以及它提供了什麼保證。有了這個，你也可以提出更有意義的問題。例如，你的問題缺乏你對A *輸出認爲錯誤的確切定義。 –

@UlrichEckhardt A *是對的，但我不能直接將A *算法應用於網格導航圖.A *需要具有節點和邊的典型圖，以便它可以應用類似Dijkstra的搜索來找出最短路徑。搜索完成，沒有路徑可以比它現在返回的路徑短。但導航網格不是一個只有節點和邊緣的圖形，它是由可通過的區域組成的，所以我搜索瞭如何在導航網格上應用A *。 – iouvxz

這些文章要麼考慮通過所有多邊形的質心或之字形路徑通過所有邊緣的中間點作爲g值的曲折路徑。但這是錯誤的，這種g值高估了距離起點指向當前的多邊形（或邊緣）。所以當搜索完成時，所有未經檢查的路徑都被高估並放棄。 – iouvxz

爲了使距離你的意思更近，你應該停止使用固定點作爲A-星節點，即停止使用三角形的中心或三角形的中心。

嘗試將點移動爲A-星傳播。例如，使用A-星上triangles'edge它們是節點：

或者與由以前的A-星節點與目的地所形成的下段A星節點的三角形的邊緣的交點
或從下一個A星點的三角形的邊緣上述路口的最近點

或者，嘗試按照目前完成的計算你的A級明星後更改路徑節點，使用類似標準。

請注意，這將平滑最終路徑（如您的圖紙上的紅線）。但這隻會有助於減少高估，但並不能保證找到最短的路徑。

更好的是，在使用拉動a.k.a漏斗算法的字符串計算使用三角形的中心點的A星後，嘗試更改路徑節點。這會給你通過A-star輸出路徑所穿過的三角形的最短路徑。

來源

2016-04-28 19:12:23 Brice

我終於選擇在C++中實現可見性圖形生成器，這是唯一合理的解決方案。 – iouvxz

給出一個開始和目標，如何在導航網格中找到最短路徑？

回答

相關問題