Wave Function Collapse on a Hex Grid: Constraints All the Way Down

Procedural generation has a dirty secret: most of it is just noise functions dressed up in a tuxedo. Perlin noise, fractal terrain, random walks — they produce plausible-looking output, but they don’t reason about structure. The result is landscapes that feel random rather than designed.

Wave Function Collapse is different, and this deep-dive on building a procedural hex map with WFC is one of the clearest walkthroughs of the algorithm I’ve seen applied to a non-square grid.

What WFC Actually Does

The name is borrowed loosely from quantum mechanics, which is either illuminating or annoying depending on your tolerance for physics metaphors. The core idea is simpler than it sounds:

1. Each cell in your grid starts in a superposition — it could be any tile.
2. You pick the cell with the fewest valid options (lowest entropy) and collapse it to one tile.
3. That choice propagates constraints to neighboring cells, eliminating options that would violate adjacency rules.
4. Repeat until every cell is resolved — or you hit a contradiction and backtrack.

The constraint propagation step is where the interesting work happens. You’re not just placing tiles randomly; you’re running a constraint solver that ensures every placed tile is locally consistent with its neighbors.

Why Hex Grids Make It Harder

Square grids have 4 neighbors (or 8 if you count diagonals). Hex grids have 6, and those 6 neighbors have a directional relationship that isn’t symmetric in the same way. A tile’s “north” edge must match the southern neighbor’s “south” edge — but in a hex layout, “north” and “south” aren’t quite the same concept depending on whether you’re using offset coordinates, axial coordinates, or cube coordinates.

The article handles this carefully, which is one reason it’s worth reading. Getting the neighbor lookup wrong in a hex grid produces subtle bugs that look like valid output until you stare at the seams.

The Backtracking Problem

WFC can fail. If you paint yourself into a corner — a cell with no valid tiles remaining — you have to backtrack. The naive approach is to restart from scratch. Smarter implementations track decision history and unwind only to the last branch point.

This is where WFC starts to feel less like “procedural generation” and more like constraint satisfaction, because that’s exactly what it is. It’s essentially a specialized SAT solver with a heuristic (minimum remaining values) that happens to work well for spatial problems.

For a hex map, contradiction frequency depends heavily on your tile set. A sparse tile set with loose adjacency rules almost never contradicts. A detailed tileset trying to produce coherent coastlines, rivers, and elevation — that’s where you earn your backtracking budget.

Worth Implementing Yourself

I’d genuinely recommend building a toy WFC implementation before reaching for a library. The constraint propagation loop is maybe 50-100 lines of code in most languages, and writing it teaches you something about how local rules produce global structure that you don’t get from just using the output.

The hex map application is a nice target because the visual feedback is immediate and the domain is familiar. You know what a reasonable map should look like, which makes it easy to spot when your adjacency rules are wrong.

For anyone building games, simulations, or even layout systems, WFC is one of those algorithms that pays dividends well beyond its original use case. The Hacker News thread has some solid discussion on variations and extensions if you want to go deeper.