WaveFunctionCollapse (WFC) originated as a GitHub repository created by Maxim Gumin on September 30th, 2016. The terminology of the algorithm is inspired by quantum mechanics. It made waves 😉 in creative development communities, and divined theses and white papers in academia.
Townscaper, built by Oskar Stålberg, uses the WaveFunctionCollapse algorithm! The screenshot was taken from the Steam page.
The sea change 😉 wrought by WFC owes to its novel formulation of pattern synthesis, which is relatively generic compared to other procedural approaches. To illustrate the difference, take for instance the donjon dungeon generator commonly used for tabletop role-playing games. Its Perl source code is specifically written for dungeon generation. That may seem obvious, but...
Please Explain!
As great as the donjon tools are and will remain to be, WFC demonstrates it may be unnecessary to invasively impose the "rules" of dungeon generation with explicit code, and that, instead, these rules can be extracted from samples as per the algorithm itself. This is not unlike the impetus for machine learning through artificial neural networks (ANNs), where supervised or unsupervised learning occurs. Élie Michel summarizes WFC's extraction process by offering the following image in a series of tweets:
Michel goes on to show that, as the procedural image is synthesized via each "slot," the extracted rules are obeyed (effectively constraint solving):
Thus, it's possible to generate some interesting, grid-based dungeons with WFC. But, as it happens, the topology of slots and their adjacency to others can be irregular! In other words, a strict square grid is not required for WFC to do its magic. One Twitter user has been taking advantage of just that à la Townscraper, reconciling WFC with the marching cubes algorithm in Godot:
Reconciling WFC with marching cubes. Pretty dumb and slow ATM. Editing voxel state triggers a full WFC re-collapse which is just fast enough to do in one frame on a 'small' globe (still 688 cells) because I ported it to GDNative. #procedural #indiedev #gamedev #screenshotsaturday pic.twitter.com/qxgfpO5snE
— Sam Bigos (@Calneon) January 17, 2021
Conclusion
To summarize, WaveFunctionCollapse is great for affording two properties:
- Generic pattern synthesis
- Permitting irregular topology
Since I'm merely singing the praises of WFC, if you're looking for additional learning resources, I recommend investigating the following:
- Keijiro Takahashi implemented WfcMaze in Unity with serious M. C. Escher vibes.
- Marian, a programmer at Hello Games, created an infinite, procedurally generated city in Unity.
- There is an explanatory demo for GameMaker Studio 2 by Jonathan Lam.
- Oh, look, a JavaScript port of WFC!
- Here's a talk on using WFC with Houdini by Paul Ambrosiussen.
- Oskar Stålberg presents how WFC was used in one of his games.
If you're interested, do something amazing with WFC and be the last splash!