[HN Gopher] The "Wavefunction Collapse" generation algorithm exp...
___________________________________________________________________
The "Wavefunction Collapse" generation algorithm explained clearly
(2018)
Author : signa11
Score : 134 points
Date : 2022-12-20 11:54 UTC (11 hours ago)
(HTM) web link (robertheaton.com)
(TXT) w3m dump (robertheaton.com)
| zzlk wrote:
| 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/...
| https://i.imgur.com/LK5a6jU.jpg
| https://cdn.discordapp.com/attachments/583406212272619571/10...
| https://cdn.discordapp.com/attachments/583406212272619571/99...
| https://cdn.discordapp.com/attachments/583406212272619571/99...
| phkahler wrote:
| Has anyone applied it to choosing fingerings for guitar? Given a
| preferred picking style of course.
| magicalhippo wrote:
| 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
| rhdunn wrote:
| 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 wrote:
| Is it then just repeated sampling of some markov space?
| denton-scratch wrote:
| 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.
| nightowl_games wrote:
| 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.
| abraxas wrote:
| 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.
| zzlk wrote:
| _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.
| danbruc wrote:
| 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.
| dang wrote:
| Related:
|
| _The Wavefunction Collapse Algorithm Explained_ -
| https://news.ycombinator.com/item?id=18744696 - Dec 2018 (44
| comments)
|
| _The Wavefunction Collapse Algorithm explained_ -
| 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 - Nov 2018 (141
| comments)
|
| _Show HN: Wave function collapse algorithm_ -
| https://news.ycombinator.com/item?id=12612246 - Sept 2016 (122
| comments)
| symmetricsaurus wrote:
| Oskar Stalberg 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
| abetusk wrote:
| 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
|
| [1] https://stackoverflow.com/questions/72721299/why-can-the-
| wav...
|
| [2] 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
| rullelito wrote:
| The name makes this algorithm so underwhelming, once you see
| what it actually is.
| symmetricsaurus wrote:
| You can use it solve sudokus as well [0]. I find the parallel
| quite enlightening.
|
| [0] https://norvig.com/sudoku.html
| abetusk wrote:
| 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.
| BoppreH wrote:
| It might be just constraint propagation, but my Sudoku solver
| didn't have weights, the concept of close and far neighbors, an
| entropy calculation, or rules derived from examples.
|
| For those reasons I still liked the article.
| Xcelerate wrote:
| 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 wrote:
| I've modified the title to try to distance it from that obvious
| misunderstanding.
| welcome_dragon wrote:
| Same. Dumb name for an algorithm
| LegitShady wrote:
| I think they should pick a new name for this algorithm.
| Koshkin wrote:
| "A rose by any other name would smell as sweet."
| marcAKAmarc wrote:
| I always thought the best way to explain wfc would be:
| Multidimensional Markov Chain
| shapefrog wrote:
| Brute force is always easier!
| ogogmad wrote:
| When?
| captainmuon wrote:
| 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 wrote:
| Especially since we don't even know what actual wavefunction
| collapse means.
| criddell wrote:
| Is there a leading theory about what the physical reality of
| wavefunction collapse is?
| magicalhippo wrote:
| I'm just a layman, but once I learned about experiments
| like delayed-choice quantum eraser[1] any physical wave
| function collapse stopped making sense to me.
|
| As a calculation tool, like the algorithm in this thread,
| sure, but not as something that really happens.
|
| [1]: https://en.wikipedia.org/wiki/Delayed-
| choice_quantum_eraser
| ablatt89 wrote:
| I think many "top" physicists (those with high citation
| counts in theory), generally believe in 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.
| Koshkin wrote:
| > _it doesn 't really make sense to ask "what is really
| happening"_
|
| But something _is_ happening. Really.
| ablatt89 wrote:
| Something is happening, it's described by quantum
| mechanics. What is "really happening" is a moot question,
| because you're assuming that QM is in invalid description
| because it doesn't satisfy how you want the world to
| work.
|
| Sorry, physics doesn't care that you find some
| descriptions of the world troubling. Some might find the
| magnetic field troubling since the divergence of the
| magnetic field is zero. Some might find the fact that
| mass and energy are equivalent as troubling.
| tines wrote:
| > you're assuming that QM is in invalid description
| because it doesn't satisfy how you want the world to
| work.
|
| That's an uncharitable interpretation. People have an
| objection to speculations like many-worlds because they
| aren't corroborated by observation, and by nature can't
| be (iiuc), and are therefore unscientific (though not
| necessarily untrue). Well-established physicists like
| Sabine Hossenfelder hold this position and it's not as
| clear-cut as "the facts don't care about your feelings"
| like some make it out to be.
| ablatt89 wrote:
| > That's an uncharitable interpretation. People have an
| objection to speculations like many-worlds because they
| aren't corroborated by observation, and by nature can't
| be (iiuc), and are therefore unscientific (though not
| necessarily untrue). Well-established physicists like
| Sabine Hossenfelder hold this position and it's not as
| clear-cut as "the facts don't care about your feelings"
| like some make it out to be.
|
| The disagreement with MWI and the general disdain for QM
| are separate issues. MWI is an interpretation that
| doesn't necessarily invalidate the framework, but
| attempts to extend it. However there's also been a
| general disdain for QM from various folk who attempt to
| completely replace it.
|
| Whether Sabine Hossenfelder likes a theory or not is not
| really an argument, given you're arguing from authority.
| As an example of her clickbaity title where she doesn't
| really seem to respect QM:
|
| https://backreaction.blogspot.com/2019/05/quantum-
| mechanics-...
|
| I think it's well known in the theory community QM can be
| updated for a more complete framework (carefully
| obviously), but the idea that QM is "completely wrong"
| because it's incomplete or introduces some complexities
| she doesn't like, is completely laughable. It's akin to
| saying classical mechanics is "completely wrong" because
| it doesn't predict quantum behavior (despite many anti-QM
| people claiming QM is wrong because they want to impose
| their classical understanding onto the quantum world) and
| then ignoring modern engineering, which uses classical
| mechanics to describe buildings, cars, machines, etc...
| tines wrote:
| > The disagreement with MWI and the general disdain for
| QM are separate issues.
|
| Fair point, I guess I didn't sense any disdain from the
| conversation so I didn't intend to comment on that.
|
| > there's also been a general disdain for QM from various
| folk who attempt to completely replace it.
|
| Too bad, it's as proven as any other theory out there. I
| wasn't responding to this as I didn't see any in the
| conversation, maybe I missed it.
|
| I was responding to the criticism that someone received
| for pointing out that what quantum mechanics describes
| (things being in a superposition of states) doesn't match
| what we observe (things being in one state at a time).
|
| > Whether Sabine Hossenfelder likes a theory or not is
| not really an argument
|
| Whether actual scientists hold a view is not an argument
| (nor did I try to use it as one), but it is relevant to
| pointless random online arguments because it can help us
| spend our time better and not waste it on debunking
| things that nobody who knows what they're talking about
| actually believes, as I was trying to help you do. You
| yourself said
|
| > I think many "top" physicists (those with high citation
| counts in theory), generally believe in consistent
| histories
|
| so your criticism applies to both of us or neither.
|
| > the idea that QM is "completely wrong"
|
| Who are you quoting here? The article you linked doesn't
| say that QM is "completely wrong" (just that it's not as
| good as QFT), and neither does anyone in the HN
| discussion, so I'm not sure what text you're referring
| to.
|
| > because it's incomplete or introduces some complexities
| she doesn't like
|
| Actually Hossenfelder is a well-known critic of the idea
| that simplicity and beauty are requirements of truth, and
| your remarks aren't supported by the text of the article,
| so I'm not sure what you're getting at here either.
| ablatt89 wrote:
| > Whether actual scientists hold a view is not an
| argument (nor did I try to use it as one), but it is
| relevant to pointless random online arguments because it
| can help us spend our time better and not waste it on
| debunking things that nobody who knows what they're
| talking about actually believes, as I was trying to help
| you do. You yourself said
|
| I don't agree here, argument from authority is not an
| appropriate argument. If you do not have particulars for
| an argument, then you shouldn't really have a strong
| opinion on the topic.
|
| > Who are you quoting here? The article you linked
| doesn't say that QM is "completely wrong" (just that it's
| not as good as QFT), and neither does anyone in the HN
| discussion, so I'm not sure what text you're referring
| to.
|
| ? The article I linked has a headline that's clearly
| misleading, and not only that, QFT is BASED on QM. You
| start with some Lagrangian and fields, impose QM
| restrictions via commutation relations, and perform
| calculations. What exactly do you think QFT is?
|
| > Actually Hossenfelder is a well-known critic of the
| idea that simplicity and beauty are requirements of
| truth, and your remarks aren't supported by the text of
| the article, so I'm not sure what you're getting at here
| either.
|
| What exactly are you trying to argue here? You started
| off dismissing my comments, and now you're defending
| Sabine for "beauty" and "truth". Beauty and truth
| relative to her, Sabine? Okay?
| criddell wrote:
| More and more I think Tegmark's mathematical universe
| hypothesis is probably correct. It's all just
| mathematics. So basically, shut up and calculate.
| kgwgk wrote:
| > It's all just mathematics. So basically, shut up and
| calculate.
|
| Does Tegmark shut up and calculate or extensively discuss
| the metaphysical meaning and reality of his "mathematical
| universe hypothesis" - whatever it is? I suspect the
| latter.
| mesofile wrote:
| 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-s... [1] https://news.ycombinator.com/item?id=31799818
___________________________________________________________________
(page generated 2022-12-20 23:01 UTC)