Some people will recognize the title of this post as mirrored from Ken Perlin’s talk, which set up the foundations for a new form of procedural generation, bringing it to the mainstream. His research is based off his work on the movie Tron, where CGI was scaled to a feature-length film.

Nowadays, procedural generation through generation of noise has become an
important tool in the creation of games. From the roughness of a rock to the
ripples of waves, the flames of a fire to the snow falling from the sky, noise
is what makes these possible! You didn’t *really* think that all those
animations were hand-made? The complexity and randomness of such animations
make it extremely difficult for a game designer to produce these at a standard
speed.

In my opinion, Ken Perlin was the first to produce results significant enough to be noticed and put into application later on. But enough history, let’s see what all the fuss is about!

The original noise generation algorithm proposed by Ken Perlin combines
interpolation and summation of nearby influences in a discrete grid to induce a
continuous, *homogeneous* noise. Now that’s a mouthful, but the concept is
fairly understandable. Given a point in continuous space (to put it simply, floating
point coordinates), find the bounding box in discretized space defined by its
four corners. Each of these corners has an associated *pseudo-random unit
vector*, which is basically chosen from a hash table filled with random vectors
before the computation took place. The resulting noise for the point is given
by interpolating these vectors by the distance of the corner to the point. I’ll
get back to this process in detail later on, since it seems hard to grasp
without an example.

Using Numpy, generating a matrix of random floating-point numbers is pretty straightforward:

Now we have a matrix whose elements are in the range (-1, 1). We need them to be in the range (0, 1).

Now we need to make sure that every row of the matrix forms a unit vector. To do this, let’s simply divide each component by the norm of the full vector.

The `dot_product`

function simply computes the euclidean dot product of two
2-dimensional vectors.

In order to choose a pseudorandom vector for a position, one must be able to map a discrete grid position to a row index in the gradients matrix. Ken Perlin originally used a shuffled set of integers and a simple modulo to achieve this. Here’s the generating of a such permutation set using Numpy.

One trick used by Ken was to double the permutation set, in order to easily combine the hashed x and y positions to choose a permutation. This is weird at first, but in the end it’s just a clever hack that simply involves adding the position to a hash, looping over the permutations using a modulo.

Once you have the hashing for an arbitrary position and the gradient vectors, the implementation of the noise function is rather straightforward:

- convert the point from world-coordinates to local-coordinates
- compute hashes for each corner around the point
- take the gradient vectors for each hash
- interpolate between the gradients

This last step is the only one that needs a bit of thought, the rest is as follows:

I’ll leave that interpolation bit for exercise, it wouldn’t be any fun otherwise!