WaveFunctionCollapse: constraint propagation from one example bitmap

The problem WFC solves, and who actually has that problem

Most procedural generation either assembles hand-written rules or trains a model. WFC takes a third route: you give it one example bitmap, and it produces new bitmaps that are locally similar to that example. The README defines local similarity with two conditions. C1 says the output should contain only those NxN patterns of pixels that are present in the input. Weak C2 says the distribution of NxN patterns in the input should be similar to their distribution over a sufficiently large number of outputs. In the examples, N is typically 3.

That framing matters because it tells you who this is for. If you already have a level, a texture, or a tile arrangement you like, and you want more of the same character without writing rules for it, the example is the specification. The repository is the canonical implementation in C#, and the README lists ports to C++, Python, Kotlin, Rust, Julia, Go, Haxe, Java, Clojure, Free Pascal, Dart, p5js and JavaScript, plus adaptations to Unity, Unreal Engine 5, Godot 4 and Houdini. It names Bad North, Caves of Qud, Dead Static Drive, Townscaper and Matrix Awakens as games where WFC generates levels. The README also states that it led to new research. So the audience is game and graphics engineers, and the reason to read this particular repository rather than a port is that it is the one the ports refer back to.

The observation and propagation cycle, and why the coefficients are booleans

The README describes the algorithm in five numbered steps. First, read the input bitmap and count NxN patterns, optionally augmenting the pattern data with rotations and reflections. Second, create an array with the dimensions of the output, called the wave in the source. Each element of that array represents the state of an NxN region in the output, and that state is a superposition of input patterns with boolean coefficients. False means the pattern is forbidden, true means it is not yet forbidden. Third, initialise the wave with every boolean coefficient set to true.

Then the loop. On each observation step, find the wave element with the minimal nonzero entropy and collapse it into a definite state, choosing according to its coefficients and the distribution of NxN patterns in the input. On each propagation step, the information gained from that collapse spreads through the output. The README notes that the number of non-zero coefficients decreases on each step until the wave is completely observed.

One detail is easy to misread. The README says the output bitmap starts with each pixel in a superposition of input colours, with real coefficients, and explicitly states that these are not complex numbers, so the program does not do actual quantum mechanics. The quantum vocabulary is a metaphor for the data structure. The mechanism is a constraint solver: boolean possibility sets, an entropy heuristic for picking the next cell, and propagation of the consequences. The entropy choice is not cosmetic. Picking the lowest-entropy region first means the solver commits where it has the least freedom, which is the standard way to reduce the chance of a late contradiction.

The simple tiled model is a different program wearing the same name

The README's tilemap section describes the simplest nontrivial case of the algorithm as NxN equal to 1x2, or more generally NxM. Simplify further by storing probabilities of colours rather than probabilities of pairs of colours, and you get what the README calls a simple tiled model. In that model the propagation phase is just adjacency constraint propagation, and the model is initialised from a list of tiles plus their adjacency data.

This is worth stating plainly because the two models have different inputs and different failure behaviour. The overlapping model derives its constraints from an example bitmap and a window size N. The simple tiled model derives them from a tile list and an adjacency table that you write or export yourself. The README's own framing is that the tiled model is a simplification of the overlapping one, but in practice the tiled model is the one that fits hand-authored tilesets, and the overlapping model is the one that fits an existing image. If you pick the wrong one for your asset pipeline, you will spend a long time trying to make the example bitmap carry information that only an adjacency table can express. The README's algorithm section describes the overlapping model; the tiled model gets a short section and no pseudocode.

Building it: what the README actually tells you

The README points to a section titled how to build from source, and offers three other routes: download an official release for Windows, download an interactive graphical version from itch.io, or run it in the browser. The most recent release listed is v1.00, dated 2022-07-21. The repository's last push is dated 2026-03-22 and it is not archived.

The README does not reproduce the build commands or the project file names in the portion available here, so I cannot give you a verified command line. What the material does support is the shape of the workflow: the program reads an input bitmap, counts NxN patterns, and writes or displays an output. The graphical version and the in-browser version exist precisely because the command-line path expects you to supply an input image and a window size. Treat the how to build section as the authoritative source for the exact invocation, and check which sample project corresponds to the model you want, because the repository contains samples for both the overlapping and the tiled model and they are configured differently. If you need a specific config key name, read the sample source rather than guessing from this description.

Contradictions are a normal outcome, not a bug

The README is unusually direct about failure. During propagation, all the coefficients for a certain pixel can become zero. That means the algorithm has run into a contradiction and cannot continue. The README states that determining whether a certain bitmap allows other nontrivial bitmaps satisfying C1 is NP-hard, so it is impossible to create a fast solution that always finishes. It then adds that in practice the algorithm runs into contradictions surprisingly rarely.

Step 5 of the algorithm makes the contract explicit: at the end, every wave element is either completely observed, with all coefficients except one at zero, or contradictory, with all coefficients at zero. In the first case the program returns the output. In the second case it finishes without returning anything. There is no partial result and no repair pass described in the README. That is the limitation to design around. If your pipeline treats a generation call as infallible, WFC will eventually hand you nothing, and the frequency of that event depends on the input, the window size, and whether you enabled rotations and reflections. Retrying with a different random seed is the obvious response, but the README does not describe a retry mechanism, so that logic belongs in your code, not in the library.

Where WFC is the wrong tool

Local similarity is a weak guarantee, and the README says so by labelling C2 as weak. The output contains only patterns seen in the input, and the pattern distribution over many outputs approximates the input's. Nothing in those two conditions promises that a generated level is playable, that a room is reachable from another room, or that a path exists between two points. If your requirement is a connected dungeon or a solvable puzzle, C1 and C2 do not address it, and you will need to check connectivity after generation and discard or repair the results.

The second case where this is the wrong tool is control. Because the constraints come from an example, the example is the only lever you have over the output's character. The simple tiled model gives you more direct control through the adjacency table, but it still does not give you placement rules, named regions, or scripted events. If your design needs a boss room at a specific depth, WFC is not the system that decides that. You can constrain cells before generation, but the README does not document such an interface, so you would be working against the grain of the reference implementation.

The third case is production support. This is a reference implementation with a v1.00 release from 2022 and no homepage. The README devotes more space to ports, forks and spinoffs than to the API. If you need a maintained library with semantic versioning and a support channel, one of the engine adaptations listed in the README is a better starting point, and you should evaluate that project on its own terms.

A real alternative, and the actual difference in approach

The README itself points at a concrete alternative: the JavaScript port by kchapelier, which is linked both in the ports list and as the in-browser example for the overlapping model. The difference is not cosmetic. The C# repository is the reference implementation, and the README's build section, release downloads and sample projects all assume you are working in that environment. The JavaScript port runs in a browser, which makes it the practical choice if you want to evaluate whether WFC suits your tileset before committing to a C# build, or if your target is a web game.

The trade-off runs the other way too. The README lists the ports and adaptations without ranking them, and it does not claim that any port is feature-equivalent to the C# original. Ports also diverge over time. The C# repository's last push is 2026-03-22, and a port's maintenance status is a separate question you would have to check at its own repository. If you are already in C# or .NET, staying with the reference implementation removes a translation layer and keeps you closest to the algorithm description in the README. If you are not, the port is not a compromise; it is the intended path, and the README presents it that way.

Maintenance, licence and what to verify before you commit

The repository is not archived, the default branch is master, the last push is 2026-03-22, and the most recent release is v1.00 from 2022-07-21. That combination suggests a project that is still touched but not releasing. For an algorithm reference implementation that is a reasonable state to be in. For a dependency in a shipped product it means you should expect to read the source when something behaves unexpectedly, because there is no changelog trail between v1.00 and the current master.

Upgrade cost is therefore low in the sense that the algorithm is stable and the README's description of it has not needed to change, and high in the sense that there is no version boundary telling you what moved. If you vendor the code, you own it. If you track master, you are tracking an unreleased branch.

The licence field in the repository metadata reads NOASSERTION, which means no standard licence was detected. The README does not state licence terms in the portion available here. That is not a detail you can defer: check the licence file in the repository root before you copy code into a product, and if the terms are unclear or absent, get your own advice rather than inferring permission from the repository being public. The README lists commercial games that use WFC, but that says nothing about the terms of this repository.

Three things to verify first. Which model your intended sample uses, overlapping or simple tiled, because the inputs differ. How that sample handles the contradictory state described in step 5, because the README says the program returns nothing in that case. And the licence file itself, because the metadata does not name one.

Editorial conclusion

Adopt this repository if you want the reference implementation of the overlapping and simple tiled models, are comfortable in C#, and can treat a failed run as a normal outcome rather than an exception. Do not adopt it if you need a supported library with a stable API, a packaged editor integration, or a guarantee that generation finishes. Before committing, verify three things in the source: which model the sample you intend to adapt actually uses, how the contradiction path is handled in that sample, and what the repository licence file says, because the metadata reports NOASSERTION rather than a named licence.

Official sources

1. Issues
2. mxgmn/WaveFunctionCollapse on GitHub
3. README
4. Releases