WFC Tiles
A Simple Example
March 17, 2023 - Tommy Dräger
"Wave Function Control" (abbr. WFC) is a rabbit hole! It is defenitly one of the algortihms that will drasticly change procedual generation in the future. The priniciple of WFC and superposition is well known in quantum physics, but it never had a real usecase. The user mxgmn (Maxim Gumin) ignited the hype around WFC. And creative people around the world started to catch wind of this like Oscar Stalberg, who also brought irregular grids into play to create awesome results. This project is my attempt to make myself familar with the algorithm itself. Originally it was my goal to also use wfc with 3d tiles on an irregular grid, but it turns out that 3d programs like houdini and blender recently started to add their own WFC implementation, which were more than enough for my purposes. So I considers this to be a learning project which might be a good start for a similar project in the future.
What is WFC?
WFC is a procedural generation algorithm that uses a grid-based approach to create patterns or layouts by adhering to a set of constraints. It operates similarly to the concept of superposition in quantum physics, where multiple states coexist until an observation collapses them into a single state.
In simple terms!
Imagine a tiled map where each cell could be one of the following kind ["Grass", "Beach", "Water","Mountains"]. Now you think of a ruleset to determine which cell can be next to each other. Easy: "Water can be next to mountain.. would be weird", so as a rule I decide that Water can only be next to Beach, and Beach can only be next to Water or Grass. Grass can only be placed next to Beach or Mountains. And finally Mountains can only be surrounded by Grass.
In the beginning the grid is completely non determined. Every cell could be potentially every Cell. So you make a random decision where to start and what the first Cells Type should be. This will immediately have an effect on the possibilities on the neighboring cells. You continue by choosing the cell with the least possibilities and make again a random choice on the type. Its like a chain reaction which will result in a nice looking map that accurate to your ruleset.
Have a look at Martin Donalds Video:
Martin Donald - Superpositions, Sudoku, the Wave Function Collapse algorithm
How Does WFC Work?
-
Input Model: The process begins with an input model, or in this case a set of predefined rules.
-
Tile Superposition: Initially, each tile of the grid is in a state of superposition, meaning it can potentially collapse into any state which is not decided yet.
-
Constraint Propagation: The algorithm uses the rules set to limit the possibilities of each tile. A simple random choice will decide in which state the cell will collapse. After that the algorithm will visit the adjacent cells, and the neighbors neighbors to strike out all state that are no longer possible.
-
Entropy Calculation: Each tile's entropy (the number of possible states), is calculated. Tiles with lower entropy are collapsed first, which reduces the number of potential configurations for neighboring tiles.
-
Collapse and Observe: The tile with the lowest entropy is observed, collapsing into a single state that conforms to the constraints. This step continues iteratively, propagating constraints to neighboring tiles until the entire grid is collapsed.
Demonstration
Click here to check out this simple example:
https://apps.fenixfox-studios.com/wfc_simple_tiles/
Conclusion
Wave Function Collapse is a powerful tool in the realm of procedural generation, blending computational algorithms with creative design. By understanding the mechanics and principles behind WFC, developers can harness its potential to create complex and visually appealing content.
Acknowledgments
Special thanks to mxgmn for pioneering this algorithm and to Oscar Stalberg for showcasing its creative applications.