A from-scratch implementation of Maxim Gumin's Wave Function Collapse algorithm in C# with raylib for visualisation. My implementation will not be the absolutely most optimal, and neither will it have the fewest files or lines of code. This type of implementation is already done by Gumin.
Wave Function Collapse is a constraint-solving procedural generation algorithm. Given a small set of tiles and adjacency rules, it fills a grid with a coherent pattern that obeys those rules. This lets you generate maps, textures, levels, and other patterns from a handful of authored constraints.
This project initially implements the Tiled Model flavor of WFC (hand-authored tiles + adjacency rules), with step-by-step visualisation so you can watch the algorithm collapse the grid in real time.
To improve, I would implement the Overlapping Model, which is the cooler WFC model. In this model, the program learns the rules itself from a sample image rather than hand written rules.
I came across Wave Function Collapse randomly in some video game context I can't recall. I assumed it referred to the Wave Function Collapse from phyiscs. Although, that made no sense. As I looked into it, I learnt the algorithm was quite cool and I wanted to visualise it, similarly to what Gumin and many others have already done. I chose C# for two main reasons. Firstly, Gumin's code is written in C#, so I'll have something to refer back to if I get stuck... Moreover, I suspect I will exposed to C# during my internship, so I'm just brushing up on those skills.
- C# / .NET 10
- Raylib-cs
Requires the .NET 10 SDK.
dotnet runEvery cell in the grid starts in a superposition of all possible tiles. Each step, the cell with the lowest entropy is collapsed to a single tile, chosen by weighted random. That collapse propagates outward: each neighbour drops any tile that no longer has a compatible partner, and if its option set shrinks, the ripple continues to its neighbours. The process terminates when every cell holds exactly one tile, or, if a cell is ever left with zero options, it restarts.
- Robert Heaton — The Wavefunction Collapse Algorithm explained very clearly
- Martin Donald — Superpositions, Sudoku, the Wave Function Collapse algorithm
- Oskar Stålberg — Wave Function Collapse in Bad North
- Maxim Gumin — WaveFunctionCollapse reference implementation