輸入/退出NavGraph - 尋路

Question

我在3D環境中手動創建了NavGraph。我瞭解（並且已經實現）之前的一個A *例程，以便在圖表上找到我通過圖表的方式。

我感興趣的是最好的方法來和'關閉'圖。

例如： 所以，例行公事就像這樣： 從源頭向目的地射出光線，如果沒有任何事情發生，繼續前進，然後行走它。如果在某種程度上，我們需要使用圖形，那麼爲了進入圖形，我們需要找到圖形上最接近的可見節點。 （爲了做到這一點，我之前根據距離源的距離對圖進行了排序，然後從壁櫥向最遠發射射線直到找到沒有障礙的射線。）

然後運行標準A * ..

然後'退出'圖形，通過與我們在圖形上獲得的相同方法（用於計算上述A *的端點），以便從端點獲取併發射光線到最近的導航節點。

這樣的時候，這是所有說的和做的，除非我navgraph很密，我已經花了更多的時間去開/關圖表比我計算路徑...

必須有做一個更好/更快的方式？ （是否有某種空間細分技巧？）

Answer 1

您可以構建所有節點的Quadtree，以快速找到距給定位置最近的節點。

Answer 2

有一個世界的空間細分是非常普遍的。類似於四叉樹或八叉樹的東西在3D世界中很常見，儘管您也可以覆蓋網格或追蹤任意區域等。基本上，這是一個簡單的數據結構問題，它允許您自己對N個導航節點進行某種訪問，而不需要O （N）搜索找到你的位置，你的選擇往往歸結爲某種樹或某種散列表。