地下城守護者2風格地圖，頂點壓縮

Question

因此，在一個小項目上工作，但考慮使地圖高效。我有一個數字柵格說

100110 
011011 
010110 

如果你玩過地下城守護者，這個想法是一個0是一個平面挖出廣場，1是一個還站在廣場。 我想利用網格佈局，並且能夠最小化使用的頂點數量。因此，而不是使用個人多維數據集等的區域：

1111 
1111 
1111 

我只想用到此最好的辦法8. 任何想法？或者甚至只知道我應該使用的算法類型的名稱。有些東西可以在飛行中快速完成，因此不會瓶頸渲染。

Answer 1

我同意這可能不會是一個性能問題，但您可以使用（稍微修改）的不平衡四叉樹在壓縮映射中表示您的地圖。

• 從您的只包含1的地圖開始。您可以將它作爲一個大小爲n * n的框存儲在樹的根節點中。

• 如果你想挖出一個你遞歸地走下樹的盒子，使用默認四叉樹規則分割n * n盒子（或者你在那裏找到的任何東西）（=將一個n * n盒子分割成四個n/2 * n/2盒等）。在某些時候，您會到達僅包含單個盒子（您想要挖出的那個盒子）的樹葉，並且您可以將其從1更改爲0.

• 此外，在葉子已更換之後並且你的遞歸調用返回（=你朝着根節點往回走），你可以檢查相鄰的框是否可以合併。 （如果你有兩個相鄰的盒子都挖出來了，你可以合併它們）。

另一種有時在像這樣索引低維數據時使用的技術是空間填充曲線。具有良好的平均局部性和可逆性的是希爾伯特曲線。基本上，您可以沿着空間填充曲線枚舉您的盒子（挖出一些和填充的盒子），然後使用簡單的遊程壓縮。

樹構思允許您減少渲染幾何圖形的數量（您可以重新縮放紋理等，以便通過單個較大的框來模擬n * n個框）。空間填充曲線可能只會爲您節省一些內存。