The initial tile/pixel grid starts with the tiles/pixels being all possible values.
The algorithm selects a random tile with a preference for low-entropy tiles/pixels (i.e. with a low number of possible values). The chosen tile is the set to a value from its possible values ("superpositions").
The adjacent tiles/pixels are then updated ("collapsed") based on the rules/constraits of the system (e.g. if there is a wall to the left of the tile, there must be a wall on the right edge). This collapse is propagated until there are no more tiles/pixels to update. If a tile/pixel during the collapse has a single value then it is assigned that value.
The process repeats until all tiles/pixels have a single value.
There can be cases where a collapse reaches a state where it is in an invalid state or cannnot be collapsed further. Various implementations of the algorithm will then reject the generation and redo it from the beginning -- similar to the rejection sampling you mentioned.
The initial tile/pixel grid starts with the tiles/pixels being all possible values.
The algorithm selects a random tile with a preference for low-entropy tiles/pixels (i.e. with a low number of possible values). The chosen tile is the set to a value from its possible values ("superpositions").
The adjacent tiles/pixels are then updated ("collapsed") based on the rules/constraits of the system (e.g. if there is a wall to the left of the tile, there must be a wall on the right edge). This collapse is propagated until there are no more tiles/pixels to update. If a tile/pixel during the collapse has a single value then it is assigned that value.
The process repeats until all tiles/pixels have a single value.
There can be cases where a collapse reaches a state where it is in an invalid state or cannnot be collapsed further. Various implementations of the algorithm will then reject the generation and redo it from the beginning -- similar to the rejection sampling you mentioned.