我正在研究遊戲世界不規則形狀的項目（想想湖的形狀）。這個形狀有一個座標放置在其上的網格。遊戲世界只在形狀的內部。 （再一次，想想湖）代表不規則形狀的遊戲世界
我該如何有效地代表遊戲世界？我知道許多世界基本上是正方形的，並且在2維或3維陣列中運行良好。我覺得如果我使用的是一個正方形的數組，那麼我基本上正在浪費空間，並增加了我需要遍歷數組的時間量。但是，我不確定鋸齒陣列如何在這裏工作。遊戲世界
X
XX
XX X XX
XXX XXX
XXXXXXX
XXXXXXXX
XXXXX XX
XX X
X
編輯的
形狀的實施例： 遊戲的世界很可能需要每一個有效的位置，通過加強。所以我想要一個方法可以輕鬆實現。
有稀疏表示相關聯的計算開銷和複雜性，因此，除非邊界區域比實際的世界大很多，它可能是最有效的方式簡單地接受了「浪費」的空間。實質上，您可以利用額外的內存使用量來更快地訪問世界內容。更重要的是，「浪費空間」的實現更容易理解和維護，在需要更復雜的實現之前，這總是比較可取的。如果您沒有足夠的證據證明它是必需的，那麼保持簡單會更好。
在我的例子中，66％的地圖會浪費空間。儘管如此，我還沒有足夠的時間知道我是否需要稀疏表示。 – 2010-06-03 18:49:00
在這種情況下，請參閱kevingessner的答案。您可以最初編寫基於數組的基於地圖的原語。如果需要，稍後可以使用不同的實現來節省內存，儘管您可能不需要並且可能通過簡單的數組獲得更好的性能。 – 2010-06-03 18:54:58
我對我創建的對象進行了一些簡單的測試。看起來循環播放的效果很好，尤其是因爲它不需要實時功能 – 2010-06-03 20:04:31
使用像列表或地圖這樣的數據結構，只插入有效的遊戲世界座標。這樣，您保存的唯一東西就是有效的地點，而且您不會浪費內存來保存非遊戲世界的位置，因爲您可以從數據結構中缺少存在推斷出這些位置。
您可以將世界呈現爲土地（或水）補丁的（無向）圖。然後每個補丁都有一個規則的形式，世界就是這些補丁的組合。每個補丁都是圖中的一個節點，並且它的所有鄰居都有圖邊。
這可能也是任何一般世界最自然的表現（但它可能不是最有效的）。從效率的角度來看，它可能會爲一個非常不規則的地圖打一個數組或列表，但不適合一個很好地適合一個矩形（或其他規則形狀）且偏離很少的地圖。
高度不規則的地圖的一個例子：
x
x x
x x x
x x
x xxx
x
x
x
x
有幾乎沒有辦法這可以有效地裝配（無論是在空間比和訪問時間）爲規則的形狀。下面，在另一方面，非常適合到通過基本幾何變換規則形狀（它與小位缺少一個平行四邊形）：
xxxxxx x
xxxxxxxxx
xxxxxxxxx
xx xxxx
最簡單的事情是隻使用數組，只是標記非遊戲空間的位置有一些特殊的標記。鋸齒陣列也可能工作，但我沒有使用那麼多。
您可以使用quadtree來最大限度地減少表示中浪費的空間量。四叉樹適合用不同的粒度分割二維空間 - 在你的情況下，最好的粒度是一個遊戲廣場。如果你有沒有任何遊戲廣場整體面積20×20的四叉樹表示將允許您使用只有一個節點來表示整個區域，而不是400作爲數組表示。
四叉樹的問題在於遊戲世界可能變成三維。我會知道一個解決方案，可以很好地適用於2或3維 – 2010-06-03 18:45:01
你的意思是在最後一句400，對不對？ – 2010-06-03 18:45:14
哎呀，謝謝馬克。 – 2010-06-03 18:45:58
使用你想出的任何結構---你可以隨時改變它。如果您對使用數組感到滿意，請使用它。不要擔心你要使用的數據結構，並開始編碼。在您編寫代碼時，從這個底層數組中構建抽象，就像將其包裝在一個語義模型中一樣;那麼，如果您意識到（通過分析）它是浪費空間或緩慢進行所需操作，則可以將其交換出來而不會造成問題。不要試圖優化，直到你知道你需要什麼。
另一種方法是存儲邊緣列表 - 沿每個直邊的線條矢量。易於檢查包含這種方式和一個四叉樹，甚至每個頂點的簡單位置散列可以加快信息查找。我們用每個邊緣的高度分量來模擬棒球場的牆壁，並且它運行得非常漂亮。
另一個選項可以讓你在O（1）時間內仍然可以訪問遊戲世界的位置，而不會浪費太多空間，那就是一個散列表，其中的鍵就是座標。
這裏沒有人提到了一個大問題：將其存儲在磁盤上並將其存儲在內存中。
假設你正在談論遊戲世界如你所說，這意味着它將會非常大。你不會一次把所有東西都存儲在內存中，而是將存儲在內存中的附近，並在玩家走動時更新它。
這個附近區域應儘可能簡單，方便和快捷地進入。它肯定應該是一個數組（或者隨着玩家移動而交換出來的一組數組）。它將經常被你的遊戲引擎的許多子系統引用：圖形和物理將處理加載模型，繪製它們，讓玩家保持在地形頂部，碰撞等等。聲音將需要知道玩家目前站在的地面類型，以播放適當的腳步聲;等等。而不是在所有子系統之間廣播和複製這些數據，如果你只是將它保存在全局數組中，他們可以以100％的速度和效率隨意訪問它。這可以真正簡化事情（但要注意全局變量的後果！）。
但是，在磁盤上，您一定要壓縮它。一些給出的答案提供了很好的建議;您可以序列化一個數據結構（如散列表），或者只列出填充的位置。你當然可以存儲一個八叉樹。無論如何，你不想在磁盤上存儲空白位置;根據你的統計，這意味着66％的空間被浪費了。確實有時間忘記優化並使其成爲Just Work，但您不希望向最終用戶分發66％的空文件。另外請記住，磁盤不是完美的隨機訪問機器（SSD除外）;機械硬盤驅動器至少應該還有幾年的時間，並且它們的工作順序最好。看看你是否可以組織你的數據結構，以便讀取操作是連續的，因爲當播放器移動時，你流動更多的附近地形，你可能會發現它是一個明顯的差異。儘管我不聽，但我並沒有真正測試過這種事情，它的意義恰到好處？
我認爲存儲世界的最佳方法取決於你在遊戲世界需要做什麼樣的操作。 – 2010-06-03 18:39:13
當你逐步瞭解每個位置時，你會做什麼？你需要看看附近的細胞嗎？ – 2010-06-03 18:44:53