基於多邊形的路徑查找

Question

我已經在Java中實現了基於網格的A * pathfindinder。我想作一個導航網/基於多邊形探路者，但我的問題是這樣的：

如果我找到了橙色的路線，然後我可以使用類似a funnel algorithm進行糾正，以獲得所需路線（藍色）。但是，如果程序計算每條路線的成本，紅色和橙色，那麼它會說紅色是更便宜的路線。如何編程我的A *算法和/或創建我的網格，以防止這種情況發生。

Answer 1

第15章在Computational Geometry: Algorithms and Applications中描述並準確解決了這個問題：自由空間可以用梯形圖描述，但使用映射找到的路徑不一定是最短的。推薦的表示法（也在LaValle的Planning Algorithms (Section 6.2.4)中進行了討論）是一種所謂的可見性圖形，它具有連接障礙物頂點的邊緣。

僞代碼和數字可從書主頁獲得，Google preview也包含本章的部分內容。

Answer 2

你應該檢查這個鏈接：http://alienryderflex.com/shortest_path/ 它解釋瞭如何計算多邊形內的最短路徑，一個非常清晰的解釋和代碼實現。

Answer 3

對不起，我不能直接幫你解決問題，但是我們將一個基於多邊形的路徑查找器移植到haxe中，並且它可以編譯爲java（只能在swing中嘗試，但可能很快會嘗試slick2d），並且可以集成到Java項目進行了一些研究。它被稱爲hxDaedalus，並在github上，可能是一個有趣的參考點。