Creating Procedural Hexagonal Maps Using Wave Function Collapse Algorithm

The fascination with procedural map generation traces back to childhood experiences with tabletop role-playing games, where random dungeon tables created unexpected discoveries through dice rolls. This same principle of algorithmic discovery has evolved into sophisticated digital map generation systems.

A new procedural map generator demonstrates this evolution, producing detailed medieval island environments complete with roads, rivers, coastlines, cliffs, forests, and settlements. Built using Three.js WebGPU and TSL shaders, the system generates approximately 4,100 hexagonal cells across 19 interconnected grids in roughly 20 seconds.

Understanding Wave Function Collapse

The foundation of this system relies on Wave Function Collapse (WFC), an algorithm developed by Maxim Gumin that has gained popularity in procedural generation circles. The concept mirrors the tile-placement mechanics found in board games like Carcassonne, where players must ensure adjacent tile edges match perfectly.

In hexagonal implementation, each tile contains six edges rather than four, creating additional constraints and complexity. While square-grid WFC has been extensively explored, hexagonal variants present unique challenges due to the increased number of adjacency relationships.

Tile Architecture

The system employs 30 distinct tile types representing various terrain features including grasslands, water bodies, roads, rivers, coastal areas, and elevation changes. Each tile includes specifications for its six edge types and weighting values that influence selection probability during generation.

A typical road junction tile might feature three road edges alternating with three grass edges, with specific weight values affecting its likelihood of placement during the generation process.

Algorithm Mechanics

The WFC process follows a structured approach:

1. Initialize with maximum entropy: Every grid cell begins containing all possible tile configurations, including different types, rotations, and elevation levels.
2. Select minimum entropy cell: The algorithm identifies cells with the fewest remaining valid options and randomly selects one configuration.
3. Constraint propagation: Each placement eliminates incompatible options from neighboring cells, creating cascading effects across the grid.
4. Iterative refinement: The process continues until all cells are resolved or an unsolvable state is reached.

Scaling Challenges and Solutions

While WFC performs reliably on smaller grids, larger implementations face increasing failure rates due to constraint conflicts. The solution involves a modular approach using 19 hexagonal subgrids arranged in concentric rings around a central grid.

Each subgrid solves independently while respecting boundary conditions established by neighboring grids. This approach reduces computational complexity but introduces new challenges when boundary constraints become incompatible.

Advanced Recovery Systems

The system implements a three-tier recovery mechanism to handle constraint failures:

Constraint relaxation: When neighboring cells create contradictions, the solver converts fixed constraints back into solvable variables, using more distant anchor points as new constraints.

Localized re-solving: Failed regions trigger mini-WFC processes on small areas around problem zones, re-solving approximately 19 cells to create compatible boundaries. This local approach proved crucial for handling cross-grid incompatibilities.

Terrain masking: As a final resort, problematic areas receive mountain tiles with cliff edges that can connect to any terrain type, effectively hiding seam issues while maintaining visual coherence.

Elevation Integration

The system incorporates five elevation levels, with ocean and grassland starting at level zero. Slope and cliff tiles can transition between levels, creating three-dimensional constraint relationships. Roads must maintain elevation consistency, while rivers follow logical downward flows. This vertical dimension significantly increases complexity but enables more realistic terrain generation.

Hexagonal Coordinate Systems

Hexagonal grids require specialized coordinate systems due to their six-directional nature. While offset coordinates provide intuitive left-to-right, top-to-bottom numbering, they complicate neighbor calculations and distance measurements.

The implementation utilizes cube coordinates (q, r, s where s = -q-r), representing three hexagonal axes in 3D space. This system simplifies neighbor identification and distance calculations, though WFC primarily treats the problem as edge-matching rather than geometric positioning.

Decoration and Detail Systems

Initial attempts to use WFC for tree and building placement proved inadequate, as the algorithm excels at local edge matching but struggles with large-scale pattern generation. Random distribution replaced the natural clustering expected in forests and villages.

The solution separates terrain generation from decoration placement. Perlin noise fields determine tree density and building locations independently of WFC, creating organic clustering patterns. Additional logic places specific structures like buildings at road endpoints, ports along coastlines, and monuments on hilltops.

Water Rendering Challenges

Oceanic effects presented significant visual challenges beyond simple blue coloring. The system generates animated caustic sparkles and coastal wave patterns emanating from shorelines.

Surface Effects

Caustic sparkles initially used four-layer Voronoi noise generation, proving computationally expensive with poor visual results. The final implementation samples scrolling caustic textures with noise masking, achieving superior appearance with minimal performance impact.

Wave Generation

Coastal waves utilize sine bands radiating from shorelines, inspired by similar effects in other games. Distance calculations rely on coast mask rendering—orthographic captures of land-water boundaries that undergo dilation and blurring to create gradient maps.

Concave coastal features like coves created visual artifacts where wave bands became distorted. Multiple solutions were attempted, including screen-space derivatives and gradient magnitude detection, before settling on CPU-based surroundedness detection that identifies enclosed water areas and adjusts wave thickness accordingly.

Asset Creation and Alignment

Three-dimensional tile assets utilize KayKit’s low-poly Medieval Hexagon pack, supplemented with custom Blender creations for missing connectors like sloping rivers, river terminals, and cliff variants.

Critical constraints include exact 2-unit tile widths and perfect edge alignment at hexagonal boundaries. UV mapping requires precise alignment to prevent visible seams across tile transitions, where even pixel-level misalignment breaks visual continuity.

Rendering and Performance

The visual system employs Three.js with WebGPU and TSL (Three.js Shading Language) for custom shader development. Post-processing effects transform the basic algorithmic output into visually appealing landscapes.

Post-Processing Pipeline

The enhancement stack includes:

1. GTAO Ambient Occlusion: Darkens tile crevices and building bases, running at half-resolution with denoising to reduce artifacts.
2. Depth of Field: Tilt-shift blur creates miniature diorama effects, with focal length scaling based on camera zoom.
3. Film Effects: Subtle vignetting and grain add analog character to the digital generation.

Shadow Optimization

Dynamic shadow mapping fits frustums to camera views each frame, projecting visible areas into light coordinate systems for optimal shadow map utilization. This approach provides high-resolution shadows when zoomed in while maintaining coverage when zoomed out.

Performance Architecture

Efficient rendering handles thousands of tiles and decorations through strategic batching:

BatchedMesh Implementation: Each hexagonal grid uses two BatchedMesh instances—one for terrain tiles, one for decorations. This approach renders multiple geometries with individual transforms in single draw calls.

Unified Materials: All meshes share a single material referencing a common palette texture, eliminating shader state changes between draw calls and maintaining consistent performance regardless of scene complexity.

The complete system renders 4,100+ cells across 38 BatchedMeshes at 60fps on both desktop and mobile platforms.

Technical Specifications

The implementation achieves 100% success rate across 500 test runs, utilizing 30 tile types across 19 hexagonal grids with up to 500 backtrack attempts and 5 local WFC recovery attempts per failure. The complete generation process requires approximately 20 seconds for full map construction.

The technology stack includes Three.js r183 with WebGPU rendering, TSL for custom shaders, Web Workers for off-thread solving, and seeded random number generation for reproducible results.