Wave Function Collapse procedural generation

Introduce

Wave Function Collapse (WFC) is a very interesting procedural generation technique, and Townscaper is a well-known example of its application.

First, a brief introduction to the WFC algorithm. We can divide space into a large number of cells and prepare a set of modules. There are rule constraints between modules—for example, module A must be placed to the left of module B. Each cell has an associated “entropy” value, which is related to the number of modules that are still allowed under the current constraints.

In each iteration, we search for the cell with the lowest entropy. If multiple cells share the same entropy, one of them is chosen at random. Then, one module is randomly selected from the set of allowed modules for that cell and placed there; this step is referred to as “collapse.” After the collapse, a propagation step follows, during which the possible modules and entropy values of other cells are updated according to the new constraints. This process is repeated until every cell has collapsed and contains a module.

My implement

In this example, I define several modules and place them randomly.

The rule design here is slightly different. The boundary of the grid must either be empty or allow a pipe to pass through. Instead of explicitly maintaining the allowed states of neighboring cells, I maintain the state of edges. Each edge can be in one of three states:

• no pipe passes through,
• a pipe passes through,
• undecided.

In the materials I found, this edge-based approach was not commonly used. When I came up with this idea, it also led to some further insights. The number of possible modules for neighboring cells is essentially just one way of expressing rule constraints. Edge states can serve the same role. Extending this idea further, vertices could also have states, and even the grid as a whole—or local regions within it—could possess their own states.

Some of these selected elements are directly associated with individual cells, while others are not. They can be combined and contribute to entropy through certain weights or algorithms. This mechanism may be a necessary component for building more complex and broadly applicable WFC systems.

When all boundary edges are set to the empty state, it becomes easy to observe that, at each corner, two edges are already determined at initialization. As a result, the WFC process will always begin collapsing from these four corner cells.

Next step

Although this simple demo already gives the image a clear procedural-generation feel, my original intention was to generate a fully connected structure. With the current simple rules, isolated structures are still allowed. Therefore, I need to consider how to design constraints that enforce connectivity, or how to generate results that resemble the layout of a Metroidvania-style map.

In addition, I have been thinking about a fractal-style WFC approach. For example, one could first generate small 5×5 maps, then treat each of these as a higher-level module to generate a larger-scale map.