Wave Function Collapse is an interesting approach to image generation, possible to extrapolate into other things, like level generation. But in this series of a few articles, I’d like to pull it back to the original class of approaches it derives from and possible applications they have for game design. Of course, this superclass is the Constraint Satisfaction Problem, but we have to start somewhere before we get to it, right?
So why am I starting with WFC? Well, basically because it’s easier to visualise, but it has issues when it’s applied beyond its intended domain. So it’s going to be easier for me to explain with this example and go to the theory from there, rather than just starting with the tough stuff.
1) So, What’s Wave Function Collapse?
Well, it’s a concept in quan…
I mean, it’s an image generation algorithm based on constraints that can deconstruct an input image and then build a derivative image of any size from the data.
It divides a given image into patches and then fills out the space of the picture by pasting in the patches so that their borders overlap. What does it mean? In its simplest form, let’s assume we have a grid of any size; the goal of this algorithm is to place one patch into each space on the grid so that for each adjacent patch, their edges match up. This can be extended in a few ways, with patches of variable size and different forms of overlap, but the general idea remains the same. It’s a bit like puzzle pieces, you need to fill out the whole frame, but each piece must interlock with its orthogonal neighbours.
The approach is also commonly applied to tilemaps. In that case, the tile edges are described with either corner-corner descriptions or corer-edge-corner descriptions. The former method is widely applied to 2D tiles/tile sprites, while the latter was used specifically in the game Neverwinter Nights (explicitly in 1 and implicitly in 2). Though please note that I am not saying that either NWN uses WFC. I am speaking strictly about tile definition, for an example that I think many people will be familiar with.
Here’s how two matching image patches might look:
(Since patches are generated from the image, they lack the metadata to establish matching edges; the issue is solved by overlapping the edges of the patches.)
Here’s an example of a tile with a corner-corner edge description:
(Corner descriptions will often correspond to terrain features. For example, green might represent grass here, red – mud, and blue – water.)
And here’s an example of a tile with a corner-edge-corner description:
(In NWN, the description of an edge would be present in a thin feature, like a corridor, road, stream, wall, etc., ran through the tile. When absent, marked with None, the tiles behave like those above.)
If you want to play around with 2D WFC, you can do so through this handy GitHub project.
We need to look at two critical parts of this algorithm. Firstly, what does it mean that this is a constraint-based algorithm. Secondly, what is Forward Checking, and why does it matter.
2) Constraints
With WFC, we have a single constraint replicated to all instances of edges between adjacent tiles:
Foreach grid cell, foreach edge, if an adjacent tile is present, the edges match.
And we can optionally add the following constraint:
Foreach space on the grid, there’s a patch/tile assigned to it.
These constraints, combined with input data such as grid size and image or tilemap, define what kind of output WFC can give us. The space of all possible assignments of pathes/tiles to the cells is our universe. And a subset (possibly empty) of that universe satisfies our constraints, presenting us with the possible outputs.
At face value, given a sufficient set of patches or tiles, we can fill our grid with them. Or at the very least discover that our data represent a contradiction – a case where the constraints cannot be met. For the procedural generation of video game content, this is enough to build procedural textures or maps.
And let’s focus on that last part – are maps built like this good? Well… no. Firstly, if impassable elements can be generated, it’s also possible that our map will be composed of separate parts. Imagine this as two islands being built when the character(s) we control cannot swim or a wholly walled-off room generated in a dungeon when we cannot get through walls.
This issue is, of course, completely natural. Unfortunately, we only have one global constraint (fill all available space); the rest represents local relations between the elements we place. As such, there are no overarching guides that would ensure we generate a map we can fully access, and to be honest, it often won’t generate good maps at all.
You need to use the corner-edge-corner approach and have a well-constructed tilemap to get non-trivial results. Results that can be built through much simpler means. How much more easily? Well, you can look at some old code I have written, presenting generation for a complete tilemap with three features:
I wrote it on the spur of the moment, and it’s all of 32 lines of code and 81 images.
We’ll get back to the issue of constraints later. But, for the moment, this is the reality of WFC and what it can do.
3) Forward Checking
The second aspect of WFC I want to focus on is Forward Checking. Previously I said that it seeks to fill the whole space (image, grid) it is provided with using the supplied elements. This is true, but there is a particular order in which the filling occurs.
Really, this application of Forward Checking is what gives the algorithm its name. Though personally, I find the analogy to be a bit of a stretch.
In any case, let’s explain how this actually works. We start with an empty grid. At this time, any cell can contain any element. Thus, we can pick a random cell and place a random element into it as our first move. At least at base, sometimes we want to place a specific element in a more or less specific place instead (like putting the dungeon entrance somewhere near one of the edges, for example).
This causes the adjacent cells to become limited. We can now only place a subset of all our elements in the cells adjacent to filled cells. As we assign more cells, this will only propagate through the gird. Because of this, after the initial placement(s), we take on a different strategy. Every next cell we assign will be from among those with the lowest cardinality (number) of matching elements still possible to slot into them. If we ever have a case where this number is 1, we know what single piece fits into that place on the grid. If we ever get a 0, well, that’s a contradiction, and we’ll talk about these later. For now, let’s say that the current attempt to satisfy our constraints was unsuccessful.
This approach of keeping track of how many elements can be placed in various grid locations and trying to resolve the ones with the least uncertainty (the smallest number of patches/tiles that fit there) is Forward Checking. It’s a fundamental approach for optimising problems of this sort. We’ll also discuss more general applications of it in the future.
4) Generalising
What we discussed above was, altogether, a specific Constraint Satisfaction Problem and a way of solving it. Now, for the latter, it’s not the only way to tackle this particular problem, but actually, as far as the specifics we’re dealing with go, it’s the correct one.
Constraint Satisfaction Problems and different approaches have shown up on this blog. You can check out more here:
Mechanics: Puzzles – Part II – A Study of Soggy Zebras
Mechanics: Puzzles – Part III – Dissecting Soggy Zebras
Mechanics: Puzzles – Part IV – Putting Zebras Behind Bars
But this would be the first time we’re approaching them to implement generative tools (the last time I did an implementation related to this, we dealt with data processing/inference).
So let’s start with giving a formal definition of CSP, and then, in the next instalments of this article series, we’ll bite into their usage.
A CSP is a pair of elements (S, C) where S is a Cartesian of arbitrary dimensionality (you can check here: Mechanics: Puzzles – Extra – Combinatorics 101) and C is a set of constraints. Every constraint c ∈ C is a Boolean function of the Cartesian space: c(s), where s ∈ S.
The solution of a CSP is every sₐ ∈ S such that ∀(c ∈ C) c(sₐ). Or, to say it more as the humans do: the solution to a Constraint Satisfaction Problem is any permutation of the available variables (we can call the different dimensions of our Cartesian variables) that satisfies every constraint.
The practical means by which we will find a solution to the problem is an algorithm called Backtracking With Forward Checking, the direct superclass algorithm for Wave Function Collapse. In the future, as we discuss possible spaces and constraints, it will become apparent why that’s the case. It’s just something that can do more, and we need to do more.
Hopefully, that sounds pretty trivial so far.
Next up, I’ll talk about the full scope of what’s possible to do with Backtracking With Forward Checking.
Esoteric Musings... 