Original article from pvs-studio.com.

Wave Function Collapse is an algorithm that can generate anything by arranging it according to rules or samples. In this article, we are going to look at how to use WFC to generate a map in Unity.

A curious project I found on GitHub inspired me to write this article. The project describes how to use WFC to generate images based on patterns in the input image.

Enjoy reading!

The essence of Wave Function Collapse

Wave Function Collapse is an algorithm inspired by the ideas of quantum mechanics. According to one of such ideas, there's a huge set of possible states for each object.

Initially, an object has some generalized state represented as a linear combination of all the elements of this set. However, under the influence of the environment, the object gets one of its possible states.

So, how to apply this idea to implement procedural map generation?

Imagine that the space where your map should be is a plane divided into many squares. Each square is a cell where you can place one of the pieces of your map. Each piece ("module") is a possible state of this cell.

While the cell is empty, any module from the set can be placed in it. So, the cell is in some generalized state or superposition.

However, if we put an arbitrary module in the cell (for example, a piece of land with a road), we will define a particular state for it from the set of its possible states.

But how will this affect the state of other cells on a map? Suppose we have a road in one section of the map. It's clear that the road must continue or end (with some kind of gates, house, bridge — whatever) in the neighboring section. It would be wrong to have a road that just suddenly disappears or accidentally leads to a dead end, a tree, or some other obstacle.

So, we shouldn't have modules of the neighboring cell that do not contain the road where it should be. As a result, we have no choice but to remove these modules from the set of possible states for this cell. Thus, by defining the state for one cell, we change possible states of another one.

Since the set of states of the second cell has been changed, some modules of its neighboring cells may also become invalid. In this case, they are removed too. Thus, the change in the set of states of one cell spreads like a "wave".

So, alternately defining a specific state for each of the cells, we gradually generate our map. The wave update after each such operation ensures that we will never put the wrong module in the cell.

I guess at this point you may think: "yeah, in theory everything looks fine, but how to implement this behavior in code?". Actually, it's not as difficult as it seems. You'll learn about the algorithm of procedural WFC generation further on. Also, we are going to briefly consider its simple implementation.

The algorithm of procedural WFC generation

Here's how the algorithm of procedural generation based on Wave Function Collapse looks like:

1. There is a space divided into several identical parts — cells. There are several modules that can be placed in each such cell. This set of modules can be called the set of cell states, and the modules themselves are the states of this cell. Initially, the set of cell states includes all possible states:

2. Next, a random cell that has the smallest number of possible states (at least two) is selected. All modules of the selected cell are removed, but one module remains. The remaining module is considered as a "definite state" of the cell. We "place" the module in the cell, so to speak. You can use any method to select a module. To make it easier, you can randomly determine the state of the cell:

3. Now we need to update the set of states of each neighboring cell: all states that do not match the selected module are removed. For example, if in the selected module the road goes left, only those states where this road continues should be remained for the left adjacent cell. Thus, the result of updating all neighboring cells will be as follows:

4. If at least one module has been removed from the set of states of a neighboring cell, the states of its neighboring cells are also updated: the modules that are not matched up with any module of the updated cell are removed. This operation is performed for all cells affected by the "wave" update:

5. Steps 2-4 are repeated as long as there's more than one state for at least one cell:

6. As a result of step 5, the state of all cells must be definite, that is, only 1 element must remain in their state sets. However, it may also happen that there will be no elements left in the set of states. In this case, we need to roll back all the changes in the map one or more steps back and try other combinations of modules. If everything is fine, the last thing to do is to connect the modules corresponding to the cells together:

Perfect! Our map is successfully generated!

In the next section, we'll consider a basic implementation of this algorithm. I'd like to note that the implementation described below is not intended to generate ready-made game levels. However, it can be a good example that will help you better understand the principles of using the WFC algorithm in Unity.

A way to implement WFC for procedural map generation

So, let's see what the basic implementation of the Wave Function Collapse algorithm might look like in the context of procedural map generation in Unity.

1. We create an empty GameObject with the Map script attached. The following parameters are configured in the Map script:

• MapSize obviously denotes the size of our map;
• CellSize means the size of one cell on the map (it is assumed that the cell has a square shape);
• MapModules is a set of module templates used to generate the map;
• ContactTypes denotes a list of contact types and their restrictions. The contact is one of the edges of the cell. Each contact has a type and a type list of other contacts with which a connection is not allowed.

2. We create a set of module templates for generation. The MapModulePrefab.cs script is attached to each template. To illustrate this, I've prepared 4 simple templates:

3. In the MapModulePrefab script of each template, we set the contact type for each side of the template. We also set the Map object which is used to get a list with restrictions for this type.

4. Our work here is done. From this moment on, Unity comes into play. The last thing we should do is to click Play and take a look at the result.

Looks quite impressive! However, scrutinizing the map, we may notice some shortcomings: the lack of passages to some parts of the map; some walls located on the edges of the map come abruptly to an end. Well, to solve all these issues, we can additionally refine the basic procedural WFC generation. The refinements depend on the idea you want to convey.

By the way, you can download this demo project from my GitHub repository to view the code. Perhaps you would like to use it as an example for your implementation.

To sum it up, let's take a look at the main classes that this implementation provides:

1. The Map class (Unity's component). It represents a generated map. With the help of other classes, Map performs 3 main generation stages. It:

• initializes an empty map as a two-dimensional array of the MapCell class objects. The set of states of each such object contains all possible versions of modules from which the map can be generated (objects of the MapModuleState class);
• selects a specific state for each cell in the map with the help of the Wave Function Collapse algorithm (the algorithm is mostly implemented in the MapCell class);
• Creates modules corresponding to cell states on the scene.

In addition, Map contains information about contact types and their limitations in the form of MapModuleContact objects.

2. The MapModule class (Unity's component). It provides the functionality for generating a list of template variants with different rotation around the Y axis (the MapModuleState class objects). Since the base of the module is a square, the rotation of each successive version differs from the previous one by 90 degrees. In the Map class, this functionality is used to generate a list of all possible states.

3. The MapModuleState class (not a Unity's component). Objects of this class are variants of modules with different rotations around the Y axis. MapModuleState also contains information about module contacts in the form of the Dictionary collection (where key has the Vector2 type and indicates in which direction the contact is pointing, and value is an instance of MapModuleContact. Also, the MapModuleState class provides the functionality to check for the possibility of connecting one module to another.

4. MapModuleContact (not a Unity's component). An object of this class stores information about the contact type of one module and a list of types with which this contact must not connect. It also provides a method to check for the possibility of connecting this contact to another. This functionality is used in MapModuleState to perform a check for the possibility of connecting modules.

5. The MapCell class (not a Unity's component). It represents a map cell. MapCell provides the functionality for determining a specific state of an object followed by a "wave" update of the state sets of other cells. In case there are no possible states left for one of the cells as a result of such an update, it's possible to roll back the updates with the subsequent selection of another state for the cell.

Conclusion

In my opinion, procedural WFC generation is fascinating mechanics that will definitely help diversify your game. In this article, we reviewed the map that was generated with the help of quite simple components. However, you can use more complicated modules with interactive objects, characters, etc. Moreover, you can significantly improve the algorithm. So, procedural WFC generation can be used as the basis of your project.

You can also apply the algorithm to generate prototypes. Here you can use a simpler implementation. Instead of modeling the entire map manually, you can do the following:

• create several simple modules from which your prototype will be created;
• generate it with the help of WFC;
• edit and improve the result manually.

It is worth noting that procedural generation has one serious drawback: a large number of generated objects can have a noticeable impact on performance. You can solve this issue by using the generation of relatively small maps or the dynamic "expansion" and "reduction" of the map depending on the player's field of view.

**

So, in this article we reviewed an example of a map generated with flaws. Bugs can appear in projects for various reasons — often it happens due to programmers' mistakes. However, there are special tools that can help find them. In case you are interested in such tools, I invite you to read the following articles:

• Why should Unity game developers use static analysis?
• Bugs found in Unity: part 1, part 2.

That's all — wish you clean code and successful projects. :)