柏林噪声算法

经典实现

经典的柏林噪声是一种基于晶格的噪声生成算法，在二维空间中定义一个栅格，晶格点处的梯度向量是随机的，任一点与晶格四周的四个梯度向量点乘，四个结果二次插值。插值后所得结果需平滑处理（一个五次函数确保一阶导为0）。

分形

最开始是两层，用低频率，大振幅来模拟大尺度变化，用高频率，小振幅来模拟小尺度的变化，并将之分形叠加。

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

地形生成

生成地形高度场

在这一过程中，利用柏林噪声分形的思想，通过改变振幅和频率进行噪声叠加，并获得了更好的模拟效果。

模拟降雨生成水系

在随机地块生成一朵云，并开始执行以下操作：

1. 假设这朵云只落在地上某点，且降水量固定。
2. 计算该点周边的梯度（高度差）。
3. 在原位置留下一定质量的水后，大雨滴向落差最大的方向移动。
4. 递归执行直到水滴质量耗尽。

在一定范围内随机生成多个云朵，便可以较好地模拟出湖泊以及河流。

洞穴生成

通过3D柏林噪声生成噪声值，若噪声值高于特定值则对应地块挖空。

生态生成

温度生成

将 依据随机种子生成2D分形柏林噪声（思路与地形生成接近） 与 地形高度数据 线性插值，生成随机数据。

湿度生成

将 依据随机种子生成的2D分形柏林噪声 与 该地块与水面的距离 进行线性插值。

其中水域以坐标的集合的形式存储，在数据量较大的情况下，使用了K-d Tree进行效率优化。

划分生态

根据温度将地块分为热带，温带，寒带；根据湿度将地块分为干燥和湿润。并叠加出六种不同的地形。

植被生成

通过温度，湿度，随机值，噪声值四种因素计算生成概率。

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

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

借助三阶贝塞尔曲线生成树叶

由于Demo中树木的高度是动态生成的，我们需要通过程序控制树叶生成的平滑。

这一步主要通过三阶Bezier曲线来计算。

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

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

村庄生成

生成村庄的范围

基于BFS的启发式算法。

1. 将随机地块设置为村庄的起点，标记进范围内。

2. 依据温度湿度高度差等因素估计该地块的邻接地块的发展值。

3. 将邻接地块放进一个优先队列（小心问你堆），按照发展值排序。

4. 从优先队列中取出最大值的地块，重复以上步骤。

5. 设置一个最大发展上限，强制迭代一定次数后结束迭代。

   由于发展值的估计依赖于温度湿度高度，它们都跟柏林噪声有较大的相关性。而柏林噪声具有连续的特性，可以确保发展域很大概率是连续的。

放置建筑

1. 获取村庄范围内的随机点，加入一个队列。
2. 尝试放置建筑，若房屋范围没有超出发展域即放置成功。
3. 如果放置成功，把房屋范围从发展域中去除。将房屋中心的上下左右四个方向的某个位置（添加一定范围的offset 以模拟村庄的错落有致）加入队列。
4. 循环直至队列为空。

生成道路

1. 通过A*算法寻路，以各个房屋的门口为目标点，生成道路。
2. 道路连接不是简单的寻找最短路，而是需要模拟出人类聚落主干道、分支路的特性。
3. 解决方法：修改代价函数，使结点在道路上的开销降低。每次生成完一条道路，需记录道路位置信息，并降低估值代价。

优化思路

1. 对每个方块进行可视测试。即检测其上下左右前后是否满足至少有一处无方块，通过测试的方块才提交至渲染队列。
2. 以区块为基本的加载单位，减少提交渲染的次数。
3. 加载和渲染分离。以玩家为中心，只对周围较小范围内的区块进行渲染，而在更大的范围内进行区块的加载。