Wave Function Collapse

A simple Wave Function Collapse algorithm.

A series of tiles are defined, and their edges are given an ID. In this case, a string.

Then a series of adjacency rules are defined. Here, grass must connect to grass, and path to path.

Step 1: Fill all cells in the grid with their potential tiles at all possible rotations.

Step 2: Pick a tile at random and "collapse" it by choosing which of it's possible tiles it will become. Then update all of that tile's neighbors' options list to comply with the adjacency rules. In this case, the chosen House has grass on all sides, so all adjacent tiles are trimmed down to options that connect with grass on an adjacent side. If this were to limit the list enough to cascade rules further outwards, that would also be done.

Step 3: Pick the tile with the least options, and collapse it to one of those options at random, cascading adjacency rules outwards. Repeat until the whole grid is complete.

Fast forwarding a bit, we end up with this:

Here's a 10x10 grid being being filled relatively slowly

And here's a few generating much faster:

Page updated

Google Sites

Report abuse