data-structures - 可用于有效表示 Minecraft 世界的标准数据结构是什么？

Question

关闭。这个问题是off-topic .它目前不接受答案。












想改善这个问题吗？ Update the question所以它是 on-topic对于堆栈溢出。

9年前关闭。




Improve this question




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

当我说高效时，我的意思不是最优。这只是意味着它足以在您的现代计算机上流畅运行。请记住，Minecraft 生成的世界非常庞大，无论如何效率都很重要。还有大量的元数据需要存储。

Answer 1

正如我在评论中所指出的，我不知道 MineCraft 是如何做到这一点的，但表示此类数据的一种常见有效方式是八叉树； http://en.wikipedia.org/wiki/Octree .一般的想法是它就像一个二叉树，但在三个空间中。您递归地划分每个维度中的每个空间块以获得八个较小的块，每个块包含指向较小块的指针和指向其父块的指针。

这使您可以高效地存储相同 Material 的大块(例如，“空白空间”)，因为您可以在到达由所有相同内容组成的块时终止递归，即使您没有t 递归到单个“立方体”单元的级别。

此外，这意味着您可以有效地找到给定区域中的所有立方体，方法是获取当前块并沿着树向上爬足够远以到达包含您能看到的所有块的块 - 这样，您就可以非常轻松地忽略其他地方的所有立方体。