Procedural Terrain Generation

Most terrain generation tutorials start with noise. Layer some octaves of Perlin, call it "fractal brownian motion," and you get something bumpy that looks vaguely like terrain from ten thousand feet up. But zoom in and it falls apart — the mountains don't have ridges, the rivers don't carve valleys, the coastlines are blobby. The fundamental problem is that noise creates texture without process. Real terrain is the product of physical forces acting over time: uplift, erosion, sedimentation. Getting terrain that feels right means simulating at least a sketch of those processes.

Beyond Noise: Process-Based Approaches

Martin O'Leary's fantasy map generator for @unchartedatlas is one of the clearest demonstrations of how far you can get with lightweight physics.¹ Rather than generating a heightmap from noise directly, O'Leary works on an irregular Voronoi mesh — random points, Lloyd-relaxed for evenness — and builds terrain in stages. First, geometric primitives (slopes, cones, blobs) establish a rough proto-landscape. Then erosion sculpts it into something plausible.

The choice of an irregular mesh over a square grid is itself instructive. Regular grids produce axis-aligned artifacts that require postprocessing to hide. An irregular grid introduces organic roughness for free — the mesh structure does visual work that noise would otherwise have to. The dual Voronoi mesh (working with polygon corners rather than centers) fixes the neighbor count at three per node, which simplifies the erosion math considerably.

Erosion is where the magic happens. O'Leary routes water downhill from every grid point, accumulates flow, and uses the product of slope and the square root of water flux as an erosion rate. That's not a rigorous geomorphology simulation — real fluvial erosion involves sediment transport, bedrock resistance, tectonic feedback — but it produces convincing ridges, valleys, and river networks from a few lines of code. The rivers emerge naturally from flow accumulation: you just threshold the water flux and draw the paths. The trick of relaxing river points toward their upstream and downstream neighbors to smooth out zigzag artifacts is the kind of small detail that separates good procedural work from great.

One subtle problem: local minima. Water that flows into a pit with no outlet forms a sink that breaks the drainage network. O'Leary uses the Planchon-Darboux algorithm to fill depressions — find the lowest surface that's everywhere at least as high as the original and has every non-edge point draining to a lower neighbor. It's the kind of problem that sounds trivial until you try to handle connected networks of depressions, at which point the combinatorics explode and you need a proper algorithm.¹

Particle-Based Hydraulic Erosion

Nick McDonald's particle erosion system takes a different approach — instead of routing water across an entire grid simultaneously, it drops individual particles onto the surface and simulates each one.² A particle has position, velocity, volume, and sediment concentration. It slides downhill via classical mechanics (acceleration proportional to the surface normal), picks up or deposits sediment based on mass transfer equations, and evaporates over time.

The beauty of this approach is in the mass transfer model. Sediment exchange between the particle and the ground follows a driving-force equation: if the equilibrium concentration (which depends on speed and slope) exceeds the current concentration, the particle erodes; if it's lower, the particle deposits. This is borrowed from chemical engineering, not ad hoc graphics heuristics. The equilibrium concentration is higher when moving fast downhill, so fast-flowing water on steep slopes erodes while slow water on flat ground deposits. The result, after 200,000 particles, is terrain with realistic ridges, sediment plateaus, and channel networks.

The implementation is remarkably compact — about 20 lines of core erosion math. But the parameter tuning matters: the time step scales all parameters proportionally, the evaporation rate controls particle lifetime, the deposition rate controls how quickly equilibrium is approached. Get the balance wrong and you get either no visible erosion or swiss cheese.

What I find most interesting about particle erosion is that it's embarrassingly parallel — each particle is independent — yet McDonald runs them sequentially on the CPU. There's an inherent race condition if two particles try to modify the same heightmap cell simultaneously. GPU implementations exist but require careful atomics or tiling schemes. The tension between the natural parallelism of the simulation and the shared-state constraint of the heightmap is a recurring theme in Gpu Pipeline Architecture.

City Placement and Political Geography

O'Leary's generator goes beyond physical terrain into political geography, and this is where it gets genuinely clever. Cities are placed by scoring every grid point on water flux (rivers attract settlement), distance from existing cities (spread them out), and distance from the map edge (avoid border clustering). Each city is placed greedily at the highest-scoring point, then scores are recalculated.

Region borders use a cost-based expansion from each city where crossing mountains is expensive (uphill costs more than downhill), crossing rivers incurs a penalty, and shoreline crossings are very costly. This produces borders that naturally follow ridgelines and rivers — exactly how real political boundaries tend to form. The label placement, by contrast, is pure pragmatic spaghetti: "a few hundred lines" of code packed with magic numbers that tries to avoid overlapping city markers, labels, coastlines, and borders. O'Leary is refreshingly honest about this.¹

The Aesthetic of Procedural Maps

There's something that pure heightfield generators miss that the fantasy-map tradition gets right: maps aren't just terrain, they're depictions of terrain. O'Leary's renderer draws hill-shading strokes based on slope, smooths rivers, and places labels in a hand-drawn cartographic style. The generator isn't trying to produce a realistic satellite view; it's trying to produce something that looks like it belongs in the back of a paperback novel. The irregular mesh, the stroke-based shading, the imperfect label placement — these are features, not bugs. They create the impression of a human cartographer who understood the landscape.

This is a useful reminder for procedural generation broadly: the goal isn't to simulate reality, it's to simulate a depiction of reality. A fantasy map doesn't need accurate erosion any more than a Demoscene entry needs physically correct lighting. It needs to activate the right visual vocabulary, and that's a design problem as much as a simulation problem.

Jump Flooding: Voronoi in Logarithmic Time

The Jump Flooding Algorithm (JFA) solves a problem that comes up constantly in procedural generation: given a set of seed points, compute the Voronoi diagram (nearest seed to each pixel) and the distance transform (distance to nearest seed) on the GPU. The brute-force approach — for each pixel, check every seed — is O(pixels × seeds). JFA does it in O(pixels × log₂(N)) where N is the texture dimension, independent of the number of seeds.³

The algorithm is elegant. Initialize a texture with seed coordinates at seed locations, sentinel values elsewhere. Then run log₂(N) full-screen passes. In each pass, every pixel samples a 3×3 grid of neighbors offset by 2^(log₂(N) - pass - 1) pixels, keeping whichever neighbor's stored seed is closest. The offsets halve each pass: for a 512px texture, offsets are 256, 128, 64, 32, 16, 8, 4, 2, 1. After the final pass, every pixel knows its nearest seed. Converting to a distance transform is one more pass: compute the distance from each pixel to the seed it stored.

The result is approximate but errors are rare in practice. The algorithm extends naturally to 3D (use volume textures), to weighted seeds (scale distances by weights), and to arbitrary seed shapes (not just points). The distance transform output is directly usable as a signed distance field texture — the "next best thing to vector graphics" for scalable fonts and decals in games. At 32×16 resolution with 8bpp, a distance field texture can produce crisp edges under substantial magnification.³

What makes JFA interesting beyond the immediate utility is that it's a spatial parallel primitive — like prefix sums for spatial relationships. The same algorithm that computes Voronoi diagrams also gives you Delaunay triangulations (the dual graph), nearest-neighbor fields for pathfinding AI, and the distance transforms that underpin SDF rendering. A single GPU-friendly algorithm serves half a dozen seemingly unrelated procedural generation needs.