12 ms·

The Wavefunction Collapse Algorithm Explained

304 points by janvdberg 8y ago

rosstex 8y ago
This seems similar to Constraint Satisfaction Problems. https://inst.eecs.berkeley.edu/~cs188/fa18/assets/notes/n2.pdf https://inst.eecs.berkeley.edu/~cs188/fa18/assets/notes/n2.p...
- elliot07 8y ago
  Constraint solving in the wild.
- kaveh_h 8y ago
  Yes, but in this case the algorithm would need to figure out the constraints from preexisting examples and so would you not need to program complex constraints rules with probabilities by hand?
elliot07 8y ago
Great explanation. Think it went over the basics a _bit_ too much. Would’ve liked to see a bit more in depth. Great write up nonetheless.
tlarkworthy 8y ago
I started an online interactive port of the original in Observable https://beta.observablehq.com/@tomlarkworthy/wave-function-collapse https://beta.observablehq.com/@tomlarkworthy/wave-function-c...
spacehome 8y ago
Am I being a pedant if I think this algorithm has been misnamed for the purposes of PR? It just looks like constraint satisfaction. What's quantum about this? There's no constructive/destructive interference, which to my mind is the crucial distinction between quantum and classical systems.
- petters 8y ago
  It is almost comical. But it seems to be working, since it got a lot of attention. I should call my latest paper about finding integer solutions to LP relaxations something with quantum. I agree that the crucial property of quantum systems is interference, specifically "negative probabilities". Just having a dead/alive ambiguity does not make "wavefunction collapse" a reasonable name.
  - dkersten 8y ago
    Not only that, but “wavefunction collapse” makes it sound a lot more complex and makes it more daunting to understand. A simple description of the simple tiled model algorithm in the article is basically “pick a candidate at random and prune remaining lists to remove now-invalid candidates” or something similar. Building the rules is simply “list all of the pairs in the example and store how frequently they occur. The frequency count prioritises more common pairs and pairs not encountered in the example can’t occur in the output”. No “quantum” or “wavefunction” or anything here. A list of candidate items isn’t a wavefunciton. When I first saw this technique, I was interested in replicating it. So I started reading about wavefunction collapse on wikipedia. It had a bunch of complex quantum math and I gave up thiniking the technique was beyond me. But now I see it was also completely irrelevant. Thanks to the bad name, I gave up on it (until now, at least, when I see that its a lot simpler).
    - mujina 8y ago
      Yes, it should really just be called "Random Field Collapse" or even just "Random Field Generation". The simple case is a naive way to sample a Markov field in 2 dimensions, estimating transition probabilities from global overall adjacency frequencies.
    - Cybiote 8y ago
      The name is not so bad as you two think. The act of measurement of a quantum state can be thought of as a filtering procedure after which a normalization operation is applied. This is the same protocol that occurs when conditioning on an observation in regular probability. If you take away normalization and stop propagating weights, that same operation corresponds to applied constraints or guards, which trigger backtracking operations, in logic programs for example. This algorithm is actually an instance of constraint propagation: https://en.wikipedia.org/wiki/Local_consistency https://en.wikipedia.org/wiki/Local_consistency and constraint satisfaction algorithms generally, that find use in say, computing graph homomorphisms.
HoppyHaus 8y ago
For how simple WFC seems to be portrayed, the only reference I can find is for use in other code. Is there any simple, but still code, examples of this? Or is it always quite a bit of work to get going?
- BorisTheBrave 8y ago
  You might want to try my project DeBroglie (https://boristhebrave.github.io/DeBroglie/ https://boristhebrave.github.io/DeBroglie/). It comes with a console application that runs WFC based on JSON config files, so you can experiment with generation without writing any code.
- Riverheart 8y ago
  He includes a link to a simple implementation on his Github. https://github.com/robert/wavefunction-collapse https://github.com/robert/wavefunction-collapse
- supergarfield 8y ago
  I wrote an post with a short and (hopefully) understandable implementation a while ago: https://terbium.io/2018/11/wave-function-collapse/ https://terbium.io/2018/11/wave-function-collapse/. There's a Jupyter notebook you can download at the bottom of the page.
buboard 8y ago
is this even an efficient way to calculate possible arrangements of collapsed quantum systems?
- whatshisface 8y ago
  The algorithm is not related to quantum mechanics, although is is very cool. Technically, before "collapse" what is there is a probably distribution function, not a wavefunction.
ewngzen 8y ago
I have no idea what this article is explaining
madhadron 8y ago
As I commented on the other thread on this article going right now, this is better known as sampling from Markov random fields. There is a sizeable literature dating back to the 1960's under that name.
erikpukinskis 8y ago
Somewhat off topic, but one of my absolute favorite YouTube videos is this https://youtu.be/p7bzE1E5PMY https://youtu.be/p7bzE1E5PMY one by Udiprod that shows visualizations of wave function collapse, with bite sized, iterative explanation of all the concepts involved.
- teacpde 8y ago
  Wow amazing simulation, that channel is also full of gold.
KirinDave 8y ago
I read this months ago, and the impression I was left with is that this technique is simply a fancily-named variant of any normal tree-based search algorithm. You have constraints which can be represented on your search, and then you attempt to navigate the hyperspace finding a configuration which matches. I really can't see how this isn't "wavefunction collapse" and is rather just, "search." But I feel like I must be missing something. If this isn't right, can someone explain to me why it's not right?
klyrs 8y ago
Neat. I wrote an algorithm very much like this... I mean, sure, it's just a greedy search over a contraint-satisfaction problem... but I love the name and I'm gonna use it.
KennyCason 8y ago
Very nice and clear write up. Looks like I know what I’m going to be programming today. I particularly liked your example of how to sample existing tiles to generate rules. I’ve been wanting to work on a 2d game world generated off similar constraint algorithms. But also allow some tiles with high entropy states to be able to occasionally “flip” and propagate around, thus changing the world dynamically as you’re walking around. And I shall name it Wave Function Collapse since it’s clearly not controversial.
meta_AU 8y ago
The algorithm for the first example reads just like an implementation of a SAT solver. Set a variable, propogate clauses, backtrack on conflict (learn new 'rule' from conflict).

304 points by janvdberg 8y ago

This seems similar to Constraint Satisfaction Problems. https://inst.eecs.berkeley.edu/~cs188/fa18/assets/notes/n2.pdf https://inst.eecs.berkeley.edu/~cs188/fa18/assets/notes/n2.p...

elliot07 8y ago
Constraint solving in the wild.
kaveh_h 8y ago
Yes, but in this case the algorithm would need to figure out the constraints from preexisting examples and so would you not need to program complex constraints rules with probabilities by hand?

elliot07 8y ago

Great explanation. Think it went over the basics a _bit_ too much. Would’ve liked to see a bit more in depth. Great write up nonetheless.

tlarkworthy 8y ago

I started an online interactive port of the original in Observable https://beta.observablehq.com/@tomlarkworthy/wave-function-collapse https://beta.observablehq.com/@tomlarkworthy/wave-function-c...

spacehome 8y ago

Am I being a pedant if I think this algorithm has been misnamed for the purposes of PR? It just looks like constraint satisfaction. What's quantum about this? There's no constructive/destructive interference, which to my mind is the crucial distinction between quantum and classical systems.

petters 8y ago
It is almost comical. But it seems to be working, since it got a lot of attention. I should call my latest paper about finding integer solutions to LP relaxations something with quantum. I agree that the crucial property of quantum systems is interference, specifically "negative probabilities". Just having a dead/alive ambiguity does not make "wavefunction collapse" a reasonable name.
- dkersten 8y ago
  Not only that, but “wavefunction collapse” makes it sound a lot more complex and makes it more daunting to understand. A simple description of the simple tiled model algorithm in the article is basically “pick a candidate at random and prune remaining lists to remove now-invalid candidates” or something similar. Building the rules is simply “list all of the pairs in the example and store how frequently they occur. The frequency count prioritises more common pairs and pairs not encountered in the example can’t occur in the output”. No “quantum” or “wavefunction” or anything here. A list of candidate items isn’t a wavefunciton. When I first saw this technique, I was interested in replicating it. So I started reading about wavefunction collapse on wikipedia. It had a bunch of complex quantum math and I gave up thiniking the technique was beyond me. But now I see it was also completely irrelevant. Thanks to the bad name, I gave up on it (until now, at least, when I see that its a lot simpler).
  - mujina 8y ago
    Yes, it should really just be called "Random Field Collapse" or even just "Random Field Generation". The simple case is a naive way to sample a Markov field in 2 dimensions, estimating transition probabilities from global overall adjacency frequencies.
  - Cybiote 8y ago
    The name is not so bad as you two think. The act of measurement of a quantum state can be thought of as a filtering procedure after which a normalization operation is applied. This is the same protocol that occurs when conditioning on an observation in regular probability. If you take away normalization and stop propagating weights, that same operation corresponds to applied constraints or guards, which trigger backtracking operations, in logic programs for example. This algorithm is actually an instance of constraint propagation: https://en.wikipedia.org/wiki/Local_consistency https://en.wikipedia.org/wiki/Local_consistency and constraint satisfaction algorithms generally, that find use in say, computing graph homomorphisms.

HoppyHaus 8y ago

For how simple WFC seems to be portrayed, the only reference I can find is for use in other code. Is there any simple, but still code, examples of this? Or is it always quite a bit of work to get going?

BorisTheBrave 8y ago
You might want to try my project DeBroglie (https://boristhebrave.github.io/DeBroglie/ https://boristhebrave.github.io/DeBroglie/). It comes with a console application that runs WFC based on JSON config files, so you can experiment with generation without writing any code.
Riverheart 8y ago
He includes a link to a simple implementation on his Github. https://github.com/robert/wavefunction-collapse https://github.com/robert/wavefunction-collapse
supergarfield 8y ago
I wrote an post with a short and (hopefully) understandable implementation a while ago: https://terbium.io/2018/11/wave-function-collapse/ https://terbium.io/2018/11/wave-function-collapse/. There's a Jupyter notebook you can download at the bottom of the page.

buboard 8y ago

is this even an efficient way to calculate possible arrangements of collapsed quantum systems?

whatshisface 8y ago
The algorithm is not related to quantum mechanics, although is is very cool. Technically, before "collapse" what is there is a probably distribution function, not a wavefunction.

ewngzen 8y ago

I have no idea what this article is explaining

madhadron 8y ago

As I commented on the other thread on this article going right now, this is better known as sampling from Markov random fields. There is a sizeable literature dating back to the 1960's under that name.

erikpukinskis 8y ago

Somewhat off topic, but one of my absolute favorite YouTube videos is this https://youtu.be/p7bzE1E5PMY https://youtu.be/p7bzE1E5PMY one by Udiprod that shows visualizations of wave function collapse, with bite sized, iterative explanation of all the concepts involved.

teacpde 8y ago
Wow amazing simulation, that channel is also full of gold.

KirinDave 8y ago

I read this months ago, and the impression I was left with is that this technique is simply a fancily-named variant of any normal tree-based search algorithm. You have constraints which can be represented on your search, and then you attempt to navigate the hyperspace finding a configuration which matches. I really can't see how this isn't "wavefunction collapse" and is rather just, "search." But I feel like I must be missing something. If this isn't right, can someone explain to me why it's not right?

klyrs 8y ago

Neat. I wrote an algorithm very much like this... I mean, sure, it's just a greedy search over a contraint-satisfaction problem... but I love the name and I'm gonna use it.

KennyCason 8y ago

Very nice and clear write up. Looks like I know what I’m going to be programming today. I particularly liked your example of how to sample existing tiles to generate rules. I’ve been wanting to work on a 2d game world generated off similar constraint algorithms. But also allow some tiles with high entropy states to be able to occasionally “flip” and propagate around, thus changing the world dynamically as you’re walking around. And I shall name it Wave Function Collapse since it’s clearly not controversial.

meta_AU 8y ago

The algorithm for the first example reads just like an implementation of a SAT solver. Set a variable, propogate clauses, backtrack on conflict (learn new 'rule' from conflict).