Blogmark

In AI Learns to Optimize Factorio Blueprints, I learned about Wave Function Collapse. It was used to eliminate options of where to place certain tiles on a grid using neighbor-based constraints. This is a form of constraint propagation.

The linked blog post goes into this in much more detail using Sudoku to demonstrate it. It builds more foundation for the concepts including going into constraint programming (constraint solving algorithms).

Guessing and backtracking eventually terminates.

Every time you backtrack you reduce the domain of at least one variable, so even though there is a lot of giving up and restarting involved, the algorithm is guaranteed to eventually terminate.

This all relates to wave function collapse in that you want to settle on a series of tile placements that all satisfy one another’s’ constraints.

In WFC, the goal is to fill in a grid with tiles such that nearby tiles connect to each other. In the terminology we used above, each tile is a different value, and each cell in the grid is a variable representing the choice of tile. And the rules about which tiles can be placed where are the constraints.