Open-source project
mxgmn/WaveFunctionCollapse avatar
mxgmn/WaveFunctionCollapse

WaveFunctionCollapse: constraint propagation from one example bitmap

Bitmap & tilemap generation from a single example with the help of ideas from quantum mechanics

25,519 stars1,369 forksC#NOASSERTION

At a glance

What is it?
The reference C# implementation of the overlapping and tiled WFC models. It generates bitmaps and tilemaps that are locally similar to a single input, and it can fail outright when it hits a contradiction.
Who is it for?
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.
Can I use it commercially?
Check first. The repository uses a licence we do not classify automatically, so read its LICENSE file before any commercial use.
Is it still maintained?
Yes. The repository last received commits 31 days ago.
What is it written in?
Mainly C#, according to GitHub's language statistics.

Answers come from the project's GitHub data, last synced on November 13, 2026, and from our analysis. They are not legal advice.

From daily snapshots

Star history

  • mxgmn/WaveFunctionCollapse25,519 ★ · +197
Star history
Repository2026-09-132026-11-13
mxgmn/WaveFunctionCollapse25.3k25.5k

197 Stars in the last 61 days, measured from the daily GitHub snapshot. Compare with other projects

Editorial analysis

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.

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 exact build steps are in the README's how to build section. The repository root holds WaveFunctionCollapse.csproj, Program.cs, samples.xml, samples/ and tilesets/. The workflow is: the program reads an input bitmap, counts NxN patterns, and writes or displays an output. 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 samples.xml.

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, so check Program.cs to see how the reference program handles a failed run before adding your own retry logic.

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.

The third case is production support. This is a reference implementation with a v1.00 release from 2022 and no homepage. 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.

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. 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.

Frequently asked questions

what is wave function collapse

In procedural generation, it is a constraint-satisfaction algorithm that fills an output using only the small square patches found in a sample image, so nothing appears in the result that was not present in the example. It repeatedly picks the undecided region with the lowest entropy, chooses a patch for it, and propagates the consequences. Despite the name, the coefficients are real rather than complex numbers and the program does not perform quantum mechanics.

What games use wave function collapse?

The repository credits a list of commercial titles that used the algorithm, including Bad North, Caves of Qud, Townscaper and Dead Static Drive, plus several smaller games and a number of prototypes. The list is undated, so it evidences that the technique reached shipped games rather than which version any of them used. The README also links academic work describing what the algorithm led to.

wave function collapse alternatives

The alternatives the README lists are ports rather than competitors. Thirteen implementations in other languages are listed, along with adaptations to Unity, Unreal Engine 5, Godot 4 and Houdini. The practical alternative to the general bitmap approach is the project's own simple tiled model, where you supply adjacency rules directly instead of a sample image.

Official sources

  1. Issues
  2. mxgmn/WaveFunctionCollapse on GitHub
  3. README
  4. Releases
Add this badge to your README

If you maintain this project, the badge below links readers to this analysis and shows its maintenance status from the daily GitHub snapshot. Paste the markdown into your README; add ?metric=license or ?metric=stars to the image URL for a different field.

Add this badge to your README

markdown
[![Hysen Labs](https://hysenlabs.com/badge/mxgmn-wavefunctioncollapse.svg)](https://hysenlabs.com/projects/mxgmn-wavefunctioncollapse)

Star history chart for your README

markdown
[![Star history](https://hysenlabs.com/chart/mxgmn-wavefunctioncollapse.svg)](https://hysenlabs.com/projects/mxgmn-wavefunctioncollapse)

Was this useful?