Beating the Wikipedia Game
Answering the questions no-one was asking
Computers aren’t very good at blending in.
This issue crops up all the time - creating creatures in video games which move organically, creating a voice assistant (Siri, Alexa, etc…) which speaks with a natural-sounding cadence, or generating realistic clouds in the sky and rocks on the ground in an animated movie.
Alas, all of these problems are quite hard (and the focus of ongoing research) so we’ll stick to something simpler.
A stream of unpredictable data is called noise. Static on a TV is noise in the truest sense of the word because every single waveform and pixel is completely random.
However, you could equally call the path of a drunk person trying to walk home ‘noise’ - they’ll walk in vaguely the right direction, but there’s no chance of guessing where any particular step will take them…
This second type of noise is much more interesting. By restricting the randomness, we can create interesting curves and shapes that are unpredictable but controllable.
In 1983, Ken Perlin created a new type of noise called ‘Perlin noise’. Just like a drunk person stumbling home, Perlin noise is random at every point, but there is an overall shape and cohesiveness to the random values.
I’ll admit, it does look a bit bizarre:
There are a few obvious properties to Perlin noise. The areas with ‘extreme’ values (i.e. very light or very dark patches) never last for long, and the grey sections fill the gaps in between. Importantly, these changes in colour always happen gradually, shifting from light to dark bit by bit.
Of course, there are also faults! If you reload the picture a few times, you might start to notice some odd blockiness and straight lines… But, as we’ll see, these faults can be covered up.
The success of Perlin noise didn’t just come from the noise it produced, but also from how fast it produced it. These little faults were a small price to pay for a fast algorithm, especially back in 1983 when computation was so slow and expensive.
Our eventual goal is to create noise which seems messy enough to seem natural. Perlin noise gets us close, but it ebbs and flows so consistently from value to value that it seems artificial.
Why is this? The real world isn’t consistent! It is sometimes smooth, sometimes jagged, and sometimes completely flat. To recreate this, we will add octaves to the noise.
The 0th octave is the original noise, like what we saw above. The 1st octave is identical, but shrunk to be half the height (i.e. amplitude) and changing twice as fast (i.e. frequency). Each sucessive octave does the same, so the 4th octave is only 1/16th the height and changing 16 times faster than the original noise.
These octaves are all ‘added together’ to create noise that can both change huge amounts very slowly, but also change in tiny fractions frequently.
You can see what different combinations look like here:
Simple noise like this is already useful. For instance, you can begin to replicate hand-drawn sketches by adding noise to each line:
And what makes Perlin noise so exciting is that it works just as well in 2D!
Perlin noise is a powerful tool once we start modifying octaves and many of its other parameters. With minimal effort, we can start creating new textures and designs.
We may have a grid of noise, but how are we actually visualising it? Behind the scenes, the Perlin noise algorithm produces a value between 0 and 1 for every pixel in the image. It’s then up to us to define how that value should be turned into a colour, like a ‘colour palette’ of sorts. For instance, up until now we’ve been turning 0s into black, 1s into white, and blending everything in between. But now, we’re going to try convert our noise into a set of islands. Here’s our new colour palette:
And so by simply swapping one colour palette out for another, we can create this:
The colour palette can also interact with space and time in complex ways. For instance, we can adjust the colour palette for pixels further away from the centre of the map so that more and more noise is converted into water closer to the edges.
With some slight changes to the terrain generation colour palettes, we can so much more.
Of course, none of these demos look exactly like what they’re trying to imitate… but perhaps it’s a little alarming that they’re already pretty close. This is especially useful in films and video games where you only have a split second to judge the realism of gravel on the ground or the shape of the shoreline.
And there is something beautiful about this – the ‘best’ noise is not necessarily the noise which mimics life most accurately; instead, it is the algorithm which runs fastest and gets the job done. Frankly, it’s a computer scientist’s dream…