algorithm - 《地下城守护者 2》风格 map ，顶点压缩

Question

所以正在做一个小项目，但考虑提高 map 的效率。我有一个数字网格

100110
011011
010110

如果您曾经玩过地下城守护者，那么这个想法是 0 是一个平坦的挖出的方 block ，而 1 是一个静止的方 block 。 我想利用网格布局并能够最小化所使用的顶点数量。因此，不要在一个区域中使用单独的立方体，例如:

1111
1111
1111

我只想使用 8。 关于最好的方法有什么想法吗？或者甚至只知道我应该使用的算法类型的名称。可以快速快速完成的事情会更好，这样就不会成为瓶颈渲染。

Answer 1

我同意这可能不会成为性能问题，但您可以使用(稍作修改的)不平衡四叉树在压缩 map 中表示您的 map 。

• 从仅包含 1 的 map 开始。您可以将其存储为大小为 n*n 的盒子在树的根节点中。

• 如果你想挖出其中一个盒子，你可以递归地沿着树走下去，使用默认的四叉树规则分割 n*n 盒子(或者你在那里找到的任何东西)(=分割一个 n*n 盒子)分成四个 n/2*n/2 盒子，等等)。在某个时刻，您将到达只包含单个盒子(您想要挖出的盒子)的树叶，您可以将其从 1 更改为 0。

• 此外，在叶子发生变化并且递归调用返回(=您沿着树向根节点走回)之后，您可以检查相邻的框是否可以合并。 (如果您有两个相邻的盒子都被挖出来，您可以将它们合并)。

在索引此类低维数据时有时会使用的另一种技术是空间填充曲线。希尔伯特曲线是一种具有良好平均局部性且可逆的曲线。基本上，您可以沿着空间填充曲线枚举您的盒子(挖出的盒子和填充的盒子)，然后使用简单的游程压缩。

树的想法允许您减少渲染几何体的数量(您可以重新缩放纹理等，以通过单个较大的框来模拟 n*n 框)。空间填充曲线可能只会节省您一些内存。