algorithm - Dungeon Keeper 2 样式贴图，顶点压缩

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。

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

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

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