前言
坑挖得太大了……
14号活动帖子发出来时，我就开始整这个投稿了，当时设想了很多东西，什么日月星辰、风雨雷电、花草树木、沧海桑田都想加进去。后来实践起来，工作量远超自己的想象。真这样搞起来10年都填不完了。
眼看着论坛里大神们一个接一个地抛出好东西，忍不住了，先把当前的成果搬出来了，以后有时间再继续加工。
关于噪声生成算法
大就是强，大就是美！谁会不喜欢大的呢？
我第一次接触到随机生成无限大世界这个概念，是看到了这一篇文章
[《无人深空》是怎样生成一个宇宙的？] https://indienova.com/indie-game-news/how-does-no-mans-sky-generate-the-universe/
里面提到了用一个自然界存在的拥有着无限量信息的无理数来构造世界，没错，那位大人就是：π！
但是当时我还是个小菜鸡，只是隐约理解了程序化生成世界使用了π，但是具体怎么操作，完全没有头绪，直到后来学shader时看了这本经典的电子书：
[thebookofshaders] https://thebookofshaders.com/?lan=ch
这本电子书里有不少内容，这里不多赘述，简单来说，它写了怎么程序化生成一个噪声。这里我会用 三个步骤 简单地告诉大家，程序化生成噪声的几个核心要点：
1一步计算即可获得的随机数
首先抛开复杂的东西，要想生成一个随机的内容，我们第一步要生成一个随机数，不，等等，在程序化生成世界的过程中，我们需要大量随机数，并且这些随机数会由它们的坐标唯一确定。
theshaderofbooks里描述了随机数生成的计算，并且用了可以编写实时查看的网页元素的方式来呈现，非常地高端大气，但是关于随机数这第一步，也许是因为翻译的问题，我个人觉得书里没有很好的说清楚。下面我将结合图片来说说我的理解，先看噪声那一章节的图：
看代码，输入值x经过了一次 fract 操作，也就是取小数部分。我们可以理解为它将曲线划分成了以 1 为周期的无限区块。
再回头看随机那一章节的图：
这里对输入的x值进行了一次 sin 操作。
好了，大声告诉我， sin的周期是多少 ！
这就是核心操作了，一个周期为 2π 的曲线，我们每隔单位 1 取一个值，取出的数值构成的数列，从数学逻辑上保证了没有周期性。所以，它是一个随机数列。
2平滑过渡，一维变二维
第一步我们获得的是一些离散的随机数，但是现实中的噪声，非常接近的两个坐标点之间的值也是非常接近的，也就是说噪声是具有连续性的。
从离散的数列到具有连续性的曲线，很简单，两个点之间平滑过渡一下即可：
一般情况下，会用常用的smoothstep算法来做平滑过渡，thebookofshader中还提到了simplexNoise中使用到的四次Hermite函数。
关于这方面我并没有过多的研究，只有一个小小的个人经验，那就是smoothstep函数，在端点处的斜率是0，也就是说上面那个曲线，每隔单位1就会出现一个“平地”。
平滑过渡之后，再将一维曲线升级一下，变成二维的噪声图即可，这里就不多赘述了，网上有的是教程：
3迭代、分形
噪声生成相关的技术中，有个听起来非常牛批的东西， 分形布朗运动（Fractal Brownian Motion） ，简称 fbm 。
别被它吓到，这玩意用简单地白话来说，就是用了一次for循环，对我们上面步骤获得的波进行了叠加而已。
布朗运动是指悬浮在液体或气体中的微粒所做的永不停息的无规则运动。
分形则是数学中的一个概念，大家可能已经忘了，一个例子帮你回忆起来： 雪花晶体 ！
所谓分形，就是放大了之后看，小的部分和大的形状相似。
那么怎么整出分形布朗运动呢？简单，把我们上面步骤获得的曲线，缩小振幅，加大频率，经过多次迭代即可。
这里还引入了一个术语： octaves（八度） 。这是音乐中的一个概念，在这里，fbm进行了几次迭代，就称为几个八度。
cocos creator代码生成网格
代码接口
ccc提供了代码生成网格的接口，直接看官方文档即可。但是只有简单地几句代码示例。
先来个简单地示例：
let mesh:Mesh = utils.MeshUtils.createMesh({
colors:[1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1],
positions:[0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1],
indices:[0, 3, 2, 0, 2, 1],
minPos:v3(0, 0, 0),
maxPos:v3(1,1,1),
// attributes: [
// new gfx.Attribute(gfx.AttributeName.ATTR_POSITION, gfx.Format.RGB32F),
// ],
});
positions
顶点坐标数组。长度必定为3的倍数，每三个值代表一个顶点的x y z
colors
顶点颜色数组。长度必定为4的倍数，每四个值代表一个顶点的rgba(这里的颜色值已经归一化)
indices
顶点数据是可以复用的，indices中的值是顶点数据的索引，每三个值构成一个三角面。
minPos & maxPos
包围盒的起点和终点。也可以缺省，然后在options参数中设置让网格自己计算，但是这样会有较大的计算量。
程序化生成网格的时候要注意，所有三角面需要从相机方向看过去呈 顺时针
这是因为一般3d引擎中，为了减少无用的渲染，通常会有正面、背面的区分，并且一般默认开启背面剔除。而正面背面的区分方式则是三角面的三个顶点的顺逆时针顺序。
attributes
顶点数据格式。可以修改默认的顶点数据的格式。在create-mesh.ts中有定义了程序化网格接口默认的顶点数据格式：
const _defAttrs: Attribute[] = [
new Attribute(AttributeName.ATTR_POSITION, Format.RGB32F),
new Attribute(AttributeName.ATTR_NORMAL, Format.RGB32F),
new Attribute(AttributeName.ATTR_TEX_COORD, Format.RG32F),
new Attribute(AttributeName.ATTR_TANGENT, Format.RGBA32F),
new Attribute(AttributeName.ATTR_COLOR, Format.RGBA32F),
];
5个默认的顶点数据的数据类型都是rgba32f，如果对某个值精度要求不那么高，可以自己改一下，减少带宽（最常见的就是把颜色值改掉）
查看网格
我们使用装饰器executeInEditMode来装饰脚本类，让脚本在编辑器中运行，便于我们观察生成的网格。
为了处理每次修改代码后，脚本反复执行创建网格产生的问题。我们将生成一个子节点，并且将网格放在子节点上，在生成之前做一次removeAllChildren操作。
@ccclass('procedural1')
@executeInEditMode(true)
export class procedural1 extends Component {
start() {
this.node.removeAllChildren()
let node = new Node()
this.node.addChild(node)
let meshRenderer:MeshRenderer = node.addComponent(MeshRenderer);
let mesh:Mesh = utils.MeshUtils.createMesh({
colors:[1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1],
positions:[0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1],
indices:[0, 3, 2, 0, 2, 1],
minPos:v3(0, 0, 0),
maxPos:v3(1,1,1),
// attributes: [
// new gfx.Attribute(gfx.AttributeName.ATTR_POSITION, gfx.Format.RGB32F),
// ],
});
meshRenderer.mesh = mesh;
meshRenderer.onGeometryChanged();
}
}
可以在编辑器中看到我们的网格了，选中后会有一个正方形的盒子边框出来，那是我们自己定义的包围盒
移动镜头到下方看上去，这时网格不见了，因为视角到了网格的背面。有兴趣的同学可以自己试试再改下顶点索引的顺逆时针，或者在后续添加了材质后，修改正面剔除、背面剔除，加深一下对正面剔除、背面剔除机制的理解。
蜂窝网格结构
构造网格时，用两个三角形拼凑成一个正方形是最简单的，但是这样的网格效率低下了一点。在相同顶点数量下，如何让面积尽可能得大，很显然是用等边三角形。而等边三角形拼凑在一起，就形成了无数个正六边形。很自然地，我就用起来六边形网格结构。
关于六角网格，可以参考这一篇文章，干货超多，并且几乎每个图都可以交互：
[六角网格大观] https://indienova.com/indie-game-development/hex-grids-reference/#iah-7
文中内容超多，不多赘述，请大家自己去看。这里只简单说下六角网格相关的计算的一个核心要点： 立方坐标
立方坐标，顾名思义，就是具有xyz三个轴的坐标系，如何在平面中用上三个轴，大家看这个截图就行了：
想象一下我们有很多立方形的方块堆在空间中。这时我们从斜着的方向看去，并且对这些方块进行一个截面的切割：
六角网格和立方坐标，一目了然。
六边形顶点规化为中心点
上面那篇文章中几乎包含了所有六角网格相关的计算的方法，但是我在构造六角网格的时候，还是遇到了一个问题：六角网格的“顶点”（相对于中心点，一个六边形周围的六个角上的点）计算坐标容易，但是重用去重时不好处理。
后来，我经过思考绘图，想到了将顶点规化为中心点：
如图，一个大六边形的顶点，可以视为其尺寸 1/3 的小六边形的中心点。
我们用一个二级map来存储顶点对应的索引值，用立方坐标的x、y来作为键值（立方坐标中x + y + z = 0，所以只需要xy两个值，详情可以看六角网格大观里的说明）
为了显示出六角网格的形状，我们将所有六角网格的 中心点顶点色用黑色，边角顶点用白色
addPoint(aid:Vec3, a:number, isCenter:boolean = false) {
let map = this.idxMap.get(aid.x);
if (!map) {
map = new Map()
this.idxMap.set(aid.x, map)
}
if (map.has(aid.y)) {
return map.get(aid.y)
}
let pos = HexUtils.getCellPositionWithAxisID(aid, a);
this.positions.push(pos.x)
this.positions.push(0)
this.positions.push(pos.y)
if (isCenter) {
this.colors.push(0)
this.colors.push(0)
this.colors.push(0)
this.colors.push(0)
} else {
this.colors.push(1)
this.colors.push(1)
this.colors.push(1)
this.colors.push(1)
}
let idx = this.positions.length / 3 - 1;
map.set(aid.y, idx);
return idx;
}
扩圈
定义一个包围圈数值N,做循环构造六角网格：
let N = 5;
let a = 1;
for (let cx = -N; cx <= N; cx++) {
for (let cy = Math.max(-N - cx, -N); cy <= Math.min(N, -cx + N); cy++) {
let cz = -cx - cy
let center = v3(cx * 3, cy * 3, cz * 3)
let idx0 = this.addPoint(center, a / 3, true)
let offset = v3(1, 1, -2)
let v1 = v3()
Vec3.add(v1, center, offset)
let idx1 = this.addPoint(v1, a / 3)
let v2 = v3()
for (let i = 0; i < 6; i++) {
// 旋转60度
offset.set(-offset.z, -offset.x, -offset.y)
Vec3.add(v2, center, offset)
let idx2 = this.addPoint(v2, a / 3)
this.indices.push(idx0)
this.indices.push(idx1)
this.indices.push(idx2)
v1.set(v2)
idx1 = idx2
}
}
}
旋转
六边形中心点规化成小六边形直接坐标乘以3即可，边角顶点我们先找到一个点，这里找的是中心点偏移（1,1，-1）后的点，然后用六角网格大观中提到的一个非常好用的技巧，通过立方坐标转置来获得旋转60度后的格子的立方坐标：
创建一个材质和shader用上，shader里的输出乘以一下顶点颜色，效果出来了：
好了，你已经学会了噪声和程序化网格了，接下来只要加亿点点细节，就能构造出程序化地形了，前提是你的机子具有理论上无限强大的性能。
亿点点细节
lod
lod(level of details)是一个3d渲染常见的技术。一般我们会在两个地方看到这个词，一个是模型lod。大致就是将制作高模、中模、低模三个模型(或者更多)，然后通过模型和相机的距离，动态地替换不同精度地模型。保证近距离下能够较高的视觉体验，远距离时能有较低的性能消耗。
另一个常见的地方就是某些shader中会定义一个lod值，用于在不同性能设备上，使用不同的shader，来兼容性能差异。
这里我们也用上大致的一个lod技术概念，不过我们不需要做的很动态，由于这个demo设定是从第一人称视角看过去的，所以，只要以角色中心，附近使用高精度网格，距离远的地方使用低精度网格即可。
我们也用下fbm里的术语，用八度octaves表示一个分级，每一级的六边形边长是上一级的2倍，用这样的方式，可以用较少的网格数量构造非常大的地图
let octaves = 5
let N = 5;
let n = N / 2
let a = 1;
for (let oct = 0; oct < octaves; oct++) {
let mul = Math.pow(2, oct)
for (let dx = -N; dx <= N; dx++) {
for (let dy = Math.max(-N - dx, -N); dy <= Math.min(N, -dx + N); dy++) {
let dz = -dx - dy
// oct>0的六角网格，内部一半部分可以不要，由小网格填充
if (oct > 0 && Math.abs(dx) < n && Math.abs(dy) < n && Math.abs(dz) < n) {
continue
}
// 略 大体同上
}
}
}
静态网格&动态网格
在进行程序化地形的尝试的过程中，我试过用ccc的动态网格，官方有个示例可以参考。
一个程序化生成的无边大地图，必定时要时刻修改更新地形的，所以理论上动态网格会更高效。但是使用时，当我将网格的量增大后，遇到了一个报错：
个人猜测是网格的数据量达到上限了。
并且，即时不考虑网格上限的问题，一个非常大的网格，更新时的这么多顶点的计算量也肯定非常夸张。
然后，我经过了几次尝试：
使用shader进行地点坐标偏移
整个网格的y坐标全都设置为0即可，实际的高度，在shader中进行计算偏移。这样的好处是，完全不需要更新网格。你只要将一个扁平的网格移动，shader会帮你显示出该有的高度。
缺点1：只适合单纯显示一个地形。当我们需要有单位在地形上移动时，需要获取地形高度，此时还需要在cpu中进行计算高度。并且，经过我的测试，shader中实时算出的高度由于精度问题，会和cpu端算出的值有较大的误差，这个误差放大到一个非常大的地图中，会非常致命。
缺点2：整个高度全有shader计算，对于超大地图来说，fbm的octaves需要很大，计算量会变得极大。
使用“瓦片”拼凑
参考2d的瓦片地图，我们可以用大量瓦片来拼凑成一个大地图。瓦片可以通过gpu instancing技术进行合批渲染。在cpu端对单个瓦片计算出各自的高度，然后在shader中加上顶点偏移矫正。
拼凑的问题
我以六边形为单位瓦片，将计算好各个六边形的坐标，高度按六边形中心点的噪声值来算。然后算出六个边角顶点的高度和法线，通过gpu示例化属性的方式传递给gpu，用shader来偏移对齐。但是这时却遇到了一个报错，经过几番尝试得出结论： gpu实例化属性的数据量上限为4个vec4 ，也就是一个mat4矩阵。
因此我不得不将所有六边形拆分成3个四边形（mesh只要构建一个即可，通过旋转来用三个拼凑成一个六边形）
使用噪声图
shader中的fbm计算直接换成一个噪声图采样，减少计算量。
通过顶点法线和采样到的fbm计算出的法线叠加，用一个简单的半兰伯特模型计算明暗
着色
程序化地形的着色一般有两种方式，一种是 三向纹理采样 ，即从x、y、z三个方向去采样纹理，然后根据当前点的 法线 来对三个采样值进行融合
如果不用三向纹理采样，单纯用一个方向，比如从俯视方向，用xz向量来采样纹理，那么在一些比较陡峭的斜坡处，会呈现出明显的拉伸现象
另一种方式则简单了，使用单纯的颜色，不过为了展现出不同的地形风貌，我们不该用单纯的一个颜色，而是应该用一个色带。
这里推荐一下shadertoy作者们常用的一个函数：
vec3 palette(in float t, in vec3 a, in vec3 b, in vec3 c, in vec3 d) {
return a + b * cos(6.28318 * (c * t + d));
}
6.28318是2π
t是一个0~1之间的参数（实际上超出了也没关系，反正取色会用cos）
abcd参数控制了rgb三个颜色的曲线，可以去这个网页调节自己想要的色带，然后把参数拿来用即可：
着色后，在将高处的部分加上一些积雪。积雪用简单地法线和竖直方向的夹角来处理计算即可，越是平坦的地方越容易积雪。
然后用高度值来定义一个雪线，在一定高度之上才会有雪。
在给雪线通过我们的噪声图加上一点随机。
float snowHeightValue = smoothstep(40.0, 50.0, v_position.y + texture(mainTexture, p * 0.1).r * 10.0);
float s1 = clamp(1.0 - snowHeightValue, 0.0, 1.0);
float snowValue = smoothstep(s1, s1 + 0.002 / (s1 + 0.1), dot(vec3(0.0, 1.0, 0.0), n)) * 0.5 + 0.5;
移动更新
我们需要在跟着主角移动时更新我们视野内的地形。由于地形很大，所以，我们要尽可能地使用少的变动来实现效果
由于我们已经使用lod的概念，将网格进行了分级，所以我们只要在相应级别的网格需要变更时才即可。
这样说起来可能有点绕，我用一个简单的例子来说明：
主角移动，时刻判定主角所在街道
主角所在街道变了，更新街道网格
更新街道网格时，如果城市变了，更新城市网格
更新城市网格时，如果省份变了，更新省份网格
更新省份网格时，如果国家变了，更新国家网格
这样，我们按我们的分级octaves来进行update更新
onCenterChanged() {
for (let i = 0; i < HexConfig.octaves; i++) {
if (!this.checkCellChange(i)) {
break;
}
}
}
在加上一个简单的方向控制ui来控制主角移动，这些代码比较基础，就略过了。
这时，我们已经可以愉快地在我们的程序世界里逛街了。
不过在完成这一步之后，我还实现了一个比较重要的优化功能
共享节点
虽然我们使用lod，但是由于每个六边形就有3个节点存在，地图上的网格数量相当多。导致我们在初始化的时候卡了比较多的时间。这时，我想起了论坛上有一篇关于共享节点的帖子：
https://forum.cocos.org/t/topic/144350
个人概括理解：共享节点就是不创建实际的节点，而是创建了1个节点加上n-1个自己定义的对象，这些对象里具备了渲染时的所有差异信息。
用这个方式，我们能创建大量节点时的时间消耗。不过那篇文章是基于2.x的，跟我们3.x的模型的共享不能说是毫不搭边，只能说是毛儿关系没有。
于是，我花时间啃了三天三夜的源码，终于整出了一个大致的3.x模型的共享节点方案出来。
代码就不发了，没啥特别的，并且我也没有好好封装，丑陋地一批。
大致原理就是，ccc的meshrender会在赋值了mesh后自动创建一个model。这个model就是渲染时的目标对象。
model有个node和transform变量都指向当前的节点，在渲染时会用到node的矩阵信息。
做了一个实验场景，构造一万个节点和使用共享节点时，编辑器中的耗时减少及其明显：
pc网页上也有一定提升：
尚未进行的构想
由于篇幅和时间的限制，本文到此为止。但是关于程序化生成地形，其实还有许多许多的东西可以探究。最后，我想将一些我没有时间和精力去继续探究，但是有了一些思路和线索的东西罗列一下，以后有时间优化，也欢迎大佬们去尝试：
使用高度+湿度定义区域类型
详情可以参考这篇文章：
https://indienova.com/indie-game-development/polygonal-map-generation-for-games-2/
根据主角视角方向，减少至少一半的网格
这个其实挺好做的，只是我现在实在没时间，倒腾这篇文章已经肝了两三个星期了。
程序化天空
这是个大课题，做得好的话可以整出极其梦幻的效果，大家可以看看shadertoy上各种天体、星空的效果，如果把这些整到一个程序化世界的天空中，成品应该是会很震撼的。
地图生物、物品
按噪声图的计算方式，去给当前点获得一个随机值，然后按这个随机值去确定当前点有什么生物或者物品即可。技术上没有什么难度，并且是一个在实际游戏中很有使用性的方向。
沧海桑田
thebookofshaders中提到了用fbm来扭曲fbm，构造出一种梦境版的扭动雾气效果。根据类似的原理，其实我们可以给地形加上一个时间参数，让地形随着时间慢慢变化。一个会变化的无限世界！
更好的噪声图
啃了两天iq大佬的文章，其实早就想好好看看了，只是一直没有时间（绝对不是害怕读英文）。目前有了一点点小收获，但是还没有实际产出，希望有一天能整出和大佬一个级别的地形表现：
风格化
我做的这个例子里的地形的渲染是按写实的方向去的，但是由于技术力有限，并没有多少真实感。其实很多时候，程序化生成的地形，也可以避开那些难点，不用一味朝着物理写实的方向，反而能做出更好看的效果，这是我查资料的过程中看到的一个程序化地形的图：
最后
过几天整理一下，打算把demo放到cocos store上，希望有兴趣的同学支持一下。毕竟是花了大量心血的东西，不打算免费放出，不过也不会标很高的价格。
