"Superpositions, Sudoku, the Wave Function Collapse algorithm" is a video published by Martin Donald that explains the Wave Function Collapse (WFC) algorithm, a procedural solver for generating content in video games. The video uses the example of solving a Sudoku puzzle to illustrate the algorithm's process of collapsing and propagating possibilities until a solution is reached.
The WFC algorithm begins with a grid of cells, each containing all possible states, referred to as the wave function. The algorithm identifies the cell with the lowest entropy and collapses it to a single state, then propagates the consequences of this collapse to other cells. This process is iterated until all cells contain only a single state, indicating that the wave function has collapsed.
To apply the WFC algorithm to game development, adjacency constraints are used to determine which modules can be connected in specific directions. Different implementations of the WFC algorithm use various methods to define adjacency constraints, such as analyzing example outputs, using a socket system, or employing a color-based system inspired by a demo by Oscar Stahlberg.
In the video, the creator showcases a method for validating adjacency between modules by labeling each module with sockets and checking their compatibility based on simple rules. The process involves analyzing each module, storing vertex positions along boundary profiles, and assembling a dictionary of socket names and profiles. Prototypes are then created for each module, containing information about the mesh, rotation, and lists of valid neighbors. This data is exported to a JSON file, which can be loaded into a game engine.
The WFC solver is implemented in the Godot game engine. The solver loads prototype data, initializes the wave function, and iterates through the wave function until it is fully collapsed. The constrain function is used to propagate changes to neighboring cells, and the final result is generated by instancing the corresponding mesh at the appropriate position and orientation for each remaining prototype.
