Minecraft类游戏地形生成机制

目录

• 前言
• 生成地形高度
• 生成生物群落
• 模拟雨水侵蚀、生成河流（未完）
• 生成洞穴、裂谷
• 生成植被
  • 放置树木（Bezier曲线）
• 生成建筑
  • 生成发展域（元胞自动机模型）
  • 放置建筑（DFS）
  • 连接道路（A*寻路）
• 优化
  • 地形加载&渲染
  • 数据存储&查询

前言

---

在毕业之际，总算是做出了一个关于Minecraft类游戏地形生成的DEMO作为毕业设计，虽然说不上有多高大上，但也算是给 Gameplay 技能栈多点了一个熟练度，了解了下一些关于地形生成的算法。不过由于博主并未透彻研究过Minecraft的源代码，凭着部分别参考资料去猜测地形生成的实现方式，因此这个地形生成算法可以说算是靠自己实践得出的经验。这篇博客便是记录自己经验的一篇博客。

在阅读本篇博客之前，还需要掌握 噪声算法 ，若对噪声算法不了解，可参考博主以前的博客：游戏开发中的噪声算法

github源码地址：https://github.com/KillerAery/Minecraft-Like-TerrainGenerationDemo

程序截图：

参考资料：

[1]. Technical jargon heavy article about how terrain is generated in DwarfCorp.

[2]. 知乎 | Minecraft的地形生成算法是什么？

生成地形高度

一般的地形生成中，地形高度场都是通过2D噪声（输入一个二维坐标，输出一个高度值）来生成的，但是一层噪声往往具有单调的特性（单一的频率Frequenccies 和 振幅Amplitudes），不能满足复杂的自然地形高度：地形可能会有大段连绵、高耸山地，也会有丘陵和蚀坑，更小点的有岩石块，甚至更小的鹅卵石块。

为了模拟出这样的自然噪声特性，我们可以借鉴 分形噪声 的思想，通过使用不同的参数进行多几次不同参数的噪声计算，然后将结果叠加在一起。

在DEMO程序的高度生成中，将使用三层2D噪声进行叠加，其中：

• 第一层：振幅大，频率小，用于模拟平坦大陆的效果
• 第二层：振幅一般，频率一般，用于模拟山脉群的效果
• 第三层：振幅小，频率大，用于模拟小山丘、地面小凹凸的效果

\(Height(x,y)=128∗Noise2D(4x,4y)+64∗Noise2D(8x,8y)+32∗Noise2D(16x,16y)\)

生成生物群落

生物群落（Biome），实际上相当于一个区域的基本地形面貌，例如可分为草地、高原、雪原、沙漠、热带雨林等。影响生物群落的因素可以有很多，包含但不限于：温度、湿度、高度、距离大海的距离、魔力值。如何定义影响因素，完全取决于你的建模。

DEMO程序中的生物群落属性只取决于 温度（Temperature）、湿度（Humidity）两个因素，而这两个因素又是分别由不同种子设置的噪声计算得出：

\(\begin{aligned}Temperature(x,y)&=Noise2D(8x,8y) \\ Humidity(x,y)&=Noise2D(8x,8y)\end{aligned}\)

DEMO程序将温度（Temperature）粗略分为热带、温带、寒带，湿度（Humidity）粗略分为干燥、湿润；然后也相应提供了六种不同的生物群落类型：草地、雪地、沙漠、热带雨林、温带树林、寒带针叶林。

模拟雨水侵蚀、生成河流（未完）

---

DFS思想解决，模拟大雨滴落在地面上砸出一个个小坑的效果。

1. 模拟一个雨滴，先定义雨滴的质量（比如5000）

2. 随机砸下来在某个位置，并计算它周边的梯度（下降最急的地方）

3. 沿着梯度移动雨滴，同时在原位置留下一定质量的水

4. 继续追踪雨滴进行计算，当雨滴质量衰减到0时或者流进海平面时视为终止

对一定范围内随机模拟多个雨滴，得到的结果将是一个有侵蚀，甚至形成河流的地形。

生成洞穴、裂谷

---

洞穴生成，实际上基于一层3D噪声（输入一个三维坐标，输出一个噪声值）来完成：

\(Cave(x,y,z)=Noise3D(16x,16y,16z)\)

然后再给定一个阈值，做如下判断：

• 若噪声值高于阈值，则三维坐标对应方块挖空
• 若噪声值低于阈值，则三维坐标对应方块保留

当阈值越小，那么更加容易产生洞穴且洞穴规模越来越大。

生成植被

植被生成，则主要是在计算生成概率，它在DEMO程序中依赖四个因素（温度、湿度、噪声值、随机值）：

\(\begin{aligned} Possible_{tree}(x,y) &=N_{tree}+H_{tree}+T_{tree}+R_{tree} \\ N_{tree} &= C_1 \cdot Noise2D(32x,32z) \\ H_{tree} &= C_2 \cdot Humidity(x,y)\\ T_{tree} &=C_3 \cdot |Temperature(x,y)-0.4|\\ R_{tree} &=C_4 \cdot Rand(x,y) \end{aligned}\)

其中，\(C_1\)、\(C_2\)、\(C_3\)、\(C_4\) 分别代表四个因素的权重，四个权重之和为1。

植物生成概率依赖湿度、温度因素很合理，为什么要依赖噪声值、随机值呢？

• 噪声值：让某些区域的植物分布足够密集，而另一些区域的植物分布可以稀疏甚至无分布，这些区域之间又可以做到植物密度的平滑衔接。
• 随机值：密集分布区域的植物几乎每一格都会满足生成概率条件，为了避免过于密集，融入一些随机值因素，让分布的树木之间至少有一定的间距。

放置树木（Bezier曲线）

一旦满足生成概率条件，我们就可以根据当前方块的生物群落属性来决定放置什么样的植物（温带草、寒带草、蘑菇、花、寒带树、温带树、热带树...）。

其中树木的放置稍微复杂些，DEMO程序采取了程序化生成而非模板生成的方式来放置树木：

1. 用一个随机数给出树木的最大高度 \(h_{max}\)

2. 还需要计算树干每层的树叶半径，这一步主要通过三阶Bezier曲线来计算。三阶Bezier曲线拥有4个控制点（2D坐标），将控制点的 \(x\) 视为树叶半径长，而 \(y\) 视为所处在的树干高度。由于树叶在最底层和最顶层都应该是没有树叶的，这样就可以将第一个控制点和最后一个控制点固定在 \((0,0)\) 和 \((h_{max},0)\) ；而中间两个控制点则可以利用两个随机数作为不同的随机半径\(r_1\)、\(r_2\)，分别设置位于 \((\frac{1}{3}h_{max},r_1)\) 和 \((\frac{2}{3}h_{max},r_2)\)。

3. 在每个单位高度上对贝塞尔曲线上一次采样，从而得到每层树叶的半径值（采样后四舍五入）。

生成建筑

生成发展域（元胞自动机模型）

基于元胞自动机模型。

发展域可以理解成一个聚落的势力范围。而生成发展域的大概做法是：

1. 在某个方块设置聚落的源点

2. 进行若干轮迭代演化，来演绎聚落的发展（扩展势力范围），其中每轮发展需要根据温度、湿度、崎岖度（周围若干方块高低差）等因素来影响发展域的扩展方向，而且只扩张在势力范围邻接的方块。

而在DEMO程序实现中，有以下细节：

• 需要设置一个最高发展度（迭代次数）。
• 一个发展块设置为3*3个方块，这是因为相同大小的势力范围下，一次添加3*3个方块相比1个方块有着更少的迭代次数。
• 每一轮迭代都从评估队列里将代价最低的发展块加入聚落的势力范围，然后将与该发展块相邻的发展块加入队列中，并分别进行代价评估（即温度、湿度、崎岖度的综合考量）。

放置建筑（DFS）

放置建筑，主要是基于DFS算法（在某种意义上，用高大上的名词来讲就是波函数坍缩），在前面生成好的发展域内通过DFS算法随机尝试放置预制建筑。

DEMO程序的大致实现：

1. 在待放置位置队列添加源点位置

2. 进行若干次循环，每次循环从队列中取出一个位置（以该位置为建筑中心点）尝试放置预制建筑。

   • 若建筑即将放置的区域并不是发展域的子集，则尝试放置失败。
   • 若建筑即将放置的区域是发展域的子集，则尝试放置成功，需将地形进行平整化后再放置建筑。接着，将该位置上下左右四个方向一定offset（需要融入一定的随机数，这样得到的建筑分布就不会过于工整）的位置添加进待放置位置队列。最后，移除发展域相应的区域方块记录（避免重复放置建筑）。

连接道路（A*寻路）

连接道路，主要是基于A*寻路算法，将每个建筑的门口视为目标点，通过寻路算法对所有目标点两两连成一条道路。然而问题在于，道路连接不是简单的寻找最短路，还得模拟出人类聚落主干道、分支路的特性。

DEMO程序的解决方式：

• 只需简单地修改代价函数，使结点在道路上的开销降低

这样，第一条道路虽然总是最短路，但是往后每次连接新道路时，这些寻路算法会相当大可能贴近或者连进原有道路，而不是直接连成最短路。若干条道路生成完毕后，就会显而易见看到干道、分支路的现象了。

优化

地形加载&渲染

有时候可能加载方块太多导致内存不足，需要实现实时自动加载周围区域和卸载过远的区域。

其次，Minecraft类地形中往往有大量方块被其它（上下左右前后共6个）方块所包围，从而不可视。而最初的渲染中，需要把所有存在的方块都渲染出来：

如果对每个方块做可视测试（即检测其上下左右前后是否满足至少有一处无方块），通过测试的才提交渲染队列，于是便有了下图：

为了解决边界问题（最外面的渲染边界的方块无法得知界外的方块信息），于是就采取了加载范围大于渲染范围的方案：

• 块区（Chunk）：基本的地形加载/卸载单位，在X轴、Y轴长度为16，在Z轴（高度轴）长度为256，可容纳16*16*256共65536个方块
• 加载块区：计算出该块区每个位置的方块属性并存于内存
• 渲染块区：将该块区里所有应该渲染的方块提交渲染队列

以摄像机的位置为中心，将周围6*6个的块区作为需要加载的块区，而周围5*5个块区作为需要渲染的块区。这样渲染边界的方块也能得知界外方块（因为相邻的块区总是会被加载）的方块信息。

数据存储&查询

一般来说，存储Minecraft类地形数据并不需要记录太多信息，得益于噪声算法的可哈希性，几乎仅需要一个种子，因为绝大部分方块（正常方块）都可以通过地形生成算法流程便能计算得出方块ID属性，即 \(F(seed,position) = blockID\)。

然而对于被玩家破坏、修改、新增而导致的方块ID属性产生变化，这时候就需要特别额外存储了。

此外，在查询时可以对坐标压缩/解压：Vector3D <=> uint64 (28 bit,28 bit,8 bit)，Z轴高度由于最高为256，因此最多占8位。