I was making my bird game & the player should be able to fly tens of kilometers to any direction, above the rich forests & deserts. There should be different species of birds flying in beautiful patterns and should interact with the world in a good way. I knew that the answer is procedural generation, which is the use of algorithms to generate levels & stuff in games. It has variety of techniques taken together to achieve a beautiful world.

Background

Choice of Data Structures

Choice of appropriate data structure is very important. Since algorithms require certain inputs which certain data structures provide better for a particular task. For instance, let us apply erosion on a terrain. Erosion can be simulated by spawning water particles randomly and letting them to travel along the slopes to carry sediment with them. If we apply this directly to a 3D mesh, the mesh data structure will not allow us to easily fetch the neighboring vertices. However, if we use heightmap, the process will be much straightforward since fetching neighboring cell’s height value will be no complex.

Thus, for any procedural task, the data structures are selected to apply an algorithm that transforms it into good output.

Randomness in Generated World

Noise functions are used within the algorithm at specific points to introduce controlled randomness and variation. For example, Perlin noise values might be used to modify the height values in a heightmap algorithm, creating a more natural-looking terrain.

Cellular Automata for Level Generation

Cellular automata is a simple, yet extremely useful technique for level generation. It consists of a grid of cells, where the state of each cell is changed over time based on the state of its neighbors.

Cave Generation

The simplest example is of cave generation, where our grid cells can have only two states ‘wall’ or ‘floor’. We can represent this using black & white colors. We only have 2 rules:

1. If a wall has less than 4 wall neighbors, then it becomes a floor.
2. If a floor has 5 or more wall neighbors, then it becomes a wall.

After running our algorithm on an initially random grid, we get our cave system.

We can further improve this by applying more algorithms to connect the disconnected cave parts (caverns).

Platformer Generation

The above mentioned cave can be transformed into a platformer if we take cell states to be ‘sky’ & ‘land’. Later, we can apply another algorithm to detect which cells are at the boundary of sky and land, and replace them with vegetation and grass texture. And those at boundary, but below the landmass can be replaced with rock tiles.

After that, we can apply more algorithms to add/remove many features to make it eventually like a platformer.

Interesting features

Cellular automata is interesting in a way that we can allow user to modify the terrain by manipulating the cell states, this way, a Minecraft-like 2D modifiable world can be made.

Pathfinding on grid

The grid structure provides efficient structure for path finding algorithms such as A-star to work.

3D Cellular Automata

A useful approach to generating caves in 3D is to apply cellular automata rules on a voxel grid (3D grid) to generate a scalar field. Later, we can pass the scalar field into marching cubes to generate caves.

Procedural Terrain Generation

Terrain Creation

Terrain is often started using Perlin noise. The noise values are either directly modified using basic math functions to make ridges, terraces, etc. or are modified using erosion and other algorithms. Finally, this math-like data is fed into algorithms such as marching cubes or surface nets to generate the mesh from them.

I highly recommend starting from marching cubes for geometry generation. Below is an example mesh created with it:

A very simple approach on the other hand is to just start with a plain mesh and displace the vertices’ y-axis values based on noise. But this is not so useful for complex levels.

for vertex in my_mesh.vertices:
    vertex.y += perlin_noise(vertex.x, vertex.z)

Detailed Fractal Terrain

A basic technique to make terrain look detailed is by using layers of any noise function on top of previous layer; with the next layer having more frequency (smaller details). This however looks like generic terrain similar to how we find in other planets.

Approximating Erosion on Fractal Terrain

Running actual erosion algorithm is expensive since it requires all the terrain available (even those chunks which are not made). However, we can approximate the erosion-like effect much cheaper.

The technique is to set the intensity of next layer based on the steepness (slope) of previous layer/octave at a each point. So if the terrain is steep at a particular point, the intensity of next layer will be little at that point. It is a rough (but fast) approximation for erosion since in real world, water runs faster through steep slopes, and thus takes all the details/sediment with it.

Terrain topology functions

Different topology can be achieved by combinations of different mathematical functions applied on bare Perlin noise. Below, I’ll mention some of the basic ones. If we are aiming for ridges, dunes, canyons, terraces and so on, we need to pass our noise values through these functions, in order to modify the value.

1. For ridges:

vec3 ridges(vec3 value){ return -abs(value); }

This function inverts the noise after discarding its sign. We are assuming that noise value passed in it is in range(-1, 1).

2. For canyons: We apply power to our noise value to amplify its effect where noise value is greater & flatten the part where noise value is less. Noise values must be in range(0, 1).

vec3 canyons(vec3 noise_value, float power){
return pow(noise_value, power);
}

3. Terraces:

vec3 terrace(vec3 noise_value, float no_of_terraces){
    float step = 1.0 / no_of_terraces;
    return math.floor(noise_value / step) * step
}

4. Craters: These are circular depressions in map.

vec3 crater(vec3 noise, vec3 center, float radius):
    float distance = length(noise.xz - center);
    return noise.y * math.exp(-distance / radius);
}

You can experiment with more functions such as sqrt(), log() and so on.

Multiple topologies in single terrain

In a real video game, you often want some parts of map to be mountains, and some other as ridges. Yet you want some parts to be plains only. For this, you need to use another sample of Perlin noise. You will use this new noise for controlling the intensity of different functions across your world.

Note that if you simply use noise value ranges & if-statements to find where to put your mountains or plains, you’ll get discontinuity in terrain where borders meet. So one solution to deal with this is to sample a different noise for each topology’s intensity.

Erosion

After you have created a general terrain using noise & other mathematical functions, it is a good idea to apply effects such as erosion. There are algorithms to approximate erosion that result in a very realistic & better looking terrain. Here is a hydraulic erosion algorithm applied on a heightmap.

Procedural Object Generation

L systems is a descent approach to get started.

Modifying & Improving our World

More things such as erosion, roads, rocks, tree placements and so on (above our base world).

Vegetation Placement

Placement of vegetation can be done using poisson disc sampling, which ensures user-defined separation between vegetation is met & trees or bushes do not clump. Clumping typically occurs when we use noise functions.

Navigating a Procedural World

A* algorithm, ACO and so on.

More Links

1. https://www.redblobgames.com/maps/terrain-from-noise/
2. http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/

Gallery