4 ms·
No. 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
by rhdunn 4y ago
No.
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.
- tetris11 4y agoIs it then just repeated sampling of some markov space?
- denton-scratch 4y agoDoesn't "redo from the beginning" potentially result in an infinite number of iterations? It would be good to be able to a) determine in bounded time whether any solution exists at all b) use a deterministic procedure to find a solution "Redo from the beginning" seems like cracking a cipher by brute force.
- abraxas 4y agoYou can backtrack to any arbitrary point but yeah it is a NP hard problem and this algorithm cannot bypass that. Also there is no guarantee of convergence on a solution.
- nightowl_games 4y agoWhen I used this algorithm, I would seed a random number generator, and if it failed to produce a result given a set of constraints, I'd increment the seed and try again up to ~1000 times or so.
- zzlk 4y agoa) determine in bounded time whether any solution exists at all I can't prove it but I think this is roughly the same thing as the circuit satisfiability problem, which is np-complete. So, I think the best thing you can do there is a very large exponential time bound. b) use a deterministic procedure to find a solution You can solve this problem deterministically with depth first search. But I found that to be pretty slow and generate not very aesthetically interesting results most of the time.