在真實3D環境（例如建築物）中尋找路徑

是否存在也適用於真實3D環境的尋路算法，例如真正的建築物與多個樓梯等C++庫或開放實施將是精彩;-) 我看到的一個解決方案是Djikstra，但我想知道是否有更優化的東西。由於距離啓發式算法效果不好，所以普通A *不會比Djikstra更好（位於目的地一層以上）。我目前正在思考的另一個解決方案是3D環境在二維圖上的映射。所以如果有這樣一些可用的C++實現/庫，這也會有所幫助。在真實3D環境（例如建築物）中尋找路徑

來源

2012-04-16 Martin

除非你有很多樓梯，否則A *可以很好地工作，不同層次上的點的啓發式算法是到最近的樓梯的距離加上垂直距離的總和。 – biziclop 2012-04-16 16:17:23

@biziclop：這是一個非常好的主意，比任何圖形轉換都簡單得多。我會試試 – Martin 2012-04-16 16:19:05

我相信尋路很容易分而治之。所以，你可以嘗試在2D級別上使用A *，並使用Dijkstra的算法將它們綁定在一起。 – comingstorm 2012-04-16 19:48:51

如果路徑必須考慮到通過障礙物的能力（即運動是具有已知空間體積的某個實體的運動），那麼我建議查看關於機器人運動規劃的文獻。配置空間的概念允許您處理姿勢的變化以應對障礙。見吉恩·克勞德·拉姆

對於一些簡單場景的經典教材，你也許可以湊合着用第一人稱的電腦遊戲所使用的路徑規劃算法，類似於Dijkstra算法，A * (example)

來源

2012-04-16 18:18:02 killogre

對於一個近似算法您可以輕鬆將3d映射到1d曲線，並用灰色代碼遍歷八叉樹。這樣你可以重新排序每條路徑。我不知道是否有最佳解決方案的保證，但它必須比任何啓發式方法更好。

來源

2012-04-16 19:04:08 Bytemain

這聽起來很有趣，但我不完全明白你的想法。對於每條路徑來說，起源顯然是不同的。那麼你是否打算爲每次運行首先創建一個八叉樹，或者如何爲樹建立一個排序標準？（我不得不承認我對octrees不是很熟悉......） – Martin 2012-04-18 07:41:55

此外，由於我沒有針對每個方向的節點（想象一個只有很少節點的走廊），樹會很大程度上稀疏，這對於八叉樹是明智的 – Martin 2012-04-18 07:55:48

在真實3D環境（例如建築物）中尋找路徑

回答

相關問題