A wavefunction collapse solver is a type of backtracking solver that generates a set of constraints from a sample, and then uses the constraints to generate an output based on those constraints. The sample could take on a variety of forms: pixels in an image, tiles in a 2D game, preset volumes in a 3D game, or even words in a sentence. As long as the sampler can determine neighbor relationships from the sample, those relationships can be used to constrain the output into a similar form as the sample.
Below is an example of the solver running in the terminal with colored letters representing Land, Coast, and Sea tiles. The training example is displayed at the top. The output conforms to the characteristics of that image.
To find the relationships between elements in the sample, the constraint generator looks at each element in the sample. For each kind of element, it tracks what kinds of neighbors it sees. These tables determine what kinds of relationships will be allowed in the generated output. If the solver never saw two kinds of elements next to each other, those kinds of elements will not be allowed to be next to each other in the output.
For added texture, the constraint generator can first batch neighboring elements into tiles, e.g. 2x2 or 3x3 subgrids. It then runs the neighbor detection on the tiles instead of directly on the elements. Larger subgrids allow larger features to remain coherent in the output, while smaller ones allow for more flexibility.
When generating output, the solver initializes the output such that each element (or tile) is in a sort of ‘superposition’ where it is simultaneously all possible elements. Then the solver visits each unvisited element in turn and chooses one of the remaining possibilities, ‘collapsing’ it into a specific concrete value. Then the solver must update the neighbors by removing possibilities that have been invalidated by the most recent collapse.
If an element ever has no possibilities, the solution must be invalid, so the solver backs up and tries another element instead. Normally this would cause the solver to try many possibilities and can take a long time to solve. However, when the solver is choosing a new element to collapse it selects the one with the fewest remaining possibilities. This means that each element has to iterate through the smallest number of possibilities which makes backtracking as cheap as possible.
In addition, custom constraints can be written for the solver. In these conditions, the solver is no longer a true WFC solver, since the constraint generation portion is abandoned. However, This allows the solver to solve other types of problems like sudoku.
First is an example of an attempt at hand writing some constraints to generate a land mass similar to the above example. In the hand written version, the only constraint is that sea and land must not touch. This allows the coastline to orient in the north-south direction, as well for the speckled islands and sand traps across the output. Additional constraints could be written to more closely match the previous version, but this would be very verbose.
A sudoku can also be solved by writing custom constraints to disallow the same number from appearing in the same row, column, or box. This solves the sudoku quickly due to the way the backtracking solver selects its next cell to collapse. In the below image, the number of backtracks required to arrive at the solution is displayed. This number is not stable and varies depending on the run. This is because the normal solver uses some randomness to make the generated output more varied and interesting from run to run.
The sudoku solver uses custom-written constraints, but it might be interesting to explore a way for the constraint generator to arrive at the same constraints. One way to do this could be to customize how neighbors are determined. Instead of the normal up-down-right-left, all cells in the same column could be considered neighbors along one dimension. Then the same for rows and boxes. Maybe this way the generator could infer that numbers are not to be repeated along each of those axes.
Future improvements and features could include the following.