#地图生成器 demo

#白噪声的问题

#柏林噪声的原理

#柏林噪声的 2D 推广

Indexes

这是一篇去年 12 月写完的文章，不过一直感觉对二维推广里的梯度的数学理解不够透彻就忘发了，这两天想查点资料又找到了这篇发现还没发 ... 算了还是先发吧

# 地图生成器 demo ↵

写这篇的原因是有看一些地图生成算法，里面是利用柏林噪声来实现的，比如将其输出看成是海拔，然后将不同海拔划分为不同地形，据此可以画出下面的地图:

意西泽恩大陆

山峰

森林

陆地

湖泊

# 白噪声的问题 ↵

下面左图是一张典型的白噪声渲染效果，可以看到其相当离散，没有一点规律

但是在实际开发中有时需要有一定规律的随机噪声，如 Minecraft 的地图生成，这类场景就不能使用白噪声了，需要单独一种更平滑的噪声了，一般来说行业内通常使用柏林噪声来实现这种带有一定平滑规律的噪声来生成地形，上面右图就是柏林噪声算法生成的效果图，可以感受下跟白噪声的不同。

# 柏林噪声的原理 ↵

柏林噪声 (Perlin Noise)

是由

肯·柏林 (Ken Perlin)

发明的自然噪声生成算法，算法的名字也是作者自己的名字，这个算法很有意思，此处以 x 轴上的点作为参数计算出一维柏林噪声作为 y 轴绘制一个二维坐标系来介绍柏林噪声的原理，具体即下图所示这般，其中的 P0、P、P1 三个点的柏林噪声分别是 r0、N、r1：

1.
P 向下取整得到 P0、向上取整得到 P1。P0 到 P1的距离为
单位距离
, 通常取 1
2.
然后将 P0 和 P1 分别当作种子去生成两个伪随机数, 将这两个伪随机数记为
r0
和
r1
3.
随着 P 点移动到 P1 点，对应的 N 即其柏林噪声会均匀从 r0 过渡到 r1
4.
根据上一步的说明, N 的位置可以这样求得：P 点在
线段 P0P1
上的位置百分比是 40%, 从 r0 到 r1 之间划一条线段，在其 40% 的位置就是 P 点对应的柏林噪声了，这个值为
r0 + 40% * (r1 - r0)
, 这种处理方式称为线性插值

关于上面提到的伪随机，柏林它使用了一个哈希数组来实现的：

00// hashes.tsx
01// 这个数组里随机放置了从 0 到 255 共计 256 个整数
02const hashes = [
03  151,160,137,91,90,15,131,13,201,95,96,53,194,233,7,
04  225,140,36,103,30,69,142,8,99,37,240,21,10,23,190,6,
05  148,247,120,234,75,0,26,197,62,94,252,219,203,117,
06  35,11,32,57,177,33,88,237,149,56,87,174,20,125,136,
07  171,168,68,175,74,165,71,134,139,48,27,166,77,146,
08  158,231,83,111,229,122,60,211,133,230,220,105,92,41,
09  55,46,245,40,244,102,143,54,65,25,63,161,1,216,80,
10  73,209,76,132,187,208,89,18,169,200,196,135,130,116,
11  188,159,86,164,100,109,198,173,186,3,64,52,217,226,
12  250,124,123,5,202,38,147,118,126,255,82,85,212,207,
13  206,59,227,47,16,58,17,182,189,28,42,223,183,170,
14  213,119,248,152,2,44,154,163,70,221,153,101,155,167,
15  43,172,9,129,22,39,253,19,98,108,110,79,113,224,232,
16  178,185,112,104,218,246,97,228,251,34,242,193,238,
17  210,144,12,191,179,162,241,81,51,145,235,249,14,239,
18  107,49,192,214,31,181,199,106,157,184,84,204,176,
19  115,121,50,45,127,4,150,254,138,236,205,93,222,114,
20  67,29,24,72,243,141,128,195,78,66,215,61,156,180
21];
22
23/**
24 * 将任意整数n塞到hashes[n % 256]中来得到一个0-255的随机数
25 */
26export function rand(n: number) {
27  return hashes[n % hashes.length];
28}

总结一下前面的结论：首先取整得到两个点并求出两个随机数，最后根据 P 的相对位置对随机数做线性插值就得到柏林噪声了，下面实现了一维柏林噪声第一版

perlin1d_v1

00// perlin1d_v1.tsx
01import { rand } from './hashes';
02
03// 第一版
04export function perlin1d_v1(x: number) {
05  // 向下/向上取整
06  const x0 = Math.floor(x);
07  const x1 = x0 + 1;
08
09  // 通过这种方式来实现伪随机
10  const r0 = rand(x0);
11  const r1 = rand(x1);
12
13  // 拿到相对位置
14  const dx = x - x0;
15
16  // 拿到相对位置占的百分比,
17  // 因为取整是 1 因此除 1 就行, 可省略提升性能
18  const rate = dx / 1;
19
20  // 最后拿到 rate 给 r0 r1 做线性插值
21  const noise = r0 + rate * (r1 - r0);
22
23  // r0 和 r1 是 0-255 的数, 我们需要返回 0-1 的范围
24  return noise / 255;
25}

注意, perlin1d_v1(x: number) 中 x 一定是要一个连续的实数算法才有意义，如果 x 都是整数那么它本质上跟从

hashes

取随机数一样没有区别, 也就是说如果想拿 canvas 绘制一维柏林噪声曲线那么需要注意将坐标除以

单位数值 n

来将整数坐标系变成带小数的浮点数。

白噪声

柏林噪声 n=1
(注意: 跟左边白噪声一模一样了)

柏林噪声 n=8

柏林噪声 n=32

当 n 变大时，我们可以看到折线转角变少了，而且线也没那么

离散

了，但是折线转角处依然非常陡峭，不够平滑规整，是哪里有问题么？此时需要再次审视

线性插值

，如下图所示，随着 x 增加，N 也会从 r0 均匀变大到 r1, 对应的柏林噪声输出也会

均匀线性变大

当 P 跨过 P1 的时候，对应的线性插值由于端点变化就会造成突变，从而最终绘制的时候都是不光滑的折角了，即折线连接处不连续

若是我们能让这个

折线

变成曲线，那么就能实现噪声的平滑处理了 —— 如下红线所示这样得到的

就形成了一条光滑的曲线，不再是折角了。

明白了关键还是线性插值后，就知道怎么改了，可以简单按

f (x) = x^{2}

作为平滑函数来处理线性插值，得到第 2 版实现

perlin1d_v2

以及绘制效果:

00// perlin1d_v2.tsx
01import { rand } from './hashes';
02
03// 第二版
04export function perlin1d_v2(x: number) {
05  // 向下/向上取整
06  const x0 = Math.floor(x);
07  const x1 = x0 + 1;
08
09  // 通过这种方式来实现伪随机
10  const r0 = rand(x0);
11  const r1 = rand(x1);
12
13  // 拿到相对位置
14  const dx = x - x0;
15
16  // 拿到相对位置占的百分比,
17  // 因为取整是 1 因此除 1 就行, 可省略提升性能
18  let rate = (dx / 1);
19
20  // 对 rate 做平滑处理
21  rate = blending(rate);
22  
23  // 最后拿到 rate 给 r0 r1 做线性插值
24  const noise = r0 + rate * (r1 - r0);
25  
26  // r0 和 r1 是 0-255 的数, 我们需要返回 0-1 的范围
27  return noise / 255;
28}
29
30// 由于 rate 的范围是0到1
31// 这样乘会让他变得更小，使得绘制更平滑不突变
32function blending(rate: number) {
33  return rate * rate;
34}

f(x)=x, n=8

f(x)=x, n=32

f(x)=x^2, n=8

f(x)=x^2, n=32

f(x)=6x^5-15x^4+10x^3, n=8

f(x)=6x^5-15x^4+10x^3, n=32

效果越来越好，值得注意的是

6x^5-15x^4+10x^3

是柏林提出的，这个效果非常好，这个函数的曲线如下图所示，可以看到类似贝塞尔曲线，它的一阶导数和二阶导数在 x=0 和 x=1 的地方都为 0，这使得其看起来非常光滑（一般来说函数越高次就越光滑）

至此，我们已经算是掌握了柏林噪声的基本原理和过程了，关键是分割整数区间然后取端点对应的随机数，再根据

比例

来做线性插值得到噪声数值，而具体的插值函数是任意的，建议使用柏林提出来的那个

f(x)=6x^5-15x^4+10x^3

, 效果非常好。

# 柏林噪声的 2D 推广 ↵

前面讨论了一维的柏林噪声处理，这里将其从一维数轴推广到二维平面上

取整的推广：晶格

对于某个点

O(x, y)

的两个坐标分量做向上/向下取整，可以得到一个正方形格子，这个格子称为

晶格 (grid)

, 如下图所示, O 点在 P1,P2,P3,P4 所围成的晶格之中：

后续的计算都围绕着这个晶格进行。

伪随机数的推广：伪随机向量 (梯度)

在前面一维场景中，我们需要将数轴上的点通过

hashes[n % 256]

的方式来生成一个随机数，类比到二维场景，则需要根据 x 和 y 来生成一个伪随机向量，下面的

randVecs

实现了这个功能：

00// hashes-vec.tsx
01import { rand } from './hashes';
02
03/** 表示一个向量 */
04export interface Vec {
05  x: number;
06  y: number;
07}
08
09/** 一个向量组 */
10const vecs: Vec[] = [
11  { x:  1, y:  1 },
12  { x: -1, y:  1 },
13  { x: -1, y: -1 },
14  { x:  1, y: -1 },
15];
16
17export function randVecs(vec: Vec) {
18  // 将 x 和 y 坐标输入到 rand 生成一个合成的随机数
19  const r = rand(rand(vec.x) + vec.y);
20  // 因为 r 是随机的，因此可以这样随机从 vecs 中选择一个向量
21  return vecs[r % vecs.length];
22}

获取你会注意到其中的

向量组 vecs

, 它内部其实可以放其他的变量来改变噪声效果，这里选的这四个是为了后面方便处理（后面会提到）

因此在二维平面的柏林噪声处理中，晶格的每个顶点都会伪随机到一个向量上，因此会生成四条向量（蓝色箭头）：

晶格顶点的噪声标量

在一维场景的讨论中我们知道线性插值需要知道两个端点和「比例」才能插值，根据这个规则我们可以实现线性插值的函数：

00// lerp.tsx
01// 线性插值
02export function lerp(t: number, v1: number, v2: number) {
03  return v1 + t * (v2 - v1);
04}

O 点在晶格内的相对位置可以由其到其中一个晶格顶点的向量表示，即下图中深绿色的向量，其他三个都可以由这个深绿色向量唯一确定：

可是，线性插值要求的是标量，向量不能作为

lerp

的参数进行调用，要怎么办呢？—— 既要考虑到相对位置的模的大小对标量的影响，又要考虑随机向量的影响，因此将晶格顶点的伪随机向量投影到

相对位置

上相乘得到一个标量作为表征这个晶格顶点的噪声标量：

实际上，上面这样投影计算标量的方式其实就是向量的点乘运算：

00// vec-dot.tsx
01import { Vec } from './hashes-vec';
02
03export function vecDot(v1: Vec, v2: Vec): number {
04  return v1.x * v2.x + v1.y * v2.y;
05}

到此为止，我们可以求出四个晶格顶点的噪声标量，最后一步就是将这四个噪声标量进行线性插值了。

线性插值

1.
拿 P1 P2 的噪声标量做一次插值得到 V1，权重取 O 点在水平方向上的相对位置
2.
拿 P3 P4 的噪声标量做一次插值得到 V2，权重取 O 点在水平方向上的相对位置
3.
将 V1 V2 再做一次插值，权重取 O 点在垂直方向上的相对位置，最后的插值结果即为这个点的二维柏林噪声值了

归一化处理

归一化指的是将输出限定在 [-1,1] 或者 [0,1] 的区间内，方便外部调用使用，而上述的二维柏林噪声的取值范围由四个晶格代表的噪声标量来确定，那么它们插值的结果能落在 0 到 1 吗？

我们特意选择的四个向量在归一化处理这里就发挥作用了，用符号

A

表示:

A = {(1, 1) (- 1, 1) (- 1, - 1) (1, - 1)}

由于这四个向量不是

+ 1

就是

- 1

, 因此对于任意向量 (x, y) 计算点乘有:

A \cdot (x, y) = \pm x \pm y

我们特意选择的四个向量在归一化处理这里就发挥作用了，上图中有几个已知的等价关系

d x d y P 1 O P 2 O = x - x 0 = y - y 0 = (x - x 0, y - y 0) = (d x, d y) = (x - (x 0 + 1), y 0) = (d x - 1, d y)

由此计算点积得到 P1 和 P2 对应的噪声标量 V1 和 V2

V 1 V 2 = A \cdot (d x, d y) = A \cdot (d x - 1, d y)

展开可以得到:

V 1 V 2 = \pm d x \pm d y = \pm (d x - 1) \pm d y

最后要将 V1 和 V2 通过下面的 lerp 做一次线性插值得到最终结果:

l er p (t, a, b) 最终结果 = a + t * (b - a) = l er p (t, V 1, V 2)

那么最终结果的取值范围是多少呢？显然，取值范围就是 lerp 的

[a, b]

, 即

[V1, V2]

完整实现

00// perlin2d_v1.tsx
01import { lerp } from './lerp';
02import { vecDot } from './vec-dot';
03import { Vec, randVecs } from './hashes-vec';
04
05// 2d 第一版
06export function perlin2d_v1(x: number, y: number) {
07  // 对 x y 取整拿到晶格顶点的坐标
08  const x0 = Math.floor(x);
09  const x1 = x0 + 1;
10  const y0 = Math.floor(y);
11  const y1 = y0 + 1;
12
13  // 四个晶格顶点的坐标
14  const P1: Vec = { x: x0, y: y0 }
15  const P2: Vec = { x: x1, y: y0 }
16  const P3: Vec = { x: x0, y: y1 }
17  const P4: Vec = { x: x1, y: y1 }
18
19  // 四个晶格顶点对应的伪随机向量
20  const vec_P1 = randVecs(P1);
21  const vec_P2 = randVecs(P2);
22  const vec_P3 = randVecs(P3);
23  const vec_P4 = randVecs(P4);
24
25  // 计算四个晶格的随机向量和相对位置的点积
26  const value_P1 = vecDot(vec_P1, { x: x - x0, y: y - y0 });
27  const value_P2 = vecDot(vec_P2, { x: x - x1, y: y - y0 });
28  const value_P3 = vecDot(vec_P3, { x: x - x0, y: y - y1 });
29  const value_P4 = vecDot(vec_P4, { x: x - x1, y: y - y1 });
30
31  // O 点在 x, y 方向上的相对位置
32  const dx = x - x0;
33  const dy = y - y0;
34  const rateX = blending(dx);
35  const rateY = blending(dy);
36
37  const noise = lerp(
38    rateY,
39    lerp(rateX, value_P1, value_P2),
40    lerp(rateX, value_P3, value_P4)
41  );
42
43  // 最后归一化处理, noise 的范围是 [-1, 1] 这里需要调整为 [0, 1]
44  return (noise + 1) / 2;
45}
46
47// 6t^5 -15t^4 + 10t^3
48function blending(t: number) {
49  return t*(t*(t*(10+t*(-15+6*t))));
50}

效果

拿上面实现的

perlin2d_v1

来画一下：

n = 16

n = 32

n = 64

n = 128

# 参考 ↵

Wiki - Perlin Noise

Minecraft地形生成与柏林噪声 (一) 详解噪声

图形学的数学基础（四十四）：柏林噪声

Perlin Noise: A Procedural Generation Algorithm