3D Pathfinding AI算法推薦和分析

我想解決以下問題：我有一個2D平鋪的遊戲，它包含飛機在空域飛行，試圖在最近的機場着陸（可以有'n'目標）。這個想法是讓飛機自己尋找最佳路線，避免出現問題。3D Pathfinding AI算法推薦和分析

所以我打算試試A *算法，但後來我發現了這個限制：如果需要的話，飛機可以改變它們的高度。所以我的想法是實現A *的相同理念，但是在3D中（將節點擴展到可能的移動，讓飛機也向上，向下，向北，向東等移動，從而形成抽象的3D處理相對高度，從而讓算法找到3D移動的最佳路徑）。

關於啓發式算法，我放棄了曼哈頓實例，因爲我希望算法更高效（因爲你知道一個好的啓發式算法提高了搜索效率，曼哈頓超過了成本，並且使用了對角線移動），所以我決定實施對角線距離（將曼哈頓和歐幾里得的各個方面相結合），推薦給8個鄰接點（對角線移動中的擴展節點）。但我有更多的鄰接關係，所以我試圖使對角距離公式適應16個鄰接點（不包括上 - 下對角線，如上 - 東北，下 - 西北部等），所以曼哈頓估計每個'對角線移動「（除了我提到的那些）具有相同的成本值（1對角線移動= 2正交移動，而不是3，因爲它在」我已經排除的上下對角線「中），並且用這個公式啓發式被廣義這樣的：

設節點A是開始時，和B中的目標，並且它們各自的位置是（XA，YA，ZA）和（XB，YB，ZB）

numberOfDiagonalSteps =分鐘{ | xa-xb |，| ya-yb |，| za-zb |}

numberOfStraightSteps = manhattanDistance - 2個* numberOfDiagonalSteps

並假設對角線步驟花費的sqrt（3）（你知道，畢達哥拉斯，具有ortogonal成本覈算1）：

啓發式是：H（N）= numberOfStraightSteps + sqrt（3）* numberOfDiagonalSteps

嗯......我的一個問題是，隨着飛機移動（「障礙節點」），算法必須更新，重新執行，所以，你推薦什麼我做得最好？我的意思是...更好地嘗試這樣做，或者更好地嘗試實施D * -Lite？

而我的另一個問題是時間複雜性。很顯然，這些算法的最壞情況是指數級的，但它可以從一個很好的啓發式算法中得到真正的改進。但我不知道如何精確分析我的問題中的算法。我可以給這個算法帶來多大的時間複雜性，或者我建議我怎麼處理這個算法？

感謝您的關注。

來源

2013-10-22 J. Alvarez

只是注意：如果你正在移動對角線（在所有維度上，例如向東北），您的距離是sqrt（3）。 – Geobits

*「曼哈頓花費超出成本」* - 您[不能使用高估成本的啓發式算法]（http://en.wikipedia.org/wiki/Admissible_heuristic）。可能你想要的是[歐幾里得距離]（http://en.wikipedia.org/wiki/Euclidean_distance）。此外，A \ *在3D中運行良好，這只是在代碼中正確構建圖形的問題。我不確定你爲什麼提到[D \ * - Lite]（http://cstheory.stackexchange.com/questions/11855/how-do-the-state-of-the-art-pathfinding-algorithms-for-更改圖形ddl/11866＃11866），它聽起來不適用於任何問題。 –

@丹尼你可以很好地使用A *和高估啓發式。這在實踐中很常見。你失去的是保證找到的解決方案的最優性。 – ziggystar

我會用簡單的地圖填充看到：

http://en.wikipedia.org/wiki/Dijkstra「s_algorithm
https://www.allegro.cc/forums/thread/599046

但地圖將有更多層（飛行高度）。可能只有少數（爲了限制時間/內存浪費），例如8層應該足夠用於多達128架飛機。

當然它取決於2D地圖面積大小和填充地圖後，只需從它的最短路徑。在填圖時，考慮任何飛機是障礙物（爲了安全起見，有一些邊界）。在這個算法中，您可以非常簡單地添加燃油消耗標準或任何其他。

而且飛機場選擇可能是通過一個非常簡單的（首先要首先得到最接近的一個）。您必須在決定的時間內爲每架飛機制定地圖（或分別爲每架飛機重新制作同一架地圖）。不需要將整個地圖...只是

如果您必須遵守空中交通管制規則，那麼你需要申請飛行計劃+特設調度，而不是目的地和平面之間的區域。這不是一件容易的事（用了差不多半年的時間來編碼），而且空中交通管制也有點複雜，特別是空中和地面上的等待問題。都必須通過動態多變的（天氣，等待，技術/政治或安全問題，...），但我強烈懷疑是這種情況那麼簡單的地圖上面填充應該做的:)

來源

2013-11-13 10:25:38 Spektre

3D Pathfinding AI算法推薦和分析

回答

相關問題