Module 11 · AI/ML in games

PCG: noise and dungeons

Procedural generation is constrained randomness, not chaos. And the workhorses here are classical, not ML: Perlin/Simplex noise for terrain, L-systems for plants, BSP for dungeons, grammars for levels. GANs for content live on the frontier and usually lose — because they don't guarantee playability.

~16 min🎲 PCG + when ML is unnecessary🏠 lab

The gist in 30 seconds

PCG = constrained randomness, not chaos, and its workhorses are classical. Noise (Perlin 1985 / Simplex 2001, patent expired in 2022 → OpenSimplex): continuous smooth fractal pseudo-randomness — stack octaves (fBm) for terrain, O(1) per sample. L-systems: string rewriting grammars → fractal plants/branching. BSP: recursively split the space → guaranteed-connected dungeon rooms. Grammars: define a grammar of a valid level, sample and check the constraints. The key insight (Spelunky): the constraints are baked into the generation itself (the exit is always reachable, difficulty grows with depth) — "generate-with-constraints" beats "generate-then-check". ML PCG (GANs for levels) exists on the research frontier but usually loses: the output is often invalid (mismatched tiles, impassable), constraints are hard to impose, and it's slower. For most content, hand-written generative rules + noise + constraints beat a trained generator — this is the content version of "classical > ML".

The mechanism: smooth randomness and baked-in constraints

Perlin/Simplex noise

A plain random() gives you "snow" — neighboring values are independent. Terrain needs smooth randomness: nearby points have nearby heights. Perlin noise: random gradient vectors at the lattice nodes; for a point you take dot products of the gradients with the offset vectors to the nodes and interpolate smoothly → a value in $[- 1, 1]$ . One octave gives smooth hills; detail comes from octaves (fBm) — a sum of copies of the noise with rising frequency and falling amplitude:

fBm (x) = \sum_{i = 0}^{k - 1} p^{i} \cdot noise (l^{i} x)

( $l$ is lacunarity, the frequency multiplier; $p$ is persistence, the amplitude multiplier, usually $l = 2$ , $p = 0.5$ ). The large octaves set the mountains, the small ones the rocks and ripples: exactly the fractal terrain of Minecraft. Fast (O(1) per sample, precomputable), parameterizable, comprehensible. Simplex (Perlin, 2001) is faster and free of directional artifacts; its 3D+ patent expired on Jan 8, 2022, and OpenSimplex (Kurt Spencer, 2014) is a clean-room patent-free alternative.

L-systems, BSP, grammars

L-systems — string rewriting rules: axiom F, rule F → F[+F]F[-F]F, iterate, interpret as turtle graphics (F — forward, [] — position stack, ± — turn). Recursion in the rules produces tree-like branching — procedural vegetation.
BSP (Binary Space Partition) — recursively split a rectangle, rooms in the leaves, corridors between neighbors. It guarantees connectivity (a corridor exists), has a natural hierarchy, O(n). The dungeons of Rogue/Diablo/roguelikes.
Level grammars — Level → Entrance Room+ Boss Exit: you sample from the grammar and check the constraints (the exit is reachable, difficulty is balanced).

The main insight: constraints baked into generation (Spelunky)

Spelunky (2008) shipped with procedural levels that feel hand-made. The secret is constraint satisfaction during generation, not after: the generator guarantees a path to the exit, rising difficulty with depth, no dead ends — because the constraints are baked into the process rather than checked afterwards. "Generate a level, then check whether it's valid" loses to "generate in a way where validity cannot be broken". Hence the definition: PCG isn't "random", it's constrained randomness, where the constraints are what deliver the quality.

And GANs? A frontier that usually loses

ML-augmented PCG exists: train a GAN on levels (the Mario-level papers, Volz et al.) — it learns the distribution of "good" levels and can interpolate. But in practice, for shippable content, it loses to the classics: the output is often invalid (mismatched tiles, impassable), hard constraints are hard to impose (a level must be traversable — and a GAN gives no guarantees), and it's slower. ML PCG is useful in spots (style blending, augmentation, textures), but structural, constraint-bound content is almost always cheaper and more reliable to generate classically — it's the same story as with RL agents, only about content.

🏠 Lab — noise and terrain, live

An interactive lab with no code: 2D Perlin noise → a heightmap colored like terrain (water/sand/grass/rock/snow). Turn the frequency, the number of octaves, lacunarity and persistence — and watch mountains and detail emerge out of smooth hills (fBm live). Change the seed. Open the lab →

The fBm formula and the Perlin/Simplex/OpenSimplex differences are in the text and the deep end; here it's about seeing the octaves with your hands.

🕹 What to play — and what to notice

Minecraft / No Man's Sky noise as terrain

The Minecraft world is Perlin/Simplex noise over height (+ caves from 3D noise); NMS generates planets with the same machinery. Large forms + small detail = fBm octaves.

🎮 Notice: in Minecraft, fly up high and look at the hierarchy of scales: big hills (a low octave) with bumps and ripples laid over them (high octaves). That is literally the sum of octaves from the formula. And the whole world isn't stored, it's computed from a seed (store the function, not the output — as in hardware).

Spelunky constrained randomness

Every level is unique and yet always traversable: the path to the exit is guaranteed by generation, difficulty grows with depth. It feels hand-made even though it's procedural.

🎮 Notice: play a few Spelunky levels and confirm it — the exit is always reachable, there are no trap dead ends. That isn't the generator getting lucky, it's a baked-in constraint. Compare with how a "random" level with no constraints would feel (an impassable mess). That's the difference between "constrained randomness" and "just random".

A roguelike a BSP dungeon

Classic roguelikes (and Diablo) build dungeons with BSP: recursive splitting → rooms in the leaves → corridors between neighbors. Always connected, cheap, "looks good".

🎮 Notice: in a roguelike, look at the dungeon map: rooms grouped hierarchically, joined by corridors, no isolated regions. That's the fingerprint of a BSP tree. A simple deterministic algorithm gives you a connected, playable level with no learning at all.

Deep end · value vs gradient noise, octaves, Simplex/OpenSimplexskippable

Value noise vs gradient noise

Value noise: random values at the lattice nodes + smooth interpolation (smoothstep). Simple, but it shows visible lattice "blockiness". Gradient noise (Perlin): random gradients at the nodes, the value = an interpolation of dot products gradient·(point−node); it's zero at the nodes with smooth extrema in between → visually richer, fewer axis artifacts. fBm on top of either: $\sum_{i = 0}^{k - 1} p^{i} noise (l^{i} x)$ — octaves add detail at shrinking scales; for $p < 1$ the series converges and the spectrum follows a power law (hence "fractal"/natural). Variations: ridged (|noise|, sharp ridges), domain warping (noise of coordinates that were themselves distorted by noise — rivers/veins).

Simplex, the patent and OpenSimplex

Classical Perlin on a cubic lattice needs $2^{n}$ corners in $n$ D (8 in 3D, 16 in 4D) and produces directional artifacts along the axes. Simplex (Perlin, 2001) puts the nodes on a simplex lattice → $n + 1$ corners (4 in 3D), fewer multiplications, better scaling into high dimensions, no axis artifacts. The catch: 3D+ use of Simplex was patented (US 6,867,776), so many engines stuck with Perlin for years; the patent expired on Jan 8, 2022. OpenSimplex (Kurt Spencer, 2014) is a clean-room free alternative, also gradient noise, without Perlin's artifacts. In practice: take Simplex/OpenSimplex for speed and isotropy, Perlin if it's already good enough.

Deep end · why the classics beat GANs, and the link to constrained decodingskippable

Validity as a hard constraint

Game content almost always has hard invariants: a level must be traversable, tiles must fit together, a dungeon must be connected. Classical PCG bakes them into generation (BSP guarantees connectivity by construction; Spelunky guarantees the path to the exit; WFC guarantees neighbor compatibility). A GAN learns a soft distribution of "looks like a good level" and easily violates hard invariants — and after-the-fact checking + resampling is expensive with no guarantee of convergence. Plus control: noise/grammars have knobs (frequency, rules, seed), a GAN has a latent that's hard to connect to "make the passage wider". So for structural content the hand-written generator + constraints wins; ML enters where the distribution is too rich for hand-written rules (textures, natural images, dialogue) and there are few hard invariants.

The same trick in LLMs: constrained decoding

"Generate-with-constraints > generate-then-check" is literally structured/constrained generation in LLMs: grammar-constrained decoding, JSON-schema/regex enforcement, masking inadmissible tokens at every step guarantee valid output by construction, instead of "generate freely → parse → reject → repeat". That's exactly the Spelunky insight carried over to token generation: bake the invariant into the process. And fBm/octaves ↔ the role of structural priors and multiscale/frequency decompositions in ML (Fourier features, positional encodings, multi-resolution). The meta-lesson is general: a cheap algorithmic generator with constraints often beats an expensive trained one when the domain has hard validity rules.

Analogy

Procedural generation is like a jazz musician improvising within a key and a harmony: it's precisely the constraints (key, tempo, form) that turn endless variation into music rather than noise. Perlin noise is the smooth melodic contour; octaves are added harmonics for texture; L-systems are recursive motifs; Spelunky's constraint satisfaction is the musician not leaving the key and the form, so any improvisation is playable. A GAN generating levels is like an AI that learned to imitate jazz from recordings but occasionally plays unresolved notes or a bar in the wrong meter: impressive, but you can't put it on stage without a human fixing the broken bars. Constrained randomness ships; untrained generation needs a babysitter.

Why it matters

This is the content half of the course's main judgment (the agent half came from RL): for structural content bound by hard rules, classical generative methods + constraints beat a trained generator on validity, control and cost. For you as an ML engineer it's both a practical skill (noise/grammars/WFC are cheap and reliable for your Novgorod) and a transfer: "generate-with-constraints" is constrained decoding in LLMs, and "store the function, not the output" is about memory and cost. Knowing when an algorithmic generator beats a neural network is part of the same maturity.

🔁 Where this leads — ties to your ML work

The lesson is about constrained randomness: generation where validity is baked into the process, and about when an algorithm beats a trained generator.

ML / AI (your domain): PCG-vs-GAN is the content side of the whole thesis: for structural generation with hard invariants, hand-written rules + constraint satisfaction beat a trained generator (validity, control, cost). The direct bridge is constrained/structured decoding in LLMs: grammar/JSON-schema/regex enforcement and token masking guarantee valid output by construction — exactly "generate-with-constraints > generate-then-check-and-retry" (the Spelunky insight at the token level). The general pattern is a generative model + hard constraints (diffusion with guidance, program synthesis with types, constrained sampling). fBm/octaves ↔ structural priors and multiscale/frequency decompositions (Fourier features, positional encodings). "Store the function, not the output" (a world from a seed) ↔ implicit representations/INRs and compression as generation. And the meta-lesson — an algorithmic generator with constraints is often better than a trained one when the domain is structural — is the same "when ML isn't the answer" discipline as in RL agents, only about generation.

Design/content: constrained randomness = controlled variety; knobs (frequency, rules, seed) matter more than "magic" — reproducibility and editability.

Systems: "store the function, not the output" — generating on the fly saves memory/bandwidth (a world from a seed), with deterministic reproducibility by seed.

Principle: for structural content take algorithm + constraints by default; ML where the distribution is too rich for rules and there are few hard invariants; bake validity into the process rather than checking it afterwards.

🔧 Run it and poke at it

🏠 The "noise and terrain" lab in the browser

Open lab-noise.html: turn the frequency, octaves, lacunarity, persistence — see fBm live (one octave = smooth; many = mountains+detail). Change the seed. Set it to 1 octave and add them one at a time, watching the fractal terrain emerge.

🧪 Build a generator ~40 min, optional

Write a BSP dungeon (recursive splitting + corridors) in Python/JS — a few dozen lines, always connected. Or an L-system for a tree (string rewriting + turtle). Then add one hard constraint (say, a minimum room size / a traversability guarantee) directly into the generation — feel "constrained randomness". Compare with the naive "scatter things randomly and hope".

Checklist: saw octaves/fBm and the role of lacunarity/persistence in the lab; understood "constrained randomness" through Spelunky/BSP; connected constrained generation with constrained decoding in LLMs; articulated where ML is NOT needed for content.

Connections

foundation

Wave Function Collapse — the constraint sibling: generating tile worlds through satisfaction of adjacency constraints.

parallel

RL agents — the agent version of "classical > ML"; this is the content version.

summary

Classical vs ML — where to bring ML into generation and where an algorithm is better.

Hardware constraints — "store the function, not the output": a world from a seed instead of gigabytes.

Questions worth asking

Perlin, Simplex, OpenSimplex — which one do you take?

All three are gradient noise (smooth randomness via gradients at the nodes), differing in lattice and history. Perlin (1985) — on a cubic lattice; the simplest, but it needs

2^{n}

corners in

n

D and produces mild directional (axis) artifacts — the lattice sometimes "shows through". Simplex (Perlin, 2001) — on a simplex lattice (

n + 1

corners), faster in high dimensions, no axis artifacts; but its 3D+ use was patented, so many libraries avoided it for years. OpenSimplex (Kurt Spencer, 2014) — a clean-room free alternative to Simplex, also artifact-free, created specifically to route around the patent. The Simplex patent expired on Jan 8, 2022, so legally it's fine now too. In practice: in 2D the difference is small — Perlin is enough; for 3D/4D (volumetric caves, noise animated over time) take Simplex/OpenSimplex for speed and isotropy. In image quality Simplex and OpenSimplex are interchangeable; the choice usually comes down to which library you have.

Why is PCG called "not random"?

Because a plain random() gives garbage for content: incoherent terrain, impassable levels, blob trees. PCG that works is constrained randomness: the randomness is there, but it runs in channels set by structure and constraints. The smoothness of noise (nearby points → nearby heights) is a constraint on the "randomness" of terrain. BSP connectivity (there is always a corridor between neighbors) is a hard invariant. Spelunky's traversability is a baked-in rule. Neighbor compatibility in WFC is a constraint. It's the constraints that turn "noise" into "a world that feels made". Hence the practical shift in thinking: not "I'll generate randomly and see", but "which invariants must hold, and how do I build them into generation so they cannot be broken?". Randomness gives variety; constraints give quality; PCG is their product.

Do GANs really lose to the classics for levels?

For shippable structural content — yes, usually. Research (Mario-level GANs, Volz et al. and others) showed a GAN can learn a distribution of levels and generate sometimes playable ones — but three problems hit production: (1) validity — the output is often invalid (mismatched tiles, impassable sections), and a GAN gives no hard "it's traversable" guarantee; (2) constraints — imposing "the exit must be reachable" on a latent model is hard, so you check and resample afterwards (expensive, with no guarantee of convergence); (3) control and cost — a grammar/noise has legible knobs and is cheap, a GAN has a latent and inference. So in production almost everything is classical (noise, grammars, BSP, WFC, constraint solvers). Where ML PCG does help: blending/interpolating styles, augmentation, generating textures and assets (a rich distribution with few hard invariants — perfect for a network), style transfer. That is, ML enters "soft" generation (how it looks), the classics hold the "hard" part (how it's built and how it plays). That's exactly the line: "a rich distribution with no hard rules → ML; structure with invariants → an algorithm".

How does "generate-with-constraints" carry over to LLMs?

It's literally constrained / structured decoding. The Spelunky insight — "bake validity into generation rather than checking afterwards" — at the token level means: at every decoding step mask the tokens that would break the grammar/schema, leaving the model a choice only among valid continuations. Grammar-constrained decoding (over a formal grammar), JSON-schema/regex enforcement (llguidance, Outlines, GBNF in llama.cpp) guarantee constructively valid output — it always parses, no retries needed. The alternative, "generate freely → parse → if broken, repeat", is exactly "generate a level → check → reject", which loses both in games and in tokens (expensive, with no guarantee). The more general pattern is a generative model + hard constraints inside the process: diffusion with guidance/projection onto the feasible set, program synthesis with type checking at every expansion, constrained sampling. Once you've got "PCG = constrained randomness", you already understand why constrained decoding is more reliable than free generation with a post-check: a constraint built into the process can't be violated, while an after-the-fact constraint can, and it costs an expensive retry.