➿ 🔲 🙎 Tips for Using the Wave Function Collapse Algorithm 🔸 🍇 🚵

Recently, I have experimented a lot with procedural constraint-based generation. In particular, with the Wave Function Collapse algorithm (WFC, wave function collapse). I even wrote my own open source library and unity asset .

WFC is a very flexible algorithm, especially with the improvements I developed. But at the same time, I found it difficult to create practical levels applicable to computer games with its help . The main difficulty is that the WFC does not have any global structure. All he does is make the output generation look locally similar to the input, for example, by looking at individual small rectangles of the output.

In this article I will tell you what I learned and what will be able to raise generators based on restrictions to a new level.

The basics

It’s hard to use WFC if you don’t know how it works. This is a constraint-based procedural generation algorithm that has been given much attention recently. In fact, it has practically nothing to do with the concept of quantum physics in whose honor it was named.

WFC is easy to configure - you just give the algorithm an example card, after which it generates new cards that look like the original card due to the repeated use of its small fragments.

It has two types - with a neighboring arrangement or with an overlay of elements. It can be done in 2D or 3D, and even on grids of hexagons or unevengrids. Most of my tips apply regardless of how you use the algorithm.

I suggest you play with this demo to get an idea about the algorithm, and read this introduction [ translation on Habré] if you are interested in technical details.

Tileset design

The WFC algorithm is tile-based. In this sense, its quality depends on the tiles that you transfer to it for work. I am not an artist, so I can help little in drawing beautiful tilesets (although you can see here ), but a good tileset also requires technical knowledge.

Marching cubes

Marching cubes is an algorithm that selects which tiles to set depending on whether each vertex of the tile is full or empty. Here is the list of tiles used for 2D.

If you build tiles so that the black and white corners always match, then the red lines will always connect correctly.

Here we don’t need an understanding of the whole algorithm, but it should be noted that the idea of designing tiles with only their behavior in the corners is a very powerful technique. It is used in many of the best tilesets, as it ensures that tiles always connect well.

This technique is especially powerful for WFC. It happened, because if you miss a few tiles, WFC it will not matter. He will circumvent this problem and will never create configurations that require missing tiles. This is very convenient for 3D, since there are dozens of potential tiles, and some of them are required only in very difficult situations. See the “Foundation” section below, in which I use this trick even more widely.

Knowing other tile patterns may also be helpful , but Marching Cubes is the best.

The rooms

Sometimes it’s easiest to work with simple tilesets. This combination of 4 tiles (one tile is empty) easily generates square rooms.

The size of rooms can easily be changed by changing the weight of each tile. After adding the door and corridor tiles, you can create the diversity that is characteristic of people’s floor plans.

Foundation

When working with WFC, it’s interesting to experiment with tilesets. If you simply put a tile, WFC seeks to squeeze the most out of the remaining space. Sometimes this leads to radically different results, as can be seen in the image of Maxim Gumin:

We can use this behavior to stimulate WFC to generate many recognizable structures.

Here's an example of a castle (inspired by @greentecq ):

In it, I used the following tileset:

These tiles have an important property - all the tiles at the base have a width no less than at the top. This means that it is not possible to build these tiles in an unsupported manner. The WFC immediately responds to this and creates buildings with a good foundation.

Fractal Split Approximation

Studying the topic of stimulating certain behaviors by choosing the appropriate tileset, I found that if the tileset consists of straight roads and branches, but without corners, then you can get a good approximation of the recursive splitting (without the “recursive” part). This is pretty good for grid levels.

Big tiles

You can add WFC to support tiles that are several times larger than a regular tile. For example, this is supported in my Tessera addon .

Large tiles can be used in various ways. Since they extend beyond the boundaries of the grid, you can use them to add smoother and wider curves than is usually possible when snapping to the grid. They are also great for elements from a large number of tiles, or simply to mask that the generation is based on tiles.

Here's an example to learn from Oscar Stalberg from the Bad North game . Oscar demonstrates how he used large tiles to add smoothly curving coasts, large houses, and cliff variability.

Limitations

At its core, WFC is a constraint based algorithm. This means that he seeks to generate levels that correspond to a specific set of criteria. In pure WFC, there is only one criterion - that the levels look locally like a sample input. Below, I’ll talk about WFC enhancements to add new types of restrictions.

Fixed tiles

It is very easy to fix individual tiles before generating a level in WFC. Later they seamlessly integrate with the generated level.

Before generation

After Generation

This technique can be used in many different ways. Here are some ideas:

- , WFC .
,
/ WFC

Limitation paths (Path constraint) - this is my own contribution to the WFC. This is an extremely powerful technique, but a complete article will most likely require a separate article.

This restriction globally scans all generated output, and forcibly indicates that a path must pass between the marked tiles. Or in other words, it tells a subset of tiles to form a single component of the graph . Due to its global nature, it complements the usual WFC behavior, which takes into account only local tiles.

I found out that adding this restriction strongly affects the appearance of the generated level. Without it, WFC often generates several divided rooms or areas that look unrealistic and not created by humans.

. .

Another situation where path limitation is appropriate is ... drawing paths. By default, path restriction only ensures that there is a route between tiles. It does not guarantee that the path will be as simple as possible. Therefore, in the case of rivers and roads, he often draws T-shaped joints in optional places. The trick is to either simply remove all the tiles of the T-joints, or give them a very low weight, so that they are selected only in case of emergency.

I love using fixed tiles to fix the endpoints of a path. Because of this, the path restriction is required to insert tiles that make the rest of the path connect.

The paths generated by fixing all four corners as the end points of the paths

If you want to experiment with paths, then I have a small javascript demo that is laid out here .

Diversity

Alternative Tiles

It is very easy to add tile options to the WFC algorithm. Just add the tiles to the list of possible tiles, making it have the same connections as the tile that it replaces. Or it can be done at the post-processing stage, as is usually done in other styles of procedural generation.

Two wall tiles, one of them with a window. They are completely interchangeable and simply add variability to the design.

Tile variability by level

If you put a lot of effort into creating a tile set design, you will notice that the randomness of WFC begins to harm him. It uses the entire tileset, that is, you can get a level with mixed lava, snow and desert. Often this looks completely illogical.

You can restore integrity in a simple way: decide in advance which biome the level will belong to, and then disable all tiles that are not suitable for this biome.

Bad North (again) is an excellent example of this. In some levels, rocks are completely forbidden, in others there is a lot of vegetation, in the third ruins and cemeteries are added. This gives each level a unique style without the need for a significant change in the generation style.

Only about 10% of the islands have elements of caves, visible in the upper right corner.

Variability of tiles within the map

Mixing tilesets can go even further.

If you use WFC to generate a large card, then it starts to look very uniform. This is another consequence of the fact that the algorithm is a solver of local constraints.

The best solution to this problem I saw in the game Caves of Qud . In the developers' story about the generation ( 1 , 2 ), they say that they split the map into different areas, and then start WFC with separate parameters for the subsets of the map. This means that on the map there may be an area of ruins and an area of a city in which completely different templates and tiles are used.

Example from Math for Game Developers: Tile-Based Map Generation using Wave Function Collapse in 'Caves of Qud'

Conclusion

The WFC algorithm, like all constraint-based generation techniques, has the principle of being careful with your desires . It is easy to customize and get beautiful looking results, but it can be very difficult to implement the specific details that are needed for your game.

I hope the techniques presented by me will help you tame this monster, but in the end, it is best to create a game design based on the strengths of procedural generation, and not try to force it to create too much for you.

I recommend you play Bad North and Caves of Qud . Both games are great examples of using WFC in real conditions, and the developers have well thought out the optimal use of the algorithm in their games.

Tips for Using the Wave Function Collapse Algorithm