Adventures in Wave-Function Collapse 2: DIY Recursion

This post follows on from a previous post about my recent attempts to implement the Wave-Function Collapse algorithm in Godot's GDScript to generate tile map levels.

I'm only just posting it now because I didn't realise I'd left it as a 'draft'.  Woe is me.

As I mentioned in the previous post, this isn't meant as a set of instructions - more as a reminder for my future self so I don't fall into the same traps again.  That said, hopefully someone else finds it useful as well.

Dealing with contradictions

When you are trying to generate a grid of tiles using Wave Function Collapse, each cell in the grid can be the top-left corner of one (and only one) super-tile.  As soon as you choose a super-tile for one grid cell, it limits which super-tiles the nearby cells can be.  This is implemented as adjacency rules: essentially there is a set of tiles which is allowed to be to the right of (or left of, or above or below) the chosen super-tile.

A contradiction occurs when there is no super-tile for a given grid cell that can satisfy the adjacency rules from nearby grid cells.  For example, if the cell above says you can only be super-tile 1, 2 or 3, but the cell to the left says you can only be super-tile 4, 5, or 6, then there is no super-tile that can be chosen which satisfies the adjacency rules from both neighbouring cells.

In my reading, I came across two ways of dealing with a contradiction:

1. Chuck the whole thing away and start again with a different random seed
2. 'Rewind' decisions until the contradiction is no longer present, then resume the process from that point, taking a different decision (thus producing different adjacency rules so you don't hit the same contradiction again)

I found neither to be effective, but that a balance between the two could work.

The problem with option 1 is that you could go almost all the way through generating a map, hit one contradiction and chuck the whole thing away and start again.  The likelihood of completing a map without hitting a single contradiction can be increased by choosing the uncollapsed cells with the lowest entropy.  However, as the desired size of the resulting tile map and the number of possible super-tiles increases, the chance of succeeding first time can become very small indeed.  Then, the program takes forever to generate a map because it's so frequently giving up and starting again.

Implemented correctly, option 2 is guaranteed to find a solution for a given seed (with super-tiles that can wrap around the template edges, there are at least those solutions which are essentially multiple copies of the template tiled together).  However, there are two problems that occur.

Firstly, if you want a tile map 32x32 or larger, you need 1024 or more recursion layers.  My first experiments were in Python, and that just smacked straight into the recursion limit and collapsed in a bloody heap.  The tile maps I wanted to generate would be larger than this, so I needed to hand-roll my own data-based recursion.

I wrote a 'collapseLayer' class, which kept track of which cell was being collapsed (i.e. which cell was having its super-tile chosen), and which grid cells were having adjacency rules applied to them.  I also wrote a 'gridCell' class which would keep a stack of the rules applied to it, so they could be removed one by one if need be.

So a 'collapseLayer' could choose a super-tile for the grid cell and check if the rules being applied caused a contradiction.  If they did, then it would undo those rules, choose the next possible super-tile and try again.  If it ran out of possible super-tiles, then it marked itself as failed and the stack of 'collapseLayer's could be unwound a level.

This way, the recursion was implemented as a stack of 'collapseLayer' instances, instead of using the interpreter's call stack.

...and it worked!

...until it would inexplicably hang with certain random seeds...

It turns out that as the number of possible super-tiles increases, the rewind-try-again method can end up stuck in a seriously long-winded explosion of possibilities.  If you have ~20 possibilities at one collapse layer, and another ~20 at the layer below, you have 400 combinations to work through.  

...but what if the problem was actually at the layer 3 collapses back, where each layer had ~20 possibilities?  You very quickly get stuck in millions of possible combinations and it simply took way too long.

The Balanced Potential Solution

It turns out that with reasonably small tile maps, the number of random seeds which get stuck in combinatorial explosions is relatively small.  So the balanced solution was to limit the number of rewinds.  If, after 500 rewinds a solution still was not found, then chuck the whole thing away and start again with a new seed.

This got me really close to a working solution, but it still slowed to a crawl as the size of the result tile map increased.  If I was working in a fast compiled language, it would probably be good enough, but I'm not...

The Current (Broken) State

So the current state of the project is a nearly-working solution which generates multiple 8x8 tile maps and puts them next to each other.  I cannot describe it as actually working because the adjacency rules do not pass from one 8x8 tile map to the next, but it is nearly fast enough to generate 8x8 chunks on-the-fly as you move around the map.  It is TANTALISING!

Thanks to the process of writing these posts, I have realised that working with 8x8 chunks means I can once again use the interpreter's call stack (64 layers) instead of my own recursion.  That might prove faster (or might not!), but even if it doesn't, I think what I have will produce a fixed-size level within an acceptable level load-time.  Then it's just trying to make sure that every level it will ever produce will actually be playable!