不規則網格的數據結構

Question

我想知道什麼是包含不同大小的矩形/正方形作爲遊戲地圖部門的網格的最佳數據結構。我需要通過簡單的xyz座標來訪問該網格中的對象。

搜索KdTrees，但他們似乎找到最近的對象，我也發現部分樹木/間隔樹木，有關於他們 乾杯一點信息。

Answer 1

您可以使用八叉樹。也就是說，您可以從包含整個區域（（0,0,0），（x，y，z））（它是樹的根）的矩形平行六面體開始。 （（0,0,0），（x/2，y/2，z/2）），（（0,0，z/2），（x/2，y/2，z））等）。這8個直角平行六面體是根的孩子。繼續爲它們中的每一個遞歸地構建樹。當一個矩形平行六面體完全位於一個區域內時，遞歸應該停止（因此它變成樹的一片葉子）。

要回答查詢，請從八叉樹的根開始，然後轉到合適的孩子，直到到達樹葉。

也可以修改k-d樹來解決這個問題。這個想法與上面描述的相似：將空間分成兩個半空間，爲它們中的每一個遞歸地構建一棵樹。遞歸的基本情況也是一樣的：一旦當前子空間僅在一個區域內，遞歸就應該停止。