Try Now | Source
(Controls and options listed at the bottom of this page.)
Wave Function Collapse (WFC) is a procedural generation technique used to create randomized structures based on a set of adjacency rules. The algorithm begins by placing each tile or voxel in a state of superposition, meaning it is every possible tile or voxel option simultaneously. To start collapsing the tiles into specific states, the algorithm selects a "guess tile" and manually collapses it to a single tile type.

The algorithm then uses the principle of superposition to calculate the probabilities of neighboring tiles and eliminate any tile types that are not allowed to be next to the previously collapsed tile. This process is repeated in a ripple effect until options can no longer be eliminated from any of the remaining tiles in the map. At this point a new "guess tile" is selected from one of the tiles with the fewest remaining legal options and the process starts over again.

This continues until every tile has been collapsed to a single state.



It is possible for the collapse of a "guess tile" to result in a conflict where there are no legal options for a tile remaining. When this happens all changes made as a result of the last guess tile are reverted and a new state is chosen for the guess tile. If all states for a guess tile are exhausted and there is still a conflict then it will revert to the previous guess tile until it finds a guess tile and if necessary the tile before that until it finds a path to collapse every tile to a single state.

The problem with this is that the further back in the chain of guess tiles it has to go the longer it takes to resolve the conflict. Enter the Celadon's water house.



This house consists of one of the largest collections of unique tiles in Celadon city. Each end of the house must be above a boulder fence tile. These fence tiles appear nowhere else on the map and must terminate on the bottom with either brick road, or old man, and must terminate upwards into a side of the house, or into more fence. This is the only one story building on this map and aside from the two window tile each tile only shows up once. The white single right window must appear above the old man, the white single left window tile must appear over that particular road tile, and that road tile must terminate into water, which must terminate to the left and right into rock. If any of the house, rock fence, or water is chosen the house essentially needs to be generated in full, and if there isn't enough space it can easily get stuck in a position where it would take far too long to ever actually complete.


Here is a live example of it getting stuck:
https://austin.straybanana.com/wfc/?noBias=1&seed=1653343915873&debug=1&normalRecursion=1

In this example green tiles are tiles queued up to be collapsed. Yellow tiles are tiles that have experienced a conflict and reached a state of zero legal options remaining. Red tiles are guess tiles that have run out of available options, forcing the algorithm to revert to the previous guess tile.



As you can see, when it starts generating the water it keeps trying to generate a new fence and house to terminate the water but the house has no room to generate the eastern fence. It keeps needing to recurse further and further back, and the amount of time it takes grows exponentially.

To solve this I came up with a new technique I refer to as "Dependency Reversion". In this technique when I encounter a conflict that I cannot resolve with any of the available states of the current guess tile, I look back through the history of that guess tile and revert to the guess tile that first collapsed the current guess tile. In doing this I can cut out huge chains of errors and retry from a point far enough back to actually make a difference in avoiding any of those mistakes.

Here is the same example with Dependency Reversion:
https://austin.straybanana.com/wfc/?noBias=1&seed=1653343915873&debug=1



Dependency Reversion has major flaws unfortunately that I was unable to solve. Due to how far back an exhausted guess tile reverts, it is very possible, depending on the complexity of the rules, for it to revert itself back to the very start. If this happens enough times it can straight up fail to generate anything at all. Also, while this does speed up the reversion process, it doesn't completely eliminate the getting stuck problem. Also, if there are any tiles that are exceptionally easy to eliminate right at the start, the oldest "dependency" could be the very first guess tile.

If you wish to play around with this you can demo it over at:
https://austin.straybanana.com/wfc/