Using wave function collapse to automatically align 3D tiles.

EDIT: Paul Merrell Pointed out that that the wave function collapse algorithm is based on his earlier “Model Synthesis” algorithm, and since I am working in 3D my partial implementation more closely matches that original algorithm. You can read more about it here: https://paulmerrell.org/model-synthesis/

I’ve been playing around with a new concept for a game so you know what that means? Time to start out with good intentions but get bogged down in an interesting coding challenge that has little effect on the game itself!

This time the problem was: How can I place tiles in a scene that automatically align with their neighbours? E.g. If I dig a pond by placing water tiles, how can I ensure the banks of that pond line up together and look natural, rather than that blocky Minecraft look?

I.e. This:

Not this:

Googling around yielded some useful results but nothing directly applicable for me.

The closest thing I could find for Unity (my engine of choice) was its tile rules for 2D tiles. I could find nothing for 3D however and the inner workings of Unity’s tile rules are opaque.

One suggestion I saw was to use the 2D tile rules and then swap out 2D assets for corresponding 3D ones but my games are as much about learning as the end product. I want to understand as much as possible about what’s going on under the hood, even if I do opt for an off the shelf solution in the end.

After some further googling and a bit of direction from my friends, I came to wave function collapse. Which is exactly the kind of high concept sounding, super impressive coding nonsense that scares the crap out of me (and is therefore exactly the stuff I want to learn.)

The basic idea behind Wave Function Collapse (or WFC as I will refer to it going forwards) is, as best as I understand it, as follows:

Each tile type has a set of rules that describe each edge. These rules dictate which tiles correspond to each other. For instance if a tile has a rule of “A” on its right edge, any tile with a rule of “A” on its left edge would be compatible.

Once you have defined your tiles and rule set, you can gather all potential tiles for any given location in a sort of superposition. You can then iterate through those possibilities and resolve them down to increasingly smaller possibility spaces which fit naturally with their neighbours.

Eventually you can get down to a single possibility, or at least a small enough set that you can arbitrarily choose one option. At which point the wave function is collapsed and you have your tiles.

Oskar Stålberg has an excellent talk on the concepts behind WFC and its implementation:

https://www.youtube.com/watch?v=0bcZb-SsnrA There’s also a wealth of resources on the subject out there, I’m just here to discuss my implementation.

Most implementations I’ve found seem to be more about procedural generation, which my efforts are not. I’m using WFC as a means to automate alignment of manual tile placements.

So how does this help us create nice continuous pond banks? Well, describing these edge patterns means that each tile type has a limited set of possible tiles that can fit in any given configuration.

If I can work my way around each edge of a tile I can build up a map of each potential compatible tile. This superposition of possibilities serves as a starting point which I can then iterate through in order to collapse my possibilities until they resolve into exactly the right configuration (or near enough) to ensure a continuous connection between my tiles.

So let’s run through my actual implementation.

First we need to think about the shape of the tiles themselves and how they will actually connect to each other. My initial forays into this problem involved me manually creating and placing water bank tiles just to understand how they would match up. This helped me identify a few common shapes.

I surmised that these are the common shapes that once rotated (X1 for full block, X2 for edges, X4 for corners) could account for every eventuality (I wasn’t 100% correct about that but we will discuss this later.)

Upon generating these shapes I could immediately see how I could express the matching edges.

Each edge is expressed as two values which can either be water or grass. E.g. the northern edge of the fourth tile would be expressed as [grass, water] and would match up to a southern edge that corresponded to [grass, water].

Now that I’ve mapped out a few possible tiles though, I can see that multiple tile types can also fit that northern edge.

With my tiles setup I can now proceed with actually placing them and resolving the surrounding tiles.

The first step in my process then is to actually place a tile. In this example we will place a water tile into a field of grass.

Now we need to work out how the surrounding tiles should look.

My expectation is that this ends up looking something like this:

The all water tile in the middle is surrounded by rotated edge and inner corner tiles.

So we have our aim, and we have our building blocks, how do we automate this process on the fly?

The first step in my process was to establish which tiles should be taken into consideration during the process, which will change as the result of a tile placement, and which will remain constant.

The tile we just placed is the primary tile and sits in the middle of everything. The tiles that are directly adjacent from it are the secondary tiles as they have border edges with the primary and finally the diagonally adjacent tiles are the tertiary tiles.

This gives us 9 active tiles (one primary and 8 surrounding neighbours) from which we can make a few assumptions and derive our constants:

• The primary tile has already been placed and since it has been changed directly, we can assume it will not need to change again, so this shall be our first constant.
• We assume that the secondary tiles will change, but we can assume that each secondary tile has two neighbours that will remain constant. The primary tile and adjacent ancillary tiles that are outside of our active operation.

E.g. The tile to the north of the primary tile:

Since the primary tile won’t change we know that the rules for the southern edge will be [water, water]

The tile to the north, whatever it may be (let’s say it is all grass for now) will not change either so the northern edge will have a rule of [grass, grass]

We can repeat this process for each secondary tile.

• The northern tile as we have seen has constants to the north and south.
• The eastern tile will have constants to its east and west.
• South is south and north.
• And finally the western tile is west and east.

We now know 50% of the correct patterns for each secondary tile. So we can take a look in our available tile types and find tiles that match on those edges which we know the rules for.

In our limited use case there is only one possible match for each, which is the edge tile.

This approach does however accommodate more complex tile sets with multiple matches per pattern. To resolve more complex sets, it is just a matter of iterating through the same algorithm until you resolve the possibilities down to one (or a satisfactory threshold)

With our secondary tiles resolved we can now move onto the tertiary tiles.

Similarly to the secondary tiles, we can immediately resolve 50% of the edges just by looking at our constants. For tertiary tiles this means the two ancillary tiles that border them.

Since this is using a very small tile set we already know what our secondary tiles should be so we can go ahead and grab those edge rules as well.

Again we have one tile that matches this pattern so we can go ahead and drop it in now.

If we again repeat the process for each tertiary tile we end up with a completed set.

With a very simple ruleset we have resolved all the tiles in one pass, but what if we have a more complex context and/or tileset to work with?

As I previously mentioned it is pretty straightforward to scale this algorithm to accommodate as many passes as you need or are willing to undergo.

We go through the same steps listed above, but instead of immediately resolving the solution for each secondary and tertiary tiles, we create a collection of possible matches which we can hold in superposition and iterate through until we can find a satisfactory resolution.

Let’s take the northern secondary tile as an example. In the original version it’s just a single edge tile.

But let’s say we have a few more tile types that could potentially fit.

In our first example we got exactly one match for each secondary tile on the first try, but here we have 3 matches.

We can resolve this by going through exactly the same steps as before, but instead we collect all of these potential tiles in superpositions which we will then test tertiary tiles against.

We do this for all the secondary and tertiary tiles to build up our first pass of possibilities.

We can then begin the process again with a new iteration.

Starting first with the secondary tiles, with our new set of tertiary possibilities we can now prune our secondary possibilities down further.

Rinse and repeat for tertiary:

Secondary:

Tertiary:

Secondary:

And we are resolved!

Depending on how many tile types you have, you could end up with multiple resolutions to the placement.

You can detect this if you iterate through secondary, tertiary and then secondary again and find that secondary is unchanged from the previous iteration.

In this case any tile you pick will fit, so you can arbitrarily select one of the options from a secondary tile (I always start in the north and work clockwise so let’s use the northern secondary tile) and then start the resolutions process again.

This time rather than alternating between secondary and tertiary tiles we will go through each superposition in a clockwise order (so in my example, N, NE, E, SE, S, SW, W, NW)

Etc…

At this point if any superpositions still contain more than one possibility, you can just arbitrarily select any options from within it and it should fit.

The end result of all of this is that you can place tiles with impunity and they will all align neatly!

I mentioned earlier that I eventually found out I was missing a tile type. Once the algorithm is complete and you have a starter set of tiles it’s actually incredibly useful for finding new patterns.

With my first implementation of the algorithm I ran around my tiles placing water everywhere and suddenly an error flashed up.

Because the algorithm is always searching for tiles that match a given pattern, it will naturally flag up any possibilities that are unaccounted for. Giving you the missing pattern as a kind of negative space, which you can then go and create a rule for.

Pretty nifty!

This example only uses two different values to define patterns (water and grass) but you can throw as many values into the algorithm as you like, providing you make tiles to account for them.

For instance you could have; water, grass and sand and as long as you have tiles that transition between the three you can run the algorithm in exactly the same way.

I think this is a really fun, robust little algorithm that adds a neat level of polish to my game. I’m curious to see if I can make any optimisations to it going forward.

Thanks for reading!