Wave Function Collapse on mobile

For a long time I wanted to try this new level building technique, but I didn't have the opportunity to properly spend time on it. And there comes my boss and he tells me "listen we're gonna have to make a whole set of new levels for this new runner minigame, do you have a magic trick for me ?". I needed nothing more to lock myself for a week in my office and dive into the subject.

Wave Function Collapse is a technique that builds automatically large worlds by assembling blocks together. To put it simple, we tell the program that this block can be set next to that block, but NOT to that other block ! That one must be paired with another, and we go on and on until the whole scene is filled.

I had implementation examples in Unity, but I never found anything other than 2D examples. And we needed 3D... So I came up with this solution:

This MIGHT look 3D, but it was honestly only 2D but with meshes. The algorhyhtm didn't have to manage the Y axis, it only had to be sure that blocks could be put next to each other but not above or below each other. And that's where it becomes tricky. To achieve that result I just had to assemble in Blender my blocks just like if I were making a 2D tileset:

I wrote a program that loops through all of the meshes in this file, and registers their possible neighbors. Then the level generation works that way:

• It starts on a random cell with a random block

• It checks for that newly placed block which possible neighbors can be placed next without breaking the rules

• And the code go on until the whole map is filled with blocks

But then I tried to add complexity: a second set of tiles that I wanted to combine with the first one...

I won't go too deep in the maths involved here, but let's just say that if we had a little bit of graphical complexity it just gets exponentially difficult in terms of code. The problem here is that I didn't have enough blocks to fill up all the possibilities. And as the number of possible tiles grows, so does the heavy load on our poor smartphones, so I had to find more tricks.

The first thing I though of was to add noise afterwards. And I must say it looked quite good ! It helped break the uniformity of the rendered map.

Next up I realized I was meant to make a runner game, so I focused on making the path my character will follow. This was pretty easy: I selected neighboring cells on my map and marked them as path, and then another script was charged to instantiate path blocks before the WFC algorithm comes in. I also wanted the path to be able to go across itself and therefore I needed to have bridges.

So this is what to whole 3D tileset looked like in the end:

And this is the result I ended up with:

I decided to have the minimal number of blocks to make the render believable, and I forced the placement of these big chunks of foliage in the cells that were unable to find a suitable cell. For the project we had in mind, and for the targeted devices this solution worked quite well!