Wave Function Collapse
The goal for this project was to understand and implement the Wave Function Collapse (WFC) algorithm.
My reason for this was to get a better understanding on how this algorithm works and how it can be
used within the games industry.
As the graphics portion lays outside of the scope for this project, i decided to use the SFML library
to easily setup and render the WFC algorithm.
Generalist Programmer
Solo
3 weeks
Windows
No Engine
SFML
Research
Before starting with this project, I was aware of what the Wave Function Collapse (WFC) algorithm was
and what it was capable of doing, but not how the algorithm itself worked.
To get a better view of this algorithm, I first started out researching what the wave function meant in
quantum mechanics. Once I had a decent understanding of the subject, I continued with reading research papers
about the algorithm and how it works.
One source that I found very helpful was the
research paper done by Isaac Karth and Adam M. Smith.
It went very in-depth on the algorithm and explained by the simple version as well as the overlapping version of the algorithm.
Once I had a clear understand of how the algorithm would work in code, I went ahead and began implement
the WFC myself with the simple method.
Constrains
Starting with my first iteration of the WFC, I decided to build the constrains by using bits as booleans.
The reason for this decision was to slightly optimize the constrain building and remaining efficient.
By doing this, each bit would represent if an image would be possible in a specific cell by being either 0 or 1.
However, later during development the limits of this approach began to show, as the sprites supported by my WFC
could only have 2 different colors and were limited to a maximum of 16 sprites. Because of this, I refactored the
constrain building.
The new approach currently samples from an image and checks the pixels of each side and compares it with the
pixels of the other sprites. If the row of pixels are the same, they can be connected. Using this approach,
the constrains would be built automatically while also allowing for more sprites and different colors.
Although the new approach is a lot slower due to the nested for-loops. It is not as much of an issue since it is only
called before the WFC has started. Because of this, it wont impact performance when the WFC has been scrambled.
As the new approach does limit sprites to be symmetrical, I will also be sure to implement another way to build
constrains using a CSV file. In this approach, people can define what sprite can be connected to which other sprite.
Which should give people more control over their constrains.
Code snippit of the constrain building after refactoring, using pixel comparison
Wave Function | Simple
Now that the constrains themselves are build and in place, I began with making the simple version of the WFC.
Although this version doesn't show the true potential of the WFC, It still shows the WFC would and generating maps.
When starting with the WFC, all cells are in a superposition. To start the chain, I select a random cell and
collapse it into a random state using the ChooseRandomCell function. Once collapsed, the adjacent cells will
be check and the possible states will be reduced as much as possible using the CheckCell function.
If one of these cells has a single state left, the cell will immediately collapse and the adjacent cells will
be checked again. This will result in a recursive function that will go over all connected cells.
When all cells have 2 or more possible states left, the wave function will come to a halt. Whenever this occurs,
a new random cell with the lowest entropy will be chosen and collapsed. From here, the process will begin again
until all cells have collapsed into a single state.
Due to the tile maps used with the Simple version, it is impossible for cells to have 0 states left. Because of
this, backtracking is not implemented for this version. But will be added in the overlapping version.
Code snippit of the WFC in C++
Wave Function | Overlapping
As of yet, the overlapping version of the WFC is not yet implemented. However, research has
been done to get a better understand of how to observe and collapse the wave per pixel, rather
than per tile.
When time allows for it, I will focus my time on implementing this version into my current WFC algorithm.