November 21st, 2026

Wave function collapse for pixel art maps, explained

Wave function collapse fills a grid from rules about what may touch what. How it works, a pixel art village built in two passes, and tested Godot code.

Paste it into Claude Code, Codex, Cursor or any coding agent.

# Add wave function collapse map generation to my game

My game needs generated maps that make sense: roads that join up, houses that face a road, details where they belong. Build a wave function collapse (WFC) solver and run it twice: once for the layout, then on a finer grid for the details, with detail rules that read the finished layout.

Before you write code, look at my project: the engine and language, how maps are drawn (tilemap, tile size, sprites, y-sorting), and what terrain and props I have art for. Fit this into what is there instead of adding a second map system, and keep my tile size and art. If my game is not a village, ask me which modules and rules I want. Tell me where the weights and rules can be tweaked.

## How it works

- Every cell keeps the set of modules it could still become, as a bitmask.
- Every module has a weight and a socket per side (N, E, S, W). Two cells can be neighbors only if the sockets on their shared side are a listed pair.
- Loop: pick the open cell with the lowest entropy, pick one of its modules at random by weight, then remove from each neighbor every module that no longer fits, and keep going through neighbors that changed (propagation).
- Grow from a start cell: only open cells next to a picked cell compete; if none are left but open cells remain, all of them do.
- A cell with no options left is a contradiction: restart the layout with the next seed.
- Pass 2 splits each layout cell into 4 x 4 spots. Each spot's allowed modules and weights come from the layout around it.

## Numbers that matter

- Entropy = log(W) - sum(w * log(w)) / W over the modules a cell still allows, W = their total weight. Add random 0 to 0.05 to break ties (pass 2: 0 to 0.3).
- Layout: 8 x 6 cells of 32 px, 14 modules: 11 road pieces (every set of 2, 3 or 4 connected sides, no dead ends), house, tree, grass.
- Sockets: roads R on connected sides, s on the others; house G on N, E, W and D (front door) on S; tree and grass G all round. Pairs (each works both ways): R-R, s-G, s-s, G-G, s-D, D-R. No edge rule in the layout pass, so roads may run off the map; houses are banned from the bottom row.
- Weights: grass 2.2, house 1.6, tree 1.4, roads 0.3 x (straight 1.4, corner 0.7, T 0.3, crossing 0.08). The first pick is a house in one of the 4 middle cells.
- Dirt: a road's lane is 2 spots (16 px) wide through the middle of its cell and out to each connected side. Below a house with a road under it, a front path covers the house cell's bottom spot row and the road cell's top row, 2 spots wide.
- Details on 8 px spots, nothing on house or tree cells. "Within n spots" counts diagonals (a square of side 2n + 1 around the spot) and means a spot of a house or tree cell. Empty 2.6; pebble 0.18 on dirt only; flower 2.2 within 1 spot of a house; bush 0.7 and mushroom 0.1 within 1 spot of a tree; tuft 1.6 on grass with dirt on one of its 4 sides, 0.15 on other grass; fence pieces 1.2 each, on grass with dirt directly above or below and a house within 3 spots. Nothing but pebbles and empty in the spot row right above a house or tree cell (its sprite hangs over it).
- Fence sockets (W, E): left end (n, a1), middle 1 (a2, b1), middle 2 (b2, c1), right end (c2, n). Pairs: a1-a2, b1-b2, c1-a2, c1-c2, n-n. Fences have N/S socket f, everything else n; n-n and n-f fit, f-f never. The map edge counts as n.
- Pass 2 starts at the grass spot nearest the first house's door (the middle of its cell's bottom edge); on a tie, the first in row order. Fence runs come out 4, 6, 8 spots long.

## Pseudo code

```
function solve(w, h, modules, pairs, seed, start, forced = none):
    allowed[d][a] = bitmask of b where (modules[a].socket[d], modules[b].socket[opposite(d)]) in pairs
    domain[c] = all modules, minus bans                # bans: map edge, unary rules
    propagate(all cells)
    collapse(start, forced)
    while true:
        c = unpicked cell with the lowest entropy(c) + random() * noise (a new random per cell, every step),
            only among cells next to a picked cell (all open cells if none)
        if no c: return result
        if not collapse(c, none): return contradiction

function collapse(c, forced):
    m = forced or weighted random among modules in domain[c]
    domain[c] = {m}; result[c] = m; mark the 8 cells around c as next to a picked cell
    return propagate([c])

function propagate(stack):
    while stack not empty:
        c = stack.pop()
        for each side d with a neighbor n:
            ok = OR of allowed[d][a] for every a in domain[c]
            keep = domain[n] AND ok
            if keep is empty: return false
            if keep != domain[n]: domain[n] = keep; stack.push(n)
    return true

layout = solve(8, 6, village modules, village pairs, seed, a middle cell, forced = house)
spots = for each 8 px spot: allowed modules and weights from layout (see numbers)
details = solve(32, 24, detail modules, detail pairs, seed, spot nearest the first door)
```

A 64 bit int holds up to 62 modules (GDScript int, C# `ulong`). Draw with your tilemap (Godot `TileMapLayer.set_cell`, Unity `Tilemap.SetTile`) plus sprites sorted by their bottom edge.

## Pitfalls

- Weights are per module: 11 road pieces at a house's weight take over the map.
- Without lowest entropy first, pieces scatter and contradictions get far more likely.
- In GDScript, a packed array inside an Array is a copy: write a changed weights array back. Reach scripts with `preload` in tests; `class_name` needs an editor import first.
- A rule can silently never fire (fence runs need 4 spots in a row). Count placements per module in a test.
- Use one seeded random generator for everything (and the next seed for a restart), so a seed always gives the same map.

## Check that it works

- 200 seeds solve with no contradiction, and the same seed gives the same map twice.
- Every house has a road cell directly below it; no house in the bottom row.
- Every road connection meets a road connection, a door or the map edge, and no road runs into the side of another road.
- Every pebble is on dirt, every flower within 1 spot of a house, every bush and mushroom next to a tree, nothing on house or tree cells, nothing but pebbles in a row a sprite hangs over.
- Every fence run starts with a left end, ends with a right end, is at least 4 spots long, and no fence is directly above another.
- A debug view of each open cell's remaining options shows them shrinking around every pick.

## Art it needs

A grass and dirt ground that can draw 2-spot lanes, houses that fit one cell with the door at the bottom center, trees, and small details. Cheapest first: colored shapes to test the generator, then my existing tiles and props mapped to the modules, then, if the SpriteCook MCP tools are available in this session, a generated grass and dirt tileset and exact-size sprites.

Source: SpriteCook (2D game assets made by your coding agent, for Claude, ChatGPT and Cursor)
Full guide with pictures, a video and tested Godot code: https://www.spritecook.ai/blog/wave-function-collapse-explained

Put tiles down at random and the map looks random. A house faces a tree, a road stops in the middle of a field. Wave function collapse (WFC) fills a grid from a few rules about what may sit next to what, so every road joins up and every door faces a road. You write the rules once and get a new map from every seed.

The village is built in two passes by the code on this page: first the layout on a grid of 32 px cells, then the details on a grid four times finer. At the end the picks play backwards so the clip loops. The cottages, trees and details are Pixel Engine sprites and the ground is a dual-grid tileset, all generated by a coding agent with SpriteCook.

Every cell starts with every option

The map is a grid, and every cell keeps a list of the pieces it could still become. I call those pieces modules. The village has 14: 11 road pieces (every way to join 2, 3 or 4 sides), a house, a tree and grass.

An 8 by 6 grid of pixel art cells before anything is picked. Each cell shows four faded icons for what it could become: a dirt road cross, a cottage, a tree and a grass square. The bottom row only shows a road, a tree and grass

Look at the bottom row. It has no house icon, because a house's door faces down. In that row it would face the map edge, so the house is taken out of those cells before the first pick.

Sockets decide what may touch

Every module has a socket on each side. Two cells can sit next to each other only when the sockets on their shared side fit.

Seven pixel art tiles in a row with a letter on each side: a straight road, a corner, a T junction and a crossing marked R where the road goes on and s on their other sides, a cottage marked G on three sides and D at the bottom, then a tree and a grass tile marked G on all sides

The village uses four sockets: R where a road goes on, s on the side of a road, G for plain ground and D for a front door. Six pairs fit: R with R, s with G, s with s, G with G, s with D, and D with R. Two rules come out of that list without writing them anywhere:

  • A road that leaves a cell has to meet another road, run up to a door, or leave the map. There are no dead-end pieces, so a road never stops in the grass.
  • A door (D) only fits a road. Every house ends up facing a road.

Pick, then narrow down the neighbors

The whole algorithm is one loop:

  1. Find the open cell with the lowest entropy, which mostly means the fewest options left.
  2. Pick one of its modules at random, weighted.
  3. Remove from its neighbors every module that no longer fits. When a neighbor changed, check its neighbors too, until nothing changes.
A close view of the empty grid, every cell showing faded road, cottage, tree and grass icons
Before the first pick
The same view after one cell became a thatched cottage. The cell below it now only shows one big faded road icon, and the cell above lost its house icon
After the first pick

One pick ripples out. The cottage's door only fits a road, so the cell below drops everything but road pieces. The cell above loses the house, because a door can't face a back wall, and it loses every road that would run into the roof. With 6 options left it has the lowest entropy, so it's the next pick, in all 200 villages I tested.

Entropy counts the weights too: log(sum of weights) - sum(w * log(w)) / sum of weights over the modules a cell still allows. A cell with one option left has an entropy of 0. I add a tiny random number (0 to 0.05, and 0 to 0.3 in the detail pass) to break ties.

Two choices make it look like a village instead of noise. The first pick is a house in the middle of the map. After that, only open cells next to a picked cell compete, so the village grows outward as one blob instead of popping up all over the map.

In theory a cell can run out of options, a contradiction. layout() then starts over with the next seed. With these sockets it never happened in 200 villages. The detail pass has no retry, since its empty module fits next to everything; add the same loop if your rules are tighter.

Weights decide the look

The sockets say what's allowed. The weights say how often. Grass is 2.2, a house 1.6, a tree 1.4. Road pieces are much lower: 0.42 for a straight piece, 0.21 for a corner, 0.09 for a T and 0.024 for a crossing (0.3 times 1.4, 0.7, 0.3 and 0.08).

My first try gave each road piece about the weight of a house. There are 11 road pieces and only one house, so roads took over the map. Weights are per module, so a family of many modules needs smaller ones.

A second pass for the details

The layout pass gives you clean blocks: a house fills a cell, grass fills a cell. That's what makes generated maps look generated. A second pass on a finer grid breaks it up.

A close view of a finished village layout with a thin white grid drawn over it, 8 pixels per square, so each 32 pixel cell is split into 4 by 4 spots. Cottages, a dirt lane and a tree sit under the grid

Every 32 px cell becomes 4 x 4 spots of 8 px, and the same solver runs again with new modules: fence pieces, flowers, mushrooms, grass tufts, pebbles, bushes and empty. What a spot may hold comes from what the first pass put around it:

  • Pebbles only lie on dirt.
  • Flowers only grow within 1 spot of a house.
  • Bushes and mushrooms only grow next to a tree.
  • Fences stand on grass right next to a lane, with a house within 3 spots.
  • Nothing grows in the row right above a house or a tree, because the roof or the crown hangs over it.
  • Tufts can go on any grass, but they're likely along a path edge (weight 1.6) and rare on open lawn (0.15).
A close view of a cottage with its front path, a second cottage and part of a third, two dirt lanes and a tree after the layout pass only. The grass is plain between them
Layout pass only
The same view after the detail pass: a wooden fence by the lane, white, pink and lilac flowers next to the cottages, a bush by the tree, tufts along the lane and pebbles on the dirt
After the detail pass

The fence uses sockets the same way the roads do. It has a left end, two middle pieces and a right end, and their sides only fit as a left end, then middle pieces in pairs, then a right end. So every fence run has two proper ends and is at least 4 spots long. Fences also get a socket on the top and bottom that never fits another fence, so two fences never stand on top of each other. The detail pass grows outward from the grass spot nearest the first house's door.

Caves of Qud builds its maps in several passes the same way: a coarse layout first, then WFC for the detail.

The finished pixel art village from above: a row of six cottages along a dirt lane at the top, more cottages below, trees and bushes, short wooden yard fences, flowers by the houses, tufts along the lanes and pebbles on the dirt

What else you can use it for

The village is one rule set. The same solver with other modules and sockets:

  • Dungeons. Rooms, corridors and doors as modules. Give walls a socket W, floors O and doors D, and let D fit only a corridor's O, just like the front doors here.
  • Terrain from a height ladder. Water, sand, grass and forest on the corners of a grid, where neighbors may only differ by one step. Each side's socket is the two corner values along it (like 12), and a socket only fits itself. Rules like this rarely, if ever, run into a contradiction.
  • Room interiors. A second pass inside each room: beds and shelves against walls, rugs in the middle, nothing in front of a door.
  • Level chunks. Hand-made rooms as modules, with their exits as sockets, so a run is new every time but every room is designed.
  • Filling around set pieces. Pick a few cells yourself before the run (a castle, the player's start) with collapse(cell, module), then let the solver fill the rest. Check domain[cell] & (1 << module) first, because a forced pick skips that test.
  • Towns on any shape. Townscaper by Oskar Stålberg matches edges the same way on an irregular grid, and Bad North, which he co-made, uses it for its 3D islands.

The code

wfc.gd is the solver. It knows nothing about villages: give it modules with a weight and four sockets, the pairs of sockets that fit, and a seed. Options are stored as a bitmask per cell, so propagation is a few bit operations.

extends RefCounted
## Wave function collapse on a grid of cells.
## Every module has a weight and a socket on each side (N, E, S, W). Two cells may touch only where their
## sockets fit. Each step picks the open cell with the lowest entropy, picks one of its modules by weight, then
## removes from its neighbors (and theirs) every module that no longer fits.
## A cell's options are a bitmask: bit m set = module m is still possible (up to 62 modules).

const DIRS := [Vector2i(0, -1), Vector2i(1, 0), Vector2i(0, 1), Vector2i(-1, 0)]  # N, E, S, W

var width := 0
var height := 0
var modules: Array = []             # {"sockets": [n, e, s, w], "weight": float, ...}
var fits := {}                      # "a b" -> true for every pair of sockets that may touch (both orders)
var domain := PackedInt64Array()    # per cell: bitmask of the modules still possible
var weights: Array = []             # per cell: PackedFloat64Array, one weight per module
var result := PackedInt32Array()    # the module picked for each cell, -1 while open
var steps: Array = []               # [cell, module] in the order they were picked
var noise := 0.05                   # tiny random tie breaker added to the entropy
var _allowed: Array = []            # _allowed[d][a]: bitmask of modules that may sit on side d of module a
var _entropy := PackedFloat64Array()
var _touched := PackedByteArray()   # cells next to a picked cell (the frontier)
var _state := 1


func setup(w: int, h: int, mods: Array, fit_pairs: Array, seed: int) -> void:
	width = w
	height = h
	modules = mods
	fits.clear()
	for p in fit_pairs:
		fits[p[0] + " " + p[1]] = true
		fits[p[1] + " " + p[0]] = true
	_allowed.clear()
	for d in 4:
		var row := PackedInt64Array()
		for a in mods.size():
			var mask := 0
			for b in mods.size():
				if fits.has(mods[a]["sockets"][d] + " " + mods[b]["sockets"][(d + 2) % 4]):
					mask |= 1 << b
			row.append(mask)
		_allowed.append(row)
	var ws := PackedFloat64Array()
	for m in mods:
		ws.append(m["weight"])
	domain.resize(w * h)
	domain.fill((1 << mods.size()) - 1)
	weights.clear()
	for i in w * h:
		weights.append(ws.duplicate())
	result.resize(w * h)
	result.fill(-1)
	steps.clear()
	_entropy.resize(w * h)
	_entropy.fill(-1.0)
	_touched.resize(w * h)
	_touched.fill(0)
	_state = posmod(seed, 2147483646) + 1


func rand() -> float:
	# Park-Miller, so a Python version of this solver can make the same picks
	_state = (_state * 48271) % 2147483647
	return float(_state) / 2147483647.0


func ban(cell: int, m: int) -> void:
	domain[cell] &= ~(1 << m)
	_entropy[cell] = -1.0


func ban_edges(edge_socket: String) -> void:
	# treat the map edge as a neighbor whose sockets are all edge_socket
	for y in height:
		for x in width:
			for d in 4:
				var q: Vector2i = Vector2i(x, y) + DIRS[d]
				if q.x >= 0 and q.y >= 0 and q.x < width and q.y < height:
					continue
				for m in modules.size():
					if not fits.has(modules[m]["sockets"][d] + " " + edge_socket):
						ban(y * width + x, m)


func propagate(stack: Array) -> bool:
	while not stack.is_empty():
		var c: int = stack.pop_back()
		var p := Vector2i(c % width, c / width)
		for d in 4:
			var q: Vector2i = p + DIRS[d]
			if q.x < 0 or q.y < 0 or q.x >= width or q.y >= height:
				continue
			var ok := 0                                    # everything any option of c allows on side d
			for a in modules.size():
				if domain[c] & (1 << a):
					ok |= _allowed[d][a]
			var n := q.y * width + q.x
			var keep: int = domain[n] & ok
			if keep == 0:
				return false                               # a contradiction: nothing fits here any more
			if keep != domain[n]:
				domain[n] = keep
				_entropy[n] = -1.0
				stack.append(n)
	return true


func propagate_all() -> bool:
	var all := []
	for c in width * height:
		all.append(c)
	return propagate(all)


func entropy(cell: int) -> float:
	if _entropy[cell] < 0.0:
		var total := 0.0
		var acc := 0.0
		for m in modules.size():
			if domain[cell] & (1 << m):
				var w: float = weights[cell][m]
				total += w
				acc += w * log(w)
		_entropy[cell] = maxf(0.0, log(total) - acc / total)
	return _entropy[cell]


func pick_cell() -> int:
	var best := -1
	var best_key := INF
	for frontier_only in [true, false]:
		for c in width * height:
			if result[c] >= 0 or (frontier_only and _touched[c] == 0):
				continue
			var key := entropy(c) + rand() * noise
			if key < best_key:
				best_key = key
				best = c
		if best >= 0:
			return best
	return -1


func collapse(cell: int, forced := -1) -> bool:
	var m := forced
	if m < 0:
		var total := 0.0
		for i in modules.size():
			if domain[cell] & (1 << i):
				total += weights[cell][i]
		var r := rand() * total
		for i in modules.size():
			if domain[cell] & (1 << i):
				m = i
				r -= weights[cell][i]
				if r < 0.0:
					break
	domain[cell] = 1 << m
	_entropy[cell] = 0.0
	result[cell] = m
	steps.append([cell, m])
	var p := Vector2i(cell % width, cell / width)
	for dy in range(-1, 2):
		for dx in range(-1, 2):
			var q := p + Vector2i(dx, dy)
			if q.x >= 0 and q.y >= 0 and q.x < width and q.y < height:
				_touched[q.y * width + q.x] = 1
	return propagate([cell])


func run(start: int, start_module := -1) -> bool:
	# grows outward from start: open cells next to picked ones go first, lowest entropy among them
	if not collapse(start, start_module):
		return false
	while true:
		var c := pick_cell()
		if c < 0:
			return true
		if not collapse(c):
			return false
	return true

village.gd holds both passes. layout() returns a solved grid of cells, details() reads it and returns the grid of spots. To draw it, I put the ground on a dual grid (grass with the lanes cut out as dirt) and the houses, trees and details as sprites sorted by their bottom edge.

extends RefCounted
## Two wave function collapse passes for a small village.
## Pass 1, the layout: one module per 32 px cell (road pieces, house, tree, grass).
## Pass 2, the details: one module per 8 px spot (4 x 4 spots per cell). What a spot may hold depends on what
## pass 1 put around it.

const WFC := preload("res://wfc.gd")
const DIRS := ["N", "E", "S", "W"]
const SPOTS := 4          # spots per cell side in pass 2

# Pass 1 sockets. R: the road goes on. s: the side of a road. G: plain ground. D: a front door.
const LAYOUT_FITS := [["R", "R"], ["s", "G"], ["s", "s"], ["G", "G"], ["s", "D"], ["D", "R"]]


static func layout_modules() -> Array:
	var mods := []
	for k in [2, 3, 4]:                                    # roads with 2, 3 or 4 connections, no dead ends
		for combo in _combinations([0, 1, 2, 3], k):
			var straight: bool = k == 2 and (combo == [0, 2] or combo == [1, 3])
			var w: float = {2: 0.7, 3: 0.3, 4: 0.08}[k]
			if straight:
				w = 1.4
			var sockets := []
			for d in 4:
				sockets.append("R" if d in combo else "s")
			mods.append({"kind": "road", "conn": combo, "sockets": sockets, "weight": 0.3 * w})
	mods.append({"kind": "house", "conn": [], "sockets": ["G", "G", "D", "G"], "weight": 1.6})
	mods.append({"kind": "tree", "conn": [], "sockets": ["G", "G", "G", "G"], "weight": 1.4})
	mods.append({"kind": "grass", "conn": [], "sockets": ["G", "G", "G", "G"], "weight": 2.2})
	return mods


static func layout(w: int, h: int, seed: int) -> WFC:
	var mods := layout_modules()
	var house := mods.size() - 3
	for attempt in 50:                                     # a contradiction restarts with the next seed
		var wfc := WFC.new()
		wfc.setup(w, h, mods, LAYOUT_FITS, seed * 1000 + attempt)
		wfc.noise = 0.05
		for x in w:
			wfc.ban((h - 1) * w + x, house)                # a door can't face the map edge
		if not wfc.propagate_all():
			continue
		var sx := w / 2 - 1 + int(wfc.rand() * 2.0)
		var sy := h / 2 - 1 + int(wfc.rand() * 2.0)
		if wfc.run(sy * w + sx, house):                    # the first cell is a house in the middle
			wfc.set_meta("attempt", attempt)
			return wfc
	return null


# Pass 2 modules: fence pieces join left end, middle, middle, right end (so a run is at least 4 spots long),
# and no fence stands right above another (N/S socket f never touches f).
const DETAILS := [
	{"kind": "empty", "sockets": ["n", "n", "n", "n"], "weight": 2.6},
	{"kind": "fence", "sockets": ["f", "a1", "f", "n"], "weight": 1.2},
	{"kind": "fence", "sockets": ["f", "b1", "f", "a2"], "weight": 1.2},
	{"kind": "fence", "sockets": ["f", "c1", "f", "b2"], "weight": 1.2},
	{"kind": "fence", "sockets": ["f", "n", "f", "c2"], "weight": 1.2},
	{"kind": "flower", "sockets": ["n", "n", "n", "n"], "weight": 2.2},
	{"kind": "mushroom", "sockets": ["n", "n", "n", "n"], "weight": 0.1},
	{"kind": "tuft", "sockets": ["n", "n", "n", "n"], "weight": 0.15},
	{"kind": "pebble", "sockets": ["n", "n", "n", "n"], "weight": 0.18},
	{"kind": "bush", "sockets": ["n", "n", "n", "n"], "weight": 0.7},
]
const DETAIL_FITS := [["n", "n"], ["n", "f"], ["a1", "a2"], ["b1", "b2"], ["c1", "a2"], ["c1", "c2"]]


static func ground(lay: WFC) -> Array:
	# the dual grid corners of pass 1 (2 tiles per cell): true = grass, false = dirt
	var w := lay.width
	var h := lay.height
	var g := []
	for y in h * 2 + 1:
		var row := []
		row.resize(w * 2 + 1)
		row.fill(true)
		g.append(row)
	for y in h:
		for x in w:
			var m: Dictionary = lay.modules[lay.result[y * w + x]]
			if m["kind"] == "road":
				g[y * 2 + 1][x * 2 + 1] = false
				for d in m["conn"]:
					var v: Vector2i = WFC.DIRS[d]
					g[y * 2 + 1 + v.y][x * 2 + 1 + v.x] = false
			if m["kind"] == "house" and y + 1 < h and lay.modules[lay.result[(y + 1) * w + x]]["kind"] == "road":
				g[y * 2 + 2][x * 2 + 1] = false            # the front path runs up to the door
				g[y * 2 + 3][x * 2 + 1] = false
	return g


static func details(lay: WFC, seed: int) -> WFC:
	var w := lay.width * SPOTS
	var h := lay.height * SPOTS
	var g := ground(lay)
	var kind := []
	var grass := []
	for y in h:
		for x in w:
			kind.append(lay.modules[lay.result[(y / SPOTS) * lay.width + x / SPOTS]]["kind"])
			grass.append(g[y / 2 + y % 2][x / 2 + x % 2])   # each corner covers the 2 x 2 spots around it
	var near := func(y: int, x: int, what: String, r: int) -> bool:
		for yy in range(y - r, y + r + 1):
			for xx in range(x - r, x + r + 1):
				if yy >= 0 and xx >= 0 and yy < h and xx < w and kind[yy * w + xx] == what:
					return true
		return false
	var wfc := WFC.new()
	wfc.setup(w, h, DETAILS, DETAIL_FITS, seed)
	wfc.noise = 0.3
	for y in h:
		for x in w:
			var c := y * w + x
			var allowed := {0: 2.6}
			var k: String = kind[c]
			if k != "house" and k != "tree":
				if not grass[c]:
					allowed[8] = 0.18                      # pebbles only lie on dirt
				else:
					# the row right above a house or tree: its roof or crown hangs over it
					var low: bool = y + 1 < h and kind[c + w] in ["house", "tree"] and kind[c + w] != k
					var edge := false
					for v in WFC.DIRS:
						var q: Vector2i = Vector2i(x, y) + v
						if q.x >= 0 and q.y >= 0 and q.x < w and q.y < h and not grass[q.y * w + q.x]:
							edge = true
					if not low:
						allowed[7] = 1.6 if edge else 0.15      # tufts, mostly along path edges
					var dirt_below: bool = y + 1 < h and kind[c + w] not in ["house", "tree"] and not grass[c + w]
					var dirt_above: bool = y > 0 and kind[c - w] not in ["house", "tree"] and not grass[c - w]
					if (dirt_below or dirt_above) and near.call(y, x, "house", 3) and not low:
						for f in [1, 2, 3, 4]:
							allowed[f] = 1.2                  # yard fences line a road
					if near.call(y, x, "house", 1) and not low:
						allowed[5] = 2.2                      # flowers only grow near houses
					if near.call(y, x, "tree", 1) and not low:
						allowed[6] = 0.1
						allowed[9] = 0.7                      # mushrooms and bushes by the trees
			var ws: PackedFloat64Array = wfc.weights[c]
			for m in DETAILS.size():
				if allowed.has(m):
					ws[m] = allowed[m]
				else:
					wfc.ban(c, m)
			wfc.weights[c] = ws
	wfc.ban_edges("n")
	if not wfc.propagate_all():
		return null
	# grow from the grass spot nearest the first house's front door
	var first: int = lay.steps[0][0]
	var door := Vector2i((first % lay.width) * SPOTS + 2, (first / lay.width) * SPOTS + SPOTS)
	var start := -1
	var best := 1 << 30
	for c in w * h:
		if kind[c] == "house" or kind[c] == "tree" or not grass[c]:
			continue
		var d := Vector2i(c % w, c / w) - door
		if d.x * d.x + d.y * d.y < best:
			best = d.x * d.x + d.y * d.y
			start = c
	if not wfc.run(start):
		return null
	return wfc


static func _combinations(items: Array, k: int) -> Array:
	if k == 0:
		return [[]]
	var out := []
	for i in items.size():
		for rest in _combinations(items.slice(i + 1), k - 1):
			out.append([items[i]] + rest)
	return out

Tested in Godot 4.6:

  • 200 villages of 8 x 6 cells (seeds 1 to 200) all solve, none hits a contradiction, and the same seed gives the same village.
  • The first pick is always a house in one of the 4 middle cells.
  • Every door faces a road: 1,226 houses, none with grass, a tree or the map edge below.
  • Every road end meets a road, a door or the map edge, and no road runs into the side of another road.
  • The detail pass solves for seeds 1 to 12 (32 x 24 spots each). Nothing lands on a house or tree cell.
  • All 12 fence pieces stand on grass next to a lane with a house within 3 spots and never in a row a roof hangs over, every run has a left end, middles and a right end, the shortest run is 4, and no fence stands right above another.
  • All 213 flowers are within 1 spot of a house and never in a row a roof hangs over, all 142 pebbles lie on dirt, and all 109 bushes and 15 mushrooms grow next to a tree.
  • 200 villages plus 12 detail passes take under a second in Godot.

Other engines

The solver is plain data, so it ports as is. In Unity, store the options in a ulong per cell and draw the result with Tilemap.SetTile (a RuleTile handles the road edges) and prefabs for houses and trees. In Godot you can also paint the lanes with TileMapLayer.set_cells_terrain_connect instead of the dual grid. I didn't run those versions.

Common pitfalls

Too many pieces of one kind. Weights are per module, so 11 road pieces at a house's weight bury everything else. Scale a big family down.

Contradictions. Tight sockets can leave a cell with nothing that fits. Restart with a new seed, keep a "plain ground" module that fits most sides, and run a few hundred seeds in a test before you trust the rules.

Picking cells at random. Without lowest entropy first, pieces land everywhere at once and contradictions get far more likely. Growing from picked cells also makes the map read as one place.

Details that ignore the layout. My first detail pass put flowers on roofs. The house sprite is taller than its cell and covers the row above. Block the spots a sprite hangs over.

Rules that can never fire. My first fence rule needed 4 grass spots in a row by a lane, but front paths cut the grass between houses into gaps of 2. Count how often each module gets placed in a test, and look at any that never shows up.

Slow propagation. Checking every pair of modules with string sockets on every step is slow. Store each cell's options as a bitmask and build the table of what fits on each side once. pick_cell() also scans every cell each step, which is fine for a few thousand cells; on big maps keep the open frontier cells in a heap.

Where to next

Add this to your game with your coding agent

The prompt has the numbers, pseudo code, pitfalls and checks from this guide, written so your agent can fit it into your own project.

# Add wave function collapse map generation to my game

My game needs generated maps that make sense: roads that join up, houses that face a road, details where they belong. Build a wave function collapse (WFC) solver and run it twice: once for the layout, then on a finer grid for the details, with detail rules that read the finished layout.

Before you write code, look at my project: the engine and language, how maps are drawn (tilemap, tile size, sprites, y-sorting), and what terrain and props I have art for. Fit this into what is there instead of adding a second map system, and keep my tile size and art. If my game is not a village, ask me which modules and rules I want. Tell me where the weights and rules can be tweaked.

## How it works

- Every cell keeps the set of modules it could still become, as a bitmask.
- Every module has a weight and a socket per side (N, E, S, W). Two cells can be neighbors only if the sockets on their shared side are a listed pair.
- Loop: pick the open cell with the lowest entropy, pick one of its modules at random by weight, then remove from each neighbor every module that no longer fits, and keep going through neighbors that changed (propagation).
- Grow from a start cell: only open cells next to a picked cell compete; if none are left but open cells remain, all of them do.
- A cell with no options left is a contradiction: restart the layout with the next seed.
- Pass 2 splits each layout cell into 4 x 4 spots. Each spot's allowed modules and weights come from the layout around it.

## Numbers that matter

- Entropy = log(W) - sum(w * log(w)) / W over the modules a cell still allows, W = their total weight. Add random 0 to 0.05 to break ties (pass 2: 0 to 0.3).
- Layout: 8 x 6 cells of 32 px, 14 modules: 11 road pieces (every set of 2, 3 or 4 connected sides, no dead ends), house, tree, grass.
- Sockets: roads R on connected sides, s on the others; house G on N, E, W and D (front door) on S; tree and grass G all round. Pairs (each works both ways): R-R, s-G, s-s, G-G, s-D, D-R. No edge rule in the layout pass, so roads may run off the map; houses are banned from the bottom row.
- Weights: grass 2.2, house 1.6, tree 1.4, roads 0.3 x (straight 1.4, corner 0.7, T 0.3, crossing 0.08). The first pick is a house in one of the 4 middle cells.
- Dirt: a road's lane is 2 spots (16 px) wide through the middle of its cell and out to each connected side. Below a house with a road under it, a front path covers the house cell's bottom spot row and the road cell's top row, 2 spots wide.
- Details on 8 px spots, nothing on house or tree cells. "Within n spots" counts diagonals (a square of side 2n + 1 around the spot) and means a spot of a house or tree cell. Empty 2.6; pebble 0.18 on dirt only; flower 2.2 within 1 spot of a house; bush 0.7 and mushroom 0.1 within 1 spot of a tree; tuft 1.6 on grass with dirt on one of its 4 sides, 0.15 on other grass; fence pieces 1.2 each, on grass with dirt directly above or below and a house within 3 spots. Nothing but pebbles and empty in the spot row right above a house or tree cell (its sprite hangs over it).
- Fence sockets (W, E): left end (n, a1), middle 1 (a2, b1), middle 2 (b2, c1), right end (c2, n). Pairs: a1-a2, b1-b2, c1-a2, c1-c2, n-n. Fences have N/S socket f, everything else n; n-n and n-f fit, f-f never. The map edge counts as n.
- Pass 2 starts at the grass spot nearest the first house's door (the middle of its cell's bottom edge); on a tie, the first in row order. Fence runs come out 4, 6, 8 spots long.

## Pseudo code

```
function solve(w, h, modules, pairs, seed, start, forced = none):
    allowed[d][a] = bitmask of b where (modules[a].socket[d], modules[b].socket[opposite(d)]) in pairs
    domain[c] = all modules, minus bans                # bans: map edge, unary rules
    propagate(all cells)
    collapse(start, forced)
    while true:
        c = unpicked cell with the lowest entropy(c) + random() * noise (a new random per cell, every step),
            only among cells next to a picked cell (all open cells if none)
        if no c: return result
        if not collapse(c, none): return contradiction

function collapse(c, forced):
    m = forced or weighted random among modules in domain[c]
    domain[c] = {m}; result[c] = m; mark the 8 cells around c as next to a picked cell
    return propagate([c])

function propagate(stack):
    while stack not empty:
        c = stack.pop()
        for each side d with a neighbor n:
            ok = OR of allowed[d][a] for every a in domain[c]
            keep = domain[n] AND ok
            if keep is empty: return false
            if keep != domain[n]: domain[n] = keep; stack.push(n)
    return true

layout = solve(8, 6, village modules, village pairs, seed, a middle cell, forced = house)
spots = for each 8 px spot: allowed modules and weights from layout (see numbers)
details = solve(32, 24, detail modules, detail pairs, seed, spot nearest the first door)
```

A 64 bit int holds up to 62 modules (GDScript int, C# `ulong`). Draw with your tilemap (Godot `TileMapLayer.set_cell`, Unity `Tilemap.SetTile`) plus sprites sorted by their bottom edge.

## Pitfalls

- Weights are per module: 11 road pieces at a house's weight take over the map.
- Without lowest entropy first, pieces scatter and contradictions get far more likely.
- In GDScript, a packed array inside an Array is a copy: write a changed weights array back. Reach scripts with `preload` in tests; `class_name` needs an editor import first.
- A rule can silently never fire (fence runs need 4 spots in a row). Count placements per module in a test.
- Use one seeded random generator for everything (and the next seed for a restart), so a seed always gives the same map.

## Check that it works

- 200 seeds solve with no contradiction, and the same seed gives the same map twice.
- Every house has a road cell directly below it; no house in the bottom row.
- Every road connection meets a road connection, a door or the map edge, and no road runs into the side of another road.
- Every pebble is on dirt, every flower within 1 spot of a house, every bush and mushroom next to a tree, nothing on house or tree cells, nothing but pebbles in a row a sprite hangs over.
- Every fence run starts with a left end, ends with a right end, is at least 4 spots long, and no fence is directly above another.
- A debug view of each open cell's remaining options shows them shrinking around every pick.

## Art it needs

A grass and dirt ground that can draw 2-spot lanes, houses that fit one cell with the door at the bottom center, trees, and small details. Cheapest first: colored shapes to test the generator, then my existing tiles and props mapped to the modules, then, if the SpriteCook MCP tools are available in this session, a generated grass and dirt tileset and exact-size sprites.

Source: SpriteCook (2D game assets made by your coding agent, for Claude, ChatGPT and Cursor)
Full guide with pictures, a video and tested Godot code: https://www.spritecook.ai/blog/wave-function-collapse-explained

More game techniques

All techniques