Wave Function Collapse library in pure C

[mkl]

Explanations of the method:

- https://robertheaton.com/2018/12/17/wavefunction-collapse-al..., 44 comments https://news.ycombinator.com/item?id=18744696

- https://www.boristhebrave.com/2020/04/13/wave-function-colla..., 18 comments https://news.ycombinator.com/item?id=18321168

More threads: https://hn.algolia.com/?q=wave+function+collapse

[krychu]

Another explanation which I found useful: https://www.gridbugs.org/wave-function-collapse/

[Asraelite]

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

[t8y]

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/

[karimabuseer]

I thought the same - though it actually gets its name from wave function collapse in quantum physics, as each pixel has multiple potential positions it can collapse to, leading to the procedurally generated map

[JoeyBananas]

It's also not clear what this algorithm has to do with quantum physics. Maybe that's how it was discovered or it has applications to physics, but the algorithm itself doesn't require any advanced math or have anything to do with the wave function. It can be described using elementary combinatorics.

[munificent]

It's reasonable to be surprised when a computer science term uses a metaphor, but I don't think it's fair to call it a poor name unless you also object to almost every other name in programming.

Strings have nothing to do with textiles. And, very confusingly, they aren't even related to fibers or threads. Zippers aren't related to textiles either.

Trees and bloom filters are not related to botany. Heaps and garbage collection are not about municipal waste management. Graph coloring, despite the term, has nothing to do with either pictures or pigments. Red-black trees aren't colored or botanical.

Bubble sort does not involve fluid dynamics. Neither does bucket or cocktail shaker sort for that matter.

Circular buffers are not round. You can't eat a spaghetti stack or poke your finger on a cactus stack.

[stagas]

Very naive question but is it even possible to do quantum experiments with code on a regular computer? Anyone knows if it's been tried?

[ArtWomb]

This gets brought up every time its mentioned. And I think its interesting. It's only tangentially related to actual physics. But parallelizing the WFC for large inputs might be exactly the kind of problem QC assists.

[erwincoumans]

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

[Yajirobe]

eli5 int*** support;

[openasocket]

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

[max_]

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

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

[_0ffh]

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

[eutectic]

I think the statistical aspect is an important part of the algorithm; it's trying to match the statistics of the input data. I guess you can think of it as an approximate sampler for Markov Random Fields.

[thomasahle]

I tried to use this to generate Numberlink puzzles. As the input I gave a solved image from https://github.com/thomasahle/numberlink . However I never even got to the "progress screen" / "cells collapsed" count. I guess the input image has to be very small for this to work well.

I also tried generating some large images (like 1000x1000 pixels output, but small 64x64 input), but it only collapses around 100 cells/second, so this still takes about 3 hours assuming no contradictions are encountered.

Works well for small inputs and outputs though!

[veltas]

I wonder why the implementation is all in a header.

[ktpsns]

This is a typical idiom frequently seen in modern C and C++ codes. As https://github.com/krychu/wfc#how-to-use-the-library says, you need to define a macro in a C file in order to "expand" the actual code there.

Having the code in the header gives a bit more flexibility considering the file layout. IMHO this is an awkward consequence of the missing de-facto-standard in C/C++ build systems.

[klyrs]

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.

[wott]

It is an atrocious fad imported a few years ago by young programmers coming from script languages, because they don't grasp modularity à la C and adding -lthatlib in a Makefile or a build script seems out of their reach :-(

[homarp]

see also Procedural Worlds from Simple Tiles - https://news.ycombinator.com/item?id=29866062

[miika]

How about something like:

World.import(World.export(props))

Run that in an infinite loop.

Anyways this post ignited some deep contemplation