Lesson 10

Wave function collapse, Poisson discs and L-systems

Three generators that work from rules instead of noise: wave function collapse fills a grid so every neighbour fits (and sometimes paints itself into a corner), Poisson disc sampling scatters things without clumps, and L-systems grow plants by rewriting strings.

Noise and dungeon generators decide shapes. The three techniques here start from rules instead: which tiles may sit next to each other, how close two things may be, how a branch grows. All three run on the procgen lab’s generators, seed 1 unless the text says otherwise.

Wave function collapse

Maxim Gumin’s WaveFunctionCollapse (2016) fills a grid with tiles so that every pair of neighbours is allowed by a set of adjacency rules. This lesson uses its simple tiled model, where you write the tiles and their rules yourself. (The overlapping model learns the rules from every small patch of a sample bitmap instead.)

The name comes from the state it keeps. Every cell starts as a “superposition” of every tile, stored as a set (here, a bitmask). Then repeat:

Observe: pick the undecided cell with the lowest entropy: the fewest, least even options left.
Collapse it to one of its tiles, chosen at random by the tiles’ weights.
Propagate: remove from each neighbour every tile that no longer has a compatible partner in the cell that changed. If a neighbour lost anything, check its neighbours, and so on until nothing changes.

// allow[d][t]: mask of tiles that may sit in direction d of tile t.
bool propagate(std::vector<uint32_t>& wave, std::vector<int> stack) {
    while (!stack.empty()) {
        int c = stack.back(); stack.pop_back();
        for (int d = 0; d < 4; ++d) {
            int n = neighbour(c, d);
            if (n < 0) continue;
            uint32_t ok = 0;
            for (uint32_t m = wave[c]; m; m &= m - 1) ok |= allow[d][ctz(m)];   // anything a remaining tile allows
            uint32_t next = wave[n] & ok;
            if (next == wave[n]) continue;
            if (next == 0) return false;                                       // contradiction
            wave[n] = next;
            stack.push_back(n);
        }
    }
    return true;
}

Loading…

The Coast tileset marks each tile’s four corners as water, sand or grass, never water next to grass, which leaves 31 tiles; two tiles may be neighbours if the corners they share match. Numbers are the options left in a cell, and darker cells are less decided. Choosing the lowest-entropy cell keeps the solver working next to what it has already decided, which is why it seems to grow outwards from a few seeds and why it rarely paints itself into a corner.

Gumin’s README lists games that generate levels with WFC, among them Bad North, Caves of Qud and Townscaper, and Epic’s The Matrix Awakens demo.

Contradictions and backtracking

Propagation only compares neighbours pairwise, so it can miss that a cell will run out of options until it does: a contradiction, a cell with no tile left. Gumin’s README says this happens “surprisingly rarely” in practice, and his program simply starts again, up to 10 tries. The other answer is to backtrack: undo the most recent choice, forbid the tile that was chosen there, and propagate that.

Loading…

The Tracks tileset has only 6 tiles, the four bends and the two straights, so every cell must carry a track and no track may leave the map. On seed 1 on this 16 × 10 grid the solver hits 1 contradiction; backtracking clears it with 1 backtrack, restarting with 1 restart. Switch tilesets: Coast is far harder to break.

How often it happens depends on the tiles. Over seeds 1 to 100 on the lab’s 24 × 16 grid, Coast never hit a contradiction (sand fits next to both water and grass, so a cell always has a way out); Loops (pipes that must close up, map edges sealed) hit one on 5 seeds; Tracks, on 7. Backtracking finished all of them, but the 7 Tracks runs needed 1,093 backtracks between them: undoing only the latest choice can thrash when the real mistake was made much earlier.

Poisson disc sampling

Scatter trees, rocks or pickups uniformly at random and they clump: nothing stops two landing on top of each other, and there are holes. Poisson disc sampling keeps every pair at least a distance r apart while still looking random. Robert Bridson’s algorithm (SIGGRAPH 2007) does it in O(N):

Put one random point on an active list. A background grid with cells of side r/√2 holds at most one point each, so checking a spot means looking at a few cells, not every point.
While the list isn’t empty, pick a random active point and try up to k candidates (typically 30) in the ring between r and 2r around it. Keep the first that is at least r from every point and make it active.
If all k fail, retire the point.

while (!active.empty()) {
    int i = active[rng.below(active.size())];
    bool placed = false;
    for (int t = 0; t < k && !placed; ++t) {
        Vec2 c = pts[i] + random_in_ring(rng, r, 2 * r);
        if (inside(c) && far_from_all(grid, c, r)) { add(c); placed = true; }   // add() also activates it
    }
    if (!placed) remove(active, i);                     // no room around this one any more
}

Loading…

With r = 4 on a 100 × 60 map, Bridson’s algorithm on seed 1 places 237 points, none closer than r, leaving only 0.2% of the map with room for another. The same number of uniform random points has 253 pairs closer than r (the closest 0.18 apart) and 18.7% of the map still empty enough for another point. A jittered grid, one random point per cell, is cheaper and fairly even, but still has 59 close pairs. Fewer tries per point is faster but leaves gaps: with k = 10 it places 225.

Games use it for foliage, props and spawn points. Run it per chunk, seeding each chunk’s edge from its neighbours, or vary r over the map from a density texture for natural clearings and thickets.

L-systems

Aristid Lindenmayer’s L-systems (1968) rewrite a string in parallel: at each step every symbol that has a rule is replaced at once, which is what distinguishes them from ordinary grammars. Read the result with a turtle and you get a plant: F moves forward drawing a line, + and − turn by an angle δ, [ saves the position and heading and ] jumps back to it, which is what makes branches.

std::string rewrite(const std::string& s, const std::map<char, std::string>& rules) {
    std::string out;
    for (char c : s) {
        auto r = rules.find(c);
        out += r != rules.end() ? r->second : std::string(1, c);              // no rule: copy it
    }
    return out;
}

Loading…

The plants are from figure 1.24 of Prusinkiewicz and Lindenmayer’s The Algorithmic Beauty of Plants (1990), with the book’s rules, angles and step counts. The tree, 1.24d, starts from X with X → F[+X]F[−X]+X and F → FF; X draws nothing but steers the growth, and F → FF makes older stems keep lengthening, as real ones do.

The strings grow exponentially. After its 7 rewrites the tree is 13,956 symbols, of which 4,118 are lines; the weed, 1.24a, reaches 7,811 symbols in 5. That is why games grow a plant once, offline or at load, and keep the mesh. A stochastic L-system picks between rules at random (from the seed), so every plant differs but all are one species; switch to it and step the seed.

Takeaways

Wave function collapse: keep every cell’s possible tiles; observe the lowest-entropy cell, collapse it, propagate. Design tilesets with flexible tiles, and handle contradictions by restarting or backtracking.
Poisson disc sampling (Bridson): random points no closer than r, in linear time with an active list and a background grid. Uniform random clumps; a jittered grid still has close pairs.
L-systems rewrite every symbol in parallel and draw with a turtle. Strings grow exponentially, so bake the result.

In the lab

The lab runs WFC on all three tilesets with restart or backtracking, Bridson’s algorithm against uniform and jittered points with any r and k, and the six plants of figure 1.24 plus the stochastic one, all stepped either way.

Watch Tracks backtrack in the procgen lab →

Wave function collapse, Poisson discs and L-systems