Map Generator - Perlin Noise

1-D and 2-D Perlin Noise, used to generate random yet smooth terrain for a map generator.

1-D Perlin Noise

Fundamentally, the goal of Perlin Noise is to turn random input into a smooth (random) output.

Consider a sequence of real values between 0 and below 1. Let $Y=y_0,...,y_n$ be this random sequence and $X=0,...,n$.

Applying piecewise linear interpolation lets us look up any value within the discrete interval between two values:

$$f_l(x)=\mathrm{lerp}(y_i,y_i+1,\alpha )=(1-\alpha )\ast y_i+\alpha \ast y_i+1$$

(where $i$ is the integer part of $x$, and $\alpha$ is the fractional part of $x$)

At this point we can already see the shape taking form, but it isn't very smooth yet, so we replace $\alpha$ with a $cos$ function.

$$ft=\frac{1-\cos (\alpha \pi )}{2}$$

$$f_c(x)=\mathrm{lerp}(y_i,y_i+1,ft)=(1-ft)\ast y_i+ft\ast y_i+1$$

We can extend the noise function beyond the interval $n$ with:

$$\mathrm{noise}(t)=f(t\mathrm{mod}n)$$

2-D Perlin Noise

We have an $n\times n$ unit grid. For each unit $[i,j]$, we generate a random point $z[i,j]=(x,y)$.

From this we derive the corner points $(x_0,y_0)$, $(x_1,y_0)$, $(x_0,y_1)$, $(x_1,y_1)$, where:

• $x_0$ is the integer part of $x$
• $x_1$ is $(x_0+1)\mathrm{mod}n$
• $y_0$ is the integer part of $y$
• $y_1$ is $(y_0+1)\mathrm{mod}n$

Given a continuous function $f(x)$, its derivative $\frac{df}{dx}$ gives the slope of the tangent line at the point $(x,f(x))$.

Instead of thinking of $f(x,y)$ as a two-parameter function, we can picture the value $(x,y,f(x,y))$ as the height of a point in 2D space. If $f$ is smooth, every point on that terrain can be related to a tangent plane.

The "slope" of the tangent plane passing through such a point is determined by the partial derivatives $\frac{\partial f}{\partial x}$ and $\frac{\partial f}{\partial y}$.

The vector $\left(\frac{\partial f}{\partial x},\frac{\partial f}{\partial y}\right)$ is the vector, on that plane, pointing in the direction of steepest ascent of $f$. This vector changes at every point, depending on $f$. It's called the gradient of $f$, denoted $\nabla f$.

$g[0,0]$, $g[0,1]$, $g[1,0]$, $g[1,1]$ are the random gradient vectors at each corner.

For each $(x,y)$, we find the vectors from the corners to that point $(x,y)$:

$v[0,0]$, $v[0,1]$, $v[1,0]$, $v[1,1]$

References

• CMSC425 - Lecture 12, 13