# Developing a Terraced Terrain Generator

# Intro š¬

In this blog post I will discuss some technnical details and give a glimpse of Terraced Terrain Generatorās (TTG) development process. TTG is a free Unity tool for procedural generation of terraced terrain meshes. Itās open source and itās on GitHub! Here are some examples of the type of terrains TTG is able to generate:

The post follows TTGās four terrain generation steps: basic shape generation, mesh fragmentation, mesh deformation and terrain slicing. Then, we discuss performance improvements and future developments. Finally, a short conclusion wraps the post up.

Letās dive in TTGās generation steps right away.

# Step 1: Basic shape generation š

This step is responsible for generating the polygon that will server as a basic shape for the terrain. In order words, how the terrain will look like from a high up, top view.

## Supported shapes

- Equilateral triangle.
- Any regular (equilateral and equiangular) polygon, from 4 to 10 sides.

## Equilateral triangle

Generating an equilateral triangle is trivial: create 3 vertices equally distant from the center of the terrain. Each pair forms a 60Ā° angle with the center.

## Any regular polygon

All other regular polygons (independent of the number of sides) will be generated using the same strategy. We take advantage of the fact that regular polygons can be created by composing triangles and define all polygon generation based on it. Regular polygons are perfect for this task because their vertices are equidistant from the polygonās center.

### Square

A square can be created by overlapping 2 isosceles, right-angled triangles on their hypotenuses. The triangles are created in a similar manner to the equilateral triangles described above, but vertices are recycled to save memory. A square contains 4 vertices and 2 triangles.

### Pentagon

A pentagon can also be created using triangles, but differently from the strategies described above. A vertex is placed on the center of the pentagon and itās used by all triangles that compose the polygon. All other vertices are equidistant from the center vertex. Once again, vertices are recycled to save memory.

### Other regular polygons

Other regular polygons with more than 5 sides are created using the same strategy as the pentagonās, just increasing the number of vertices. For example, hereās a decagon:

# Step 2: Mesh fragmentation š§Ø

The basic shape generated by the previous step does not contain enough vertices and triangles to generate a nice terrain. We need to fragment it into smaller triangles to increase its detail and resolution.

We start by taking advantage that all shapes generated in the previous steps are composed by triangles. Then, we can fragment these triangles into smaller ones. Breaking down a triangle into smaller triangles is trivial: divide it into 4 triangles like the image below. The outer, bigger triangle is the original one and the smaller, inner triangles are the outcome of a triangle fragmentation.

The fragmentation can continue recursively, on the generated triangles. If we fragment the 4 triangles above, we would obtain the following 16 triangles.

The more fragmentation iterations we perform, the higher is the resolution of the final mesh. We can say a mesh was fragmented with a depth D of there were performed D fragmentation iterations on it. The resulting mesh will contain $T * 4^D$ triangles, where T is the number of triangles in the original mesh and D is the fragmentation depth.

Hereās an example of a triangle that has been fragmented 6 times (depth = 6):

Hereās a pentagon that has been fragmented 5 times (depth = 5):

# Step 3: Hills and valleys generation (a.k.a. mesh deformation) š

Now that weāve got a flat surface which serves as a base to a terrain, itās time to create hills and valleys to make the terrain more interesting.

## Requirements

- Fully automate this task, eliminating the tedious job of terrain shaping.
- It should be able to repeatedly generate random terrains.
- At the same time it should have a deterministic behaviour, so it could easily reproduce a given terrain whenever necessary.
- The maximum height of the generated hills should be a parameter.
- The frequency (how often hills are formed) should be a parameter.

## The strategy

The chosen strategy is well known in the field, yet itās quite efficient: noise filters. These filters can generate noise, often following some pattern. Simply put, they are functions that, for a given point in space, will return a noise value - often between 0 and 1. The idea is to use the noise values to deform the mesh by moving its vertexes upwards, creating hills. This can be accomplished by multiplying the noise value by the maximum height, and adding it to the vertexās `y`

coordinate.

1

vertex.y += noise(vertex.x, vertex.y) * maximumHeight

The challenge is to choose the right filter. Fortunately, the Perlin filter is famous for delivering filters that are a great fit for the kind of deformation weāre looking for. Better yet, Unityās standard API already contains a function for Perlin noise: `Mathf.PerlinNoise`

. Hereās an example of an image of a Perlin filter:

In order to control the frequency, we simply multiply the vertex coordinates by a given parameter `frequency`

.

1
2
3

var filterX = vertex.x * frequency;
var filterY = vertex.z * frequency;
vertex.y += height * Mathf.PerlinNoise(filterX, filterY);

Unityās API call doesnāt support randomizer seeds, so we had to get creative. We introduced randomisation by offsetting all verticesā position by a random value.

1
2
3
4
5
6
7
8
9
10
11
12

var vertices = mesh.vertices;
var xOffset = _random.Next(-1_000, 1_000);
var yOffset = _random.Next(-1_000, 1_000);
for (var i = 0; i < vertices.Length; i++)
{
var vertex = vertices[i];
var filterX = (vertex.x + xOffset) * frequency;
var filterY = (vertex.z + yOffset) * frequency;
vertex.y += height * Mathf.PerlinNoise(filterX, filterY);
vertices[i] = vertex;
}

And to add replicable, deterministic terrain generation, the randomizerās seed can be provided.

## Outcome

The outcome was quite convincing. Hereās an example of a pentagon-based terrain, fragmented 2 times (depth = 2), with a maximum height of 5 and a frequency of 0.2.

Hereās another example; an octagon-based terrain, fragmented 6 times (depth = 6), with a maximum height of 10 and a frequency of 0.2.

Hereās the same octagon-based terrain with a frequency of 0.5:

## Height curve

Even though this strategy delivers great results and we can control the noise frequency, it would be great if we could control other parameters. For example, we could benefit from controlling the height distribution over the terrain: how low valleys and how high hills should be, and everything in between. This would allow developers to customize the terrain with characteristics such as āI want a mostly flat terrain, with sudden hillsā.

This can be accomplished by using a height curve that modifies the output of the Perlin noise algorithm. This curve would be limited to the [0,1] interval, on both X and Y axes, where the X axis represents the Perlin noise output and the Y axis represents the modified value. Finally, the final value can be multiplied by the maximum height as explained on the section above.

Such a curve can be easily defined in Unity using Animation Curves. The function that calculates the height of a given points becomes:

1
2
3
4
5
6
7
8
9

static float GetHeight(float x, float y, float maximum, AnimationCurve heightDistribution)
{
// Step 1, fetch the noise value at the given point
var noise = Mathf.PerlinNoise(x, y);
// Step 2, apply the height deformation curve (if it's not null) to the noise value
var modifier = heightDistribution?.Evaluate(noise) ?? 1;
// Step 3, apply the modifier to the maximum height
return maximum * modifier;
}

At this point, we can start playing with the height distribution curve. Letās play with a given terrain, changing the height distribution curve to see how it modified the generated terrain. A āneutralā curve (a curve that doesnāt modify the Perlin noise values) should output the same value as its input. That can be accomplished with a linear curve starting from (0,0) and ending at (1,1).

The neutral curve generates the following unmodified terrain:

Now letās start playing with the height distribution curve. First, letās try to change it to the following exponential curve:

The curve above generates the terrain below. Notice how the hills seem higher. In reality, they are not; the valleys around the hills are lower.

Letās be even more aggressive in that distribution, bringing the lower values even closer to the Y=0 line and rise quickly towards (1,1):

The curve above generates the following terrain. As expected, the terrain is flatter and the hills quickly ābumpā out of the plane.

We can get more creative and create curves like the one below, which creates a plateau with a few canyons:

The curve above generates the terrain below.

Or even a curve that has a plateau, but still has both hills and valleys:

The curve above generates the terrain below.

At this point, we have good control of the height distribution.

# Step 4: Terrain slicing šŖ

## The approach

Now that weāve got a terrain with hills and valleys, itās time to start creating some terraces. the method I used was based on Icospheric Planetoidās approach of using the meandering triangles algorithm to slice each triangle using planes that are located exactly where the terraces will be. Check their article for further explanation on how that algorithm can be applied on this domain.

Hereās an example of a terrain before and after slicing it into 15 terrains:

The end result looks great, but something is missingā¦

## Material assignment

Using the same material for all terraces is boring. Ideally, we should be able to assign a different material for each terrace to introduce some color palettes and progressions. To achieve this, terrace generation creates multiple sub meshes, one for each terrace. This simple trick allows for material assignment per sub mesh in Unity. The end result looks like something like this:

And as usual, we can play with the generation parameters to create unique terrains like the one below:

If we modify the height distribution curve of the terrain above, we can obtain a completely different terrain, where the different colored materials make the distinction really obvious:

# Performance improvements ā”ļø

Even though the goal of the terraced terrain generator was mostly accomplished on the feature level, performance was far from ideal. The efforts put into performance improvements were described in a separate article.

# Whatās next? š®

Although it looks like the Terraced Terrain Generator is complete, thereās always more work to be done. The following features are planned in future updates:

- Custom terrain heights: instead of evenly spacing the terraces between the terrainās lowest and highest points, allow custom heights to be chosen.
- Sphere as a basic shape: letās create completely terraced planets!
- Improve terrain detailing: use Perlin noise octaves to create more natural terrains.
- Realtime sculpting: instead of letting an algorithm generate the hills, let the user interactively sculpt them.
- Outer walls: ācloseā the generated mesh so it looks like a model carved in wood, sitting on a desk.

You can follow the development of TTG in its Trello board. If you have suggestions, feature requests or bugs to report, use the Issues section of TTGās GitHub repository to communicate them.

# Conclusion š

TTG was a great side project that taught me a lot about several aspects of game development tools creationāincluding non-coding nuances. I hope the effort Iāve put in the creation of the tool and its documentation help someone out there.

If you made it this far, thank you very much for the dedication. I hope youāve found this an interesting read. As usual, feel free to leave comments, suggestions or corrections in the comments section. See you next time!