Mostly Harmless


A blog about science, art, coding, life,... mostly harmless stuff.


PCG Terrain I: The Basics

This is the first post in what will be (I hope) a long series on procedural content generation. For the first part of the series, I will focus on what I think is the best content to begin with, procedural terrain. I choose terrain because there are a number of fairly straightforward algorithms that generate pretty good looking terrains, and are not that hard to understand or implement.

To warm things up, this is a quick look at what I’ll be showing in the next few posts.

Shoreline Beach close-up Bird's eye

This will not be a tutorial, neither will I dive too deep into the code. There is simply too much code for me to go into great detail. I will lay out the basic ideas, and point to further resources for a deeper understanding.

That said, please feel free to comment and ask anything that is not clear enough. I’ll do my best to answer.

There are few basic skills that I think are necessary to understand and implement these techniques:

  • Some knowledge of C# and specifically Unity 3D programming. This is not a tutorial in Unity 3D, so you’ll need to know the basics about creating a scene in Unity, adding components, and scripting.

  • Some basic understanding of Computer Graphics topics, such as how are meshes built, the math behind basic transformations, and such.

  • Some basic data structures, specifically, we’ll be dealing later on with some sort of tree-like structures, and will be talking about tree search algorithms (DFS, BFS, etc.).

Let’s begin…

First steps

The whole of set of tutorials about terrain generation will take place in a very simple scenario. Here is the basic setup I designed. Yours may vary:

Unity 3D basic scene and layout

It basically consists of a scene, with a huge water plane from the standard packages (scaled up to 10000x), a skybox with a pretty flare, a directional light (arranged with the skybox’s sun), and an empty GameObject, with a single script named TerrainGenerator, placed at the origin. There is where all the action will take place.

On the project pane you can see a few more scripts with funny names. These are all algorithms for procedural content generation of something, that will find their place in this PCG series some time in the future.

Now lets make some mountains.

Basic ingredients for terrain generation

As I see it, there are three basic components for terrain generation, at least to the extent we’ll be dealing with in this first few posts:

  • A heightmap generator, which is basically just a function that takes a point in the plane and gives us a height value for it. This is the single most important ingredient, because it determines the shape of the terrain. This function should be continuous, that is, it can evaluate every single possible point of the plane, no matter the resolution, so that we can build terrains with as much details as we want.

  • A mesh generator, which will be the responsible for actually visualizing our terrain. It will take as input our height function, and will build a mesh (with a fixed level of detail) whose vertices are layed out according to the corresponding height values. In huge scenarios (think Skyrim), it is simply not possible to have a single mesh with a uniform resolution for all the terrain. The mountains far away require much less details than the ground beneath your feet. The mesh generator is responsible for creating a mesh with a topology such that more detail is given to the closest spots, dynamically creating and removing vertices and triangles as the player moves around the map.

  • A texture generator, which takes a point in space, and returns a color for it. It can be as complicated as we want (interpolating many different grass or rock textures), but for our purposes, we will use very simple color gradients, which are fast, easy to implement, and don’t look that bad.

Let’s take a one at a time approach, and fix two of the components to their simplest form, so that we can concentrate on improving the third.

Generating the heightmap

For this first part, I will concentrate on the heightmap only, and will leave mesh and texture for future deliveries.

The simplest possible mesh we can use is a squared plane with a fixed number of vertices in the side. It is very easy to build such a mesh in Unity, just take a look at the documentation if you need.

Here is a quick and dirty snippet. I asume Width is the float field (or property) that stores the width in world units of the mesh being created, and Samples is the number of vertices you want on the side.

SampleHeight is the heightmap function that maps any point in the 2d plane to its height.

float edge = Width / (Samples - 1);

// Create the vertices and texture coords
var vertices = new Vector3[Samples * Samples];
var uvs = new Vector2[Samples * Samples];

// Fill in the data
for (int i = 0, p = 0; i < Samples; i++) {
    for (int j = 0; j < Samples; j++) {
        // Current vertex
        var center = new Vector3(i * edge, 0, j * edge);
        // Height of this vertex (from heightmap)
        float h = SampleHeight(center.x, center.z);
        center.y = h;
        vertices[p] = center;
        // UV coords in [0,1] space
        uvs[p++] = new Vector2(i/(Samples - 1f),
                               j/(Samples - 1f));
    }
}

For the texture part, as a first you can simply asign the same color to all vertices, by means of the material.color property of the MeshRenderer component. Again, look at the documentation if in trouble.

So lets move onto actually generating the heightmap.

Perlin powered mountains

For a start, we’ll use Perlin noise. Its a very powerful algorithm that generates noise that looks both random and smooth, although it is completely deterministic. In Unity 3D, it comes in the form of the Mathf.PerlinNoise(x, y) function.

Perlin noise is nice because it gives smooth bumps that look random, non-repeating, yet they have structure. In Unity 3D, its very easy to get a Perlin powered mesh of mountains:

public float SampleHeight(float x, float y) {
    return Mathf.PerlinNoise(x, y);
}

Yeap, just like that. This is how a 10x10 squared mesh with 100 vertices of side looks like with such a heightmap.

Perlin heightmaps

Of course the borders look awful, and we will deal with that a bit later, but we can see the potential of using Perlin for procedural terrain generation.

The next step consists in mixing a more than one layer of Perlin, with different scales, to get a more complex terrain. We sample Perlin a number of times (3 or 4 suffice), each time with a smaller scale. This is a code snippet just for that:

private float SamplePerlin(float x, float y) {
    float width = Width / 10f;
    float result = 0;

    for (int i = 0; i < PerlinLevels; i++) {
        result += (Mathf.PerlinNoise(x / width, y / width))
                  * width / 2;
        width /= 10;
    }

    return result;
}

And this is what 4 layers of Perlin can get:

Mixing Perlin layers

I’m actually cheating here, using a more complex mesh generator that do exploits the viewer distance to make subdivisions and improve detail on close areas. You can see some of the seams where the more detailed meshes join with the less detailed ones. You cannot really get a big terrain with enough detail just using a single mesh with uniform resolution, but we will address that in a future post.

The problem with this approach is that, it either creates terrain that looks too flat, or, if you increase the scale in the Y axis, it creates very dull looking sand dunes. This is due to the very nature of Perlin, a smooth and regular noise all over the plane. If we want areas of sharp mountains and areas of valleys, we need more control over the heightmap.

Gaussian powered mountains

A method that offers good tradeoff between control, quality and speed, is using a blend of gaussian functions. Gaussians are both easy to generate, and very controllable. A gaussian function is defined by a center and a “spread” value (mean and variance in statistical terms).

So, the infamous formula for generating a gaussian is very simple:

private float SampleGaussian(float x, float mu, float sigma) {
    float d = (x - mu);
    return Mathf.Exp(-d * d / (sigma * sigma));
}

I’m actually forgetting about the normalization factors, but since this is for generating terrain and not for a statistical analysis, it really doesn’t matter. Moving the sigma parameter to an appropiate value gets rid of the need for normalization.

For our mountains, the x would be the distance in world space from the current point in the mesh to the center of the mountain.

This is how one of such mountains looks like:

Single gaussian mountain

Now comes the tricky part: mixing a few of these together to get a nice looking island, with beaches and all. The first idea that comes to mind is just generating a few of these, randomly located, and with random spread factors. The thing is, it doesn’t work very well, because you end up with a bunch of unrelated bumps coming out of the ocean.

So, how can we do better? Here is an idea: we make a grid of possible locations for the mountains. In each cell in the grid we throw a coin to choose if we actually place a mountain there or not, and if chosen, pick a random starting point inside the cell. After choosing all the mountain centers locations, you make them grow until they start to bump into each other.

This is a fairly long code snippet (not sure if actually call it a snippet at all), but here it goes:

private Island[] GenerateIslands(int count, float size,
                                 float density,
                                 float separation) {
    List<Island> islands = new List<Island>();

    for (int i = 0; i < count; i++) {
        for (int j = 0; j < count; j++) {
            if (!RandomBernoulli(density)) {
                continue;
            }

            float x = i * size + RandomUniform(0, size - size
                      * separation) - size * count / 2;
            float z = j * size + RandomUniform(0, size - size
                      * separation) - size * count / 2;

            var island = new Island(new Vector3(x, 0, z), 0);
            islands.Add(island);
        }
    }

    bool[] cannotGrow = new bool[islands.Count];
    int canGrow = islands.Count;

    while (canGrow > 0) {
        for (int i = 0; i < islands.Count; i++) {
            var child = islands[i];

            if (cannotGrow[i]) {
                continue;
            }

            for (int j = 0; j < islands.Count; j++) {
                if (i == j) {
                    continue;
                }

                var other = islands[j];

                if (Vector3.Distance(child.Center,
                                     other.Center)
                    - size * separation <
                    (child.Radius + other.Radius)) {
                    cannotGrow[i] = true;
                    canGrow--;
                    break;
                }
            }

            if (!cannotGrow[i]) {
                child.Radius += size * 0.01f;
            }
        }
    }

    return islands.ToArray();
}

I think some explanations are due. The Island class is just a tiny container for a center and a radius. The parameters count and size define the number of rows (and columns) of the grid, and the size of each cell, respectively. The density parameter defines the probability that a given cell is taken. The separation parameter defines how close together can islands get. If this parameter is greater than zero, you’ll get a separated island per gaussian. If its smaller than zero, you’ll actually get a single island with many mountains blended into each other.

After running this method you’ll get a few pairs of centers and radios which you can use to sample gaussians out of them. Then you just add all the gaussians together to get the height for every point in the mesh:

public float SampleHeight(float x, float y) {
    float h = 0f;

    for (int i = 0; i < islands.Length; i++) {
        h += SampleHeight(x, y, islands[i], heights[i]);
    }

    return h;
}

This is what a grid of 20x20 with a density of 0.05, in a mesh of 100x100 vertices gives you:

Gaussian island

You can see how you get some big mountains, surrounded by some smaller mountains, and even some bays. You’ll probably need to tinker with the separation parameter to get an island like this one.

I’ll stop here for now. In the next post I’ll talk about adding detail to the surface, using the infamous Perlin noise. But for that we’ll need a more powerful mesh generator. Also, I’ve been cheating, showing images with some gradient colors. Its a pretty easy task, so we’ll deal with it next time.