浅谈游戏Minecraft中的数据结构

作者: liadrinz | 来源:发表于2020-02-06 15:55 被阅读0次

前言

《我的世界》(英文名：Minecraft, 简称: MC) 相信大多数人并不陌生，它是一款沙盒游戏，最初由瑞典游戏设计师马库斯·阿列克谢·泊松（别名Notch）单独开发，随后由2009年成立的瑞典公司Mojang开发并发行。玩家可以在一个随机生成的3D(世界内，以带材质贴图的立方体为基础进行游戏。游戏中的其他特色包括探索世界、采集资源、合成物品及生存冒险等。（来自维基百科）

图1 玩家在Minecraft中建造的豪宅（侵删）

方块是MC的灵魂。玩家的创意通过方块的形式表现出来，游戏内容通过方块进行呈现，方块是组成这个世界的最小单位。玩家通过多样化的方块可以构建出任何自己想构建出的东西，甚至有大神已经尝试在MC中构建计算机，这充分地体现出《我的世界》高自由度、高真实性的特点。本文主要就MC中方块存储的数据结构进行简要介绍，并讨论其设计上的值得学习的思想和精妙之处。

方块的存储

重要结构

方块的存储中有两个重要的结构，即分区 (Section, 又名Chunk Section)和区块 (Chunk, 又名Chunk Column)。一个分区是由16*16*16个方块构成的大立方体，而一个区块由16个分区堆叠而成，方块、分区和区块三者的关系如图2所示。可以看到，一个区块共包含16*256*16个 (共65536个)方块。(Chunk其实有两重含义，MC玩家所说的Chunk一般指的是Chunk Column，也就是本文中所说的区块，而Mojang公司所说的Chunk一般指的是Chunk Section).

图2 方块、分区和区块的关系

分区

分区中的4096个方块每个都可能为空。如果一个分区中所有方块都为空，那么这个分区将被视为空分区，这个分区的数据将不会被发送到客户端。如果这个分区至少有一个方块不为空，则该分区将被视为活跃分区，分区的所有数据都会被发送到客户端。分区在数据传输中具有不可分割的性质。
分区中存储了4096个方块的数据，按照方块在分区中的相对位置存储在数组中。分区的绝对位置由其所在的区块来确定，也就是说分区本身不包含该分区的绝对位置。

区块

分区的数据被封装在区块中进行传输。区块的头部包含了区块的 $x$ 和 $z$ 坐标，但没有 $y$ 坐标。举一个例子，一个区块可以看作一栋高为256，长和宽均为1的大楼， $x$ 和 $z$ 确定了大楼所在的地址，不存在 $y$ 数据是因为大楼必须建在地面上， $y$ 默认为0，且不允许从 $y$ 不为0的地方开始“建造”这栋大楼，这也就解释了为什么早期版本的MC的高度限制为256。确定了区块的 $x$ 和 $z$ 也就确定了区块中所有方块的 $x$ 和 $z$ .

区块需要对分区进行组织，使分区在区块内的位置是可以确定的，即确定区块中所有方块的 $y$ . 一种最简单的方案就是参考分区对方块的做法，使用长度为16的数组来存储分区，然而这种做法有一个缺陷，空分区也需要占用存储空间。以图3为例，但如果直接去掉这6个空分区，将所有活跃分区连续地存储在长度为10的数组中，那么每个活跃分区的 $y$ 就被改变了，虽然节约了空间，但数据都被篡改了，显然不可行。

图3 区块中的活跃分区和空分区

开发者在区块中增加了一个位掩码 (bitmask)来解决这个问题。以图3为例，首先将空分区去掉，将所有活跃分区存储在长度为10的数组中，然后按照该区块中分区是否为空来设置16位掩码，第 $i$ 个区块为空则将掩码的第 $i$ 为置为0，反之则置为1，则图三所示区块的位掩码应为 1001101101110101. 通过位掩码可以还原各分区在分区中的 $y$ 位置，例如，掩码中的第3个1位于掩码的第5位，因此数组中第3个分区的真实 $y$ 值为5. 这样一来既节省了存储空间，又防止了数据的丢失。

图4 去除空分区

调色板机制

对于MC中的场景，通常存在大量相同的方块。图1所示的场景便是一个最好的例子，大量的树叶使用的是同一种方块。试想，如果每个树叶方块都包含材质、光线、功能等信息，这些信息就会被重复存储多次。最简单的解决方案就是只存储方块的ID，并将ID与方块建立一对一的关系表，这个关系表就被称为调色板 (palette)。好比涂色游戏，将一幅图划分为多个区域，每个区域标记上一个数字代表该区域应该涂上什么颜色，玩家根据数字和颜色的对应关系完成上色，其中数字和颜色的对应关系就是调色板。

调色板

假设树叶方块的大小为 $n$ bytes，图中共有 $m$ 个树叶方块，不使用调色板进行存储需要 $mn$ bytes的存储空间。方块ID为long类型整数，所占空间为8 bytes，调色板中的一条记录包含ID和方块，共需 $n+8$ bytes，因此存储 $m$ 个树叶方块需要 $n+8(m+1)$ bytes的存储空间。使用调色板能节省的存储空间为 $n(m-1)-8(m+1)$ ， $m\rightarrow \infty$ 时为 $m(n-8)$ . 一个方块所占的存储空间远大于一个long类型整数。

对比实验

选用线性存储和哈希存储的方式与上述区块存储进行对比。线性存储即最简单粗暴的方法，将每个方块直接存储在列表中，方块中包含了该方块的位置信息 $x, y, z$ . 哈希存储是根据哈希函数 $h(x, y, z)$ 计算出位置的哈希值，然后将方块存储到哈希表的指定位置。对比了三种存储方式插入方块、查找方块、从磁盘读取方块和将方块写入磁盘的时间，实验结果如图6所示。实验源代码在作者的GitHub仓库。

图6 三种存储方式的性能对比实验结果

参考文献

网友评论

本文标题：浅谈游戏Minecraft中的数据结构

本文链接：https://www.haomeiwen.com/subject/qdxdxhtx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！