2

所以在做一个小项目，但考虑让地图更高效。我有一个数字网格说

100110
011011
010110

如果你曾经玩过地牢守卫，那么这个想法是 0 是一个平坦的挖出的方块，而 1 是一个静止的方块。我想利用网格布局并能够最大限度地减少使用的顶点数量。因此，不要将单个立方体用于以下区域：

1111
1111
1111

我只想使用 8。关于最佳方法的任何想法？甚至只知道我应该使用的算法类型的名称。可以在运行中快速完成的东西会比瓶颈渲染更可取。

4

1 回答 1

2

我同意这可能不会是性能问题，但是您可以通过使用（稍作修改的）不平衡四叉树在压缩地图中表示您的地图。

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

  • 如果您想挖掘其中一个框，则递归地沿着树向下走，使用默认的四叉树规则拆分 n*n 框（或您在其中找到的任何内容）（= 将 n*n 框拆分为四个 n/2* n/2 盒等）。在某些时候，您会到达仅包含单个框（您要挖出的框）的树的叶子，您可以将其从 1 更改为 0。

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

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

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

于 2012-07-06T16:46:47.220 回答