地下城守护者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个框）。空间填充曲线可能只会为您节省一些内存。