Unity: infinite procedurally generated city, obtained using the WFC algorithm (wave function collapse)
Hi, Habr!
As trendsetters on Unity on the Russian market, we suggest you read an interesting study on the practical use of the WFC (Wave Function Collapse) algorithm, built in the image and likeness of the well-known principle of quantum mechanics and very convenient for procedural generation of levels in games. Earlier on Habré already published a detailed account of this algorithm. The author of today's article, Marian Kleineberg, considers the algorithm in the context of three-dimensional graphics and the generation of an infinite city. Enjoy reading!
We'll talk about the game, where you walk through an endless city that is procedurally generated as you move. A city is built from a set of blocks using the WFC algorithm (wave function collapse).
')
Playable build is available for download on itch.io. You can also get the source code on github . Finally, I propose a video in which I am walking on a city generated in this way.
I will call the word “cell” such an element of a 3D voxel grid, which may contain a block or be empty. The word "module" I will call a block that can occupy such a cell.
The algorithm decides which modules to select in each cell of the game world. A cell array is considered to be a wave function in its unobservable form. Thus, each cell corresponds to a set of modules that may be in it. In terms of quantum mechanics one could say, "the cell is in the superposition of all modules." The existence of the world begins in a completely unobservable form, where in each cell there can be any module. Further, all the cells collapse, one after another. This means that for each cell, one module is randomly selected from among all possible.
The next step is the propagation of constraints (constraint propagation). For each module, a subset of modules is selected that are allowed to be adjacent to it. Each time the module collapses, the subsets of other modules are updated, which are still allowed as adjacent ones. The stage of propagation of constraints is the most resource-intensive part of the algorithm in terms of computing power.
An important aspect of the algorithm is determining which cell to collapse. The algorithm always collapses the cell with the lowest entropy . This is a cell that allows the minimum number of choices (that is, the cell with the least randomness). If all modules have the same collapse probability, then the smallest entropy will be in that cell, which corresponds to the minimum number of possible modules. As a rule, the probabilities of being chosen for different modules are different. A cell with two possible modules that have the same probability provides for a wider choice (greater entropy) than the one in which there are two modules, and for one of them the probability to fall under the choice is very large, and for the other - very small.
(Gifka ExUtumno placed on Github)
More information about the wave function collapse algorithm, as well as a number of beautiful examples can be found here. Initially, this algorithm was proposed for generating 2D textures based on a single sample. In this case, the probabilistic indicators of the modules and the adjacency rules are determined depending on their occurrence in the example. This article provides this information manually.
Here is a video demonstrating this algorithm in action.
The world is generated from a set in which there are about 100 blocks. I created them with Blender. At first I had very few blocks, and I gradually added them when I considered it necessary.
The algorithm needs to know which modules can be located next to each other. For each module there are 6 lists of possible neighbors, one in each of the directions. However, I wanted to avoid having to create such a list manually. In addition, I wanted to automatically generate rotated variants for each of my blocks.
Both of these tasks are solved with the help of the so-called prototype modules. In essence, this is
A difficult problem has arisen with modeling information about adjacency, so that this automatic process works. Here's what I got:
Each block has 6 contacts, one for each face. The contact has a number. In addition, horizontal contacts can be flipped, non-flipped, or symmetrical. Vertical contacts either have a rotation index in the range from 0 to 3, or are marked as rotationally invariant .
Based on this, I can automatically check which modules are allowed to adjoin each other. Adjacent modules must have the same pin numbers. Their symmetry must also coincide (the same index of rotation along the vertical, a pair of inverted and non-inverted contact horizontally), or the modules must be symmetrical / invariant.
There are exclusion rules with which I can prohibit neighborhood options that would be allowed by default. Some blocks with matching contacts to each other simply look ugly side by side. Here is an example of a map generated without applying exclusion rules:
The original wave function collapse algorithm generates maps of finite size. I wanted to build a world that will expand and expand as you move along it.
At first I tried to generate fragments of finite size and use the contacts of adjacent fragments as constraints. If the fragment is generated, and the adjacent fragment is also generated, then only such modules are allowed, which are placed next to the existing modules. With this approach, the following problem arises: each time a cell collapses, the propagation of constraints will cut capabilities even at a distance of several cells. The following image shows the effects of collapsing a single cell:
If at each step of the algorithm to generate only one fragment, then the restrictions do not apply to adjacent fragments. In this case, such modules were selected inside the fragment that would be unacceptable if other fragments were taken into account. As a result, when the algorithm tried to generate the next fragment, it could not find a single solution.
Now I no longer use fragments, but I store the map in a dictionary that displays the position of a cell on a cell. The cell is filled only if necessary. Some elements of the algorithm should be adjusted to reflect this point. When choosing a cell that should collapse, it is impossible to take into account all the cells if their number is infinite. Instead, we simultaneously generate only a small portion of the map as soon as the player reaches it. Outside this area, restrictions continue to spread.
In some cases, this approach does not work. Consider a set of modules for a straight section of the tunnel from the figure shown above - there is no entrance to the tunnel. If the algorithm chooses such a tunnel module, then the tunnel by definition will be infinite. At the stage of propagation of restrictions, the program will try to allocate an infinite number of cells. I developed a special set of modules to get around this problem.
Here there are two important boundary conditions. All faces on the top level of the map must have "air" contacts. All faces on the basis of the card must have "solid" contacts. If these conditions are not met, then there will be holes in the ground on the map, and some buildings will be roofless.
On a map of finite size, this problem would be solved easily. For all cells at the highest and lowest levels, it would be necessary to remove all modules with inappropriate contacts. Then run the distribution of restrictions and remove the remaining modules that are no longer suitable for us.
On a map of infinite size, this does not work, since we have an infinite number of cells both at the highest level and at the lowest level. The most naive solution is to delete all inappropriate cells as they arise. However, when the module is removed at the top level, the limitations affect those cells that adjoin it. An avalanche-like effect occurs, again leading to an infinite selection of cells.
I solved this problem by creating a 1 × n × 1 map, where n is the height. This card uses world wrapping to propagate restrictions. The mechanism works as in the game Pacman: leaving the right edge of the card, the character returns to it from the left edge. Now I can apply any restrictions to my map. Whenever a new cell is created on an infinite map, this cell is initialized with a set of modules corresponding to a specific position on the map.
Sometimes the WFC algorithm reaches a state in which no possible module matches the cell. In applications where we are dealing with a world of finite size, you can simply reset the result and start over. In an infinite world, this will not work, as part of the world is already shown to the player. At first I settled on a solution in which the places of occurrence of errors were filled with white blocks.
I am currently using a return search. The cell collapse order and some information on the propagation of constraints is stored as history. If the WFC algorithm fails, then part of the history is canceled. As a rule, it works, but sometimes it is possible to recognize errors too late, and a return search covers a lot of steps. In rare cases, the cell in which the player is located is regenerated.
In my opinion, due to this limitation, the use of the WFC algorithm with infinite worlds is not suitable for commercial games.
I took up the study of this problem after watching a lecture by Oscar Stelberg , telling how he uses the algorithm to generate levels in the game Bad North. In general, my algorithm was implemented during the procjam week.
I have some ideas for further refinement of this algorithm, but I’m not sure that I’m ever going to add gameplay to it. And if I get together, it will most likely not be such an epic strategy that you have already imagined. However, if you want to check how your favorite game mechanic works with this algorithm - just try it yourself! In the end, the source code is publicly available and licensed by MIT.
As trendsetters on Unity on the Russian market, we suggest you read an interesting study on the practical use of the WFC (Wave Function Collapse) algorithm, built in the image and likeness of the well-known principle of quantum mechanics and very convenient for procedural generation of levels in games. Earlier on Habré already published a detailed account of this algorithm. The author of today's article, Marian Kleineberg, considers the algorithm in the context of three-dimensional graphics and the generation of an infinite city. Enjoy reading!
We'll talk about the game, where you walk through an endless city that is procedurally generated as you move. A city is built from a set of blocks using the WFC algorithm (wave function collapse).
')
Playable build is available for download on itch.io. You can also get the source code on github . Finally, I propose a video in which I am walking on a city generated in this way.
Algorithm
I will call the word “cell” such an element of a 3D voxel grid, which may contain a block or be empty. The word "module" I will call a block that can occupy such a cell.
The algorithm decides which modules to select in each cell of the game world. A cell array is considered to be a wave function in its unobservable form. Thus, each cell corresponds to a set of modules that may be in it. In terms of quantum mechanics one could say, "the cell is in the superposition of all modules." The existence of the world begins in a completely unobservable form, where in each cell there can be any module. Further, all the cells collapse, one after another. This means that for each cell, one module is randomly selected from among all possible.
The next step is the propagation of constraints (constraint propagation). For each module, a subset of modules is selected that are allowed to be adjacent to it. Each time the module collapses, the subsets of other modules are updated, which are still allowed as adjacent ones. The stage of propagation of constraints is the most resource-intensive part of the algorithm in terms of computing power.
An important aspect of the algorithm is determining which cell to collapse. The algorithm always collapses the cell with the lowest entropy . This is a cell that allows the minimum number of choices (that is, the cell with the least randomness). If all modules have the same collapse probability, then the smallest entropy will be in that cell, which corresponds to the minimum number of possible modules. As a rule, the probabilities of being chosen for different modules are different. A cell with two possible modules that have the same probability provides for a wider choice (greater entropy) than the one in which there are two modules, and for one of them the probability to fall under the choice is very large, and for the other - very small.
(Gifka ExUtumno placed on Github)
More information about the wave function collapse algorithm, as well as a number of beautiful examples can be found here. Initially, this algorithm was proposed for generating 2D textures based on a single sample. In this case, the probabilistic indicators of the modules and the adjacency rules are determined depending on their occurrence in the example. This article provides this information manually.
Here is a video demonstrating this algorithm in action.
About blocks, prototypes and modules
The world is generated from a set in which there are about 100 blocks. I created them with Blender. At first I had very few blocks, and I gradually added them when I considered it necessary.
The algorithm needs to know which modules can be located next to each other. For each module there are 6 lists of possible neighbors, one in each of the directions. However, I wanted to avoid having to create such a list manually. In addition, I wanted to automatically generate rotated variants for each of my blocks.
Both of these tasks are solved with the help of the so-called prototype modules. In essence, this is
MonoBehaviour , which is convenient to work with in the Unity editor. Modules, along with lists of valid neighboring elements and rotated variants, are automatically created based on such prototypes.
A difficult problem has arisen with modeling information about adjacency, so that this automatic process works. Here's what I got:
Each block has 6 contacts, one for each face. The contact has a number. In addition, horizontal contacts can be flipped, non-flipped, or symmetrical. Vertical contacts either have a rotation index in the range from 0 to 3, or are marked as rotationally invariant .
Based on this, I can automatically check which modules are allowed to adjoin each other. Adjacent modules must have the same pin numbers. Their symmetry must also coincide (the same index of rotation along the vertical, a pair of inverted and non-inverted contact horizontally), or the modules must be symmetrical / invariant.
There are exclusion rules with which I can prohibit neighborhood options that would be allowed by default. Some blocks with matching contacts to each other simply look ugly side by side. Here is an example of a map generated without applying exclusion rules:
Way to infinity
The original wave function collapse algorithm generates maps of finite size. I wanted to build a world that will expand and expand as you move along it.
At first I tried to generate fragments of finite size and use the contacts of adjacent fragments as constraints. If the fragment is generated, and the adjacent fragment is also generated, then only such modules are allowed, which are placed next to the existing modules. With this approach, the following problem arises: each time a cell collapses, the propagation of constraints will cut capabilities even at a distance of several cells. The following image shows the effects of collapsing a single cell:
If at each step of the algorithm to generate only one fragment, then the restrictions do not apply to adjacent fragments. In this case, such modules were selected inside the fragment that would be unacceptable if other fragments were taken into account. As a result, when the algorithm tried to generate the next fragment, it could not find a single solution.
Now I no longer use fragments, but I store the map in a dictionary that displays the position of a cell on a cell. The cell is filled only if necessary. Some elements of the algorithm should be adjusted to reflect this point. When choosing a cell that should collapse, it is impossible to take into account all the cells if their number is infinite. Instead, we simultaneously generate only a small portion of the map as soon as the player reaches it. Outside this area, restrictions continue to spread.
In some cases, this approach does not work. Consider a set of modules for a straight section of the tunnel from the figure shown above - there is no entrance to the tunnel. If the algorithm chooses such a tunnel module, then the tunnel by definition will be infinite. At the stage of propagation of restrictions, the program will try to allocate an infinite number of cells. I developed a special set of modules to get around this problem.
Border conditions
Here there are two important boundary conditions. All faces on the top level of the map must have "air" contacts. All faces on the basis of the card must have "solid" contacts. If these conditions are not met, then there will be holes in the ground on the map, and some buildings will be roofless.
On a map of finite size, this problem would be solved easily. For all cells at the highest and lowest levels, it would be necessary to remove all modules with inappropriate contacts. Then run the distribution of restrictions and remove the remaining modules that are no longer suitable for us.
On a map of infinite size, this does not work, since we have an infinite number of cells both at the highest level and at the lowest level. The most naive solution is to delete all inappropriate cells as they arise. However, when the module is removed at the top level, the limitations affect those cells that adjoin it. An avalanche-like effect occurs, again leading to an infinite selection of cells.
I solved this problem by creating a 1 × n × 1 map, where n is the height. This card uses world wrapping to propagate restrictions. The mechanism works as in the game Pacman: leaving the right edge of the card, the character returns to it from the left edge. Now I can apply any restrictions to my map. Whenever a new cell is created on an infinite map, this cell is initialized with a set of modules corresponding to a specific position on the map.
Error states and search with return
Sometimes the WFC algorithm reaches a state in which no possible module matches the cell. In applications where we are dealing with a world of finite size, you can simply reset the result and start over. In an infinite world, this will not work, as part of the world is already shown to the player. At first I settled on a solution in which the places of occurrence of errors were filled with white blocks.
I am currently using a return search. The cell collapse order and some information on the propagation of constraints is stored as history. If the WFC algorithm fails, then part of the history is canceled. As a rule, it works, but sometimes it is possible to recognize errors too late, and a return search covers a lot of steps. In rare cases, the cell in which the player is located is regenerated.
In my opinion, due to this limitation, the use of the WFC algorithm with infinite worlds is not suitable for commercial games.
Prehistory
I took up the study of this problem after watching a lecture by Oscar Stelberg , telling how he uses the algorithm to generate levels in the game Bad North. In general, my algorithm was implemented during the procjam week.
I have some ideas for further refinement of this algorithm, but I’m not sure that I’m ever going to add gameplay to it. And if I get together, it will most likely not be such an epic strategy that you have already imagined. However, if you want to check how your favorite game mechanic works with this algorithm - just try it yourself! In the end, the source code is publicly available and licensed by MIT.
Source: https://habr.com/ru/post/455004/
All Articles