6 ms·

The “Wavefunction Collapse” generation algorithm explained clearly (2018)

169 points by signa11 4y ago

marcAKAmarc 4y ago
I always thought the best way to explain wfc would be: Multidimensional Markov Chain
- shapefrog 4y ago
  Brute force is always easier!
  - ogogmad 4y ago
    When?
magicalhippo 4y ago
Isn't this just essentially rejection sampling[1]? Generate a a random sample (shuffled seating positions) and reject it if it doesn't meet some criteria? [1]: https://en.wikipedia.org/wiki/Rejection_sampling https://en.wikipedia.org/wiki/Rejection_sampling
- 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 ago
    Is it then just repeated sampling of some markov space?
  - denton-scratch 4y ago
    Doesn'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 ago
      You 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 ago
      When 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 ago
      a) 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.
Xcelerate 4y ago
I got really excited about the title of this post, thinking there might have been some 100 year breakthrough in quantum mechanics before I realized that was not what this was about.
- dang 4y ago
  I've modified the title to try to distance it from that obvious misunderstanding.
- welcome_dragon 4y ago
  Same. Dumb name for an algorithm
captainmuon 4y ago
Unfortunate name for an interesting algorithm. In a very high level way, it reminds me of Stable Diffusion, where you also kind of cool a random state into a desired ordered state.
- karmakaze 4y ago
  Especially since we don't even know what actual wavefunction collapse means.
  - criddell 4y ago
    Is there a leading theory about what the physical reality of wavefunction collapse is?
    - ablatt89 4y ago
      I think many "top" physicists (those with high citation counts in theory), generally believe in consistent histories: https://en.wikipedia.org/wiki/Consistent_histories https://en.wikipedia.org/wiki/Consistent_histories That is, there is no collapse. QM is a description of the quantum level of the world relative to our fixed sized, such that it doesn't really make sense to ask "what is really happening" since "what is really happening" is relative to what we can measure and ask from a human perspective. The probabilisitic nature is the description we have to describe systems at the quantum scale since it doesn't really make sense to ask the question what a quantum system looks like at a quantum scale, since measurement devices are inherently classical. I guess you can say it's sorta like taking some algorithm for some problem, caching all possible inputs, and thus knowing the full solution to that problem but not really knowing the "true" algorithm that has no memory space optimizations. Some might say the problem should have a more "real" solution, but the infinite cache solution might be all we have and it doesn't mean the solution is worthless. While this may seam unsatisfactory to some, I think QM is a very consistent description to much physics, and alternatives like LQG are inherently problematic as it violates Lorentz invariance since it chooses a privileged reference frame (the reference frame with the smallest length metric). A lot of the hate comes from some physicists who want to introduce their own theories, want to full status and glory of being the next Einstein who disrupted physics, but will never address any criticism of their theories, berate others who work on QM or string theory for not wanting to work on their framework, and essentially saying those who are working on QM/theory don't deserve their jobs nor funding.
mesofile 4y ago
Another great explanation (also in a game-development context) here [0], previously discussed here [1] [0] https://www.gamedeveloper.com/blogs/how-townscaper-works-a-story-four-games-in-the-making https://www.gamedeveloper.com/blogs/how-townscaper-works-a-s... [1] https://news.ycombinator.com/item?id=31799818 https://news.ycombinator.com/item?id=31799818
danbruc 4y ago
Let me throw in another name, I think this is essentially just constraint propagation with back tracking and making mostly random choices if there are no more constraints to propagate. But the idea of extracting constraints from a sample images and using those to generate variants is neat.
symmetricsaurus 4y ago
Oskar Stålberg has famously used WFC in Bad North and Townscaper. Here's a nice presentation from him explaining it: https://www.youtube.com/watch?v=0bcZb-SsnrA https://www.youtube.com/watch?v=0bcZb-SsnrA
abetusk 4y ago
As others have mentioned, this is "just" constraint propagation. I think much of the success is that it's a simple idea to grasp and implement, that provides very good results, and has a compelling name. I don't want to be dismissive, I think it's very cool. The original author of "wave function collapse" also has "convchain" [0] which is similarly "just" using Monte Carlo Markov Chains to sample the space. It's also a kind of "staple" algorithm for physicists, theoretical computer scientists, etc but I guess hasn't caught on as much as WFC. Note that WFC has major problems when the tile set is too constrained. There's a SO question about it [1] and I also happen to have written a small article about it as well [2](). [0] https://github.com/mxgmn/ConvChain https://github.com/mxgmn/ConvChain [1] https://stackoverflow.com/questions/72721299/why-can-the-wave-function-collapse-algorithm-fail https://stackoverflow.com/questions/72721299/why-can-the-wav... [2] https://www.fxhash.xyz/article/lessons-learned-from-implementing-%22wave-function-collapse%22 https://www.fxhash.xyz/article/lessons-learned-from-implemen... () trigger warning, it's an NFT but please don't let that stop you from reading
- symmetricsaurus 4y ago
  You can use it solve sudokus as well [0]. I find the parallel quite enlightening. [0] https://norvig.com/sudoku.html https://norvig.com/sudoku.html
  - abetusk 4y ago
    Ah, well, this is of course doing constraint propagation but is doing full backtracking search to find solutions. WFC, as usually presented in the procgen community (that I've seen) is a "one-shot" algorithm without any backtracking. This is not to say that people don't do this or make compromises like running it multiple times, if it fails, but Norvig's solution is doing proper search.
- rullelito 4y ago
  The name makes this algorithm so underwhelming, once you see what it actually is.
- BoppreH 4y ago
LegitShady 4y ago
I think they should pick a new name for this algorithm.
- Koshkin 4y ago
  "A rose by any other name would smell as sweet."
zzlk 4y ago
I implemented this algorithm to generate StarCraft 1 maps and it worked quite well. The results it generates have quite a natural property to them that you don't see with similar things like perlin noise. I wrote it in rust which I compiled down to wasm, put it on a web page with an ugly UI and gave it to the community. They used to to produce some interesting maps and the results of one run even got included in a real released and finished map. One other benefit of this algorithm is that people can hand craft a map, placing tiles in certain places, and then you can ask the algorithm to complete the map. The algorithm will seemlessly blend generated content with your original tile placements (which are just more constraints). This is really nice for filling in unimportant areas with a consistent level of detail. Unfortunately I could never really get it to be fast enough. There are an enormous number of tiles in StarCraft, 15,000+ for some tilesets, and people want to generate maps of up to 256x256 tiles. This is a huge state space and under these conditions the algorithm very often gets stuck in a local minima. I've tried so many different heuristics to get it to work but it doesn't work reliably enough to be a truly useful tool in this situation unfortunately. There are many explanations out there about how this algorithm works, more so than many other algorithms. I think the reason for that is because from hearing the basic high level idea of this algorithm most people are able to then go and implement it and then that makes for an interesting blog post (I could do the same after implementing, I think). What almost all of these blog posts are missing is how to make it fast, and how to implement back tracking efficiently. I had to try a lot of things to get to where I am now and I don't feel like I've fully explored the space of possible implementations despite trying a lot of different approaches. Here are some example generated maps: https://media.discordapp.net/attachments/583406212272619571/1006666232575053824/unknown.png https://media.discordapp.net/attachments/583406212272619571/... https://i.imgur.com/LK5a6jU.jpg https://i.imgur.com/LK5a6jU.jpg https://cdn.discordapp.com/attachments/583406212272619571/1001173689594822676/PF1.jpg https://cdn.discordapp.com/attachments/583406212272619571/10... https://cdn.discordapp.com/attachments/583406212272619571/997424873662070825/out.webp https://cdn.discordapp.com/attachments/583406212272619571/99... https://cdn.discordapp.com/attachments/583406212272619571/997367143245033572/unknown.png https://cdn.discordapp.com/attachments/583406212272619571/99...
- Doxin 4y ago
  So one solution I've used in the past to get WFC unstuck from local maxima is to keep a counter for each tile location with how many times it has gotten stuck at that location. Whenever it gets stuck it'll reset all the tiles within a radius relative to that counter. First time it gets stuck it'll reset all direct neighbors. Second time it'll reset all direct neighbors and their neighbors etc. For the tilesets I was using it'd hardly ever have to reset the same spot more than twice, which kept things relatively fast. It has the nice property of eventually guaranteeing a solution, though that may involve resetting the entire map many many times if it's a sufficiently gnarly problem.
phkahler 4y ago
Has anyone applied it to choosing fingerings for guitar? Given a preferred picking style of course.
dang 4y ago
Related: The Wavefunction Collapse Algorithm Explained - https://news.ycombinator.com/item?id=18744696 https://news.ycombinator.com/item?id=18744696 - Dec 2018 (44 comments) The Wavefunction Collapse Algorithm explained - https://news.ycombinator.com/item?id=18742295 https://news.ycombinator.com/item?id=18742295 - Dec 2018 (3 comments) Infinite procedurally-generated city with the Wave Function Collapse algorithm - https://news.ycombinator.com/item?id=18443311 https://news.ycombinator.com/item?id=18443311 - Nov 2018 (141 comments) Show HN: Wave function collapse algorithm - https://news.ycombinator.com/item?id=12612246 https://news.ycombinator.com/item?id=12612246 - Sept 2016 (122 comments)
keepquestioning 4y ago
Can ChatGPT make this algorithm?
euix 4y ago
I saw this being explained by the Caves of Qud developer recently and it was quite impressive, as someone who has been working on procedural generation the way it can be used to generate believable dungeons and maps is very neat.
atum47 4y ago
I remember when I tried to share my version of this very same algorithm, people also got mad cause of the name. https://news.ycombinator.com/item?id=31384676 https://news.ycombinator.com/item?id=31384676

169 points by signa11 4y ago

marcAKAmarc 4y ago

I always thought the best way to explain wfc would be: Multidimensional Markov Chain

shapefrog 4y ago
Brute force is always easier!
- ogogmad 4y ago
  When?

magicalhippo 4y ago

Isn't this just essentially rejection sampling[1]? Generate a a random sample (shuffled seating positions) and reject it if it doesn't meet some criteria? [1]: https://en.wikipedia.org/wiki/Rejection_sampling https://en.wikipedia.org/wiki/Rejection_sampling

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 ago
  Is it then just repeated sampling of some markov space?
- denton-scratch 4y ago
  Doesn'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 ago
    You 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 ago
    When 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 ago
    a) 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.

Xcelerate 4y ago

I got really excited about the title of this post, thinking there might have been some 100 year breakthrough in quantum mechanics before I realized that was not what this was about.

dang 4y ago
I've modified the title to try to distance it from that obvious misunderstanding.
welcome_dragon 4y ago
Same. Dumb name for an algorithm

captainmuon 4y ago

Unfortunate name for an interesting algorithm. In a very high level way, it reminds me of Stable Diffusion, where you also kind of cool a random state into a desired ordered state.

karmakaze 4y ago
Especially since we don't even know what actual wavefunction collapse means.
- criddell 4y ago
  Is there a leading theory about what the physical reality of wavefunction collapse is?
  - ablatt89 4y ago
    I think many "top" physicists (those with high citation counts in theory), generally believe in consistent histories: https://en.wikipedia.org/wiki/Consistent_histories https://en.wikipedia.org/wiki/Consistent_histories That is, there is no collapse. QM is a description of the quantum level of the world relative to our fixed sized, such that it doesn't really make sense to ask "what is really happening" since "what is really happening" is relative to what we can measure and ask from a human perspective. The probabilisitic nature is the description we have to describe systems at the quantum scale since it doesn't really make sense to ask the question what a quantum system looks like at a quantum scale, since measurement devices are inherently classical. I guess you can say it's sorta like taking some algorithm for some problem, caching all possible inputs, and thus knowing the full solution to that problem but not really knowing the "true" algorithm that has no memory space optimizations. Some might say the problem should have a more "real" solution, but the infinite cache solution might be all we have and it doesn't mean the solution is worthless. While this may seam unsatisfactory to some, I think QM is a very consistent description to much physics, and alternatives like LQG are inherently problematic as it violates Lorentz invariance since it chooses a privileged reference frame (the reference frame with the smallest length metric). A lot of the hate comes from some physicists who want to introduce their own theories, want to full status and glory of being the next Einstein who disrupted physics, but will never address any criticism of their theories, berate others who work on QM or string theory for not wanting to work on their framework, and essentially saying those who are working on QM/theory don't deserve their jobs nor funding.

mesofile 4y ago

Another great explanation (also in a game-development context) here [0], previously discussed here [1] [0] https://www.gamedeveloper.com/blogs/how-townscaper-works-a-story-four-games-in-the-making https://www.gamedeveloper.com/blogs/how-townscaper-works-a-s... [1] https://news.ycombinator.com/item?id=31799818 https://news.ycombinator.com/item?id=31799818

danbruc 4y ago

Let me throw in another name, I think this is essentially just constraint propagation with back tracking and making mostly random choices if there are no more constraints to propagate. But the idea of extracting constraints from a sample images and using those to generate variants is neat.

symmetricsaurus 4y ago

Oskar Stålberg has famously used WFC in Bad North and Townscaper. Here's a nice presentation from him explaining it: https://www.youtube.com/watch?v=0bcZb-SsnrA https://www.youtube.com/watch?v=0bcZb-SsnrA

abetusk 4y ago

As others have mentioned, this is "just" constraint propagation. I think much of the success is that it's a simple idea to grasp and implement, that provides very good results, and has a compelling name. I don't want to be dismissive, I think it's very cool. The original author of "wave function collapse" also has "convchain" [0] which is similarly "just" using Monte Carlo Markov Chains to sample the space. It's also a kind of "staple" algorithm for physicists, theoretical computer scientists, etc but I guess hasn't caught on as much as WFC. Note that WFC has major problems when the tile set is too constrained. There's a SO question about it [1] and I also happen to have written a small article about it as well [2](). [0] https://github.com/mxgmn/ConvChain https://github.com/mxgmn/ConvChain [1] https://stackoverflow.com/questions/72721299/why-can-the-wave-function-collapse-algorithm-fail https://stackoverflow.com/questions/72721299/why-can-the-wav... [2] https://www.fxhash.xyz/article/lessons-learned-from-implementing-%22wave-function-collapse%22 https://www.fxhash.xyz/article/lessons-learned-from-implemen... () trigger warning, it's an NFT but please don't let that stop you from reading

symmetricsaurus 4y ago
You can use it solve sudokus as well [0]. I find the parallel quite enlightening. [0] https://norvig.com/sudoku.html https://norvig.com/sudoku.html
- abetusk 4y ago
  Ah, well, this is of course doing constraint propagation but is doing full backtracking search to find solutions. WFC, as usually presented in the procgen community (that I've seen) is a "one-shot" algorithm without any backtracking. This is not to say that people don't do this or make compromises like running it multiple times, if it fails, but Norvig's solution is doing proper search.
rullelito 4y ago
The name makes this algorithm so underwhelming, once you see what it actually is.
BoppreH 4y ago

LegitShady 4y ago

I think they should pick a new name for this algorithm.

Koshkin 4y ago
"A rose by any other name would smell as sweet."

zzlk 4y ago

I implemented this algorithm to generate StarCraft 1 maps and it worked quite well. The results it generates have quite a natural property to them that you don't see with similar things like perlin noise. I wrote it in rust which I compiled down to wasm, put it on a web page with an ugly UI and gave it to the community. They used to to produce some interesting maps and the results of one run even got included in a real released and finished map. One other benefit of this algorithm is that people can hand craft a map, placing tiles in certain places, and then you can ask the algorithm to complete the map. The algorithm will seemlessly blend generated content with your original tile placements (which are just more constraints). This is really nice for filling in unimportant areas with a consistent level of detail. Unfortunately I could never really get it to be fast enough. There are an enormous number of tiles in StarCraft, 15,000+ for some tilesets, and people want to generate maps of up to 256x256 tiles. This is a huge state space and under these conditions the algorithm very often gets stuck in a local minima. I've tried so many different heuristics to get it to work but it doesn't work reliably enough to be a truly useful tool in this situation unfortunately. There are many explanations out there about how this algorithm works, more so than many other algorithms. I think the reason for that is because from hearing the basic high level idea of this algorithm most people are able to then go and implement it and then that makes for an interesting blog post (I could do the same after implementing, I think). What almost all of these blog posts are missing is how to make it fast, and how to implement back tracking efficiently. I had to try a lot of things to get to where I am now and I don't feel like I've fully explored the space of possible implementations despite trying a lot of different approaches. Here are some example generated maps: https://media.discordapp.net/attachments/583406212272619571/1006666232575053824/unknown.png https://media.discordapp.net/attachments/583406212272619571/... https://i.imgur.com/LK5a6jU.jpg https://i.imgur.com/LK5a6jU.jpg https://cdn.discordapp.com/attachments/583406212272619571/1001173689594822676/PF1.jpg https://cdn.discordapp.com/attachments/583406212272619571/10... https://cdn.discordapp.com/attachments/583406212272619571/997424873662070825/out.webp https://cdn.discordapp.com/attachments/583406212272619571/99... https://cdn.discordapp.com/attachments/583406212272619571/997367143245033572/unknown.png https://cdn.discordapp.com/attachments/583406212272619571/99...

Doxin 4y ago
So one solution I've used in the past to get WFC unstuck from local maxima is to keep a counter for each tile location with how many times it has gotten stuck at that location. Whenever it gets stuck it'll reset all the tiles within a radius relative to that counter. First time it gets stuck it'll reset all direct neighbors. Second time it'll reset all direct neighbors and their neighbors etc. For the tilesets I was using it'd hardly ever have to reset the same spot more than twice, which kept things relatively fast. It has the nice property of eventually guaranteeing a solution, though that may involve resetting the entire map many many times if it's a sufficiently gnarly problem.

phkahler 4y ago

Has anyone applied it to choosing fingerings for guitar? Given a preferred picking style of course.

dang 4y ago

Related: The Wavefunction Collapse Algorithm Explained - https://news.ycombinator.com/item?id=18744696 https://news.ycombinator.com/item?id=18744696 - Dec 2018 (44 comments) The Wavefunction Collapse Algorithm explained - https://news.ycombinator.com/item?id=18742295 https://news.ycombinator.com/item?id=18742295 - Dec 2018 (3 comments) Infinite procedurally-generated city with the Wave Function Collapse algorithm - https://news.ycombinator.com/item?id=18443311 https://news.ycombinator.com/item?id=18443311 - Nov 2018 (141 comments) Show HN: Wave function collapse algorithm - https://news.ycombinator.com/item?id=12612246 https://news.ycombinator.com/item?id=12612246 - Sept 2016 (122 comments)

keepquestioning 4y ago

Can ChatGPT make this algorithm?

euix 4y ago

I saw this being explained by the Caves of Qud developer recently and it was quite impressive, as someone who has been working on procedural generation the way it can be used to generate believable dungeons and maps is very neat.

atum47 4y ago

I remember when I tried to share my version of this very same algorithm, people also got mad cause of the name. https://news.ycombinator.com/item?id=31384676 https://news.ycombinator.com/item?id=31384676