Hacker News Reader

Comment by mrspeaker | Hacker News Reader

I've struggled with implementing my own version of this algorithm - so I know I don't understand it properly. I get lost because of the "quantum mechanics" aspect - I am kind of suspecting it's just an analogy for the actual algorithm (maybe it's not?)... but I'd love to see if this could be re-written without the "entropy" and "superposition"-type wording, just to see if I can finally make it click in my brain!

View on HN

It's been discussed numerous times that this is simply a constraint satisfaction problem with hand-wavey BS applied over the top.

Here's a good (free) explanation: https://www.boristhebrave.com/2020/04/13/wave-function-colla...

Specifically read the 'Least Entropy' section: It's broken down very simply:

Pick a random tile which is the 'least random', because (due to already having resolved the constraints we can), this is most likely to be a cell that won't cause problems (ie. unsatisfiable constraints) later.

You might also like to read this (also) free paper on implementing WFC using a constraint solving library: https://canvas.ucsc.edu/files/109152/download?download_frd=1, which I quote here:

> The heuristic of selecting the most constrained variable or equivalently the variable with minimum remaining values (MRV) is well known in constraint solving.

> Since there is more than one valid pattern for that location—or it would already have been set to zero entropy in the previous loop—one of those patterns needs to be chosen. One of the patterns is chosen with a random sample, weighted by the frequency that pattern appears in the input image.

> This implements Gumin’s secondary goal for local similarity: that patterns appear with a similar distribution in the output as are found in the input [12].

I agree that the quantum mechanics terms are often more confusing than helpful here. To the point that I wrote a journal article to try to demystify how the algorithm works [1].

If you're familiar with constraint solving, "superposition" is just "the remaining possible choices in the domain" and "entropy" is just describing how to select the next node.

[1]https://ieeexplore.ieee.org/abstract/document/9421370

Do you get a commission from this?

No way to read online for free?

Here's an open access link: https://escholarship.org/uc/item/3rm1w0mn

Academics don't make any money from sales of paywalled journal articles. If you click a link to a journal article and hit a paywall, it's usually because whoever shared the link has institutional access to the journal and forgot that the paywall was there (since it effectively isn't for them.)

I wondered why you would link to magazines a while ago, as they're often behind a paywall and the author doesn't get a cut as I understand. Maybe it's for the citations? Do authors mind sharing the article for free next to the publication link?

Check out sci-hub.

I looked at the WFC recently ("Level generation and style enhancement - deep learning for game development overview", https://arxiv.org/abs/2107.07397).

Yes, it is a big inspiration, and there are numerous beautiful examples of its results. However, the QM wording is at best an extremely loose analogy (one that a hacker would use). If you want to compare it to other methods, see "WaveFunctionCollapse is constraint solving in the wild" https://dl.acm.org/doi/10.1145/3102071.3110566.

"WaveFunctionCollapse is constraint solving in the wild."

Reply on news.ycombinator.com