▲ 102 points
back
18 comments
Oh also here is the original creator of the algorithm that this implementation is based on:
https://github.com/mxgmn/WaveFunctionCollapse
Even more examples up there.
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.
> 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?
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/ -- the maps generated are entirely outputs of the algorithm.
It's constraint-based programming. It's closer to an SAT or old-school AI than anything else.
I think the article title here is a little wanting... I was expecting something a little different.
For background, here is an earlier HN thread about wave function collapse.
I suggest checking out the "Features" page:
https://boristhebrave.github.io/DeBroglie/articles/features....
This is really neat. The stylization of the hexagonal tile sets reminds me of a tabletop game I played years ago called Heroscape. Is there any chance that it was inspired by that?
Not sure about the inspiration, but I believe it's these:
Been working with this implementation of WFC in Unity and it’s been a lot of fun. The game Bad North that just came out also uses this technique heavily for 3D island generation.
This is really neat. Did you create this for a game?
Author here. No. I saw some neat stuff from the author of WFC[1], and realized it combined perfectly with another proc gen algorithm I'd designed earlier[2]. Hence why this is the only implementation I've seen with non-local constraints[3]
[1]: https://github.com/mxgmn/WaveFunctionCollapse [2]: https://www.boristhebrave.com/2018/04/28/random-paths-via-ch... [3]: https://boristhebrave.github.io/DeBroglie/articles/features....
Pedantic note: wave functions do not collapse; decoherence occurs.
Not directly related, but for People interested in fundamental physics, classical mechanism is becoming very relevant for explaining particles.
«in the deterministic collapse theory of 2016 [29] the nonlocal absolute phase constants of the wavepackets were taken as hidden variables (cf. [30]). Collapse occurs when two wavepackets spatially overlap and satisfy a mathematical criterion, which demands that their phase constants very nearly coincide. The wavepackets then collapse to the overlap volume. In a measurement this mimics the action of a point particle. The phase constants are pseudorandom numbers, in the sense of the deterministic chaos theory, and the Born rules are derived under the assumption that their distribution is uniform. »
« Physicists report that quantum behavior can be explained with classical physics for a single particle, but not for multiple particles as in quantum entanglement and related nonlocality phenomena ("spooky action at a distance" ["gruselige Action in einiger Entfernung" (german)],[344] according to Albert Einstein) »And another hidden variable theory explain quantum entanglement.
Thus, classical mechanism deterministically explain ALL of quantum mechanics ! What still needs to be done is to unify those three local hidden variable theories and wouldn't that create the first theory of Everything ? A thing that quantum mechanics will never by design be able to do by being incompatible with general relativity.
Let's be clear, probabilities distributions (quantum mechanics) are a Nice map of the territory. But the map isn't the territory ans the territory IS superdeterministic like classical mechanics.
Also, I believe that local hidden variable theories are deeply underresearched because mainstream scientists have not updated their belief on them since 40 years... I guess too that many quantum scientists are afraid of dropping the Nice absurd Idea of free will...
I thought Bell's theorem ruled out local hidden variable theories? https://en.wikipedia.org/wiki/Bell%27s_theorem
From https://en.wikipedia.org/wiki/Pilot_wave_theory#Principles
> The theory brings to light nonlocality that is implicit in the non-relativistic formulation of quantum mechanics and uses it to satisfy Bell's theorem.
[Disclaimer: I don't like pilot wave theory.]
Bell theorem is kinda a circular reasoning in it's attempt to disprove classical mechanics, see https://en.m.wikipedia.org/wiki/Superdeterminism
Also all the theories I cited justify in their respective paper why the Bell theorem doesn't apply on them.
Some does it by being non local but it is not a necesssity.