Canvas: Wave Function Collapse for terrain generation

Wave Function Collapse, it sounds like a complicated quantum mechanics process, partly because it is, but it's also an algorithm to generate 2D tiled layouts.

The Wave Function Collapse algorithm works by reducing the possibilities for each tile on the grid, and then collapses the tile with the lowest entropy (i.e., the tile that has the least number of possibilities). Once collapsed, the new constrain is propagated to all neighbour tiles, and then the next tile is selected for collapsing.

With terrain generation, we have 5 types of tiles: Sea, Sand, Land, Forrest, and Mountains. Each tile then defines its possible neighbours:

• Sea tiles can be boarded by Sea and Sand tiles
• Sand tiles can be boarded by Sea, Sand, and Land tiles
• Land tiles can be boarded by Sand, Land, Forrest, and Mountain tiles
• Forrest tiles can be boarded by Forrest and Land tiles
• Mountain tiles can be boarded by Land and Mountain tiles

With these simple constraints, the algorithm can loop over each tile, collapse, and then propagate the new constraints to each neighbour.

Check out how the algorithm propagates and collapses tile on the canvas playground

This implementation is very basic. The entropy calculation on looks at tiles with the least number of possibilities, which allows Sea and Sand tiles to take over the generation, as they typically reduce to the lowest number possibilities quickly, and then take over. To combat this, I've increased the chance that, where possible, tiles will collapse to a Land tile. This also means the initial tile will likely collapse to a land tile, causing most generations to start with Land in the top left corner, and Sea and Sand tiles generating on the right. A better entropy calculation that takes into account neighbouring tiles might help to reduce this issue.

Performance is generally good, but takes increasingly longer the larger the grid becomes, as each time a tile is collapsed, the changes need to propagated to an increasing number of neighbouring tiles. Without animation, a 50x50 grid typically takes around 2-3 seconds. Further performance improvements can be made with the propagation routine.

The Wave Function Collapse algorithm is a general purpose algorithm. I've use it here for terrain generation, but it can also be used to generate any kind of structured random pattern. It's also possible to train the algorithm by providing an input reference, that is scanned to determine the possible tile combinations.

Other Wave Function Collapse uses would be generating floor plans, village/town maps, pseudo circuitry etc, as well as textures like stone walls and wood grain.