Wave Function Collapse

Before delving into the algorithm itself, I would like to explain three terms that are used for WFC.

1. Entropy: The amount of chaos in a cell. This is chaos represents how many possible states the cell can be in.

2. Adjacency constraints: These are rulesets that the algorithm must follow when generating the output map (i.e., colour adjacency for 2D maps).

3. Module: A module represents one possible end state for a cell . A module typically contains the sprite or model for said state and info that might be required by the adjacency constraints.

Wave Function Collapse takes a set of tiles as input. These tiles for 2D and 3D WFC are sprites and 3D models respectively. The algorithm uses the given adjacency constraints to generate the output map. Multiple adjacency constraints can be stacked and combined to tailer the outcome map to the desire of the user.

The final result of the algorithm is represented as a grid of cells, which also represents the "wave" that will ultimately get collapsed. These cells initially are all in superpositions, meaning that their final state is not yet decided. To collapse the wave, WFC loops over these steps:

1. Observation: Start by looking for the cell with the lowest entropy. Collapse the cell into its final state using constraints or pure randomness. This final state is one of the still possible modules left for this cell.

2. Propagation: Relay the info of the collapsed cell to its neighbours. Discard modules that can no longer fit and propagate this info to those neighbouring cells. Repeat this until all cells that need to discard modules have done so.

3. Search for the cell with the lowest entropy. Check if one has been found.
     a. Cell was found; repeat the loop from step 1.
     b. No cell was found; stop the loop as the wave has collapsed.

When the wave is fully collapsed, all cells have their final state, and the map can be generated and used. A step-by-step guide on how this was implemented and the testing methodology and results in can be found in my paper.

Finally, I would like to talk about my experience and takeaways regarding this project.

Suffice to say that I learned a lot about procedural content generation in researching WFC and had a look at a lot of different approaches towards it. It is amazing to see how much replayability can come with a (relatively speaking) simple content generator. Throughout this project I also found myself becoming a lot better at preparing and outlining classes or functions before starting to program them. This really helped in keeping a clear oversight of the project.

I also definitely learned some things about myself that I had not yet realized before. First of all, I really enjoyed researching atopic and gradually becoming more and more familiar with it. I did realize that I should sometimes rely a bit more on my gathered research instead of delving in headfirst and creating something from scratch.

Secondly, I learned the difference between speed and efficiency. There were some moments where I took shortcuts in order to save time, but had to come to the realization that I lost even more time afterwards. I.e., I created some 3D models that were very basic and not very modular. This made it difficult for the algorithm to generate good levels and cost me a lot of time spent debugging. Suffice to say that it is often better to do something correctly rather than fast.

Finally, I became a planner for this project. Throughout my years as a game programmer I have often procrastinated and disregarded planned project outlines or structures. For this project I was required to plan the entire scope of the case study and paper and I decided to try to stick to it as much as possible. This helped me so much with stress and keeping my project on a correct course, that I am sure that I am on my way to become a planner rather than a procrastinator.

To close this project off, I would like to give a major thanks to my supervisor Flor Delombaerde for guiding and helping me throughout all the project.