什么是标准数据结构，可以有效地表示Minecraft世界？

Question

我在考虑每个x、y、z坐标都有一个3x3的矩阵，但这样会浪费大量的内存空间，因为很多方块空间是空的。另一个解决方案是使用哈希表 ((x,y,z) -> BlockObject)，但这似乎也不太高效。

当我说高效时，并不是指最优化。它只是意味着可以在现代计算机上平稳运行就足够了。请记住，Minecraft生成的世界非常巨大，因此效率非常重要。还有大量需要存储的元数据。

- TheOne

---

这可能更适合放在http://gamedev.stackexchange.com上。 - Paul

所有那些类似于StackOverflow的衍生网站开始变得让人烦恼了。每天都会有新的出现。 - TheOne

请求将此问题移动到适当的StackExchange网站。 - TheOne

我不会在这方面和你不同意...虽然SE世界存在太多的碎片化，但游戏开发是一个可以作为独立社区的好选择。 - Paul

这个问题不是一个真正的问题的原因之一是你在问两个独立的问题，而不仅仅是一个问题。此外，“如何高效地渲染Minecraft世界？”是一个模糊的问题，需要写一篇文章才能合理回答。另一个使它不是一个真正的“编程”问题的原因是它非常局限于一个特定的闭源程序，我们中很少有人可以访问，因此不太可能得到一个真正的答案。询问“存储这种数据的标准数据结构是什么？”是一个更容易回答的问题。 - Brooks Moses

Answer 1

如我在评论中所提到的，我不知道MineCraft是如何实现这一点的，但常见的有效表示此类数据的方法是八叉树；http://en.wikipedia.org/wiki/Octree。其基本思想是它类似于二叉树，但是在三维空间中。您可以递归地将每个空间块在每个维度上分成八个较小的块，并且每个块都包含指向较小块的指针和指向其父块的指针。

这使您能够高效地存储大量相同材料（例如“空白空间”）的块，因为即使您没有递归到单个“立方体”单位的级别，只要您到达由所有相同事物组成的块，您就可以终止递归。

此外，这意味着您可以通过取当前块并向上遍历树，直到达到包含您所能看到的所有块的块，从而高效地查找给定区域中的所有立方体 - 这样，您可以非常容易地忽略其他位置的所有立方体。

- Brooks Moses

Answer 2

如果你有兴趣探索代表Minecraft世界（块）数据的替代方法，你也可以研究一下位串的想法。每个“块”由一个16*16*128的体积组成，而16*16可以用单个字节字符充分表示，并可以合并为二进制字符串。

由于这种方法高度特定于交易客户端计算与高度优化的存储和传输时间的某个目标，因此试图解释所有细节似乎是不明智的，但如果你有兴趣，我已经为此创建了一个规范。

使用这种方法，计算存储成本与当前的每块1字节的方法截然不同，而是“可变比特率”：（（每块1位，向上取整到8的倍数）*（块类型在块中出现的唯一层数）+ 2字节）

然后对该块中的（唯一块类型数量）进行求和。

在绝大多数情况下，只有在故意的边缘情况下，这可能比通常结构化的块更昂贵，在超过99%的Minecraft块是自然生成的，并且在我的许多测试中都可以通过这种可变比特表示以8:1或更高的比例获益。

- hexparrot

Answer 3

你最好的选择是反编译Minecraft并查看源代码。修改Minecraft：源代码是一个很好的教程，告诉你如何做到这一点。

- Paul

Answer 4

Minecraft非常不高效。它只存储数据的“块”。

请查看Minecraft Wiki上开发资源中的“地图格式”。据我所知，内部表示完全相同。

- kaoD