Wave Function Collapse Algorithm
Project Details
- Engine: Unreal Engine 4
- Topic: Procedural Generation
- Duration: 3 Days
Introduction
In between two of my school blocks, I wanted to challenge myself with making something that I had seen some videos about on YouTube. Which was to make a Wave Function Collapse algorithm within UE4. Ofcourse there were some limitations of pure Blueprint that I had to work around. But it has given me deeper understanding of how to write solid blueprints. If anything, this small project has given me the knowledge of how to tackle such systems in a proper way, should I ever have to create such systems again.
One small downside that I did notice after finishing this, is that the new UE5 that had been released around the days that I was working on this shipped with a Wave Function Collapse system by default. So I definitely don't have any reason to reuse this exact code here. But that was never really the point of this project in the first place.
Functionality
Ruleset
Defining Layouts
The rules for how tiles are allowed to connect to each other are defined within a text file. But to save myself time on writing out that massive textfile, I have created a secondary system to encode example placements into a textfile of allowed placements which could in turn be fed into the Wave Function.
Superpositions
Slow decay of allowed possibilities
At the beginning of the generation. Every single tile on the grid is allowed to be any tile it wants. The tile with the lowest amount of possibilities then collapses, which means that it permanently chooses one of its allowed tile variants, and updates its neighbouring tiles with what placements are now prohibited due to this tile's collapse. (If multiple tiles have the same amount of possibilities, one gets picked at random)
Performance
Loading times
The time it takes to generate a map from this wave function collapse algorithm greatly depends on framerate. The actual calculations are not that heavy, but in my implementation most things are sequential, not parrallelized. This is ofcourse not the most performant, as things like Vsync will affect the generation time of the map. But this was mainly to prevent the engine from flagging certain actions as infinite loops. And it helps in showing how the generation is progressing. which is great for debugging purposes.