3 ms·

I wrote a js wave function collapse implementation earlier this year and really enjoyed the process and its results. Constraint support is a feature I'm still l

by wcarss 8y ago

I wrote a js wave function collapse implementation earlier this year and really enjoyed the process and its results. Constraint support is a feature I'm still looking forward to adding in the future, so it's pretty neat to see how others have tackled similar things. This algorithm is really amazing -- it's effectively very similar to a markov chain to generate map/image data.

platz 8y ago
> The coefficients in these superpositions are real numbers, not complex numbers, so it doesn't do the actual quantum mechanics, but it was inspired by QM. I'm not sure how to think about this algorithm. Is it just applied statistics?
- wcarss 8y ago
  I've never done any applied statistics that I know of, so I'm not sure! For a 2D map the loose layout of the algorithm is this: construct a 2D array of blank tiles. Choose a tile at random from the set of most-constrained tiles (this is currently all of them as they are all equally unconstrained) and give it a value according to some distribution. Constrain its neighbors' potential values and update whatever system you use to track most-constrained-tiles for selection, then repeat until no unset tiles remain. Depending on the complexity of the distribution (# of tile types and absoluteness of neighbor relations), you may end up with a contradiction where an unset tile has no possibilities. At this point you could progressively backtrack, throw the whole set away, or fudge something, depending on what matters to you in life. You can end up with some very cool things! The problem has some neat aspects to consider in how to represent tiles, how to track constraints, how to efficiently update your selector, how to design your distributions, etc! There are a ton of avenues to explore. I make no claims on the goodness of this example or its implementation, but I wrote a small game to use/test my wfc code here: https://wcarss.ca/jabiru/ https://wcarss.ca/jabiru/ -- the maps generated are entirely outputs of the algorithm.
- c3534l 8y ago
  It's constraint-based programming. It's closer to an SAT or old-school AI than anything else.

by wcarss 8y ago

platz 8y ago

> The coefficients in these superpositions are real numbers, not complex numbers, so it doesn't do the actual quantum mechanics, but it was inspired by QM. I'm not sure how to think about this algorithm. Is it just applied statistics?

wcarss 8y ago
I've never done any applied statistics that I know of, so I'm not sure! For a 2D map the loose layout of the algorithm is this: construct a 2D array of blank tiles. Choose a tile at random from the set of most-constrained tiles (this is currently all of them as they are all equally unconstrained) and give it a value according to some distribution. Constrain its neighbors' potential values and update whatever system you use to track most-constrained-tiles for selection, then repeat until no unset tiles remain. Depending on the complexity of the distribution (# of tile types and absoluteness of neighbor relations), you may end up with a contradiction where an unset tile has no possibilities. At this point you could progressively backtrack, throw the whole set away, or fudge something, depending on what matters to you in life. You can end up with some very cool things! The problem has some neat aspects to consider in how to represent tiles, how to track constraints, how to efficiently update your selector, how to design your distributions, etc! There are a ton of avenues to explore. I make no claims on the goodness of this example or its implementation, but I wrote a small game to use/test my wfc code here: https://wcarss.ca/jabiru/ https://wcarss.ca/jabiru/ -- the maps generated are entirely outputs of the algorithm.
c3534l 8y ago
It's constraint-based programming. It's closer to an SAT or old-school AI than anything else.