Wave Function Collapse

Overview

This demo was developed as additional course work at the Academy of Interactive Entertainment. It was made in C++ using a graphics framework called Raylib.

The 'Wave Function Collapse' algorithm works by storing possibilities for each tile, in my version for example there are 4 for each tile; water, sand, grass and trees, first a random tile is given a random type and then every tile around that one is collapsed, and around those ones, etc. The tile with the lowest possibilities is then chosen as the next start tile and it is given a random tile type, then the tiles around the new start tile are collapsed, etc. This is repeated until every tile is fully collapsed.

A tile is collapsed by checking its adjacent tiles against the adjacency rules, in my version for example; water can go next to itself and sand, sand can go next to water, itself and grass, grass can go next to sand and itself, and trees can only go next to grass and not itself. Any adjacent tiles that adhere to the adjacency rules are then added as the tiles new possibilities, thereby making it collapsed.

For a better explanation check out this video.

Unfortunately, as this was developed within a course work repo, I no longer have access to it :( .

Challenges

Collapsing the Map

At the time, one of the biggest challenges I had was how to approach collapsing every tile. Originally I had a while loop that would collapse every single tile, then loop over them again to find the tile with the lowest number of possibilities, then loop over them again to check if they had all been collapsed. To say the least, this was very inefficient.

To slightly solve the triple looping problem, I basically eliminated the collapsing loop. Instead, there is now a pending tiles queue that only gets added to if the possibilities of any adjacent tiles changes. This way there is very few tiles that actually get collapsed per-loop, and as such the overhead is much less. With this one change it runs much more reasonably, although still fairly slow.

Adjacency Rules

Another challenge I had was how to handle the adjacency rules, my first approach was to store the adjacent possibilities when collapsing a tile, i.e. if left could possibly be a water tile then we could possibly be a water tile. And then using that array of possibilities, check if our current possibilities were valid, i.e. if left could be water, then we can't be tree, that kind of thing. This made the logic very hard to keep track of, and just not feasible for adding new tile types.

Solving this problem was tricky because I was essentially shooting myself in the foot using the two array approach, so I decided to remove the adjacent possibilities array. Instead, I simplified it to 'for each neighboring possibility, add valid possibilities to our array.' It is much easier to explain with a visual aid, so here is an example check for a water tile:

// water : 0 : water, sand
if (ValInVector(m_tileMap.at(i).possibilities, 0))
{
    if (ValInVector(m_tileMap.at(index).possibilities, 0) || ValInVector(m_tileMap.at(index).possibilities, 1))
        newPossibilities.push_back(0);
}

So for neighboring index 'i', can they possibly be water? If yes, and we at index 'index' can possibly be water or sand, then add water to our new possibilities. It sounds a bit confusing, because it is, but essentially the type your are checking goes in the first if and the push_back call, and then the adjacency rules of *that* type go in the second if.

I hope that makes sense ...

What would I do differently?

Remove the Loops

I would use a priority_queue with my Tile struct and a custom comparator so that instead of looping over the entire map for lowest 'entropy', you just take the first element of the queue ( O(1) ). This would speed up lookups by a lot, and as a bonus also simplify the logic as well.

It should be said that the pending tiles queue will probably remain, as that can be simplified to a queue of ints to maintain the speed of the initial tile collapsing. Then replace the secondary loop with the priority_queue method. And finally, instead of looping over all tiles to check for any remaining tiles, I can re-use the priority_queue by popping the elements that have 1 possibility left, and then loop while that queue is not empty. I have not tested these improvements, but in theory this should be much quicker than the current implementation.

Better Adjacency Rules

For the adjacency rules I would probably switch to a *.bmp of the valid rules, and extract them into some container / class called 'AdjacencyChecker', so that the complex logic can be hidden from the main wave function collapse logic. This would also make the rules dynamic, meaning that by simply changing the *.bmp file, you can entirely change how the algorithm would behave. This approach is actually used quite a bit with other implementations, mainly for the reasons described, I only didn't implement it as I knew I was only going to have a handful of types in my little demo.

Overall Modularity

Another thing I would like to change is to break the logic up. It is currently all contained basically in the main.cpp file, which is fine, but it does make modification hard to keep track of. I would probably have the logic split into 3 classes; AdjacencyChecker (from above), TileMap, and of course WaveFunctionCollapse. This would keep the necessary logic contained in their own little classes, and make the main file very easy to understand. Not a big change, but I would like to focus on that a bit more if I ever re-did this project again.