Live data from Hacker News

Wave Function Collapse library in pure C

github.com

51–60 of 87 posts

Re: Wave Function Collapse library in pure C

#51

Reminds me of the 5-star WFC code on github: https://github.com/merrell42/model-synthesis/blob/master/src... int***** support; see https://paulmerrell.org/wp-content/uploads/2021/07/compariso... Pierre Terdiman from nvidia is doing some experiments using it, for Omniverse level generation: https://twitter.com/PierreTerdiman/status/147663502794968678...

eli5 int*** support;

Whats the matter? Never used 3+ levels of indirection on a variable before? /s

Re: Wave Function Collapse library in pure C

#52
I've never heard this referred to as "Wave Function Collapse" before. Isn't this just constraint satisfaction being solved via backtracking? Like this is the standard way of solving the N-queens problem. Make a random choice, propagate the constraints, and repeat, backtracking if you reach a contradiction.

https://en.wikipedia.org/wiki/Backtracking

Re: Wave Function Collapse library in pure C

#53
post #10

I feel like the algorithm is maybe poorly named. At first I thought this was a tool to help with computational quantum physics.

Wave Function Collapse is actually the same (or essentially identical) as Model Synthesis[1]. IMO that is a better name. [1] https://paulmerrell.org/model-synthesis/

Taking a look at the comparison paper [0] provided on that site, there does seem to be a significant difference. The images generated with MS are more prone to long horizontal lines while WFC produces larger blocks of texture. This is hard to spot with more homogeneous textures like pipes, but it's more apparent with something like the grey cat faces, where WFC generates a variety of shapes and MS mostly makes very long ones. Going back up to section 2 I found the explanation: "Model synthesis sweeps through the grid in scanline order. WFC chooses the lowest entropy cell." The results from WFC look more natural and varied to me so I'd call this a significant advance.

But it does seem appropriate to say they're variations of the same algorithm. As for the name, I don't like either: Wave Function Collapse is based on a silly pop-science interpretation of quantum mechanics, and Model Synthesis is extremely generic and forgettable. And it's not even a synthesis, more of a filtering process. I guess I'd stick with Wave Function Collapse.

[0] https://paulmerrell.org/wp-content/uploads/2021/07/compariso...

Re: Wave Function Collapse library in pure C

#54
post #36
post #25

Earlier quoted context omitted.

Have you ever tried using a unity build?

Another nonsense, no I haven't ever bothered with it. A hack designed by those that cannot be bothered to modularize a build with binary libraries.

It definitely is a hack, but it's not nonsense. The speedups on large projects are significant, even on modularised ones.

Re: Wave Function Collapse library in pure C

#55
post #2

I wonder why the implementation is all in a header.

I've come across a lot of C programs that should be libraries, but they're written as an executable tool. They tend to assume that they're the only program in existence, never free their memory, use non-constant globals, stuff a whole bunch of logic into main(), etc.

By contrast, wfc is a breath of fresh air. The good stuff is in wfc.h, and the tool is in wfctool.c, which serves as an example for people who want to use the library. Consumers of the library have the option of writing a thin wrapper to produce an object file, or directly including it, if they prefer.

If this was a gargantuan library, it would make more sense to dicker about what's going into your build. But it's not a gargantuan library; it's tiny, and has the appropriate guard to prevent multiple compilations.

Re: Wave Function Collapse library in pure C

#56

I've never heard this referred to as "Wave Function Collapse" before. Isn't this just constraint satisfaction being solved via backtracking? Like this is the standard way of solving the N-queens problem. Make a random choice, propagate the constraints, and repeat, backtracking if you reach a contradiction. https://en.wikipedia.org/wiki/Backtracking

[deleted]

Re: Wave Function Collapse library in pure C

#57

I've never heard this referred to as "Wave Function Collapse" before. Isn't this just constraint satisfaction being solved via backtracking? Like this is the standard way of solving the N-queens problem. Make a random choice, propagate the constraints, and repeat, backtracking if you reach a contradiction. https://en.wikipedia.org/wiki/Backtracking

After reading [1], I'm not really sure backtracking is even an integral part of WFC, as apparently it sometimes fails to find a solution and needs to retry from start. Backtracking seems to be more of an optional add-on.

[1] https://paulmerrell.org/wp-content/uploads/2021/07/compariso...

Re: Wave Function Collapse library in pure C

#58
post #47

Earlier quoted context omitted.

> Oh well, I guess people like the fancy name. The way "quantum leap" is used by laypeople springs to mind too; literally the opposite of what they mean (not only tiny but random).

is it though? I've heard the argument, but to me it still makes sense as it is used colloquially. It is a discrete jump forward, thus if you are not talking about electrons and just the latin definition can be an arbitrary sized quanta if defined to an an appropriate set. a quantum leap between scientific epochs is quite large for example also just reread your comment. I don't agree with the definition "small and ran…

Here's my interpretation: a classical leap is when you are somewhere, you expend a bit of energy you have, and you end up somewhere else as a result. Basically, you do something and something happens.

A quantum leap, on the other hand, happens when you are somewhere just sitting, and boom, now you're somewhere else. It just happened randomly, without any energy input from you. So to bring this back to the idiom, an example of a quantum leap would be this: "I had a dream yesterday that gave me the insight I needed to finish my proof of XYZ theorem!"

Re: Wave Function Collapse library in pure C

#59
post #31

Earlier quoted context omitted.

https://en.wikipedia.org/wiki/Gleason%27s_theorem

Huh. I can't believe I missed this. Thanks.

In quantum computing the consequence of the theorem (as I understand it) is that once you have asked every yes/no question there is to ask about the state, the state has collapsed.

Re: Wave Function Collapse library in pure C

#60

I've never heard this referred to as "Wave Function Collapse" before. Isn't this just constraint satisfaction being solved via backtracking? Like this is the standard way of solving the N-queens problem. Make a random choice, propagate the constraints, and repeat, backtracking if you reach a contradiction. https://en.wikipedia.org/wiki/Backtracking

The original implementation[0] has a comprehensive description in the README file.

[0] https://github.com/mxgmn/WaveFunctionCollapse

Post reply on HN