網格的最優高密度二進制空間分區

我正在寫一個遊戲，其中一個角色在隨機生成的地圖上實時移動（因爲它被顯示）。這導致我產生了一個有趣的數據結構問題。地圖是以角色的形式生成的（可能是20-60個瓦片），因此，在有數據的地方，數據非常密集，並且全部位於網格中。然而，如果沒有數據，可能會有巨大的未生成空間。例如，角色可以走在一個巨大的圓圈內，在廣闊的空白空間周圍創造一圈瓷磚。網格的最優高密度二進制空間分區

簡單的矩陣會產生大量不需要的開銷，並浪費大量空間。但是，典型的BSP似乎會導致性能下降，因爲數據密集且類似於網格。

你有什麼建議？矩陣 - 四叉樹 - 兩者的混合？

來源

2010-06-29 dlras2

我一直在解決這個在過去的一個月，都拿出了什麼，我相信這是一個相當不錯的解決方案。它不如純矩陣快，但具有無限可擴展性的優點（在int的範圍內）。

基本上，它是一種向上構建的二元空間分區（而不是像四叉樹那樣向下）。如果寫入當前分配的矩陣空間之外的某個點，則會生成更大的節點並展開。如果一個節點的大部分子節點都被分配了矩陣，那麼它會將它們聚合到自己並刪除它們的引用。這意味着你使用的邊界越清晰，你獲得的性能越好，因爲這個結構就像矩陣一樣。

我已經發布我的代碼here，並且會嘗試在將來寫一些演示，並轉移到更好的託管站點。

不要猶豫，讓我知道你的想法，或者如果你有任何問題。

來源

2010-07-31 19:54:04 dlras2

由於您的示例代碼沒有評論，我沒有真正看它很多...從你是什麼介紹一個非常簡單的解決方案。將你的景觀劃分爲矩陣，並使用相對座標（對演員）來檢索數據。這樣你最多隻能生成/檢索4個矩陣的數據，而其他的則未初始化。 – 2010-08-03 07:41:06

我正在考慮在我的遊戲中實施類似的工作。我將創建一個可以像二維數組ex前一樣訪問的自定義類。 map[x][y]但基礎數據類型將更接近散列表。像data[x.Value.ToString() + "," + y.Value.ToString()]

我的遊戲是相當基本的，因爲我的瓷磚將只能走路，致命或不可行。

我感興趣的是，雖然一個更優雅的解決方案：d

來源

2010-06-29 17:18:32

你有正確的想法。您可以定義一個自定義類，該類具有爲建模40 x 40個標準圖塊的標準2D數組所需的屬性和方法。隨着角色移近（<5）下一個標準2D陣列，您將加載下一個標準2D陣列。 – 2010-06-29 17:28:29

最初，我做了那樣的事情。我有一個'詞典'一切工作正常，除了從字典中檢索元素，這花了太長時間。也許更好的結構可以以相同的方式使用，但我擔心混合四叉樹矩陣是爲了... – dlras2 2010-06-29 17:29:34

網格的最優高密度二進制空間分區

回答

相關問題