我正在研究使用体素来表示具有可破坏地形的大型（256x256x256 体素）战场对于服务器托管的多人游戏的可行性。任何游戏一次只存在一个战场。然而，为了能够广播房间和改变他们的地形，我试图找到一种算法，可以将体素分组到尽可能少的矩形块中。
举个简单的例子，如果关卡的下半部分完全由一种类型的体素填充，而上半部分则由另一种类型的体素填充，则关卡应分为两个块，一个代表关卡的下半部分，而其他代表顶部。理想情况下，该算法应该能够实时运行，因此地形中的任何变形都可以按帧计算并广播给客户端。这应该使客户端能够有效地渲染地形，而不必担心在客户端中重复地形破坏逻辑。
以下是我尝试过的方法以及我发现的问题。报告的块数是通过将超过 4,194,304 个“EARTH”体素随机放入尽可能靠近底部的随机选择的 (x,z) 坐标来填充 256^3 空间。只计算“EARTH”块。
- 八叉树：非常快，但如果我在一个空间的中间分裂，它会产生大量的块（800,000+）。
- kD 树分裂以最小化分裂后的加权熵：比八叉树稍慢，但块少得多（~350,000）。
- kD 树分裂以最大化信息增益比：比以前的 kD 树方法快两倍，生成的块少得多（~167,000），但仍然很慢。
- kD 树分裂以最小化 Gower 相似性：非常慢，但生成的块比任何其他 kD 树方法都少（~155,000）。
- 当考虑每个无人认领的“EARTH”块作为块的定义点时，贪婪地获取最大的非相交、最大体积块的子集：即使是线程，这个算法也非常慢（在 8 核系统上使用 8 个线程大约需要 16 分钟） ，但它生成的块最少（<65,536）。
- 贪婪地抓取最大的非相交块子集，同时将块的尺寸视为目标分数以最大化：比其他贪婪方法慢得多，并且也生成了几千个块。
考虑到最大可接受的块数是每个 (x,y) 坐标一个块来表示单个列，只有贪心体积的结果可以被认为接近最优。
我不知道如何在不使用永无止境的蛮力方法的情况下计算最小块数，所以我不知道是否有可能比贪心交易量方法做得更好。此外，我不知道如何使它更快。谁能给我一个算法来尝试或至少指出我正确的方向？如果这不能做得更好，我想用另一种方法来解决我的问题。