Minecraft 类游戏地形生成算法

噪声算法

为什么要有噪声？

随机数 VS 噪声

随机数：随机生成一个噪点不一的黑白图，但因为过于随机生成的图看起来特别不舒服。

噪声：具有随机性、可哈希的、平滑性。

Value 噪声算法

Noise2D(pos) = lerp(顶点A,顶点B,s(t)),t∈[0,1]

定义若干个顶点，且每个顶点含有一个随机值（以顶点坐标为参数，通过 Hash 运算得到）

顶点会对周围坐标产生影响，越靠近顶点，则越容易受该顶点的随机值影响

某个坐标的噪声值 = 该坐标附近的所有顶点所造成的影响之和

Perlin 噪声 (柏林噪声)

定义若干个顶点，且每个顶点含有一个随机向量（以顶点坐标作为参数，通过 Hash 运算）

顶点会对周围坐标产生影响，和顶点随机向量的夹角越小，则得到的值越大

某个坐标的噪声值 = 该坐标附近的所有顶点所造成的影响值之和

Simplex 噪声（高维制作常用）

Perlin 噪声在晶格结构上是正多胞，在 N 维下有 2^N 个顶点，一次噪声计算需要计算 2^N 个顶点的势能影响

Simplex 噪声在晶格结构上是单形，在 N 维下有 n+1 个顶点，一次噪声计算需要计算 n+1 个顶点的势能影响

地形生成流程

生成地形高度图

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

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

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

第一层：振幅大，频率小，用于模拟平坦大陆的效果

第二层：振幅一般，频率一般，用于模拟山脉群的效果

第三层：振幅小，频率大，用于模拟小山丘、地面小凹凸的效果

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

生成生物群落

生物群落（Biome）:

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

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

Temperature(x,y)=Noise2D(8x,8y)

Humidity(x,y)=Noise2D(8x,8y)

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

模拟雨水侵蚀、生成河流

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

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

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

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

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

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

生成洞穴、裂谷

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

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

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

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

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

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

然而这种洞穴往往是不规则的，显然是不符合裂谷、峡谷这种带有狭长特点的中空地形，对于这类地形可另外使用伸缩变换后的3D坐标参数，此外还应当加入高度因素的影响（例如高度越低，意味着越接近地底，因此赋予更低的阈值），这样也可以形成具有一定深度的裂谷。

生成植被

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

其中，C1、C2、C3、C4 分别代表四个因素的权重，四个权重之和为1。

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

噪声值：让某些区域的植物分布足够密集，而另一些区域的植物分布可以稀疏甚至无分布，这些区域之间又可以做到植物密度的平滑衔接。

随机值：密集分布区域的植物几乎每一格都会满足生成概率条件，为了避免过于密集，融入一些随机值因素，让分布的树木之间至少有一定的间距。

放置树木（Bezier曲线）

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

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

1.用一个随机数给出树木的最大高度 hmax

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

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

如图所示，当计算出一棵树的随机高度为5时，用于生成树叶的贝塞尔曲线的第一个控制点和第四个控制点分别为(0,0)和(5,0)。接着，中间两个控制点，通过随机数4.5、2.5确定坐标分别为(1.66667,4.5)、(3.33333,2.5)。当树需要计算每层树叶半径时，就可以逐层对该贝塞尔曲线进行采样，共采样6次，对应6层树叶半径，分别为(0,0)、(1,2.2)、(2,2.6)、(3,2.4)、(4,1.6)、(5,0)，四舍五入后即为 (0,0)、(1,2)、(2,3)、(3,2)、(4,2)、(5,0)。

生成建筑

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

基于元胞自动机模型。
发展域可以理解成一个聚落的势力范围。而生成发展域的大概做法是：

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

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

温度、湿度越适中、崎岖度越小的方块的代价更低，从而也更容易让聚落范围往这种方块的方向去扩展。

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

需要设置一个最高发展度（迭代次数）。

一个发展块设置为33个方块，这是因为相同大小的势力范围下，一次添加33个方块相比1个方块有着更少的迭代次数。

每一轮迭代都从评估队列里将代价最低的发展块加入聚落的势力范围，然后将与该发展块相邻的发展块加入队列中，并分别进行代价评估（即温度、湿度、崎岖度的综合考量）。

在《DwarfCorp》中，这种元胞自动机模型又可以用于模拟各文明在地图上的势力范围，让文明源点尽可能往条件宜人、土地肥沃且少冲突的区域扩张，通过若干轮迭代后，就能得出一条合理的文明势力边界

放置建筑（DFS）

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

程序的大致实现：

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

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

-若建筑即将放置的区域并不是发展域的子集，则尝试放置失败。

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

连接道路（A*寻路）

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

程序的解决方式：

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

每次生成完一条道路，需记录道路位置信息，以方便下次寻路查询某个坐标是否位于道路中。

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

优化

######地形加载&渲染

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

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

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

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

块区（Chunk）：基本的地形加载/卸载单位，在X轴、Y轴长度为16，在Z轴（高度轴）长度为256，可容纳1616256共65536个方块

加载块区：计算出该块区每个位置的方块属性并存于内存

渲染块区：将该块区里所有应该渲染的方块提交渲染队列

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

数据存储&查询

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

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

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