Wave Function Collapse For World Generation
"In quantum mechanics, wave function collapse occurs when a wave function — initially in a superposition of several eigenstates — reduces to a single eigenstate due to interaction with the external world."
Wikipedia: Wave function collapse
How WFC Applies to World Generation
- For world generation, each tile has a set of possible types of tiles
- Until one is chosen, it is in its "superposition" state
- The tile map is procedurally iterated over, randomly selecting one of the possible types for each tile
- This is the collapse phase
- There are adjacency rules for which tiles can be next to each other, so as tiles are chosen, the set of possible types for adjacent tiles will be reduced (probability space reduced)
- These rules can be different depending on direction from the tile
Determining Valid Neighbors
Multiple approaches:
- Map of valid neighbors for each tile / direction
- "Socketing" system where each tile / direction has a socket ID that is used to match valid neighbors
- Relevant section of "Superpositions, Sudoku, the Wave Function Collapse algorithm" Video
Ideas for Pathing
- There can be an additional step after each tile is collapsed to check that pathing is still possible and the previous tile can be regenerated on failure until pathing is solvable
- The adjacency rules could include pathing when reducing neighboring sets (i.e. if there are are walls on all other sides, walls are excluded from the possible set for the remaining tile)
- The entire world/map could be generated and then checked that pathing is solvable using something like A* - either breaking down paths or re-generating until solvable