This article is about how to generate terraced terrain as seen in the game “Godus”, using Unity. This article focuses on the general approach and does not offer a copy-paste solution for you to use in your projects. It aims to tell you how to approach the problem and how to implement the algorithm yourself. I’ll offer some code snippets, those arent Unity specific for the most part, so you should be able to adapt it for different environments.

This is what we are going to recreate (just the terrain for now):

Source: https://www.youtube.com/watch?v=W7t-oqvSl6A

This article is part 1 in a series of articles and focuses exclusively on the foundation of the algorithm, the extraction of countour lines from a perlin noise.

Approach

The general approach will be the following:

Generate a perlin noise
Extract the contour lines from the noise
Prost-process the contour lines
Triangulate the contour lines for use as terrain

Generating a perlin noise

This is trivial in Unity using Unity’s Mathf.PerlinNoise(float x, float y) function, if you want or need to implement it yourself, here is a good starting point.
We will add parameters to the script that will let us tweak the noise to our liking and sample the noise like this:

public float SamplePerlinNoise(float x, float y)
{
    var xCoord = settings.NoiseOffset.x + x * settings.NoiseScale;
    var yCoord = settings.NoiseOffset.y + y * settings.NoiseScale;
    return Mathf.PerlinNoise(xCoord, yCoord);
}

The settings object in my case looks like this:

[System.Serializable]
public class ContourTerrainSettings
{
    public Vector2 Size;
    public float SquareSize;
    public int NumContours;
    public int Subdivisions;

    public Vector2 NoiseOffset;
    public float NoiseScale;
}

Extracting contour lines

After having sampled the noise, we need to somehow convert it to a set of contour lines, each being a linked list of vertices.

There is an excellent article on how to do this by Grgrdvrt that explains how to approximate the contour lines of the noise and extract line segments that make up a contour line. Grégoire’s article is the foundation of this article, but it doesn’t cover everything. You should read it first, in order to understand what I’m doing here.

I modified Grégoire’s algorithm to produce the exact result I wanted, my version of it is made up of the following steps:

Generate a grid of squares
For each corner of a square (called a “node”), sample the noise
Subdivide a square’s edges into “sub-edges” a number of times
For each sub-edge, calculate how many contours it crosses (see Grégoire’s article for illustrations)
Assume the noise is linear and approximate it by evenly distributing as many vertices along the sub-edge as it crosses contours
Connect all vertices of a square as specified in Grégoire’s article and store each pair of connected vertices for later use

Generating the square grid

This part is kind of trivial, but I want to briefly describe it anyway. I did this the object-oriented way and created classes Square, Edge and Node. Each square contains four edges left, top, right and bottom and holds a reference to it’s four neighbouring squares. Edges are strictly reused, so two squares that share an edge do not create the same edge twice. The grid is created from the bottom left towards the top right, and each square re-uses the edges previously generated by it’s neighbours. Each edge contains a start and an end node and these nodes are always assigned such that the left or bottom node of an edge is the start, and the top or right node is the end. A node samples the noise at it’s given position and stores that sampled value.

Subdividing edges

When an edge is created for the first time, it subdivides itself into “sub-edges” as many times as specified in the settings object. So if the settings object specifies 2 subdivisions, that means that we will end up with 2^2=4 sub-edges. This of course is implementation-dependant and it doesn’t matter how exactly you implement the subdivision. I implemented it using a recursive constructor that can be seen here:

public Edge(Node start, Node end, ContourTerrainArgs args) : this(start, end, args, args.Settings.Subdivisions) { }
private Edge(Node start, Node end, ContourTerrainArgs args, int subdivisions)
{
    Args = args;
    Start = start;
    End = end;

    if (subdivisions > 0) Subdivide(subdivisions);
    else CalculateVertices();
}

If an edge is not subdivided any further, it then calculates it’s vertices. Edges are subdivided, because if they aren’t, the contour lines look very jagged, with angles only being in steps of 45 degrees, similar to a result produced by the marching squares algorithm.

The number of subdivisions controls the precision of the contour lines, the number of squares controls the subdivisions of (number of vertices along) the contour, so with more subdivisions you get a more accurate result, and with more squares you get smoother contours, albeit with the price of an increased vertex count. These two values should be balanced between performance and visuals.

An intermediate result, using Unity’s Debug.DrawLine method, looks like this:

Connecting the vertices

Each square now has four edges. Those edges have sub-edges, but these are of no concern to the square, as we have introduced enough abstraction to make the sub-edges invisible to the square: All it sees is an edge with a list of vertices.

We now need to connect the vertices that lie on the edge of the square, because currently all we have is a bunch of points and we want to get continuous contour-lines from them. The way we do this is vital to this article, unfortunately it isn’t trivial, in fact, it isn’t even deterministic. By sampling the noise the way we do, we lose too much information to be able connect the resulting vertices correctly 100% of the time, I have not found a solution for this and neither has the author of the original approach mine is based on, but I have found this to be negligable, because if the grid is fine- and the noise big enough, the contours look correct 99% of the time. Those 1% of the time will be either ignored, corrected or removed later.

Grégoire goes into great detail in his article and I will not repeat what he is saying, go read his approach and then come back :wink:

I assiged a boolean value to each edge that remembers if the edge is falling or rising. An edge is called falling, if it’s start node has a bigger noise value than it’s end node, and vice versa. This information is now used to determine entry and exit vertices the way Grégoire does it. The top and left edge of a square are considered to have entry vertices if they are falling, the opposite is true for the right and bottom edges:

var leftIsEntry = LeftEdge.IsFalling;
var topIsEntry = TopEdge.IsFalling;
var rightIsEntry = !RightEdge.IsFalling;
var bottomIsEntry = !BottomEdge.IsFalling;

We then walk through the vertices in clockwise order and work with a stack as described in Grégoire’s article to connect entry and exit vertices. This works almost perfectly.

When connecting two vertices, we store the pair in a list, so we can later see which vertices have been connected. This is important in order to create a linked list of vertices from the loose vertex pairs later. I am storing these in a hash map that maps a vertex to a list of vertex pairs, so that I can look up which vertex is part of which pairs.

The 1%

You can see in the image above that some contours have holes. This is, because the vertex connection algorithm sometimes detects too many vertices to be of the same kind, so you end up with a square that has three entry and one exit vertex, for example. Grégoire’s algorithm never connects two vertices of the same kind, so the two remaining vertices will leave a hole in our beautiful contours.

This bug can be “fixed” by checking, after the algorithm has terminated, whether there are exactly two vertices remaining on the stack, in which case those two are connected. This workaround works fairly well in eliminating at least the trivial and most common edge cases.

Linking contours

Our contour lines are currently only loose lines with a start and an end, that happen to line up in a way that looks right, if we debug-print them in our 3d scene. None of these seemingly continuous lines are linked up yet though, so the computer doesn’t know how to walk along a contour, which is vitally important for triangulation, as we need to know which vertices make up a single contour.

When linking to vertices, I store them in a hash map:

1	new VertexPair(vertex, other.vertex).Remember(dict);

The VertexPair class contains references to the two vertices provided in the constructor, and it has a very important method: Remember.
Remember takes a Dictionary<Vertex, List<VertexPair>> as a parameter, which in C# is the equivalent of a hash map between a reference to a Vertex and a list of VertexPairs.
This dictionary maps each vertex to all the vertex pairs that it is part of. If the algorithm is working correctly, the list should only ever contain one or two items. This way of doing things is probably very inefficient, so optimization can be done here.

Keeping this dictionary is important, because it allows us to walk along vertex pairs like this (the dictionary is called pairsByVertex).

Below you can see the algorithm that walks along the vertex pairs and links them up to a continuous contour line, implemented in C#.

Notice the variable allowStartInMiddle: It is a parameter that is set to false be default. We can only walk those contours that are open with this algorithm. That means, closed contours will remain. For those, we pick a random vertex and call the function again, using allowStartInMiddle = true.

var contourLine = new List<Vertex>();
var currentVertex = start;
contourLine.Add(start);

VertexPair previousPair = null;

do
{
    visitedVertices.Add(currentVertex);

    var pairs = pairsByVertex[currentVertex];
    if (pairs.Count == 0) throw new System.Exception("Cannot walk vertex chain - vertex isn't connected to anything");
    if (pairs.Count > 2) throw new System.Exception("Cannot walk vertex chain - vertex is connected to too many other vertices");
    if (pairs.Count == 2 && previousPair == null)
    {
        if (!allowStartInMiddle) throw new System.Exception("Cannot walk vertex chain - vertex is connected to too many other vertices");

        pairs.RemoveAt(1);
    }

    if (pairs.Count == 1)
    {
        if (currentVertex != start) break;

        currentVertex = pairs[0].Other(currentVertex);
        previousPair = pairs[0];
    }
    else if (pairs.Count == 2)
    {
        var otherPair = pairs.Where(pair => pair != previousPair).FirstOrDefault();
        if (otherPair == null) throw new System.Exception("Cannot continue walking - something very weird happened");
        previousPair = otherPair;
        currentVertex = otherPair.Other(currentVertex);
    }

    contourLine.Add(currentVertex);

    // Draw Unity debug line between the previous and the current vertex. This creates the while contours as seen in the image above
    Debug.DrawLine(contourLine[contourLine.Count - 2].Position, currentVertex.Position, color, 1);
} while (currentVertex != start);

This algorithm results in a list of Vertices that make up a contour line. We call the function repeatedly until there are no Vertices that aren’t part of a contour.

After linking the contours and debug-printing them with random colors, this is what we get:

Closing contours

You can see that many contours are not closed rings without an end, but are cut off by the end of the grid, where the noise is no longer sampled, so they have an opening. This opening needs to somehow be closed, because if we just naively connect the two end vertices, in some cases those lie on opposite ends of the grid, so that the connection would go across the grid without regard for anything inbetween.

In order to generate proper geometry, we need to connect these end vertices along the edges of the grid, because although we may not want to generate any side-facing geometry at the end of the grid, we need to generate upwards-facing geometry, and without closing those loops that do not end on the same grid edge, the surface will have holes and maybe also intersect itself, which causes problems with the triangulation algorithm that will be discussed later.

To do this, every edge of a square detects if it is lying on an outer edge of the grid (the edges surrounding all of the contours; called “super-edges” from now on). If yes, it remembers which one (left, top, right or bottom). Vertices remember part of which edge they are, so via the edge they can also know what super-edge they are on, if any.

There is something very important that is missing in this approach, which I will describe in part 2.

Trivial case

Closing those contours that have their ending vertices on the same super-edge is trivial: We add a new VertexPair consisting of the two end vertices and are done.

Non-trivial case

If the super-edges of the two ending vertices are not the same, we need to do the following:

There are two possible ways to connect those vertices: Walk along the super-edges clockwise or counter-clockwise, until the other vertex is found. The correct path is the shorter one, so we need to compute both and calculate the length for them.

For this we first walk from one of the end vertices to both ends of the super-edge that it lies on. Then we walk along the edges clockwise and counter-clockwise, until we have reached the super-edge of the other vertex. If we have, we add all intermediate corners to a list. We then calculate the length of that path, chose the shortest one, and add the following vertex pairs:

Start to the first super-corner
Inbetween all super-corners
Last super-corner to end

The result looks like this:

We package this algorithm inside a method that I called ConnectVerticesAlongSuperEdges, that we can now call for any two vertices and it will add the required vertex pairs to the dictionary for us:

void ConnectVerticesAlongSuperEdges(Vertex v1, Vertex v2, Dictionary<Vertex, List<VertexPair>> pairsByVertex, ContourTerrainArgs args)
{
    if (v1.SuperEdge == v2.SuperEdge)
    {
        new VertexPair(v1, v2).Remember(pairsByVertex);
        return;
    }

    // FindIntermediateVerticesToEdge returns all the super-corners as a Vertex[] that lie between the two super-edges of v1 and v2
    var path1 = FindIntermediateVerticesToEdge(v1.SuperEdge.Start, v1.SuperEdge, v2.SuperEdge, args);
    var path2 = FindIntermediateVerticesToEdge(v1.SuperEdge.End, v1.SuperEdge, v2.SuperEdge, args);

    // GeometryTools.PathLength simply calculates the length of a path of Vector3s
    var shortestPath = GeometryTools.PathLength(path1.Select(v => v.Position)) > GeometryTools.PathLength(path2.Select(v => v.Position)) ? path2 : path1;
    var completePath = new List<Vertex>();
    completePath.Add(v1);
    foreach (var v in shortestPath)
    {
        v.y = v1.Position.y;
        args.Result.Vertices.Add(v);
        completePath.Add(v);
    }
    completePath.Add(v2);

    for (int i = 0; i < completePath.Count - 1; i++)
        new VertexPair(completePath[i], completePath[i + 1]).Remember(pairsByVertex);
}

Merging contours

Look at the picture above and see if you notice something: Not only are the previously open contours now connected, the algorithm also worked out when multiple contours are actually the same contour, cut in half by the super-edges.

This works as follows:

Starting with the left super-edge, in clockwise direction, build a list of all vertices on super-edges. So we take all the vertices that on the left super-edge, concatenated by those of the top super-edge and so on. We need to add vertices to this list in clockwise order.

Then we can walk through the list and add the vertices to a stack. If the top of the stack has the same elevation as the current vertex, pop the stack and connect the two vertices. Otherwise add the current vertex to the stack. This way, two neighbouring vertices with the same elevation will be connected, too, because they must be part of the same contour. Think about it: Contours are always closed loops, so if you cut them in half, two vertices of the same contour must always have an even number of vertices between them. The two in the middle belong to the same contour, as do the two before and after that, and so on.

Vertex y-coordinates

For this to work we need vertices of the same contour to have the same y coordinate, as that’s the only way we can determine if they belong together or not. Because of this, when creating the vertices in the Edge class, we need to round their y coordinate to the nearest value. In the settings object I have an int NumContours that stores how many contours the noise should be divided into. I use this parameter to round the vertices to the nearest contour:

1	var yValue = Mathf.Round((approxValue * Vector3.up * settings.Strength).y * settings.NumContours) / settings.NumContours;

Be sure to also read part 2: How to generate geometry from the extracted contours!

Thoughts or questions? Leave me a comment!