Generating Terrain with Cellular Automata

This post is about a world-building tool I’ve been working on. The goal is to generate semi-realistic landscapes including rivers and other effects of erosion. The tool is really some code written in R. At heart, it’s a map that takes the form of a grid, where each square has an altitude — forming what’s called a height map.

Cellular Automata

The code falls roughly into a category of models called “cellular automata.” The cellular part are the cells in the grid. Each cell has a state like on/off, a color, or a numeric value. The model runs over time, and in each time-step (which might represent a second or a millenium), the cells may change according to a small set of rules.

The neat thing is that each cell essentially decides on its own how to change, based only on its immediate neighbors. Some surprisingly complex behaviors can emerge from very simple rules — John Conway’s “Game of Life” is probably the most famous example, and worth investigating.

In my world simulation, each cell represents a little slice of land, and the question at each time-step is whether that land will erode: whether its altitude will be decreased. The rules, therefore, a crude approximations of geologic processes — as guessed at by a non-specialist. In another post, I’ll describe all the different rules in detail, but here I’ll walk you through the broad strokes of making a little island.

Generating an Island

Before the erosion model can work, it has to have something to erode: we have to begin with some high, elevated land. For testing, I use a few quick and dirty methods.

The first step is to make a ramp of height values, from 0 up to 100. Placing two ramps end-to-end yields a long ridge. Adding another ridge on top of this, but turned at a right angle, yields a decent hill (with a little water at the corners):

Next we can transform this square into a round island. First, I carved land away by running the erosion model with a very simple rule: any tile adjacent to the sea (or the edge) will erode 1%. This created abrupt cliffs, so I ran a simple type of weathering to soften them.

Here’s the rule for this weathering effect. For each cell, measure the drop-off to the lowest neighboring cell. Then generate a random number between 5 and 10. If the random number is lower than the drop-off, erode the land. This means that gradual slopes don’t erode, steep slopes always do, and moderate ones might.

Adding Terrain Features

Our hill is far too regular, so the third step is adding some variability.

We’ll start with some medium-scale features generated through random noise. Perlin noise is one variety, which can be scaled very easily to make either huge mounds and dips, or very fine-grained texture. For a lot of land generators, this is the only method used, but I think it’s best as a supplement, because it cannot make realistic mountain ranges or other large-scale features.

Here I’ve added one layer of noise that adjusts the base altitude up or down.

Next I added some fine-grained texture with another run of the erosion model: but the “rule” is simply a random chance of eroding in each cycle.

Hydrology

All of this is to get ready for the interesting part: putting river and lakes onto the island. Most simple terrain generators don’t bother with water, probably because it’s a significant layer of added complexity. But the results are worth it: not only do you get the rivers and lakes themselves, you can also get erosion caused by water — which creates mid-scale features that look a lot more interesting.

The basic idea is to separately keep track of a layer of water covering the surface, let that water flow downhill, and then erode the land where that flow was very intense. Here’s what the island looks like after a good bit of water-based erosion:

If we map the tiles where water is constantly found, we can show rivers (light blue) and deeper lakes (medium blue):

The coast has various low-lying areas, as is realistic, and one major river system never drains significantly, indicating a wetland or shallow lake.

While there is still a lot of room to improve the model, I think it shows plenty of promise. By using cellular automata — rather than a more top-down approach — simple, understandable rules can be implemented and tested quite easily. Without being overly sophisticated, pretty good terrain can be generated — all on a home computer.

Some future posts will detail the cellular automata programming, the hydrological model, and attempts to generate entire planets.


Originally published at ideabyre.com.