C/C 编程笔记：游戏开发中的噪声算法详解，游戏编程常用技术（噪声）

噪声

噪声是游戏编程的常见技术，广泛应用于地形生成，图形学等多方面。

那么为什么要引入噪声这个概念呢？在程序中，我们经常使用直接使用最简单的rand()生成随机值，但它的问题在于生成的随机值太“随机”了，得到的值往往总是参差不齐，如下图使用随机值作为像素点的黑白程度：

而使用噪声，我们得到的值看起来虽然随机但平缓，这种图也看起来更自然和舒服：

而根据wiki，现在噪声类型已经有很多种类：

本文主要说明Value噪声，Perlin噪声，Simplex噪声这三种常见的噪声。

随机性

随机性是噪声的基础，不必多说。

哈希性

在《Minecraft》里，由于世界是无限大的，它以“Chunk”区块（16×16×256格子）为单位，只加载玩家附近的区块。也就是说，当玩家在移动时，它会卸载远离的区块，然后加载靠近的区块。

一个问题是，当玩家离开一个区块时，进入第二个区块，然后又回到第一个区块，此时玩家期望看到的第一个区块和之前看到的保持一致。例如，输入1时得到0.3，输入2时得到0.7，当再次输入1时预期得到0.3。

因此噪声的一个重要性质是哈希性（可哈希的）。

尽管使用输入值作为srand()的参数来设置rand()的种子，从而达到哈希效果也是可行的。

然而最好花点时间写一个自己的哈希函数，使其简易使用而且也不破坏程序其他地方使用rand()的效果。

hash11的11代表输入一维坐标，输出一维值。类似的hash22代表输入二维坐标，输出二维值。
若要了解更多随机性哈希函数实现，可参考下面两个shadertoy的代码：
https://www.shadertoy.com/view/4sc3z2
https://www.shadertoy.com/view/4djSRW

平滑性(连续性)

对一个随机生成地形来说，如果简单的使用随机和哈希组合，

那么容易得到下图（以一维地图举例，x轴为位置，y轴为地形高度）：

容易看出的问题是，由于随机的杂乱无章，地形非常的参差不齐，这可不是一个自然的地形。

我们期望得到的地形不仅随机还应该是平滑的，这样才显得自然，如下图：

Value噪声

Value噪声是最简单的一种噪声，其主要思路是定义若干个顶点且每个顶点含有一个随机值，这些顶点会根据自己的随机值对周围坐标产生影响，越靠近顶点则越容易受该顶点影响。当需要求某个坐标的输出值时，需要将该坐标附近的各个顶点所造成的影响值进行叠加，从而得到一个总值并输出之。

原理

1.首先定义一个晶格结构，每个晶格的顶点有一个伪随机值（Value）。对于二维的Value噪声来说，晶格结构就是一个平面网格（通常是正方形），三维的就是一个立体网格（通常是正方体）。

2.输入一个点（二维的话就是二维坐标，三维就是三维坐标，n维的就是n个坐标），我们找到和它相邻的那些晶格顶点（二维下有4个，三维下有8个，n维下有2n个），得到这些顶点的伪随机值。

3.使用缓和曲线（ease curves）来计算这些伪随机值的权重和。在原始的Perlin噪声实现所使用的缓和曲线是s(t)=3t^2−2t^3，在2002年的论文中，Perlin又改进为s(t)=6t^5−15t^4 10t^3。

若直接使用线性插值，其一阶导在晶格顶点处（即t = 0或t = 1）不为0，会造成明显的不连续性。s(t)=3t^2−2t^3
在一阶导满足连续性，s(t)=6t^5−15t^4 10t^3在二阶导上仍然满足连续性。
所以实际上两种缓和曲线都是可用的，如果需要压榨开销，则使用s(t)=3t^2−2t^3。
对于预计算，例如程序化生成凹凸纹理（置换纹理），使用s(t)=6t5−15t^4 10t^3的效果更好。

实现(二维）

柏林噪声

谈起噪声，最著名的且最常用的莫过于Perlin噪声，Perlin噪声的名字来源于它的创始人Ken Perlin。

在理解了上面Value噪声后，我们再来看看柏林噪声的主要想法：

定义若干个顶点且每个顶点含有一个随机梯度向量，这些顶点会根据自己的梯度向量对周围坐标产生势能影响，沿着顶点的梯度方向越上升则势能越高。当需要求某个坐标的输出值时，需要将该坐标附近的各个顶点所造成的势能进行叠加，从而得到一个总势能并输出之。

我们给顶点赋予一个随机性的哈希函数，输入一个坐标可以得到一个随机向量，满足上述随机性和哈希性。

此外，由于势能是沿着梯度方向渐变的，所以很容易得到平滑性。

原理

和Value噪声一样，它也是一种基于晶格的噪声，也需要三个步骤：

1.首先定义一个晶格结构，每个晶格的顶点有一个随机的梯度向量。对于二维的Perlin噪声来说，晶格结构就是一个平面网格（通常是正方形），三维的就是一个立体网格（通常是正方体）。

2.输入一个点坐标（二维的话就是二维坐标，三维就是三维坐标，n维的就是n维坐标），我们找到和它相邻的那些晶格顶点（二维下有4个，三维下有8个，n维下有2n个），计算该点到各个晶格顶点的距离向量，再分别与顶点上的梯度向量做点乘，得到2n个点乘结果。

//点乘floatdot(Vector2 v1,Vector2 v2){returnv1.x*v2.x v1.y*v2.y;}

3.使用缓和曲线来计算它们的权重和（同样的，可以是s(t)=3t2−2t3

，也可以是s(t)=6t5−15t4 10t3

）

下图通过颜色差异显示了由2D柏林噪声生成的各像素点的值：

实现(二维）

另一个更快的实现方式，它与标准实现方式的区别是：晶体顶点是从若干个梯度向量里随机选择一个向量而不是产生一个随机向量，这样做可以预先计算好求梯度值时各项的系数。因此我们只需这样重写一下grad函数：

这里示例提供了4个可选的随机向量，实际上这个数量是偏少的，如果想要更加多样的效果，建议在实现时多提供些可选的随机向量。

Simplex噪声

Simplex噪声也是一种基于晶格的梯度噪声，它和Perlin噪声在实现上唯一不同的地方在于，它的晶格并不是方形（在2D下是正方形，在3D下是立方体，在更高纬度上我们称它们为超立方体，hypercube），而是单形（simplex）。

通俗解释单形的话，可以认为是在N维空间里，选出一个最简单最紧凑的多边形，让它可以平铺整个N维空间。我们可以很容易地想到一维空间下的单形是等长的线段，把这些线段收尾相连即可铺满整个一维空间。在二维空间下，单形是三角形，我们可以把等腰三角形连接起来铺满整个平面。三维空间下的单形就是四面体。更高维空间的单形也是存在的。

总结起来，在n维空间下，超立方体的顶点数目是2n，而单形的顶点数目是n 1，这使得我们在计算梯度噪声时可以大大减少需要计算的顶点权重数目。

一个潜在的问题是如何找到输入点所在的单形。

在计算Perlin噪声时，判断输入点所在的正方形是非常容易的，我们只需要对输入点下取整即可找到。

对于单形来说，我们需要对单形进行坐标偏斜（skewing），把平铺空间的单形变成一个新的网格结构，这个网格结构是由超立方体组成的，而每个超立方体又由一定数量的单形构成：

我们之前讲到的单形网格如上图中的红色网格所示，它们有一些等边三角形组成（注意到这些等边三角形是沿空间对角线排列的）。经过坐标倾斜后，它们变成了后面的黑色网格，这些网格由正方形组成，每个正方形是由之前两个等边三角形变形而来的三角形组成。这个把N维空间下的单形网格变形成新网格的公式如下：

x'=x (x y ...)⋅K1

y'=y (x y ...)⋅K1

其中，K1=n 1√−1n

在二维空间下，取n为2即可。这样变换之后，我们就可以按照之前方法判断该点所在的超立方体，在二维下即为正方形。

原理

1.坐标偏斜：把输入点坐标进行坐标偏斜。

x'=x (x y ...)⋅K1

y'=y (x y ...)⋅K1

其中，K1=n 1√−1n

2.找到顶点：对偏斜后坐标下取整得到输入点所在的超立方体xi=floor(x')

,yi=floor(y'),...我们还可以得到小数部分xf=x'−xi,yf=y'−yi,...

我们把之前得到的(xf,yf,...)中的数值按降序排序，来决定输入点位于变形后的哪个单形内。这个单形的顶点是由按序排列的(0, 0, …, 0)到(1, 1, …, 1)中的n 1个顶点组成，共有n!种可能性。

我们可以按下面的过程来得到这n 1个顶点：从零坐标(0, 0, …, 0)开始，找到当前最大的分量，在该分量位置加1，直至添加了所有分量。这一步的算法复杂度即为排序复杂度O(n2)。

例如，对于二维空间来说，如果xf,yf满足xf>yf，那么对应的3个单形坐标为：首先找到(0,0)，由于x分量比较大，因此下一个坐标是(1, 0)，接下来是y分量，坐标为(1,1)；对于三维空间来说，如果xf,yf,zf满足xf>zf>yf，那么对应的4个单形坐标位：首先从(0, 0,0)开始，接下来在x分量上加1得(1, 0, 0)，再在z分量上加1得(1, 0, 1)，最后在y分量上加1得(1, 1, 1)。

3.梯度选取：我们在偏斜后的超立方体网格上获取该单形的各个顶点的伪随机梯度向量。

4.变换回单形网格里的顶点：我们首先需要把单形顶点变回到之前由单形组成的单形网格。这一步需要使用第一步公式的逆函数来求得：

x=x' (x' y' ...)⋅K2

y=y' (x' y' ...)⋅K2

其中，K2=1n 1√−1n

5.贡献度取和：我们由此可以得到输入点到这些单形顶点的位移向量。这些向量有两个用途，一个是为了和顶点梯度向量点乘，另一个是为了得到之前提到的距离值dist，来据此求得每个顶点对结果的贡献度：

(r2−|dist|2)4×dot(dist,grad)

实现（二维）

r^2取0.5的原因是因为要求经过第一步坐标偏斜后得到的网格宽度为1，因此我们可以倒推出在变形前单形网格中每个单形边的边长为23−−√，这样一来单形每个顶点到对面边的距离（即高）的长度为2√2，它的平方即为0.5。很奇妙的是，不仅是二维，在其他维度下，每个单形顶点到对面边/面的距离都是0.5。

虽然理解上Simplex噪声相比于Perlin噪声更难理解，但由于它的效果更好、速度更优，因此很多情况下会替代Perlin噪声。

而且高维的噪声并不少见，例如对于常见的二维噪声纹理，我们可以额外引入时间分量，变成一个2D纹理动画（三维噪声），用于火焰纹理动画等..

对于常见的三维噪声纹理，引入额外的时间分量，就可以变成一个3D纹理动画（四维噪声），用于3D云雾动画等..

当我们需要一个可循环无缝衔接的动画时（见下文可平埔的噪声），那噪声又要提高一个维度。

可平铺的噪声

可平铺的噪声就是指那些可以tiling的、seamless的噪声，因为很多时候我们想要让噪声纹理可以无缝连接，例如在生成地形时。按照我们之前提到的方法直接产生噪声，得到的噪声纹理其实是不可以平铺的，你可以看生成纹理的左右、上下其实是不一样的。那么，怎么生成可平铺的噪声纹理呢？

翻转纹理

一种低开销的trick是，首先对一张噪声纹理分别进行X轴翻转，Y轴翻转，XY轴同时翻转，从而得到新的三张噪声纹理，将它们拼接成一张大纹理，此时该大纹理为可tiling无缝的。

一个基础噪声纹理：

一个基础噪声纹理和另外三个生成的纹理拼接城的大纹理：

缺点是这样的纹理看起来可能会过于对称，影响美观。

对高维度的圆采样

一种方法是在2n维上计算n维可平铺噪声。我们以二维噪声为例，如果我们想要得到二维的无缝Perlin噪声，就需要用四维噪声算法来产生。

这种方法是思想是，由于我们想要每个维度都是无缝的，也就是当该维度的值从0变成1的过程中，0和1之间比较是平滑过渡的，这让我们想起了“圆”，绕圆一周就是对该维度的采样过程，这样就可以保证无缝了。

因此，对于二维噪声中的x轴，我们会在四维空间下的xz平面上的一个圆上进行采样，而二维噪声的y轴，则会在四维空间下的yw平面上的一个圆上进行采样。这个转化过程很简单，我们只需要使用三角函数sin和cos即可把二维采样坐标转化到单位圆上。同样，三维空间的也是类似的，我们会在六维空间下计算。这种方法不仅适用于Perlin噪声，像Worley噪声这种也同样是适合的。

Unity Wiki里二维可平铺的Simplex噪声的实现：