The tileset
Seventeen tiles and one table
Every cell of the grid is one of seventeen things: solid rock, or an open floor distinguished by which of its four edges carries a wall. That is a four-bit marching-squares mask, so there are sixteen floors.
Each tile then exposes a symbol on each edge. Void shows E for empty. A floor edge with no wall shows F. A floor edge with a wall shows W. And the compatibility rule is three lines long: F meets F, E meets E, W meets E. Everything else is forbidden.
Two things fall out of that, and they are the reason the generator has no dungeon rules in it. A floor edge facing void must carry a wall, because F-against-E is illegal and only W can sit opposite E — so walls appear exactly on the floor/void seam and nowhere else. And two adjacent floors must leave their shared edge open, because W-against-F is illegal too — so there are no stray walls inside a room and no doubled walls between cells.
The weights are where taste lives. Void sits at 1.3, an open floor at 2.2, and every wall on a tile multiplies its weight by 0.55 — so a cell with three walls is about a sixth as likely as an open one, and the fully boxed-in single cell is knocked down by a further factor of 0.15 because a one-cell room with four walls is a mistake, not a feature.
Nothing in the solver knows what a room is. It knows that a certain symbol may not sit opposite a certain other symbol, and rooms are what that produces.
The solver
Observe, propagate, repeat
Wave Function Collapse is two operations in a loop. Observe: pick the least certain cell and commit it to one tile, chosen by weighted random. Propagate: work out what that makes impossible elsewhere, and cascade.
“Least certain” is minimum Shannon entropy over the still-possible tiles, weighted, with a 10⁻⁶ random nudge to break ties. Collapsing the most-constrained cell first is what keeps the whole thing from painting itself into a corner: you spend your freedom where you have least of it.
Propagation uses the AC-4 trick rather than re-checking everything. For every triple of cell, tile and direction, the solver keeps a count of how many still-possible neighbours support that tile on that side. Banning a tile decrements the counts it was supporting; when a count reaches zero, that tile has no legal neighbour on that side and is banned in turn, which decrements more. It is a single stack, drained until empty.
Sometimes it fails. A cell can end up with zero possibilities, which is a contradiction and unrecoverable — this implementation has no backtracking. It simply throws the attempt away and starts again, up to forty times. In practice the first attempt almost always survives; the figure's counter tells you.
One line of the source is a note about arithmetic: a support count may dip below zero after its tile has already been banned, which is inert, and acting on anything but the exact zero crossing would ban tiles twice.
The engine's own WFC and buildTileset, stepped by this page. Orange is uncertainty; the deeper it is, the more tiles that cell still has.
Hands on
Try it
One call to the real generator, painted flat: rooms tinted by type, corridors in plain stone, perimeter walls from the tileset's masks, dividing walls in grey and doors in orange. Roll another one and watch how differently the same six passes behave.
The actual generateLayout, imported by this page. Its statistics line is layout.stats verbatim.
The pipeline
Six passes from a blob to a floor plan
The solver runs on a coarse grid — fourteen columns by ten, say — and produces a blob of floor with a void border. Everything that makes it read as architecture happens afterwards, in plain code.
Connect. The floor may come out in several disconnected blobs, so a pass carves L-shaped corridors between components until one region remains. Those carved cells are tagged as corridor rather than room, which is the only reason a corridor looks different later.
Partition. A big blob is one cavern, not a set of rooms. The coarse solve also planted a handful of seed cells — roughly one per eight grid cells — and a multi-source breadth-first search from those seeds assigns every floor cell to its nearest nucleus. A cavern becomes four rooms without anything cutting it up.
Upsample. Everything is scaled by three, so a coarse cell becomes a 3×3 block of fine cells. Generating coarse and rendering fine is what keeps the solver's job small — a fourteen-by-ten solve is trivial where a forty-two-by-thirty one would be slow and much more likely to contradict.
Doors. The region-adjacency graph is built, and for every adjacent pair exactly one edge along their shared boundary becomes a door; the rest becomes solid dividing wall. Because doors are chosen per pair rather than per cell, there are no doors to nowhere, the dungeon is connected by construction, and it comes out naturally cyclic rather than a tree.
Type. A room-only graph, a breadth-first depth from the room nearest the map edge — that one becomes the entrance — and the deepest dead end becomes the boss. The rest are assigned from a theme's vocabulary, with one rule worth naming: a room whose bounding box is at least 1.45 times longer than it is wide becomes a library, because elongated rooms read as processional.
Mask. Finally every floor cell gets its four-bit perimeter mask back — the same marching-squares number the tileset used — which is what the 3D builder reads to decide where to place a wall mesh.
The generator will also retry the whole coarse solve up to six times looking for a layout at least 18% floor, keeping the roomiest one it saw. An empty dungeon is technically valid and no fun at all.
Determinism
A dungeon is a string
Every random decision in the pipeline comes from one seeded generator, threaded from the top: the solve, the tie-breaks, the corridor carving, the room types, the props and the monsters.
That means the entire dungeon is a pure function of its seed. Type the same word twice and you get the same dungeon twice, down to which skeleton is standing where. It costs nothing — a four-line mulberry32 and a string hash — and it turns an unreproducible bug into a bug report you can paste.
It is also why the figure above has a “same seed” button next to its “new seed” one. Watching the identical collapse twice is how you convince yourself the solver is not doing anything clever behind your back.
The bill
What this approach costs
Constraint solving gives you local correctness for free and global structure not at all. Everything architectural in this dungeon is bolted on afterwards, and the seams are worth knowing.
WFC has no idea what it is making. It produces a texture that satisfies a local rule. Left alone it gives blobs — sometimes several disconnected ones, sometimes a nearly empty grid. Rooms, corridors, doors, entrances and boss chambers are all imposed by later passes that have nothing to do with the solver.
There is no backtracking. A contradiction throws the whole attempt away. That is fine for a seventeen-tile set on a small grid and would be untenable for a richer one, where a solve might fail forty times in a row and never finish.
Coarse-then-upsample is a resolution ceiling. Because a room is built from 3×3 blocks of one coarse decision, nothing in the layout can be finer than three cells. There are no one-cell alcoves, no diagonal walls, no shapes the coarse grid could not have made.
Room types are a heuristic on shape and depth. Elongated means library; deepest leaf means boss. It reads as intent surprisingly often and it is not intent — a long room is a library whatever is in it.
Doors are one per adjacency, chosen once. There is no notion of a door being in a sensible place along the wall, only that there is exactly one, so a door can land in a corner that a level designer would never have used.
The solver is a faithful implementation of the simple tiled model after Maxim Gumin's WaveFunctionCollapse, and the propagation is the AC-4 arc-consistency algorithm; neither is mine. The 3D dungeon is built from Kay Lousberg's KayKit Dungeon Remastered pack.
Seventeen tiles, one compatibility table and six passes of ordinary code. The solver contributes the part nobody can write by hand, and everything a person would call design happens after it has finished.
