Wave Function Collapse

Fill a grid from a small set of tiles so that every pair of neighbors is legal. Each cell starts out holding all the tiles at once, which is called a superposition. The solver takes the most constrained cell and collapses it to a single tile, picked at random by weight. It then passes that choice to the neighbors and drops the options that no longer fit. It repeats both steps until every cell is decided. This is the constraint-solving, texture-synthesis technique behind procedurally generated tile maps.

The result is a grid of tile indices, and you draw it however you like. Each tile is a Shape or a small draw block, so it feeds the existing geometry path. A solve is a pure function of the seed, so the same seed always produces the same layout.

There are two models, and they differ in where the rules come from. The tiled model, below, takes tiles you designed and edge sockets you declared. The overlapping model takes a small picture and works out the vocabulary for itself.

Contents

• Tiles and sockets
• Solving and drawing
• Rotations
• Learning from a picture: the overlapping model
• What it's for, and what it isn't

Tiles and sockets

A WFCTile is four edge sockets and a weight. Two tiles may sit next to each other when the sockets on their shared edge are equal. A socket is therefore an Int label for what an edge connects to. For example, a socket can mark a pipe or no pipe, and it can mark a grass edge or a water edge. Sockets are listed clockwise from the top.

WFCTile(_ sockets: [Int], weight: Double = 1)   // [top, right, bottom, left]
WaveFunctionCollapse(tiles: [WFCTile], columns: Int, rows: Int)

let blank    = WFCTile([0, 0, 0, 0])            // no pipe on any edge
let vertical = WFCTile([1, 0, 1, 0])            // a pipe top-to-bottom
let elbow    = WFCTile([1, 1, 0, 0])            // a pipe turning top-to-right

A higher weight makes a tile more likely when a cell collapses, so you can push a layout toward straights rather than crossings, for example.

Solving and drawing

Solve with the wfc shorthand, then draw the result with drawWFC. Solving takes real time, so do it once rather than every frame. Keep the result in a stored property, or guard the call so it runs on the first frame.

func wfc(tiles: [WFCTile], columns: Int, rows: Int, attempts: Int = 40) -> [[Int]]?
func drawWFC(_ grid: [[Int]], in bounds: Rectangle? = nil, padding: Insets = 0, gutter: Double = 0,
             tile: (Int, Rectangle) -> Void)

wfc returns the tile indices as grid[column][row]. It returns nil when it cannot find a legal filling within attempts restarts. A contradiction is a cell left with no legal tile, and one contradiction restarts the whole solve. Contradictions are rare with a forgiving tileset, and adding a blank tile makes them almost impossible. drawWFC lays a Grid over bounds and hands your closure each cell's tile index and frame.

if let grid = wfc(tiles: tiles, columns: 18, rows: 18) {
    strokeWeight(6); strokeCap(.round)
    drawWFC(grid, padding: .all(40)) { index, cell in
        // draw a line from the cell center to each edge that carries a pipe
        let sockets = tiles[index].sockets
        let mids = [Vector2(cell.center.x, cell.y), Vector2(cell.x + cell.width, cell.center.y),
                    Vector2(cell.center.x, cell.y + cell.height), Vector2(cell.x, cell.center.y)]
        for edge in 0..<4 where sockets[edge] != 0 { drawLine(cell.center, mids[edge]) }
    }
}

Because you draw straight from a tile's sockets, one draw block covers a tile and all of its rotations. See the WaveFunctionCollapse example.

Rotations

Most tilesets are one drawn shape plus its rotations. rotations() makes those rotations for you and turns the sockets to match, so you declare each shape once.

func rotated() -> WFCTile              // 90° clockwise, sockets rotated to match
func rotations(_ count: Int = 4) -> [WFCTile]

let tiles = [WFCTile([0, 0, 0, 0], weight: 1.1)]     // blank
    + WFCTile([1, 0, 1, 0], weight: 1.6).rotations(2) // straight: vertical + horizontal
    + WFCTile([1, 1, 0, 0], weight: 1.3).rotations()  // elbow: four corners
    + WFCTile([1, 1, 1, 0], weight: 0.5).rotations()  // tee: four orientations
    + [WFCTile([1, 1, 1, 1], weight: 0.3)]            // cross (rotations are identical)

Learning from a picture: the overlapping model

Declaring tiles and sockets takes work, and some textures do not break into tiles at all. The overlapping model skips that step. You hand it a small example picture, and it cuts the sample into every patternSize × patternSize patch the sample contains. It counts how often each patch occurs, then works out which patches may overlap. The solve then fills a much larger grid so that every overlap agrees.

What comes out is new as a whole, but every small part of it comes from the sample. Stated exactly, the guarantee is that every square of the output is a square the sample already contained.

func wfc(from sample: Image, width: Int, height: Int,
         patternSize: Int = 3, symmetry: WFCSymmetry = .all,
         wrapsSample: Bool = true, tileable: Bool = false,
         attempts: Int = 10) -> Image?

if let texture = wfc(from: sample, width: 72, height: 44) {
    drawImage(texture, in: bounds)
}

symmetry costs you orientation. Some samples have a clear up and down, such as a skyline, a waterline, or flowers standing on ground. Use .none for those, or the result comes back sideways. Use .all for a texture with no particular orientation. It gives the solver more patterns to work with, and it does not ask you for a bigger sample.

wrapsSample is easy to get wrong, and the default loses edges. Reading the sample as wrapping joins its bottom row to its top row. A sample with ground along the bottom then teaches patches where ground sits directly under sky. Synthesize from those patches and the ground repeats in bands up the picture. Pass wrapsSample: false when your sample has a meaningful top and bottom.

Learning is the slow half, and it does not depend on the output. A sketch that solves more than once builds the model itself and keeps it:

let model = OverlappingWFC(learningFrom: sample, patternSize: 3)   // once, in setup
// ... then as often as you like
let texture = wfc(model, width: 64, height: 64)

OverlappingWFC also reports what it learned, and that is worth drawing while you tune a sample. patternCount is how many patterns there are, pattern(_:) gives each patch as its own small image, and weight(_:) gives how often that patch occurred.

Two practical notes follow. First, draw the result a rectangle at a time rather than with drawImage when you scale it up much. drawImage smooths the image, which turns a 3-pixel wall into a gradient. A rectangle per pixel also exports to SVG and PDF as real rectangles. Second, do this once, in setup or guarded so it runs on the first frame. Neither learning nor solving belongs in a frame loop.

What it's for, and what it isn't

The sample should be small and use few colors: pixel art or a hand-drawn motif, tens of pixels a side, a handful of colors. Patches are matched by exact color equality. A photograph has a distinct color in nearly every patch, so nearly every patch is unique. Nothing then overlaps anything else, and the solve has nothing to choose between. A sample past OverlappingWFC.maxColors (256) or OverlappingWFC.maxPatterns (1024) is refused with a note saying so, rather than grinding away.

A solve can fail, and failures begin above about 50 pixels a side. A contradiction is a cell left with no fitting pattern. Each one restarts the whole solve, attempts times, and then wfc returns nil. This is a limit of the technique, not of the implementation. The problem is NP-hard in general, so success rates fall off sharply as the output grows. Solve a smaller texture, loosen the sample, or drop patternSize to 2.

tileable can be impossible rather than only hard. The sample may have a repeating structure whose period does not divide the output size. No seamless answer exists at that size, so every attempt fails. Size the output to a multiple of the sample's period to fix it, because retrying never will.

Not here yet: a way to constrain the solve before it starts. Such a constraint would pin the bottom row to ground, fix a pixel, or seed a region. The reference implementation has a ground flag for the first of those. The flag names a pattern by index, and that index depends on the order the patterns were extracted in. When the sample or the symmetry changes, the flag quietly means something different. A version worth having would name a color or a region instead.

Related: Truchet tiling (tiles chosen at random rather than by constraint), Circle packing, L-systems, and Differential growth (the other generative-geometry generators), Geometry (the Grid the layout draws through), Images (the Image a sample comes from and a texture goes back to).