The “Wavefunction Collapse” generation algorithm explained clearly (2018) | Hacker News Reader

The “Wavefunction Collapse” generation algorithm explained clearly (2018)

robertheaton.com

169 pointssigna1147 comments

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

You can use it solve sudokus as well [0]. I find the parallel quite enlightening.

[0] https://norvig.com/sudoku.html

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.

The name makes this algorithm so underwhelming, once you see what it actually is.

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.

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.

Oskar Stålberg 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

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)

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

I always thought the best way to explain wfc would be: Multidimensional Markov Chain

Brute force is always easier!

When?

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...

So one solution I've used in the past to get WFC unstuck from local maxima is to keep a counter for each tile location with how many times it has gotten stuck at that location. Whenever it gets stuck it'll reset all the tiles within a radius relative to that counter. First time it gets stuck it'll reset all direct neighbors. Second time it'll reset all direct neighbors and their neighbors etc. For the tilesets I was using it'd hardly ever have to reset the same spot more than twice, which kept things relatively fast. It has the nice property of eventually guaranteeing a solution, though that may involve resetting the entire map many many times if it's a sufficiently gnarly problem.

This is a nice solution. I came up with something similar where once it got stuck without making much progress I would just blow away a big radius and that would often help it get unstuck. I did eventually abandon this approach though. I can't remember the exact reason why but I think my back tracking system was not compatible with it. So if it got stuck after blowing away some tiles then it would be truly stuck and could not backtrack anymore.

Mine didn't even have any backtracking at all. It'd just keep blowing stuff up until it happened to stumble on a solution. Obviously that only works if your tileset allows for many solutions, if there's only a single solution to an area it'll take a long while to stumble on it.

I saw this being explained by the Caves of Qud developer recently and it was quite impressive, as someone who has been working on procedural generation the way it can be used to generate believable dungeons and maps is very neat.

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

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.

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.

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.

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.

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.

Is it then just repeated sampling of some markov space?

I remember when I tried to share my version of this very same algorithm, people also got mad cause of the name.

https://news.ycombinator.com/item?id=31384676

Has anyone applied it to choosing fingerings for guitar? Given a preferred picking style of course.

I think they should pick a new name for this algorithm.

"A rose by any other name would smell as sweet."

Can ChatGPT make this algorithm?

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.

I've modified the title to try to distance it from that obvious misunderstanding.

Same. Dumb name for an algorithm

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.

Especially since we don't even know what actual wavefunction collapse means.

Is there a leading theory about what the physical reality of wavefunction collapse is?

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

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.

> it doesn't really make sense to ask "what is really happening"

But something is happening. Really.

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.

> 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.

> 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...

> 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.

> 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?

You misread every line of my reply so I'm not going to take the time to reply to you in detail, have a nice day.

More and more I think Tegmark's mathematical universe hypothesis is probably correct. It's all just mathematics. So basically, shut up and calculate.

> 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.

Well, at least he does only have a single book about that, compared to his ~200 publications.

Reply on news.ycombinator.com