The city that built itself

There is a city that nobody drew. No one placed its crossroads, no one decided that this block would get the tall building with the lit windows and that one would stay low. I pressed a key, looked away from the viewport for a few seconds, and when I looked back there were streets, pavements, façades, roofs, and a car politely waiting for another car at a junction that had not existed a minute earlier. It is the closest thing to watching frost grow on a window that my job has ever given me: order arriving on its own, out of nothing but rules about what is allowed to sit next to what.

The honest version of that story is less romantic. The city built itself because I had five days, and five days is not enough time to build a city.

Five days

The task itself belongs to a project I am not going to talk about yet, so the outline will have to do: I needed a working urban environment for VR, believable at street level, big enough to move through, and I needed it on a deadline that had already been half eaten by my computer deciding to die at the worst possible moment. What was left, by the time I had a machine in front of me again (someone else’s machine, reached over a remote desktop, which is its own story) was five days.

The by-hand version of this work is well understood and completely impossible in that window. You block out the road network, you lay pavements along it, you place buildings one by one, you dress the corners so they do not repeat, and three weeks later you have four streets. I did not have three weeks, and I have never particularly enjoyed being a bricklayer anyway.

So instead of building the city, I spent the time building the thing that builds the city.

What Wave Function Collapse actually is

Wave Function Collapse is a procedural generation algorithm with a stolen name. It was published by Maxim Gumin in 2016, the physics vocabulary is decoration, and the idea underneath is the one you already use to solve a Sudoku.

Divide the world into a grid of cells. Each cell will eventually hold exactly one tile from a set you designed: a piece of straight road, a corner, a stretch of pavement, a slice of façade. At the start, every cell could still be anything: every tile is possible everywhere, which is the “superposition” the name is winking at. Then you apply the only two moves the algorithm has. Find the cell with the fewest remaining options (the most constrained one, the cell closest to being decided) and decide it: pick one of its surviving tiles, at random, weighted however you like. Then let the consequences spread. Every neighbour of that cell now throws away the options that no longer fit against what you just placed, and their neighbours do the same, and so on outward until the ripple runs out. Repeat until every cell holds exactly one tile.

That is genuinely all of it. There is no global plan, no template of a city hiding anywhere in the code. All of the intelligence lives in one place: the compatibility rules, the list of which tile edges are allowed to touch. I encoded those as sockets: each side of each tile carries a label, ROAD, PAVEMENT, WALL, and two tiles may be neighbours only if the labels facing each other agree. A straight road ends in a ROAD socket, so the only tiles that can continue it are the ones that begin with one. Write enough of those small local agreements and coherence stops being something you author. It becomes something the grid cannot avoid.

The seductive part, and the reason this algorithm has a small cult around it (Oskar Stålberg’s Townscaper is the famous demonstration) is exactly that inversion. You never describe the result. You describe what is legal, and the result is whatever survives.

Pass one: the plan

My first solver runs flat, on the ground plane. Its tile set knows about roads, junctions, pavements, cycle lanes, and one more tile type that does not look like anything at all: the building plot. Its only job is to be the kind of cell that roads are not, to sit behind the pavement line, and to come out of the solve grouped into clean rectangular regions.

So pass one collapses the whole map and hands back a street network with the gaps between the streets explicitly marked. Those marked regions are the entire point of the pass. Everything that makes a city look like a city, the vertical part, is deliberately absent from this tile set, because it is somebody else’s problem.

Pass two: up

That somebody else is a second Wave Function Collapse, run once for each plot the first one produced. This one adds a dimension.

It starts at the ground floor and collapses it the same way as before: doors, shopfronts, blank wall, corners that agree with each other through their sockets. Then it moves up one level and does it again, except that the tiles of floor one are constrained not only by their horizontal neighbours but by the tiles of the floor directly beneath them. A window lines up over a window. A wall continues over a wall. Nothing cantilevers out over a doorway unless a tile explicitly exists that is allowed to. Floor by floor, each level inheriting its constraints from the one already decided, until the rules produce the only tiles that can end the column: roofs.

Splitting the problem in two is what made it tractable in the time I had. A single solver that understood roads and rooflines at once would have needed a tile set describing every legal combination of the two, and that set grows multiplicatively. Two solvers, each with a small vocabulary and a clean handoff between them, and suddenly each half is simple enough to debug in an afternoon. On a five-day budget, that is the only kind of debugging there is.

The sockets know the way home

Here is the part I am actually proud of, because it cost almost nothing.

A socket exists to answer one question during generation: may these two tiles touch? But a ROAD socket that matched during the solve is also a statement about the finished world: it says the asphalt on this tile physically continues onto the next one. The compatibility data and the connectivity data are the same data. So when the solve finishes, I read the sockets a second time: every collapsed road tile becomes a node, every matched ROAD socket becomes an edge, and the street network I never drew hands me its own graph for free.

On top of that graph, traffic is a solved problem rather than a research topic. Spawn cars on the edges, give each one a destination node, run a standard shortest-path search over the graph, and let a small amount of local etiquette handle the rest: a car approaching an occupied node waits, junctions get right-of-way, nobody drives through anybody. None of it is sophisticated, and none of it needs to be, because the hard part, knowing where the roads are in a world that did not exist until thirty seconds ago, was already paid for by the generator.

That is the move I will reuse from this project long after the project itself stops mattering: the rules you write to build a world are also a description of the world you built. Most of the time we throw that description away the moment generation ends. Keep it, and the environment comes out of the oven already knowing its own streets.

What five days buys

By the deadline there was a city you could put a headset on and ride through. Streets that meet properly, buildings that stand on their plots and agree with themselves all the way up to the roofline, traffic that flows and yields and occasionally forms a small, believable queue. A different seed, a different city, in seconds. The small personal result that came out the other side of that deadline is a story for another post, once I am allowed to tell it.

What I want to record now is the shape of the decision, because it is the same decision every time and I keep having to relearn it. With five days and a city to build, the instinct is to start laying bricks immediately, because bricklaying feels like progress and writing a solver feels like a gamble. The gamble is the right call more often than it feels like it. Hand-placed work is linear: every street costs what the last one cost. A generator is a cliff and then a plain: nothing works, nothing works, nothing works, and then on day three a whole city exists before lunch, and every city after it is free.

The algorithm did not know it was building a city. It knew that a road may continue a road, that a window sits over a window, that everything ends in a roof. It turns out that is what a city is: a few thousand small agreements, kept everywhere at once. I just wrote the agreements down and let the frost grow.