Magic Bookof Algorithms DE

Randomness & NoiseRND-02

Perlin Noise

Raw randomness turns into smooth noise, the raw material for landscapes, clouds and textures.

Running time
O(n · o)
Extra memory
O(n)
Value range
0 … 1
Controls
octaves, persistence

01What it is about

Pure randomness looks like television static: every point is completely independent from its neighbours. Nature looks different. Mountains, clouds and waves are random, yet neighbouring places resemble each other.

That is exactly what Perlin noise produces. It smooths random values and then layers several levels of detail on top of each other until coarse shapes and fine structure come together. Ken Perlin developed the method in 1983 for the movie Tron and received an Academy Award for technical achievement for it.

The same random values with 2, 3, 4 and 6 octaves, generated with the code below.

02How it works

The basis is a field of random values. On top of it the algorithm layers several octaves.

One octave samples the random field on a fixed grid, for example only every 32 points. Everything in between is interpolated from the four surrounding grid points. The result is a soft gradient instead of hard jumps.

Several octaves use the same random field with an ever finer grid: first the whole image, then half of it, then a quarter. Each additional octave adds finer detail, but is weighted down by the persistence.

Finally all octaves are added up and divided by the sum of their weights, so the result lands between 0 and 1 again. Few octaves give gentle hills, many octaves give rugged rocks.

03Try it

04Implementation

MagicBook.Algorithms/Randomness/PerlinNoise.csC#
public static class PerlinNoise
{
    // Layers the same random values at several zoom levels ("octaves") on top of each other.
    // seed holds width * height random values in [0, 1); the result has the same size.
    // Works best with square sizes that are a power of two.
    public static float[] Generate(float[] seed, int width, int height, int octaves, float persistence)
    {
        var noise = new float[width * height];

        for (var y = 0; y < height; y++)
        {
            for (var x = 0; x < width; x++)
            {
                var value = 0f;
                var amplitude = 1f;
                var amplitudeSum = 0f;

                for (var octave = 0; octave < octaves; octave++)
                {
                    // Every octave samples the seed on a finer grid: whole image, half, quarter, ...
                    var step = Math.Max(width >> octave, 1);

                    value += Sample(seed, width, height, x, y, step) * amplitude;
                    amplitudeSum += amplitude;

                    // Later octaves add finer detail with less and less weight.
                    amplitude *= persistence;
                }

                // Dividing by the sum of all amplitudes keeps the result inside [0, 1).
                noise[y * width + x] = value / amplitudeSum;
            }
        }

        return noise;
    }

    // Takes the four grid corners around (x, y) and blends between them.
    private static float Sample(float[] seed, int width, int height, int x, int y, int step)
    {
        // Round down to the grid of this octave; the modulo lets the noise wrap around seamlessly.
        var left = x / step * step;
        var top = y / step * step;
        var right = (left + step) % width;
        var bottom = (top + step) % height;

        // How far the point lies between the corners, as a value from 0 to 1.
        var blendX = (float)(x - left) / step;
        var blendY = (float)(y - top) / step;

        var topValue = Lerp(seed[top * width + left], seed[top * width + right], blendX);
        var bottomValue = Lerp(seed[bottom * width + left], seed[bottom * width + right], blendX);

        return Lerp(topValue, bottomValue, blendY);
    }

    // Linear interpolation: returns a for t = 0, b for t = 1 and the values in between.
    private static float Lerp(float a, float b, float t) => a + (b - a) * t;
}

05Example: noise as a picture

MagicBook.Console/Examples/PerlinNoiseExample.csC#
const int size = 32;

// Perlin noise does not invent the randomness, it only smooths existing random values.
var random = new Pcg(seed: 2024);
var seed = new float[size * size];
for (var i = 0; i < seed.Length; i++)
    seed[i] = (float)random.NextDouble();

var noise = PerlinNoise.Generate(seed, size, size, octaves: 5, persistence: 0.6f);

// Averaging the octaves pulls all values towards the middle, so the range
// is stretched back to 0 .. 1 to make the structure clearly visible.
var darkest = noise.Min();
var range = noise.Max() - darkest;

// Draw the result as ASCII art: dark values become spaces, bright ones become @.
const string ramp = " .:-=+*#%@";
for (var y = 0; y < size; y++)
{
    for (var x = 0; x < size; x++)
    {
        var brightness = (noise[y * size + x] - darkest) / range;
        var index = Math.Clamp((int)(brightness * ramp.Length), 0, ramp.Length - 1);

        // Each pixel is printed twice because characters are taller than they are wide.
        Console.Write(new string(ramp[index], 2));
    }

    Console.WriteLine();
}
Console output
********++++========------::::..    ..::----::--------==++++++**
++********++++++++====----::::........::------------====++++**++
++++******++++++**++==----::::::::::::::----==------====++****++
**++++++****++****++====--------------------------====++++******
****++++**********++==============--------------====++++++++****
++++++++++********++++======--------------------======++++++++++
++++**++++++****++****++====--::::::----::------================
++++++++************++++====--::..::--::::::----================
++++++******######**++++++==--::..::::::::::----========--======
======++++******##****++++==----::----------============--======
==========++********##**++====------========++======----------==
==========++****####******++++==--==++++++++++++====----------==
========--==****####**####****++==++++******++++++==----------==
----------==++**##**************++++++++**++====------------::--
..::::----==++**************######**++++++++==--::----------::::
....::----====++**********####%%%%##****++==----::::------::::..
  ..::::----==++********####%%@@@@%%##**++==--::..::------::....
....::----====++**********####%%@@%%##**++==----::----------::::
::::::--======++************####%%##****++==----==------------::
::::::--======++**++++++++******##****++============----------::
--------====++++++++++++++++++++****++==--======++==------------
========================++++++++++++====----====++==------------
========--==================++++++======------==++==============
++++====----==----------========----------================++++++
**++==----------::::::----------::::::----==============++++++**
**++++==--------::::----------::::::::--========--========++++++
++++++++====----::----------::::::::::--========--==++====++++++
++++++++====----::--------::::::..::::--======----========++++++
++++====++==----::------::::::::..::::--====--------====++++++++
++++++++++====------------::::....::----==----------====++++++++
********++++====----------::::....::----==--------====++++++==++
********++++======--------::::..  ..::------::------====++++++++

06Example: an island from a height map

MagicBook.Console/Examples/PerlinNoiseTerrainExample.csC#
const int size = 64;

// Every range of height values gets its own meaning. That is the whole trick
// behind a height map: one number per point turns into a landscape.
static char Terrain(float height) => height switch
{
    < 0.20f => '~', // deep water
    < 0.34f => '-', // shallow water
    < 0.40f => '.', // beach
    < 0.54f => ',', // grass
    < 0.66f => '#', // forest
    < 0.70f => '^', // rock
    _ => '*',       // snow
};

var random = new Pcg(seed: 7);
var seed = new float[size * size];
for (var i = 0; i < seed.Length; i++)
    seed[i] = (float)random.NextDouble();

var noise = PerlinNoise.Generate(seed, size, size, octaves: 6, persistence: 0.5f);

// The octaves pull everything towards the middle, so stretch it back out.
var lowest = noise.Min();
var range = noise.Max() - lowest;

// Characters are about twice as tall as they are wide, so every second row
// is enough to get a map that is not stretched.
for (var y = 0; y < size; y += 2)
{
    for (var x = 0; x < size; x++)
    {
        var height = (noise[y * size + x] - lowest) / range;

        // An island instead of an endless landscape: the further a point is from
        // the middle, the more height is taken away, so the border sinks into the sea.
        var offsetX = (x - size / 2f) / (size / 2f);
        var offsetY = (y - size / 2f) / (size / 2f);

        height -= 0.5f * (offsetX * offsetX + offsetY * offsetY);

        Console.Write(Terrain(height));
    }

    Console.WriteLine();
}

Console.WriteLine();
Console.WriteLine("~ water   - shallow   . beach   , grass   # forest   ^ rock   * snow");
Console output
~~~~~~~~~~~~~~~----~~~~~~~~~~~~~~~~~~~~~~~~~~---.---~~~~~~~~~~~~
~~~~~~~~~~~~~~~---~~~~~~~~~~~~~~~~~~~~~~~~~~----.----~~~~~~~~~~~
~~~~~~~~---------------~~~~~~~~~~~~~~~~~~~~---------~~--~~~~~~~~
~~~~~~~~~--------------------~~~~~~~~~~~~~~-----...-----~~~~~~~~
~~~~~~~-----~---------..,.-----~~~~~~~~~~~----..,,...---~~~~~~~~
~~~~~~~~~~~~-~~~--------..------~~~~~~-----...,,,,,..---~~~~~~~~
~~~~~~~~~~~~~~~~~~--------------~~--~---...,,,,,.,,,.---~----~~~
~~~~~~~~~~~~-~~~~~~-----------~~~~----.,,,,,,,,,,,,,..-------~~~
~~~~~~~~~~~~~~~~~~~~-----------~~----.,,,,,,,,,,,,,......---~~~~
~~~~~~~~~~---~~~~~~------------------.,,,,,,,,,,,,,,......---~~~
~~~~~~~-------------------------------.,,,,,,,,,,,,,....,.------
~~~~~~--------------------------~~---..,,,,,,,,##,,,...------~~~
~~~~~~~----...----------~~~---~~~~---.,,,,,,######,,----~~~~~~~~
~~~~~---..,,,,.,,......--------~~-----..,,,,,,,,,,,..-----~~~~~~
~~~~~--.,,,,,,,,,,,,,,,,,,,.----~~-------.,,,,,,,,,.----------~~
~~~--.,,,,,,,,,####,,####,..---~~~~--------.....-------------~~~
~~---,,#############^^###,,.--~~~~~~------------~-------------~~
~~----.,,##,,############,,..--~~~~---.....,,...--..--.---.---~~
~~~~---.,,,,,,##^#####,,,,,,,..----.,,...,,,,,,,,,,..........--~
~~~---.,,,,,,,#####,,,,,,,,,,,,.....,,,,,,,,,,,,,,,,,,,,,.----~~
~~~-...,,,,,###,,,,,,,###,,,,,,,,,,,,,,,,,,,,##########,,,.-~~~~
~~~----...,,,,,,,,##,,#,,,,,,,,,,,,,,,,,,,,,,#########,,,,.---~~
~~~-------.--.,,,#########,,,,,,#,,,,,,,########^#####,,,,...--~
~~~~~-------..,,,,,,,,,,,,,,,,,,,,,,,,,,,,######^^####,,,,,.--~~
~~~~-~~~~~---..,,,,..,,,,,,,,,,,#####,,,.,,##^^**^^######,.--~~~
~~~~~~~~~---...,,,,..,,,,,,,...,,,,,,,,..,,,,#######,,,,,,.--~~~
~~~~~~~~~---...,,,...,,,,,,....------.,,,,,,,,,,,,###,,,.---~~~~
~~~~~~~~~~------....-.,,,,..----~---....,,,,,,,,,,,,,,,.--~~~~~~
~~~~~~~~~~~~~---------..,..---~~~~~---..,,,,,,,,,..-------~~~~~~
~~~~~~~~~~~~~~--------------~~~~~~~~~---....,,,,,,...----~~~~~~~
~~~~~~~~~~~~~-------~~~~~~~~~~~~~~~~~~~~~--.,...,....----~~~~~~~
~~~~~~~~~~~~~~~-----~~~~~~~~~~~~~~~~~~~~~~----...------~~~~~~~~~

~ water   - shallow   . beach   , grass   # forest   ^ rock   * snow
~~~~~~~~~~~~~~~----~~~~~~~~~~~~~~~~~~~~~~~~~~---.---~~~~~~~~~~~~
~~~~~~~~~~~~~~~---~~~~~~~~~~~~~~~~~~~~~~~~~~----.----~~~~~~~~~~~
~~~~~~~~---------------~~~~~~~~~~~~~~~~~~~~---------~~--~~~~~~~~
~~~~~~~~~--------------------~~~~~~~~~~~~~~-----...-----~~~~~~~~
~~~~~~~-----~---------..,.-----~~~~~~~~~~~----..,,...---~~~~~~~~
~~~~~~~~~~~~-~~~--------..------~~~~~~-----...,,,,,..---~~~~~~~~
~~~~~~~~~~~~~~~~~~--------------~~--~---...,,,,,.,,,.---~----~~~
~~~~~~~~~~~~-~~~~~~-----------~~~~----.,,,,,,,,,,,,,..-------~~~
~~~~~~~~~~~~~~~~~~~~-----------~~----.,,,,,,,,,,,,,......---~~~~
~~~~~~~~~~---~~~~~~------------------.,,,,,,,,,,,,,,......---~~~
~~~~~~~-------------------------------.,,,,,,,,,,,,,....,.------
~~~~~~--------------------------~~---..,,,,,,,,##,,,...------~~~
~~~~~~~----...----------~~~---~~~~---.,,,,,,######,,----~~~~~~~~
~~~~~---..,,,,.,,......--------~~-----..,,,,,,,,,,,..-----~~~~~~
~~~~~--.,,,,,,,,,,,,,,,,,,,.----~~-------.,,,,,,,,,.----------~~
~~~--.,,,,,,,,,####,,####,..---~~~~--------.....-------------~~~
~~---,,#############^^###,,.--~~~~~~------------~-------------~~
~~----.,,##,,############,,..--~~~~---.....,,...--..--.---.---~~
~~~~---.,,,,,,##^#####,,,,,,,..----.,,...,,,,,,,,,,..........--~
~~~---.,,,,,,,#####,,,,,,,,,,,,.....,,,,,,,,,,,,,,,,,,,,,.----~~
~~~-...,,,,,###,,,,,,,###,,,,,,,,,,,,,,,,,,,,##########,,,.-~~~~
~~~----...,,,,,,,,##,,#,,,,,,,,,,,,,,,,,,,,,,#########,,,,.---~~
~~~-------.--.,,,#########,,,,,,#,,,,,,,########^#####,,,,...--~
~~~~~-------..,,,,,,,,,,,,,,,,,,,,,,,,,,,,######^^####,,,,,.--~~
~~~~-~~~~~---..,,,,..,,,,,,,,,,,#####,,,.,,##^^**^^######,.--~~~
~~~~~~~~~---...,,,,..,,,,,,,...,,,,,,,,..,,,,#######,,,,,,.--~~~
~~~~~~~~~---...,,,...,,,,,,....------.,,,,,,,,,,,,###,,,.---~~~~
~~~~~~~~~~------....-.,,,,..----~---....,,,,,,,,,,,,,,,.--~~~~~~
~~~~~~~~~~~~~---------..,..---~~~~~---..,,,,,,,,,..-------~~~~~~
~~~~~~~~~~~~~~--------------~~~~~~~~~---....,,,,,,...----~~~~~~~
~~~~~~~~~~~~~-------~~~~~~~~~~~~~~~~~~~~~--.,...,....----~~~~~~~
~~~~~~~~~~~~~~~-----~~~~~~~~~~~~~~~~~~~~~~----...------~~~~~~~~~
  • deep water
  • shallow water
  • beach
  • grass
  • forest
  • rock
  • snow

07Good to know

  • The modulo while sampling makes the noise continue seamlessly at the borders. That allows textures to be repeated as tiles.
  • The method works in any dimension: one dimension for curves, two for height maps, three for animated clouds.
  • The most common use is a height map: read every value as a height and split the range into zones. Below one limit there is water, above it beach, then grass, forest, rock and snow. Because neighbouring values are similar, coherent coastlines and mountain ranges appear instead of single pixels. The second example does exactly that.
  • Multiplying the height with a mask on top of it shapes the map. A mask that falls off towards the border gives an island, a horizontal gradient gives a coastline.
  • Because all octaves are summed up, the values crowd towards the middle. For a high contrast image you stretch the range afterwards, just like the example below does.