New Computerphile Video Explores Procedural Generation with Wave Function Collapse
In this video, the presenter from Computerphile delves into the concept of procedural generation, focusing particularly on a fascinating algorithm called Wave Function Collapse (WFC). The main goal is to demonstrate how simple rules can generate complex structures, a phenomenon observable in games like Minecraft or "dungeon crawler" games. To illustrate this principle, the presenter uses the board game Carcassonne as a concrete example.
The game Carcassonne involves building a map or kingdom by placing tiles that must align correctly with adjacent tiles. Players score points by completing roads, cities, or other landscape elements. The presenter explains the basic rules of the game, particularly how tiles must be placed so that roads and cities are continuous. This game mechanic serves as a starting point to introduce the Wave Function Collapse algorithm.
The Wave Function Collapse algorithm draws its name and inspiration from quantum physics, particularly the concept of quantum superposition. In quantum physics, a particle can exist in multiple states simultaneously until it is observed, at which point it "chooses" a specific state. The presenter uses this analogy to explain how the algorithm works. In the context of procedural generation, each cell in a grid can be considered a particle in superposition, meaning it can take on several possible states (different tiles) until a decision is made.
To illustrate how the algorithm functions, the presenter shows how an undetermined cell can have multiple tile possibilities that align with already placed tiles. For example, if a road comes in from the left side of a cell, that cell must have a road on its left side. The algorithm "observes" a cell by randomly choosing from its possibilities and propagates this decision to adjacent cells, thereby reducing their possibilities. This process is repeated until all cells are determined.
The presenter also explains the concept of entropy, borrowed from information theory, to determine which cell to observe first. Entropy measures the degree of uncertainty or surprise associated with a cell. By choosing to "collapse" cells with the lowest entropy (those with the fewest possibilities) first, the algorithm minimizes the risk of ending up with cells that have no viable solution. This allows for the generation of more coherent and complete maps.
To make the algorithm more realistic in relation to Carcassonne, the presenter introduces modifications. For instance, he adjusts the wave function to account for the fact that players must draw the top tile from the stack, not a random tile. This makes the generation more faithful to the game's rules, although it may result in imperfections like incomplete roads or cities.
Next, the presenter shows how to redefine the wave function to favor certain configurations, such as longer roads or cities. By assigning different weights to possibilities based on specific criteria (e.g., the length of a road), the algorithm can generate maps that more closely resemble those created by human players. This approach uses Shannon entropy, which considers the weighted probabilities of different possibilities to determine which cell to observe first.
The presenter illustrates these concepts with a simulation written in Python, showing how the algorithm generates Carcassonne maps in real-time. He also demonstrates how minor adjustments in the definition of the wave function and entropy can produce very different results, ranging from highly structured maps to more chaotic and organic ones.
Finally, the presenter encourages viewers to experiment with the algorithm by modifying the wave and entropy functions to explore different possibilities. He mentions that the source code for the simulation is available on GitHub, allowing interested individuals to adapt it and create their own procedural generations. This video highlights the beauty and power of procedural generation algorithms, capable of creating complex structures from simple, local rules.
For those wishing to delve deeper into the subject or see the algorithm in action, the video offers a captivating visual demonstration and a clear explanation of the underlying principles. Whether for applications in video games, texture generation, or other creative fields, Wave Function Collapse proves to be a powerful and versatile tool.