我正在寫一個遊戲，其中大量的對象將在平鋪的2D地圖的區域上產生「區域效果」。重疊空間區域的有效數據結構
所需的功能：
什麼數據結構將最適合呢？
提供你真的有很多的區域效應同時發生，那他們將有任意的形狀，我會做這種方式：創建一個新的效果時，
一些蠻力解決方案，不靠花哨的計算機科學：
1000×1000是不是太大 - 只是一個MEG。電腦有Gigs。你可以有一個2D數組。字節中的每一位都可以是'區域類型'。更大的'受影響的地區'可能是另一回事。如果您擁有合理數量的不同類型的區域，則仍然可以使用多字節位掩碼。如果這變得荒謬可以使數組元素指向重疊區域類型對象列表。但那你就失去了效率。
你也可以實現一個稀疏數組 - 使用散列表中的鍵（例如，key = 1000 * x + y） - 但是這會慢很多倍。
如果當然如果你不介意編碼花哨的計算機科學方式，他們通常會更好！
會有大量的效果類型，所以它可能必須是某種列表。但是接下來會有一個潛在的問題，即一個「多達10個方格以外的」效果可能需要生成或更新441個不同的列表....？ – mikera 2010-06-28 20:48:31
通常取決於地圖的密度。
如果您知道每個瓷磚（或瓷磚的主要部分）至少包含一個效果，則應使用常規柵格 - 簡單的二維瓷磚陣列。
如果您的地圖無法填充且存在大量空白切片，則可以使用類似四叉樹或R樹或BSP樹的spatial indexes。
好想法 - 我想地圖大概是10-20％覆蓋面積效應，所以空間索引類型的方法可能更好 – mikera 2010-06-28 20:50:32
空間索引允許您不浪費內存以用於未使用的圖塊。但請注意，大多數此類索引都設計用於存儲靜態數據。據我瞭解，所有「影響區域」都可以沿着地圖移動，因此您需要始終重建/更新空間索引。這可能會造成很大的開銷。 – 2010-06-29 07:39:41
如果您已知每個區域效果的最大範圍，則可以使用您選擇的數據結構並存儲實際來源，這隻針對正常2D碰撞測試進行了優化。
然後，當檢查瓷磚上的效果時，只需在最大範圍內檢查所有效果源（碰撞檢測樣式，針對您的數據結構進行優化），然後應用定義的測試功能（例如，一個圓圈，檢查距離是否小於一個常數;如果它是一個正方形，檢查x和y距離是否都在一個常數內）。
如果你有一個很小的（< 10）大小的效果「場」形狀，你甚至可以在其預先計算的最大範圍內爲每個效果場類型做一次獨特的碰撞檢測。
感謝Kylotan--這看起來像是最「全面」的方法來保證快速訪問。我想我可能最終會做這樣的事情，但是對於每個磁貼存儲使用四叉樹類型的方法，並且可能爲每個磁貼列表使用某種類型的高速緩存以避免大量的重複列表 – mikera 2010-06-29 10:31:15
我不明白有什麼好處你可以從四叉樹中得到：平鋪地圖通常（根據定義）是從位置到平鋪的2D哈希。當你還沒有這樣一個快速查找系統時（例如，對於連續的世界，而不是平鋪的世界），你通常只需要一個四叉樹。 – Kylotan 2010-06-29 16:38:07