Wave Function Collapse Visualizer
Overview
This project is a visualization of the Wave Function Collapse algorithm being used to randomly generate a 3d maze the player can walk around in. Players can change parameters of the maze to see how the algorithm changes when given different inputs.
Below I've written up a description of Wave Function Collapse using what I learned during my research. I described how I implemented the algorithm and problems I ran into. I really recomend checking it out!
ROLES:
Entire project including research, implementation, UI work, polish, and playtesting
DURATION:
2 Weeks
ENGINE:
Unity
PLATFORMS:
Windows
Wave Function Collapse: What is it?
The Wave Function Collapse Algorithm is a procedural generation algorithm that can make really cool randomized maps. If you give it a series of tiles and rules for which tiles can be adjacent to each other, it will make a map that follows all those rules (if that's possible given the ruleset).
If you've played Sudoku, you've probably used Wave Function Collapse
In Sudoku, you want to find the space with the fewest possible numbers that fit the ruleset. If you have a row with all the numbers except a 5, you know the one missing space is a 5! Once you fill that in, you find the next space with the least possible numbers and repeat.
WFC works the same!! It picks a space that has the fewest possible tiles and collapses down to one choice (usually through weighted random selection). It then finds the next space with the least possible tile choices and repeats until a full map is formed.
There's a really cool playable example here: Wave - by Oskar Stålberg (oskarstalberg.com)
WFC Examples
Wave Function Collapse has been used in many different ways. Here are some examples:
Disclaimer: These are NOT mine
My Implementation
While some implementations of the Wave Function Collapse algorithm use tens of different components to stich together intricate environments, I decided to keep it simple and only use a few building blocks to make a random maze-like structure.
Each yellow structure here has a WFC component script that tracks which sides are open and closed. When they're being put together, open sides must always connect to open sides and the outside perimeter of the maze must be closed.
When the player inputs their desired size for the maze, the system will place down a grid of equally spaced WFC Nodes. They will then add the restriction to every node on the outside saying "you can't use any structures with open edges facing the border". The system then informs nearby nodes so they can remove any options that are no longer available. Then the system randomly picks a node with the fewest possible options (which in our case is one of the corners). It will randomly select one of the available options for that node and let all adjacent nodes know what node was chosen so they can update their options accordingly.
