Perlin Noise

Home --> Programming Projects --> Fractal Block Engine --> Procedural World Generation --> Perlin Noise

2D Perlin Noise

See this article for an exposition of how Perlin noise works.

The core Perlin noise function takes integers (seeds) for the 4 lattice points (0,0), (0,1), (1,0), (1,1) and a point (x, y) inside this square. The algorithm returns a real number. The returned real number can be positive or negative, with an expected value of 0. It works by using the corner seeds to get random length one vectors in R^2. Then dot products are taken and we interpolate. It is not hard to understand how this works, but it can be hard to understand why it works. Here is the code:

//See https://rtouti.github.io/graphics/perlin-noise-algorithm
//Optimized version (less multiplications).
//This returns a real number between 0 and 1.
//Inputs close to 0 get pulled to 0,
//and inputs close to 1 get pulled to 1.
float Fade(float t) {
    return ((6*t - 15)*t + 10)*t*t*t;
}

//Fractal Block World max random number.
#define FBW_RAND_MAX 	32767

//A class for setting a (pseudo) random seed
//and then getting random integers.
class RandCore {
private:
    //C++ Standard Mersenne Twister.
    std::mt19937 gen;

public:
    RandCore();

    //Seeding the random number generated.
    void SRand(int seed) {
        gen.seed(seed);
    }

    //Will return an int between 0 and FBW_RAND_MAX.
    int Rand() {
        return (gen() % FBW_RAND_MAX);
    }
};

//Returning a length one vector in the plane.
Vector RandGradient2D(
    RandCore & rc, int seed)
{
    rc.SRand(seed);
    int i = rc.Rand();
    switch(i % 16) {
        case 0: return Vector(-0.740233,0.67235,0);
        case 1: return Vector(0.837073,0.547091,0);
        case 2: return Vector(-0.948447,-0.316936,0);
        case 3: return Vector(-0.683452,-0.729995,0);
        case 4: return Vector(-0.909245,0.416261,0);
        case 5: return Vector(0.431214,-0.90225,0);
        case 6: return Vector(0.990217,-0.139538,0);
        case 7: return Vector(0.978472,-0.20638,0);
        case 8: return Vector(-0.950965,0.309299,0);
        case 9: return Vector(0.690884,-0.722966,0);
        case 10: return Vector(0.210842,0.97752,0);
        case 11: return Vector(0.986295,-0.164991,0);
        case 12: return Vector(0.828223,0.560398,0);
        case 13: return Vector(0.421108,-0.90701,0);
        case 14: return Vector(0.0248632,-0.999691,0);
        case 15: return Vector(-0.940438,0.339966,0);
    }
    //Error.
    return Vector(0.0f, 0.0f, 1.0f);
}

//Linear interpolation of floats.
float Interp(
    float v1,
    float v2,
    float f) //The fraction.
{
    return v1*(1.0f-f) + v2*f;
}

//Read the code to see what order
//in which to put the seeds.
//The values x,y should be between 0 and 1.
float PerlinNoiseXY(
    vector<int> seeds,
    float x, float y)
{
    RandCore rc;
    Vector grad_left_back   = RandGradient2D(rc, seeds[0]);
    Vector grad_left_front  = RandGradient2D(rc, seeds[1]);
    Vector grad_right_back  = RandGradient2D(rc, seeds[2]);
    Vector grad_right_front = RandGradient2D(rc, seeds[3]);

    Vector pos(x,y,0.0f);
    Vector offset_left_back   = pos - Vector(0.0f, 0.0f, 0.0f);
    Vector offset_left_front  = pos - Vector(0.0f, 1.0f, 0.0f);
    Vector offset_right_back  = pos - Vector(1.0f, 0.0f, 0.0f);
    Vector offset_right_front = pos - Vector(1.0f, 1.0f, 0.0f);

    float dot_left_back   = Dot(grad_left_back,   offset_left_back);
    float dot_left_front  = Dot(grad_left_front,  offset_left_front);
    float dot_right_back  = Dot(grad_right_back,  offset_right_back);
    float dot_right_front = Dot(grad_right_front, offset_right_front);

    float xf = Fade(x);
    float yf = Fade(y);

    float left  = Interp(dot_left_back,  dot_left_front,  yf);
    float right = Interp(dot_right_back, dot_right_front, yf);
    //
    float value = Interp(left, right, xf);

    return value;
}

Something that makes Perlin noise hard to understand is that there is tension. As our point gets closer to a corner, it gets weighted more. On other hand, as our points gets closer to a corner, the associated dot product gets smaller.

3D Perlin Noise

With 3D Perlin noise, the function takes 8 seeds (for the 8 corners of the unit cube) as well as a point inside the cube. The function returns a real number.

//Returns one vector from a list of 32
//length one vectors that were generated at random.
Vector RandGradient3D(
    FBWRandCore & rc, int seed)
{
    rc.SRand(seed);
    int i = rc.Rand();
    switch(i % 32) {
        case 0: return Vector(-0.489851,0.444929,-0.749723);
        case 1: return Vector(0.673811,0.440387,-0.593329);
        case 2: return Vector(-0.622205,-0.207918,0.754739);
        case 3: return Vector(-0.551831,-0.58941,-0.589982);
        case 4: return Vector(-0.549751,0.251681,-0.796512);
        case 5: return Vector(0.399894,-0.836718,0.374151);
        case 6: return Vector(0.803786,-0.113267,-0.584036);
        case 7: return Vector(0.977822,-0.206243,-0.0364279);
        case 8: return Vector(-0.95093,0.309288,0.00854616);
        case 9: return Vector(0.688933,-0.720925,0.0750848);
        case 10: return Vector(0.131953,0.611769,-0.779954);
        case 11: return Vector(0.284032,-0.0475139,-0.957637);
        case 12: return Vector(0.584857,0.39573,0.708054);
        case 13: return Vector(0.283696,-0.611043,0.739015);
        case 14: return Vector(0.016353,-0.657514,0.753265);
        case 15: return Vector(-0.752473,0.272017,0.599826);
        case 16: return Vector(0.862066,0.286175,-0.418265);
        case 17: return Vector(0.63215,-0.629253,0.452136);
        case 18: return Vector(-0.212415,-0.550622,0.807277);
        case 19: return Vector(0.821132,-0.500229,0.274798);
        case 20: return Vector(0.887219,0.449819,-0.1025);
        case 21: return Vector(-0.819412,-0.533291,0.210155);
        case 22: return Vector(-0.648608,0.513027,0.562238);
        case 23: return Vector(-0.685061,-0.537699,0.491499);
        case 24: return Vector(-0.617783,0.697558,-0.362983);
        case 25: return Vector(-0.128589,0.405483,0.905013);
        case 26: return Vector(-0.499459,0.325154,0.803004);
        case 27: return Vector(0.826998,-0.202922,-0.524307);
        case 28: return Vector(0.417892,-0.462326,-0.782062);
        case 29: return Vector(0.298697,-0.596288,0.745131);
        case 30: return Vector(0.0563963,-0.66715,-0.742785);
        case 31: return Vector(-0.523338,-0.539075,0.659936);
    }
    //Error.
    return Vector(0.0f, 0.0f, 1.0f);
}

//Read the code to see what order
//in which to put the seeds.
//The values x,y,z should be between 0 and 1.
float PerlinNoiseXYZ(
    svector<int> seeds,
    float x, float y, float z)
{
    RandCore rc;
    Vector grad_left_back_bot   = RandGradient3D(rc, seeds[0]);
    Vector grad_left_back_top   = RandGradient3D(rc, seeds[1]);
    Vector grad_left_front_bot  = RandGradient3D(rc, seeds[2]);
    Vector grad_left_front_top  = RandGradient3D(rc, seeds[3]);
    Vector grad_right_back_bot  = RandGradient3D(rc, seeds[4]);
    Vector grad_right_back_top  = RandGradient3D(rc, seeds[5]);
    Vector grad_right_front_bot = RandGradient3D(rc, seeds[6]);
    Vector grad_right_front_top = RandGradient3D(rc, seeds[7]);

    Vector pos(x,y,z);
    Vector offset_left_back_bot   = pos - Vector(0.0, 0.0, 0.0);
    Vector offset_left_back_top   = pos - Vector(0.0, 0.0, 1.0);
    Vector offset_left_front_bot  = pos - Vector(0.0, 1.0, 0.0);
    Vector offset_left_front_top  = pos - Vector(0.0, 1.0, 1.0);
    Vector offset_right_back_bot  = pos - Vector(1.0, 0.0, 0.0);
    Vector offset_right_back_top  = pos - Vector(1.0, 0.0, 1.0);
    Vector offset_right_front_bot = pos - Vector(1.0, 1.0, 0.0);
    Vector offset_right_front_top = pos - Vector(1.0, 1.0, 1.0);

    float dot_left_back_bot   = Dot(grad_left_back_bot,   offset_left_back_bot);
    float dot_left_back_top   = Dot(grad_left_back_top,   offset_left_back_top);
    float dot_left_front_bot  = Dot(grad_left_front_bot,  offset_left_front_bot);
    float dot_left_front_top  = Dot(grad_left_front_top,  offset_left_front_top);
    float dot_right_back_bot  = Dot(grad_right_back_bot,  offset_right_back_bot);
    float dot_right_back_top  = Dot(grad_right_back_top,  offset_right_back_top);
    float dot_right_front_bot = Dot(grad_right_front_bot, offset_right_front_bot);
    float dot_right_front_top = Dot(grad_right_front_top, offset_right_front_top);

    float xf = Fade(x);
    float yf = Fade(y);
    float zf = Fade(z);

    float left_back   = Interp(dot_left_back_bot,   dot_left_back_top,   zf);
    float left_front  = Interp(dot_left_front_bot,  dot_left_front_top,  zf);
    float right_back  = Interp(dot_right_back_bot,  dot_right_back_top,  zf);
    float right_front = Interp(dot_right_front_bot, dot_right_front_top, zf);
    //
    float left  = Interp(left_back,  left_front,  yf);
    float right = Interp(right_back, right_front, yf);
    //
    float value = Interp(left, right, xf);

    return value;
}

Getting the Corner Seeds

So far everything we have said is just like Perlin noise in a non-fractal game. However, one thing that makes a fractal game complex is it is more difficult to get the corner seeds. That is, as input we have the block path of the chunk being generated. Using that path, we can generate a seed to be used with the (0,0,0) corner of the chunk. To get seeds for the other 7 corners, we want to compute adjacent paths and generate seeds from them. We feel that the best way to do this is by using tail seeds which are described here. The function GetAdjTailSeedXYZ is defined in that page. Here is what the code might look like:

void GetPerlinDataXYZTail(
    int world_seed,
    const BlockPath & block_path,
    int chop, int salt,
    vector<int> & seeds)
{
    BinPath bin;
    bin.SetFromBlockPath(block_path);

    BinPath chopped_bin = bin;
    for(int i = 0; i < chop; ++i) {
        chopped_bin.path.pop_back();
    }

    seeds.clear();
    seeds.push_back( GetAdjTailSeedXYZ(world_seed, salt, chopped_bin, 0,0,0) );
    seeds.push_back( GetAdjTailSeedXYZ(world_seed, salt, chopped_bin, 0,0,1) );
    seeds.push_back( GetAdjTailSeedXYZ(world_seed, salt, chopped_bin, 0,1,0) );
    seeds.push_back( GetAdjTailSeedXYZ(world_seed, salt, chopped_bin, 0,1,1) );
    seeds.push_back( GetAdjTailSeedXYZ(world_seed, salt, chopped_bin, 1,0,0) );
    seeds.push_back( GetAdjTailSeedXYZ(world_seed, salt, chopped_bin, 1,0,1) );
    seeds.push_back( GetAdjTailSeedXYZ(world_seed, salt, chopped_bin, 1,1,0) );
    seeds.push_back( GetAdjTailSeedXYZ(world_seed, salt, chopped_bin, 1,1,1) );
}

The XY version is similar.

The chop value is for if we want the Perlin noise chunk to be a virtual chunk instead of the chunk being procedurally generated. See here for a discussion of virtual chunks.

This function could be changed to also return the rmin/rmax values that the GetVChunkData function here returns (so the caller does not have to call both functions).

Multiple Layer Perlin Noise

We can generate the height of terrain using Perlin noise taken from various virtual chunks that contain the chunk being generated.

For example, let C1 be the chunk being procedurally generated. Let (x,y) be a point inside C1 (or rather, the x,y coordinates of a point inside C1). Let n1 be the Perlin noise value generated from x,y using the C1 chunk. Now let C2 be virtual 2x2x2 chunk which contains C1. Let n2 be the Perlin noise value generated from x,y using the C2 chunk. Now we take n1 + n2 to be the terrain height within C1. Or we could take a weighted combination, such as n1 + 0.5 * n2.

Pictures of 2D Perlin Noise

If we use the height of terrain to be generated from 2D Perlin noise, we get pictures like the following:

Level of Detail (LOD) Perlin Noise

This is not to be confused with "Multiple Layer Perlin Noise". With level of detail (LOD) Perlin noise, we have a chunk C1 which we want to procedurally generate and we also have a chunk C2 which contains C1 and we also want to procedurally generate C2. We can have the C2 chunk have terrain generated by Perlin noise, and we have C1 use the same height function. This can be used to generate huge rolling hills as shown by the following picture:

In the above picture, you can see a rolling hill in the foreground, with more hills (at a coarser level of detail) in the background.

A Quirk: Chunk Aligned Lattice Points

A quirk of getting the seed using the path of a chunk is that the lattice points we use for Perlin noise are always "chunk aligned". Essentially, lattice points are always of the form (x,y,z) where x,y,z are integers that are multiples of 16 (because a chunk is 16 blocks wide). In a non-fractal game it would be easy to modify this to have the lattice points be of the form (x,y,z) where x,y,z are integers that are multiples of 5 (for example). We see no easy way around this for our setting.

Continuously Changing the Parameters

Suppose that the height z of terrain is generated using two noise values, n1 and n2, as follows: z = 0.5 * n1 + 0.25 * n2. We can make it so that the parameters 0.5 and 0.25 are themselves chosen at random. Call these parameters p1 and p2. That is, in some large virtual chunk V we can randomly get values for p1 and p2. We can also get these values for all the 2x2x2 surrounding virtual chunks with V being the left,back,bottom one of these. We can then interpolate.