5 ms·

Amazing work! I've been excited about this technique since I first saw the original demos of it (https://github.com/mxgmn/WaveFunctionCollapse https://github.co

Amazing work! I've been excited about this technique since I first saw the original demos of it (https://github.com/mxgmn/WaveFunctionCollapse https://github.com/mxgmn/WaveFunctionCollapse) - but can someone explain (at a very high level) how Wave Function Collapse works? I've read through some of the documentation on various repos - it starts with the nitty-gritty details, and I haven't been able to grasp the concepts.

justinpombrio 8y ago
Here's my high-level understanding. You're going to tile (say) the plane with a set of tiles you've chosen beforehand. (In this example, it looks like the tiles are 3d.) There are rules for which tiles can go next to each other---the edges must match. As you go, there are two regions: a region in which you've settled on which tiles to use, and a boundary region in which you haven't. In the boundary region, you keep track of a probability distribution over the tiles. This distribution is influenced by the neighboring tiles (exactly how is probably the most interesting bit of the algorithm; I don't know). The algorithm proceeds by repeatedly (i) picking a tile on the boundary that has a very skewed probability distribution, and fixing it to be the most likely tile; and (ii) updating the probability distributions of the neighboring tiles in the boundary. It's possible that you end up making poor tile placements at the beginning that gets you stuck later, so the algorithm must sometimes backtrack to undo past decisions. You want to pick a set of tiles such that the algorithm doesn't need to backtrack too often, or it will take too long. Note that the distribution is an ordinary probability distribution, not a sum of complex amplitudes like the name "Wave Function Collapse" would make you think.
- platz 8y ago
  Prev https://news.ycombinator.com/item?id=18322770 https://news.ycombinator.com/item?id=18322770
- jbattle 8y ago
  Maybe this is a dumb comparison, but it sounds like an algorithm for solving minesweeper. The big difference is there's no "right" answer, the puzzle emerges from the outplaying of probabilities.
  - c3534l 8y ago
    Basically.
- Qwertystop 8y ago
  Two additions to this: - AFAIK, the probability distribution is based on how common any particular adjacency is in the input. If the input is just rules rather than a small sample map, they'd all be equal, but if the input is an image that shows (for example) that only one in ten roads dead-end, that would carry over to generated stuff. - It can also do an "overlapping" model, where it sets one pixel at a time but considers overlapping tiles of 2x2 or 3x3 pixels. This breaks away from the grid structure, but requires a full sample image, not just a list of tiles.
  - marian42 8y ago
    In my case, the probabilites for each block are supplied manually.
- vokep 8y ago
  Oh my....perhaps this backtracking to fix past inconsistencies could allow for a game environment in which "Mandela effect" events happen naturally from time to time. Could make for an interesting game mechanic.
  - marian42 8y ago
    You're right. There is backtracking in the demo and when it happens it looks quite eerie. The world around you just decides it wants to look different and changes.
    - yoklov 8y ago
      That sounds like it could be mechanically cool. Or at least lead to a cool setting.
  - minkzilla 8y ago
    It seems like it would work very well in a horror game. Though random generation doesn’t lend itself too well to horror.
- sophistication 8y ago
  This sounds like standard procedures for sampling from a Markov random field. https://en.wikipedia.org/wiki/Markov_random_field https://en.wikipedia.org/wiki/Markov_random_field
- teddyknox 8y ago
  I wonder if machine learning could be used to model the probability distributions at a greater capacity, and thus reduce backtracking. One might also consider placing the algorithm in the context of a generative adversarial network (GAN) to adapt the tile probability modeling ML component towards a pattern that is less distinguishable from a real city.
- tobr 8y ago
  A while back I hacked together a crossword generator that works almost exactly like this, but using a wordlist to provide probabilities.
BorisTheBrave 8y ago
Have you ever written a Sudoku solver. It works like that. You start with an array where every tile is possible in every location. Then you pick a random cell and assign a tile to it. That tile implies some choices are impossible, so you set those possibilities to false. That further implies some other possibilities are false and so on. You propogate that as far as it goes, and when you are done, pick another random cell and assign a random possible tile to it. Because you are propogating information as much as possible before making the next choice, the algorithm very rarely needs to backtrack. You can run WFC without any backtracking at all and it'll still find a solution most of the time. Some animated examples I put together might illustrate things more: https://boristhebrave.github.io/DeBroglie/articles/gallery.html https://boristhebrave.github.io/DeBroglie/articles/gallery.h...
- doubleunplussed 8y ago
  As a physicist who works with quantum mechanics, I have to say, "wave function collapse", is an extremely apt name for what you're describing. Usually when quantumy things are used in names of things it's just 'cause it sounds cool, but this is spot-on.
  - madhadron 8y ago
    As an ex-physicist, I would say "Markov random field sampling" would be the right name.
  - BorisTheBrave 8y ago
    It's really not. There's no probability field (unless you count booleans as a scalar), no complex numbers, and no entanglement. It's just constraint propogation, optimized for certain conditions and given a fancy name. I guess you could call it a markov random field, but I don't think it does unbiased sampling.
    - doubleunplussed 8y ago
      There kind of is entanglement though! You 'measure' one cell, and then all the other ones 'collapse' to values consistent with the result, because they have a hidden relationship with the cell you measured. That's what happens in quantum mechanics. When you measure one thing, all the other things its entangled with collapse somewhat too - but not necessarily completely, it depends on the entanglement they had with the measured system. It's a metaphor, I'm just saying it's very apt, not that it's mathematically equivalent.

justinpombrio 8y ago

Here's my high-level understanding. You're going to tile (say) the plane with a set of tiles you've chosen beforehand. (In this example, it looks like the tiles are 3d.) There are rules for which tiles can go next to each other---the edges must match. As you go, there are two regions: a region in which you've settled on which tiles to use, and a boundary region in which you haven't. In the boundary region, you keep track of a probability distribution over the tiles. This distribution is influenced by the neighboring tiles (exactly how is probably the most interesting bit of the algorithm; I don't know). The algorithm proceeds by repeatedly (i) picking a tile on the boundary that has a very skewed probability distribution, and fixing it to be the most likely tile; and (ii) updating the probability distributions of the neighboring tiles in the boundary. It's possible that you end up making poor tile placements at the beginning that gets you stuck later, so the algorithm must sometimes backtrack to undo past decisions. You want to pick a set of tiles such that the algorithm doesn't need to backtrack too often, or it will take too long. Note that the distribution is an ordinary probability distribution, not a sum of complex amplitudes like the name "Wave Function Collapse" would make you think.

platz 8y ago
Prev https://news.ycombinator.com/item?id=18322770 https://news.ycombinator.com/item?id=18322770
jbattle 8y ago
Maybe this is a dumb comparison, but it sounds like an algorithm for solving minesweeper. The big difference is there's no "right" answer, the puzzle emerges from the outplaying of probabilities.
- c3534l 8y ago
  Basically.
Qwertystop 8y ago
Two additions to this: - AFAIK, the probability distribution is based on how common any particular adjacency is in the input. If the input is just rules rather than a small sample map, they'd all be equal, but if the input is an image that shows (for example) that only one in ten roads dead-end, that would carry over to generated stuff. - It can also do an "overlapping" model, where it sets one pixel at a time but considers overlapping tiles of 2x2 or 3x3 pixels. This breaks away from the grid structure, but requires a full sample image, not just a list of tiles.
- marian42 8y ago
  In my case, the probabilites for each block are supplied manually.
vokep 8y ago
Oh my....perhaps this backtracking to fix past inconsistencies could allow for a game environment in which "Mandela effect" events happen naturally from time to time. Could make for an interesting game mechanic.
- marian42 8y ago
  You're right. There is backtracking in the demo and when it happens it looks quite eerie. The world around you just decides it wants to look different and changes.
  - yoklov 8y ago
    That sounds like it could be mechanically cool. Or at least lead to a cool setting.
- minkzilla 8y ago
  It seems like it would work very well in a horror game. Though random generation doesn’t lend itself too well to horror.
sophistication 8y ago
This sounds like standard procedures for sampling from a Markov random field. https://en.wikipedia.org/wiki/Markov_random_field https://en.wikipedia.org/wiki/Markov_random_field
teddyknox 8y ago
I wonder if machine learning could be used to model the probability distributions at a greater capacity, and thus reduce backtracking. One might also consider placing the algorithm in the context of a generative adversarial network (GAN) to adapt the tile probability modeling ML component towards a pattern that is less distinguishable from a real city.
tobr 8y ago
A while back I hacked together a crossword generator that works almost exactly like this, but using a wordlist to provide probabilities.

BorisTheBrave 8y ago

Have you ever written a Sudoku solver. It works like that. You start with an array where every tile is possible in every location. Then you pick a random cell and assign a tile to it. That tile implies some choices are impossible, so you set those possibilities to false. That further implies some other possibilities are false and so on. You propogate that as far as it goes, and when you are done, pick another random cell and assign a random possible tile to it. Because you are propogating information as much as possible before making the next choice, the algorithm very rarely needs to backtrack. You can run WFC without any backtracking at all and it'll still find a solution most of the time. Some animated examples I put together might illustrate things more: https://boristhebrave.github.io/DeBroglie/articles/gallery.html https://boristhebrave.github.io/DeBroglie/articles/gallery.h...

doubleunplussed 8y ago
As a physicist who works with quantum mechanics, I have to say, "wave function collapse", is an extremely apt name for what you're describing. Usually when quantumy things are used in names of things it's just 'cause it sounds cool, but this is spot-on.
- madhadron 8y ago
  As an ex-physicist, I would say "Markov random field sampling" would be the right name.
- BorisTheBrave 8y ago
  It's really not. There's no probability field (unless you count booleans as a scalar), no complex numbers, and no entanglement. It's just constraint propogation, optimized for certain conditions and given a fancy name. I guess you could call it a markov random field, but I don't think it does unbiased sampling.
  - doubleunplussed 8y ago
    There kind of is entanglement though! You 'measure' one cell, and then all the other ones 'collapse' to values consistent with the result, because they have a hidden relationship with the cell you measured. That's what happens in quantum mechanics. When you measure one thing, all the other things its entangled with collapse somewhat too - but not necessarily completely, it depends on the entanglement they had with the measured system. It's a metaphor, I'm just saying it's very apt, not that it's mathematically equivalent.