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

https://robertheaton.com/2018/12/17/wavefunction-collapse-algorithm/

by signa11 • 4 years ago

169 47 4 years ago

robertheaton.com

marcAKAmarc• 4 years ago

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

shapefrog• 4 years ago

Brute force is always easier!

ogogmad• 4 years ago

When?

magicalhippo2• 4 years ago

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• 4 years ago

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• 4 years ago

Is it then just repeated sampling of some markov space?

denton-scratch• 4 years ago

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.

Xcelerate• 4 years ago

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.

dang2• 4 years ago

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

welcome_dragon• 4 years ago

Same. Dumb name for an algorithm

captainmuon• 4 years ago

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• 4 years ago

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

criddell2• 4 years ago

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

mesofile• 4 years ago

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

danbruc• 4 years ago

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.

symmetricsaurus2• 4 years ago

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

abetusk2• 4 years ago

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

symmetricsaurus2• 4 years ago

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

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

abetusk2• 4 years ago

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.

rullelito• 4 years ago

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

BoppreH• 4 years ago

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.

LegitShady• 4 years ago

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

Koshkin2• 4 years ago

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

zzlk3• 4 years ago

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

Doxin2• 4 years ago

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.

zzlk3• 4 years ago

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.

phkahler• 4 years ago

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

dang2• 4 years ago

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)

keepquestioning• 4 years ago

Can ChatGPT make this algorithm?

euix• 4 years ago

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.

atum47• 4 years ago

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

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

Related Stories