Procedural Generation

Summary

Procedural generation (PCG) uses algorithms rather than hand-authoring to create game content — terrain, flora, dungeons, textures, music, and more. The goal is content that is varied, scalable, and feels organic without requiring an artist or designer to manually produce every instance. The core tools are probability distributions, noise functions, recursive grammars, and simulation rules. Yannakakis and Togelius treat PCG as one of the central AI-in-games pillars, not merely as a content trick. (Yannakakis and Togelius, Artificial Intelligence and Games, see source-ai-and-games)

PCG offers: enhanced replayability, reduced development time and costs, and the capacity to generate vast diverse game worlds. Modern PCG increasingly uses ML (PCGML) for more dynamic content generation.

(Shiffman, The Nature of Code, Chs. 0, 8, see source-nature-of-code; Prof Charles, CRE341 Wk 6.1, see source-cre341-lectures)

Unity/C# translation note

Most Nature of Code procedural examples are written in JavaScript with p5.js, where drawing and simulation happen inside one lightweight draw() loop. In Unity, the algorithm stays the same, but the implementation usually shifts into Update(), a coroutine, or a grid/texture workflow. So the important translation is not syntax-for-syntax. It is:

• keep the same simulation rule
• separate data update from rendering
• use Unity’s own drawing surface such as sprites, Texture2D, Tilemap, or meshes

For the current Unity route through this material, see overview-unity-nature-of-code-examples and the random-walk example at RandomWalker2D.cs.

---

PCG history

• Elite (1984) — Guinness World Record for first use of procedural generation in a video game; generated eight 3D galaxies each containing 256 procedurally generated star systems
• Daggerfall (1996) — 161,600 km² of explorable terrain via procedural generation
• Roguelikes — influenced by Dungeons & Dragons; PCG dungeons with rooms, corridors, monsters, and treasure; conserved memory and increased replayability with unique layouts per playthrough

(Prof Charles, CRE341 Wk 6.1, citing Guinness World Records 2023)

---

Randomness — the starting point

All procedural generation starts with controlled randomness. Plain uniform random (Random.Range in Unity, random() in p5.js) produces every value with equal probability. This is appropriate for dice rolls and shuffles but produces unnatural results for motion and texture — nature clusters around means, varies smoothly over space, and rarely visits extremes.

---

Probability distributions

Gaussian (normal) distribution

Values cluster around a mean (μ) with spread controlled by standard deviation (σ):

• 68% of values within 1σ
• 95% within 2σ
• 99.7% within 3σ

// Unity — Gaussian via Box-Muller transform
float GaussianRandom(float mean, float stdDev)
{
    float u1 = 1f - Random.value;
    float u2 = 1f - Random.value;
    float z  = Mathf.Sqrt(-2f * Mathf.Log(u1)) * Mathf.Sin(2f * Mathf.PI * u2);
    return mean + stdDev * z;
}

Use for: particle sizes, NPC attribute generation, spawn spread, weapon recoil.

Monte Carlo accept-reject

Generate custom arbitrary distributions by sampling a candidate value and accepting it with a probability equal to a qualifying function evaluated at that point:

float AcceptReject()
{
    while (true)
    {
        float r1 = Random.value;         // candidate x
        float r2 = Random.value;         // qualifying draw
        float p  = r1 * r1;              // e.g. quadratic — higher values more likely
        if (r2 < p) return r1;
    }
}

Use for: procedural loot tables biased toward middle values, terrain slope distributions, encounter rarity curves.

---

Perlin noise

Ken Perlin developed this function in 1983 for Tron’s procedural textures; it won an Academy Award for technical achievement. Unlike uniform random, noise returns values that are smooth and correlated — nearby positions in noise space return nearby values.

1D noise: smooth animation

float t = 0f;
 
void Update()
{
    float n = Mathf.PerlinNoise(t, 0f);          // 0–1
    float x = Mathf.Lerp(0f, Screen.width, n);
    t += 0.01f;                                   // small step = smooth change
}

Step size controls smoothness: small (0.005) = silky; large (0.5) = jittery. The function is deterministic — same input always returns same output.

2D noise: terrain and textures

Sample noise at (x * scale, y * scale) across a grid to get a height map:

float[,] GenerateHeightMap(int width, int height, float scale, float offsetX, float offsetY)
{
    float[,] map = new float[width, height];
    for (int x = 0; x < width; x++)
    for (int y = 0; y < height; y++)
        map[x, y] = Mathf.PerlinNoise(
            offsetX + x * scale,
            offsetY + y * scale
        );
    return map;
}

Random offsetX/offsetY seeds produce different terrain each run. Combine multiple scales (octaves) for more detailed terrain:

// Octave noise (fractal noise / fBm)
float OctaveNoise(float x, float y, int octaves, float persistence, float lacunarity)
{
    float value = 0f, amplitude = 1f, frequency = 1f, maxValue = 0f;
    for (int i = 0; i < octaves; i++)
    {
        value    += Mathf.PerlinNoise(x * frequency, y * frequency) * amplitude;
        maxValue += amplitude;
        amplitude  *= persistence;   // how much each octave contributes
        frequency  *= lacunarity;    // how much detail each octave adds
    }
    return value / maxValue;
}

Use for: terrain height maps, cloud textures, water surface animation, cave density, wind simulation.

Noise vs. random — the key distinction

	Uniform random	Perlin noise
Consecutive values	Uncorrelated	Smooth transition
Range	Specified min–max	0–1 (approximately)
Deterministic	No (seeded pseudorandom)	Yes (same input → same output)
Best for	Discrete events, shuffles	Continuous animation, terrain, texture

---

Fractals and L-systems

A fractal is a shape with fine structure at any scale — zooming in reveals the same pattern. Most natural shapes (coastlines, trees, clouds, ferns) are fractal. Two generation approaches:

Deterministic recursion

Apply the same transformation rule recursively until a minimum size is reached:

void DrawBranch(Vector3 start, Vector3 direction, float length, int depth)
{
    if (depth == 0) return;
 
    Vector3 end = start + direction * length;
    Debug.DrawLine(start, end);
 
    float angle = 25f * Mathf.Deg2Rad;
    DrawBranch(end, Rotate(direction,  angle), length * 0.7f, depth - 1);
    DrawBranch(end, Rotate(direction, -angle), length * 0.7f, depth - 1);
}

Always include an exit condition — the recursive call doubles the branch count each level; at depth 10, that is 1,024 simultaneous branches.

Stochastic fractals: randomise the angle and branching count each call. The result looks far more natural than the perfectly symmetric deterministic version.

L-systems (Lindenmayer systems)

A formal grammar that generates complex organic shapes by repeatedly applying character substitution rules to an initial string, then interpreting that string as drawing commands.

Three components:

1. Alphabet: Valid characters. F = draw forward; + = turn right; − = turn left; [ = save state; ] = restore state.
2. Axiom: Starting string, e.g. "F".
3. Rules: Substitution map, e.g. F → FF+[+F-F-F]-[-F+F+F].

Three iterations of the rule above:

• Step 0: F
• Step 1: FF+[+F-F-F]-[-F+F+F]
• Step 2: (substituting each F again) → long complex string
• Step 3: → the string now encodes a recognisable branching plant

string LSystemGenerate(string axiom, Dictionary<char, string> rules, int generations)
{
    string current = axiom;
    for (int i = 0; i < generations; i++)
    {
        System.Text.StringBuilder next = new();
        foreach (char c in current)
            next.Append(rules.ContainsKey(c) ? rules[c] : c.ToString());
        current = next.ToString();
    }
    return current;
}
 
void DrawLSystem(string sentence, float angle, float length)
{
    Stack<(Vector3 pos, Vector3 dir)> stateStack = new();
    Vector3 pos = Vector3.zero, dir = Vector3.up;
    foreach (char c in sentence)
    {
        switch (c)
        {
            case 'F': Debug.DrawLine(pos, pos + dir * length); pos += dir * length; break;
            case '+': dir = Rotate2D(dir,  angle); break;
            case '-': dir = Rotate2D(dir, -angle); break;
            case '[': stateStack.Push((pos, dir)); break;
            case ']': (pos, dir) = stateStack.Pop(); break;
        }
    }
}

Notable L-system results:

• Sierpiński triangle: Axiom A, Rules A→B-A-B, B→A+B+A
• Dragon curve: Axiom FX, Rules X→X+YF+, Y→-FX-Y
• Koch snowflake: Axiom F--F--F, Rule F→F+F--F+F
• Barnsley fern (stochastic version)

Use for: procedural flora, branching cave networks, lightning/crack effects, alien/organic UI decoration.

---

Procedural techniques by use case

Content type	Primary technique
Terrain heightmap	Perlin noise (octaves / fBm)
Cave / dungeon layout	Cellular automaton (smooth + threshold) → see cellular-automata
Organic flora	L-systems; stochastic fractal trees
Texture / surface detail	2D Perlin or Worley noise
Enemy patrol paths	Random walk biased by territory
Loot rarity	Monte Carlo accept-reject; Gaussian distribution
Crowd / ambient motion	Perlin noise for position offsets
Cloud / fog	2D or 3D Perlin noise sampled over time

---

In practice (Unity)

Unity provides Mathf.PerlinNoise(x, y) natively. For:

• Terrain generation: use Terrain.terrainData.SetHeights(0, 0, heightMap)
• Tilemap generation: map noise output to tile types with thresholds
• Animation variation: offset idle animations with Perlin noise instead of Random.value

Procedural generation in Unity typically combines:

1. A noise function or distribution for values
2. A threshold or mapping function to convert to game content
3. A seed to make runs reproducible for debugging

// Seeded reproducible noise
Random.InitState(seed);
float offsetX = Random.value * 9999f;
float offsetY = Random.value * 9999f;
// then use offsetX/offsetY as Perlin noise offsets

Random walk as the simplest Unity translation

Before Perlin noise, L-systems, or cave generation, the simplest procedural-movement example is a random walker. It shows how a tiny rule set can still produce visible trails and coverage patterns over time.

• RandomWalker2D.cs — one walker taking one random step at a fixed interval
• WalkerBootstrap.cs — spawns a small population of walkers for pattern comparison

This is intentionally simpler than most production procgen systems, but it is a very good first bridge between the book’s examples and Unity scene work. See overview-unity-nature-of-code-examples for the wider sequence.

---

Terrain generation algorithms

A comparison of algorithms used to generate landscape heightmaps and features (Prof Charles, CRE341 Wk 6.1):

Algorithm	Key characteristics	Example games
Perlin Noise	Smooth, continuous noise; basic terrain shapes	Minecraft
Simplex Noise	More efficient than Perlin; fewer artefacts in higher dimensions	No Man’s Sky
Diamond-Square	Fractal-like terrain; varied levels of detail	Minecraft
Midpoint Displacement	Realistic valleys and hills	7 Days to Die
Erosion Simulation	Realistic canyons and riverbeds	Dwarf Fortress
L-systems	Realistic trees and vegetation	SpeedTree middleware

For noise details and Unity implementation, see the Perlin noise section above.

---

Dungeon generation algorithms

(Prof Charles, CRE341 Wk 6.1)

Binary Space Partitioning (BSP)

Recursively divides space into smaller sub-spaces, generating a tree-like structure that creates rooms and corridors. Produces dungeons with a clear hierarchy and distinct areas. Each division becomes a potential room; corridors connect adjacent nodes.

Random walk algorithm

Simulates a random path through a grid, generating winding corridors and interconnected rooms. Results in more organic and less predictable layouts. Risk: dead ends or confusing paths if not managed carefully.

Dungeon “growing” algorithm

Begins with a single room and adds new rooms and corridors one at a time. The dungeon “grows” outwards, adapting to the existing layout. Produces natural, interconnected spatial feel. Good for mid-scale dungeons.

Room chunks (Spelunky approach)

Pre-designed room templates (chunks) are assembled procedurally. Each template guarantees playability and spatial quality; the assembler ensures connectivity. Combines hand-design quality with PCG variety. Spelunky is the canonical example — the designer provides chunks, the algorithm assembles the level.

Choosing an algorithm

Goal	Recommended algorithm
Hierarchical, readable rooms	BSP
Organic, cave-like corridors	Random walk
Natural, growing spatial feel	Growing algorithm
High production quality + variety	Room chunks

---

Related

• source-nature-of-code — primary source (Chs. 0, 8)
• source-cre341-lectures — terrain/dungeon algorithm comparison; PCG history
• cellular-automata — cave generation and emergent texture
• steering-behaviours — flow fields powered by Perlin noise
• systems-thinking — emergence framework; procgen as second-order design
• second-order-design — the designer creates rules; the algorithm makes the content
• randomness-in-games — when randomness in generated content affects player fairness
• internal-economy — procedurally generated loot must respect economy balance
• machine-learning-games — PCGML: applying ML to content generation
• overview-unity-nature-of-code-examples — Unity/C# path for practical Nature of Code examples