I started out with a small number of blocks and made more whenever I had some spare time. The world is generated from a set of ~100 blocks, which I made with Blender. Here is a video of the algorithm in action: Wave Function Collapse is based on Paul Merrel’s Model Synthesis. In that case, the module probabilities and adjacency rules are determined based on how they occur in the example.

The algorithm was proposed to generate 2D textures from a single example. You can find more information and some beautiful examples of the Wave Function Collapse algorithm here. In general, modules have different probabilities to be selected.Ī slot with two possible modules of the same probability has more choice (greater entropy) than one with two modules where one is very likely and one is very unlikely.

If all modules have the same probability, the slot with the smallest number of possible modules has the lowest entropy. That is the slot which has the least amount of choice (or chaos). The algorithm always collapses the slot with the lowest entropy. The constraint propagation step is the most computationally expensive part of the algorithm.Īn important aspect of the algorithm is deciding which slot to collapse. Whenever a slot is collapsed, the sets of modules that are still possible to be placed in nearby slots need to be updated. This is followed by a step of constraint propagation.įor each module, only a subset of modules are allowed to be placed adjacent to it. That means, one module from the set of possible modules is selected at random. The world starts in a completely unobserved state where every module is possible in any slot. In the language of quantum mechanics, one could say “The slot is in superposition of all modules”. That means that each slot has a set of possible modules that could be put there. The array of slots is considerd a wave function in an unobserved state. The algorithm chooses which modules to select for each slot in the world. I will use the word “slot” for a place in the 3D voxel grid that can contain a block (or be empty) and I will use the word “module” for a block that can inhabit such a slot.

Building generator algorithm