Procedural Hexagonal Map Generation Using Wave Function Collapse

I've been fascinated by procedural generation ever since I rolled my first random dungeon table as a kid. There's something magical about a system that creates a unique world every time you run it. This project combines that childhood wonder with modern web technologies to generate medieval island worlds using the Wave Function Collapse (WFC) algorithm and Three.js WebGPU rendering.

The generator creates approximately 4,100 hexagonal cells across 19 grids, featuring roads, rivers, coastlines, mountains, forests, and trees — all generated in about 20 seconds.

'Carcassonne,' but the Computer Plays

The WFC approach works like the board game Carcassonne. You have tiles with edges — grass, road, city. Neighboring tile edges must match. A road edge connects with another road edge. Grass connects with grass.

Tile Definitions

The system defines 30 different tile types, each with 6 edges that can be grass, road, river, coast, cliff, or slope. Each tile type can be rotated into 6 orientations and placed at 5 different elevation levels, giving us 900 potential states per cell.

Here's an example tile definition:

{ name: 'ROAD_D', mesh: 'hex_road_D',
  edges: { NE: 'road', E: 'grass', SE: 'road', SW: 'grass', W: 'road', NW: 'grass' },
  weight: 2 }

How WFC Works

The WFC algorithm follows four steps:

1. Start with superposition — every grid cell contains all 900 possible tile states
2. Collapse — select the cell with the lowest entropy (fewest remaining valid states) and randomly choose one state for it
3. Propagate — ripple the constraints outward, removing incompatible states from neighboring cells
4. Repeat — continue until the entire grid is solved or a contradiction is reached

Hexagonal tiles present 50% more edge constraints than squares (6 faces vs. 4), creating a combinatorial explosion that makes the problem significantly harder.

The Multi-Grid Problem

Rather than solving one massive grid, the approach divides the map into 19 interconnected hexagonal grids — one center grid, a ring of 6, and an outer ring of 12. This makes individual WFC solves manageable but introduces a new challenge: boundary conflicts between adjacent grids.

Backtracking

When the WFC solver reaches a contradiction (a cell with zero valid states), it must backtrack. The solver attempts up to 500 backtracking iterations before giving up on that grid and invoking the recovery system.

The Recovery System

The three-layer recovery system handles inter-grid conflicts:

• Layer 1: Liberation — converts fixed boundary constraints from neighboring grids into solvable cells, giving the solver more freedom
• Layer 2: Local WFC — re-solves a small 19-cell region around the problem area, with up to 5 retry attempts
• Layer 3: Mountain masking — places mountain terrain to hide incompatible seams, since mountain cliff faces are compatible with everything

This system achieves a 100% success rate across 500 test runs.

The Third Dimension

The map uses 5 elevation levels. Cliff faces and slopes provide transitions between heights. Road networks must connect at matching elevations or through slope tiles. Rivers always flow downhill — they cannot flow upward.

Hexagonal Coordinates: An Unexpected Quirk

The article recommends using cube coordinates (q, r, s) instead of offset coordinates for hexagonal grids. Cube coordinates satisfy the constraint q + r + s = 0 and make neighbor-finding and distance calculations much simpler.

Trees, Buildings, and Why Not Everything Should Be WFC

WFC excels at local constraint satisfaction but fails at producing large-scale patterns. The solution: WFC handles terrain, Perlin noise generates decorations.

Tree forests and building clusters use global noise fields rather than tile-based WFC rules, creating organic clustering that pure constraint propagation cannot achieve. Separate logic places buildings at the ends of roads and near ports.

Water: Harder Than It Looks

Water effects required particular attention and use multiple layered techniques.

Caustics

The system uses a small scrolling caustic texture with noise-based UV sampling rather than purely procedural generation. This produces the shimmering light pattern you see on shallow water surfaces.

Coastal Waves

Sinusoidal wave bands radiate outward from coastlines. The amplitude decreases with distance from shore, creating a natural falloff effect.

The Bay Problem

Concave bays presented a unique challenge — waves radiating inward from opposite coastlines would overlap and interfere destructively. The solution uses CPU-based sampling to detect how much a water cell is surrounded by land, then reduces wave amplitude accordingly in enclosed areas.

Creating Tiles in Blender

3D tile assets were sourced from the Medieval Hexagon pack by KayKit. Additional models were created in Blender with precise edge alignment and UV mapping for seamless texture application across tile boundaries.

Visual Polish

The raw output receives atmospheric treatment through several post-processing stages.

WebGPU and TSL Shaders

The rendering pipeline uses Three.js r183 with the WebGPU renderer and TSL (Three.js Shading Language) for GPU shaders. TSL provides a JavaScript-native way to write shaders without GLSL/WGSL string manipulation.

Post-Processing Stack

• GTAO Ambient Occlusion — rendered at half resolution for performance, adds depth perception to crevices and contact shadows
• Depth-of-field tilt-shift effect — creates a miniature/diorama appearance that scales with camera zoom distance
• Film grain and vignetting — adds analog character and draws focus toward the center

Dynamic Shadow Maps

The system uses cascaded shadow map resolution that adapts to camera distance — higher resolution when zoomed in for crisp detail, lower resolution when zoomed out for performance.

Optimizations

Two key strategies achieve 60fps on 4,100+ cells:

BatchedMesh consolidation: Each hex grid uses just two BatchedMesh objects (one for tiles, one for decorative objects), reducing draw calls to merely 2 per grid regardless of how many individual hexes it contains.

Single material architecture: All meshes share one material. UV coordinates map into palette textures for color extraction, completely eliminating shader state switching between draw calls.

Summary

The system achieves a 100% success rate across 500 test runs, generating unique, explorable medieval worlds procedurally.

The Numbers

• ~4,100 hexagonal cells
• 19 hex grids (1 center + 6 inner ring + 12 outer ring)
• 38 BatchedMesh objects total
• 60fps on desktop and mobile
• ~20 seconds generation time
• 100% solve rate over 500 tests

Technology Stack

• Three.js r183 with WebGPU renderer
• TSL (Three.js Shading Language) for GPU shaders
• Web Workers for off-thread WFC solving
• Vite for build tooling
• PRNG with seed values for reproducibility

Try It Yourself

The live demo is available online, and you can generate your own unique medieval island worlds. Each generation produces a completely different map thanks to the seed-based PRNG system.

Acknowledgments and Links

Special thanks to the open-source community and the creators of the Medieval Hexagon asset pack. The WFC algorithm implementation draws inspiration from Maxim Gumin's original WFC project and the extensive research by others in the procedural generation community.