我正在研究使用体素来表示大型（256x256x256 体素）战场以及服务器托管的多人游戏的可破坏地形的可行性。任何游戏一次只存在一个战场。然而，为了能够广播房间及其地形的变化，我试图找到一种算法，可以将体素分组为尽可能少的矩形块。
举一个简单的例子，如果关卡的下半部分完全充满一种类型的体素，上半部分充满另一种类型的体素，则关卡应分为两个块，一个代表关卡的下半部分，另一个代表关卡的下半部分。其他代表顶部。理想情况下，该算法应该能够实时运行，这样地形中的任何变形都可以在每帧的基础上进行计算并向客户端广播。这应该使客户端能够有效地渲染地形，而不必担心在客户端中重复地形破坏逻辑。
以下是我尝试过的方法以及我发现的问题。报告的块计数用于通过将超过 4,194,304 个“地球”体素随机放置到尽可能靠近底部的位置来填充 256^3 空间，以获取随机选择的 (x,z) 坐标。仅计算“EARTH”块。
- 八叉树：非常快，但如果我在空间中间分裂，它会产生大量的块（800,000+）。
- k-D 树分裂以最小化分裂后的加权熵：比八叉树稍慢，但块少得多（~350,000）。
- k-D 树分裂以最大化信息增益比：比之前的 k-D 树方法快两倍，生成的块少得多（~167,000），但仍然很慢。
- k-D 树分裂以最小化 Gower 相似度：非常慢，但生成的块比任何其他 k-D 树方法都要少（~155,000）。
- 当将每个无人认领的“地球”块视为块的定义点时，贪婪地抓取可用的非相交的最大子集、最大体积块：即使是线程化的，该算法也慢得令人发指（在 8 核系统上使用 8 个线程大约需要 16 分钟） ，但它生成的块最少（
- 贪婪地抓取不相交块的最大子集，同时将块的尺寸视为目标分数以最大化：比其他贪婪方法慢得多，并且还会生成数千个块。
考虑到最大可接受的块数是每个 (x,y) 坐标一个块来表示单个列，只有贪婪卷的结果才可以被认为接近最佳。
我不知道如何在不使用永无休止的强力方法的情况下计算最小块数，所以我不知道是否可以比贪婪体积方法做得更好。此外，我不知道如何才能让它更快。谁能给我一个算法来尝试或至少为我指明正确的方向？如果不能做得更好，我想用另一种方法来解决我的问题。
None
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
