Lecture 1 – Terrain Generation

Procedural Content Generation for Computer Games

Vojtěch Černý

cerny@gamedev.cuni.cz

Terrain generation

• Arguably the most common form of PCG
• Why do it?
• Cost-efficiency
• Consistency
• High-level of detail
• Works well as mixed-initiative
• Infinite worlds
• Exploration as a game mechanic
• It is fun

No Man’s Sky

Minecraft

Different kinds of terrain generation

• By approach:
• Teleological / Ontological
• By timing:
• Design time / Runtime
• By representation:
• Tilemaps
• Heightmaps
• Meshes
• …

​

TileMaps

• Quite simple for 2D games; assign a tile (integer) to each grid position

Transition from left to right with ordering of tiles and authoring overlaps

HeightMaps

• Each point in a grid has an assigned height value
• Tilemaps can be just a discretization of height-maps

​

Pros: Quite simple to handle, good results

Cons: Cannot generate overhangs, caves, etc.

height visualized as brightness

HeightMaps�Simple approaches

Fault formation

• Start with a grid of height 0
• Randomly create a line across the cell. Increase height of points on one side by an amount.
• Iterate previous step with continuously decreasing amount
• Apply filter in the end

Hills-adding

• Add random hills (parabolas) to a flat terrain until satisfied hills cannot be distinquished

Particle deposition

• Add a unit of height on a random spot
• This unit will fall “down” on a neighboring square, if there is one that is at least two units of height lower

Diamond-square algorithm

• Improvement on midpoint-displacement algorithm
• Start with low-resolution height-map
• Alternate performing „diamond-step“ and „square-step“

Diamond-square algorithm

• Results are impressive, given the simplicity of the algorithm
• Can be used as mixed-initative (smooth-out given heightmap)

HeightMaps�Noise approaches

Noise functions

• White noise isn’t practical as a heightmap
• Can we make it smoother?
• Simple approach - interpolate

White noise

Bilinear interpolation

Octaved

Smooth interpolation

This approach is called value noise

Side-note: Octaves

• A single noise function usually either:
• Has no low-level details
• Has no large-scale variations

​

• This can be solved by combining multiple instances with different frequencies and scales
• The parts are usually called „octaves“
• Can be used on many kinds of noise
• (even value noise with octaves is usable)

Perlin noise

• (Ken Perlin, 1983)
• The first of gradient noise algorithms – generate random gradients and interpolate

​

​

​

• Fewer plateaus than value noise

​

​

Perlin noise

Gradient interpolation explained

Perlin noise

Gradient interpolation explained

Perlin noise

Gradient interpolation explained

Perlin noise

Gradient interpolation explained

For interpolation, use smoothstep (Perlin, 1983)

or smootherstep (Perlin, 2002)

• Due to starting in 2D grid,

Perlin noise often has visible directional artifacts by both axes

Perlin noise

Simplex noise

• (Ken Perlin, 2001)
• Improvement over the original algorithm, by:
• Removing directional artifacts
• Better performance, better scaling to higher dimensions (4D, 5D)
• Simply computable gradients at any point
• Easy hardware implementation

​

• The algorithm is a little more complex, so we won‘t go into detail here
• However, usually a very solid choice
• There exists an open source implementation called OpenSimplex

​

Simplex noise

Single Octave

Multiple Octaves

Value noise

Perlin noise

Simplex noise

Cellular noise

• Steven Worley, 1996
• Start with random points
• Take distance to n-th closest
• With tweaking, can look like:
• Water
• Stone
• Biological cells

​

Cellular noise, taking 2nd closest

Domain warping

• Inigo Quilez (iquilezles.org)
• Offset the positions by another noise function
• Better distribution of gradients

​

​

f(p) = noise(p + noise(p))

f(p) = noise(p + noise(p + noise(p)))

Ridged noise

• Noise functions tend to generate smooth mountain tops, which isn’t very realistic
• To combat, you can use an ABS function to noise in the range (-1, 1), and then invert (so you have ridged mountains instead of valleys)

Billow noise

• Using just ABS is called billow noise
• Useful for rocks / clouds / …

Analytical derivatives

• Inigo Quilez
• Both value and gradient noise can be computed with derivatives
• Useful for lighting and even to modify noise in low-level octaves
• E.g. Lengthening the features on the slopes, smoothening slopes

​

Advantages of noise functions

• Very low cost of resources
• Usually nothing needs to be stored
• Computation is quite effective
• Modifiable, constrainable
• Combinable

​

​

​

​

Limitations of heightmaps

• Cannot create caves, natural bridges, etc.
• Workarounds:
• Only use heightmaps as a first step, then sculpt by other methods
• May even treat “overhangs” as not terrain
• Create e.g. three heightmaps, use one as bottom layer, second as ceiling, third as a new bottom layer
• Don’t use heightmaps ☺

Limitations of heightmaps

• Remember that there are two different triangulations of a square

Non-linear triangulations

• Michael Garland and Paul S. Heckbert (1995)

Original

Triangulated using 5% of points

Side-note: Biomes

• Large(r) scale partitions of game-world with different terrain properties
• e.g. Mountains, Grasslands, Deserts, Sea, etc.
• Good to increase the variability of terrain

​

​

Biomes of Map from Outer Colony

HeightMaps�Non-noise approaches

Terrain with Cellular Automata

• Jason Cawley, 2011
• 2018 ProcJam submission by twillacy

Simulation

• Heightmaps generated by noise still don’t look very real
• Real-life terrain is shaped by erosion

-> erosion simulation (wind / water)

​

Rarer approaches

• Geological simulation (erosion, tectonic uplift, …)
• Agent based simulation
• AI methods (e.g. GANs)
• Grammar based methods

​

Figure 2 of Interactive Example-Based Terrain Authoring with Conditional Generative Adversarial Networks by Guérin et al.

Non-heightmaps

Three-dimensional approaches

• Random walk
• Perlin worms
• Use 3D noise
• Cellular automata
• Agent-based approaches (miners)

Random walks

• Perlin noise might be used to smoothen a random walk
• Map linear noise to 0-360º, and use it as a sequence of directions

​

Perlin worms

• Apparently what Minecraft and NMS use to generate caves
• (Small) threshold of noise

3D Noise

• Most of the previous notes on noise still apply
• The 3D noise is coupled with a threshold (or multiple) to select where there will be mass and where there won’t
• Converting this 3D array to triangles is slightly more complicated
• Marching Cubes algorithm
• Dual Contouring algorithm
• Can be combined with 2D noise
• No Man’s Sky does this extensively

Summary

• Noise is your friend
• Modify, mix, experiment
• 2D and 3D noise can work well together
• Noise + other methods

​

Q & A

Vojtěch Černý

cerny@gamedev.cuni.cz