7 ms·

Wave Function Collapse library in pure C

136 points by graderjs 5y ago

homarp 5y ago
see also Procedural Worlds from Simple Tiles - https://news.ycombinator.com/item?id=29866062 https://news.ycombinator.com/item?id=29866062
veltas 5y ago
I wonder why the implementation is all in a header.
- ktpsns 5y ago
  This is a typical idiom frequently seen in modern C and C++ codes. As https://github.com/krychu/wfc#how-to-use-the-library 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.
  - titzer 5y ago
    All code in the header leads to a lot of duplicated work for the compiler, which means slow build times. You should avoid this unless it is absolutely necessary for performance to inline methods.
    - krychu 5y ago
      That work will be done by the preprocessor and should be fairly quick given it doesn't compile the duplicated code and only removes it.
      - titzer 5y ago
        It may still generate code for function definitions, which are deduped by the linker, so a lot of the code can still go through the whole compiler.
        flohofwoe 5y ago
        An STB-style header with the implementation disabled (which is the default) looks exactly the same to the compiler as a regular C header which only contains public API declarations (e.g. just struct declarations and function prototypes, and most importantly, no inline code). All code that would otherwise live in .c files is between an #ifdef/#endif block which is only activated in a single compilation unit in the whole project. Not sure how this approach would lead to redundant "function definitions" which would need to be deduped by the linker. The only overhead is in the preprocessor for skipping the implementation block, but that happens pretty much at IO speed - it's not comparable with the parsing overhead in typical C++ headers with template and inline code.
        titzer 5y ago
        Sure, after brushing up on this "stb style", then I see what you mean. Still, it seems like an ugly kludge to cope with a breathtakingly antiquated way of doing things.
        sledgehammers 5y ago
        Why should it be any more complicated than that? What ever happened to keeping it simple?
        titzer 5y ago
        Things can be locally simple but have complex and chaotic implications. E.g. just by pushing the complexity up a level and dumping it on literally everyone else. I've learned over the years that complexity sometimes has a right place and a wrong place. (Most times complexity ends up everywhere, TBH.) I think resolving references between different parts of code in different compilation units is definitely within the purview of a compiler/build system, and should not be up to every programmer to flail at poorly with #ifdefs.
  - shannongreen 5y ago
    How is it more flexible exactly? I hate this idiom every time I come across it. I like to look at the header file to see the interface and important documentation, and this just obscures it. Depending on your compiler it can make debugging a huge pain as well.
    - veltas 5y ago
      It does seem that 'modern' idioms tend to just be doing the same thing in a more obfuscated manner. Just a .c/.h pair would have been easier to add to your source.
      - NavinF 5y ago
        That would be easier if the most popular build systems weren’t terrible
        pjmlp 5y ago
        Or I don't know, people actually bothered to learn them.
        wizzwizz4 5y ago
        Learning something doesn't stop it being terrible. One time I ran `cmake`, and forgot to run `sudo -k` beforehand. It reconfigured my system.
        pjmlp 5y ago
        That has more to do with sudo than cmake.
        wizzwizz4 5y ago
        This might be an unpopular opinion, but compiling a program into a local directory shouldn't try to install packages globally. `make install`, I could understand doing that. I had no idea that cmake would do this, after reading quite a lot of things about cmake v.s. make and how to write various makefiles for them. I posit that the C build tools are fundamentally hard to comprehend.
  - pantalaimon 5y ago
    You don't need an elaborate build system to add a single .c file to your project
    - chii 5y ago
      and now you need to add a .h to where ever you need to call those function. This .h will need to know if it got included multiple times, and so isn't just a trivial declaration. It's just easier to have a single .h you include.
      - charcircuit 5y ago
        >to add a .h to where ever you need to call those function No, it can be in a single place and you can just #include it. >This .h will need to know if it got included multiple times, and so isn't just a trivial declaration. This is the point of using header guards. >It's just easier to have a single .h you include. Depending on the build tool it's the same or only marginally easier (you save like 10 characters)
  - pjmlp 5y ago
    This is a sad idom followed in C and C++ libraries that cannot be bothered to learn build tools, dealing with C and C++ as if they were scripting languages.
    - floor_ 5y ago
      Have you ever tried using a unity build?
      - pjmlp 5y ago
        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.
        maccard 5y ago
        It definitely is a hack, but it's not nonsense. The speedups on large projects are significant, even on modularised ones.
        glouwbug 5y ago
        Not entirely. If you think about it, a resulting C binary is just data and text - it’s all compiled into a single unit of globals and functions, much like a unity build layout. Regarding optimization it allows for LTO without the need for a link time optimizer. Regarding convenience, it spares one from function prototypes and using Make or CMake. Should one use Make to speed up build times it’s as simple as tossing the unity code you’re not working on into a precompiled header; this primes the compiler for a quick compilation of the newly written code. As for design, I find unity builds resemble the design mind of a mechanical, civil, or electrical engineer - a single assembly (main.c) incorporates sub assemblies (*.c) like a CAD designer would design SolidWorks parts for a vehicle or spacecraft
        pjmlp 5y ago
        I rather prefer the software engineering mind to use binary libraries for what they were designed for.
- wott 5y ago
  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 :-(
- klyrs 5y ago
  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.
Asraelite 5y ago
I feel like the algorithm is maybe poorly named. At first I thought this was a tool to help with computational quantum physics.
- stagas 5y ago
  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?
  - rndphs 5y ago
    You can simulate quantum dynamics but the number of bits required is exponential with respect to the number of qubits simulated. So basically you can simulate really simple quantum systems but it becomes pretty much intractable when the system you are simulating has many parts.
  - nabla9 5y ago
    Yes. It's just an equation. The complexity of quantum system that can be simulate is limited. https://marl0ny.github.io/QM-Simulator-2D/index.html https://marl0ny.github.io/QM-Simulator-2D/index.html From the above link you can look single slit, double slit, triple slit, step, spike, or load an arbitrary image as a potential and do experiments in 2d box. >This WebGL program simulates the quantum mechanics of a single particle confined in a 2D box, where inside this box the user can create new potential barriers and scatter Gaussian wavepackets off them. The full instructions are found here. https://github.com/marl0ny/QM-Simulator-2D https://github.com/marl0ny/QM-Simulator-2D btw. Wave function collapse in quantum physics is completely speculative phenomenon. There is only apparent wave function collapse.
    - tsimionescu 5y ago
      > btw. Wave function collapse in quantum physics is completely speculative phenomenon. There is only apparent wave function collapse. To be more precise, the Born rule non-linear adjustment of the wave function to a single real value after a measurement is strictly necessary for QM to match experiments. Whether this should be interpreted as a physical phenomenon of wave function collapse, or as entanglement with the environment (MWI), or as an update of probabilities for hidden variables (Pilot wave) or some other phenomenon is speculative, but the wave function must be "collapsed" to a single real value after a measurement to correctly predict experimental results.
miika 5y ago
How about something like: World.import(World.export(props)) Run that in an infinite loop. Anyways this post ignited some deep contemplation
mkl 5y ago
Explanations of the method: - https://robertheaton.com/2018/12/17/wavefunction-collapse-algorithm/ https://robertheaton.com/2018/12/17/wavefunction-collapse-al..., 44 comments https://news.ycombinator.com/item?id=18744696 https://news.ycombinator.com/item?id=18744696 - https://www.boristhebrave.com/2020/04/13/wave-function-collapse-explained/ https://www.boristhebrave.com/2020/04/13/wave-function-colla..., 18 comments https://news.ycombinator.com/item?id=18321168 https://news.ycombinator.com/item?id=18321168 More threads: https://hn.algolia.com/?q=wave+function+collapse https://hn.algolia.com/?q=wave+function+collapse
- krychu 5y ago
  Another explanation which I found useful: https://www.gridbugs.org/wave-function-collapse/ https://www.gridbugs.org/wave-function-collapse/
erwincoumans 5y ago
Reminds me of the 5-star WFC code on github: https://github.com/merrell42/model-synthesis/blob/master/src/propagator/PropagatorAc4.h#L15 https://github.com/merrell42/model-synthesis/blob/master/src... int***** support; see https://paulmerrell.org/wp-content/uploads/2021/07/comparison.pdf 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/1476635027949686785 https://twitter.com/PierreTerdiman/status/147663502794968678...
- Yajirobe 5y ago
  eli5 int*** support;
  - ragnot 5y ago
    Whats the matter? Never used 3+ levels of indirection on a variable before? /s
    - omoikane 5y ago
      See also: https://wiki.c2.com/?ThreeStarProgrammer https://wiki.c2.com/?ThreeStarProgrammer
      - erwincoumans 5y ago
        Hah, this is actually a FiveStarProgrammer with 5 indirections, rather than https://wiki.c2.com/?FiveStarProgrammer https://wiki.c2.com/?FiveStarProgrammer
openasocket 5y ago
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 https://en.wikipedia.org/wiki/Backtracking
- deleted 5y ago
  [deleted]
- _0ffh 5y ago
  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/comparison.pdf https://paulmerrell.org/wp-content/uploads/2021/07/compariso...
- max_ 5y ago
  The original implementation[0] has a comprehensive description in the README file. [0] https://github.com/mxgmn/WaveFunctionCollapse https://github.com/mxgmn/WaveFunctionCollapse
- eutectic 5y ago
  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 5y ago
I tried to use this to generate Numberlink puzzles. As the input I gave a solved image from https://github.com/thomasahle/numberlink 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!

136 points by graderjs 5y ago

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

veltas 5y ago

I wonder why the implementation is all in a header.

ktpsns 5y ago
This is a typical idiom frequently seen in modern C and C++ codes. As https://github.com/krychu/wfc#how-to-use-the-library 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.
- titzer 5y ago
  All code in the header leads to a lot of duplicated work for the compiler, which means slow build times. You should avoid this unless it is absolutely necessary for performance to inline methods.
  - krychu 5y ago
    That work will be done by the preprocessor and should be fairly quick given it doesn't compile the duplicated code and only removes it.
    - titzer 5y ago
      It may still generate code for function definitions, which are deduped by the linker, so a lot of the code can still go through the whole compiler.
      - flohofwoe 5y ago
        An STB-style header with the implementation disabled (which is the default) looks exactly the same to the compiler as a regular C header which only contains public API declarations (e.g. just struct declarations and function prototypes, and most importantly, no inline code). All code that would otherwise live in .c files is between an #ifdef/#endif block which is only activated in a single compilation unit in the whole project. Not sure how this approach would lead to redundant "function definitions" which would need to be deduped by the linker. The only overhead is in the preprocessor for skipping the implementation block, but that happens pretty much at IO speed - it's not comparable with the parsing overhead in typical C++ headers with template and inline code.
        titzer 5y ago
        Sure, after brushing up on this "stb style", then I see what you mean. Still, it seems like an ugly kludge to cope with a breathtakingly antiquated way of doing things.
        sledgehammers 5y ago
        Why should it be any more complicated than that? What ever happened to keeping it simple?
        titzer 5y ago
        Things can be locally simple but have complex and chaotic implications. E.g. just by pushing the complexity up a level and dumping it on literally everyone else. I've learned over the years that complexity sometimes has a right place and a wrong place. (Most times complexity ends up everywhere, TBH.) I think resolving references between different parts of code in different compilation units is definitely within the purview of a compiler/build system, and should not be up to every programmer to flail at poorly with #ifdefs.
- shannongreen 5y ago
  How is it more flexible exactly? I hate this idiom every time I come across it. I like to look at the header file to see the interface and important documentation, and this just obscures it. Depending on your compiler it can make debugging a huge pain as well.
  - veltas 5y ago
    It does seem that 'modern' idioms tend to just be doing the same thing in a more obfuscated manner. Just a .c/.h pair would have been easier to add to your source.
    - NavinF 5y ago
      That would be easier if the most popular build systems weren’t terrible
      - pjmlp 5y ago
        Or I don't know, people actually bothered to learn them.
        wizzwizz4 5y ago
        Learning something doesn't stop it being terrible. One time I ran `cmake`, and forgot to run `sudo -k` beforehand. It reconfigured my system.
        pjmlp 5y ago
        That has more to do with sudo than cmake.
        wizzwizz4 5y ago
        This might be an unpopular opinion, but compiling a program into a local directory shouldn't try to install packages globally. `make install`, I could understand doing that. I had no idea that cmake would do this, after reading quite a lot of things about cmake v.s. make and how to write various makefiles for them. I posit that the C build tools are fundamentally hard to comprehend.
- pantalaimon 5y ago
  You don't need an elaborate build system to add a single .c file to your project
  - chii 5y ago
    and now you need to add a .h to where ever you need to call those function. This .h will need to know if it got included multiple times, and so isn't just a trivial declaration. It's just easier to have a single .h you include.
    - charcircuit 5y ago
      >to add a .h to where ever you need to call those function No, it can be in a single place and you can just #include it. >This .h will need to know if it got included multiple times, and so isn't just a trivial declaration. This is the point of using header guards. >It's just easier to have a single .h you include. Depending on the build tool it's the same or only marginally easier (you save like 10 characters)
- pjmlp 5y ago
  This is a sad idom followed in C and C++ libraries that cannot be bothered to learn build tools, dealing with C and C++ as if they were scripting languages.
  - floor_ 5y ago
    Have you ever tried using a unity build?
    - pjmlp 5y ago
      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.
      - maccard 5y ago
        It definitely is a hack, but it's not nonsense. The speedups on large projects are significant, even on modularised ones.
      - glouwbug 5y ago
        Not entirely. If you think about it, a resulting C binary is just data and text - it’s all compiled into a single unit of globals and functions, much like a unity build layout. Regarding optimization it allows for LTO without the need for a link time optimizer. Regarding convenience, it spares one from function prototypes and using Make or CMake. Should one use Make to speed up build times it’s as simple as tossing the unity code you’re not working on into a precompiled header; this primes the compiler for a quick compilation of the newly written code. As for design, I find unity builds resemble the design mind of a mechanical, civil, or electrical engineer - a single assembly (main.c) incorporates sub assemblies (*.c) like a CAD designer would design SolidWorks parts for a vehicle or spacecraft
        pjmlp 5y ago
        I rather prefer the software engineering mind to use binary libraries for what they were designed for.
wott 5y ago
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 :-(
klyrs 5y ago
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.

Asraelite 5y ago

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

stagas 5y ago
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?
- rndphs 5y ago
  You can simulate quantum dynamics but the number of bits required is exponential with respect to the number of qubits simulated. So basically you can simulate really simple quantum systems but it becomes pretty much intractable when the system you are simulating has many parts.
- nabla9 5y ago
  Yes. It's just an equation. The complexity of quantum system that can be simulate is limited. https://marl0ny.github.io/QM-Simulator-2D/index.html https://marl0ny.github.io/QM-Simulator-2D/index.html From the above link you can look single slit, double slit, triple slit, step, spike, or load an arbitrary image as a potential and do experiments in 2d box. >This WebGL program simulates the quantum mechanics of a single particle confined in a 2D box, where inside this box the user can create new potential barriers and scatter Gaussian wavepackets off them. The full instructions are found here. https://github.com/marl0ny/QM-Simulator-2D https://github.com/marl0ny/QM-Simulator-2D btw. Wave function collapse in quantum physics is completely speculative phenomenon. There is only apparent wave function collapse.
  - tsimionescu 5y ago
    > btw. Wave function collapse in quantum physics is completely speculative phenomenon. There is only apparent wave function collapse. To be more precise, the Born rule non-linear adjustment of the wave function to a single real value after a measurement is strictly necessary for QM to match experiments. Whether this should be interpreted as a physical phenomenon of wave function collapse, or as entanglement with the environment (MWI), or as an update of probabilities for hidden variables (Pilot wave) or some other phenomenon is speculative, but the wave function must be "collapsed" to a single real value after a measurement to correctly predict experimental results.

miika 5y ago

How about something like: World.import(World.export(props)) Run that in an infinite loop. Anyways this post ignited some deep contemplation

mkl 5y ago

Explanations of the method: - https://robertheaton.com/2018/12/17/wavefunction-collapse-algorithm/ https://robertheaton.com/2018/12/17/wavefunction-collapse-al..., 44 comments https://news.ycombinator.com/item?id=18744696 https://news.ycombinator.com/item?id=18744696 - https://www.boristhebrave.com/2020/04/13/wave-function-collapse-explained/ https://www.boristhebrave.com/2020/04/13/wave-function-colla..., 18 comments https://news.ycombinator.com/item?id=18321168 https://news.ycombinator.com/item?id=18321168 More threads: https://hn.algolia.com/?q=wave+function+collapse https://hn.algolia.com/?q=wave+function+collapse

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

erwincoumans 5y ago

Reminds me of the 5-star WFC code on github: https://github.com/merrell42/model-synthesis/blob/master/src/propagator/PropagatorAc4.h#L15 https://github.com/merrell42/model-synthesis/blob/master/src... int***** support; see https://paulmerrell.org/wp-content/uploads/2021/07/comparison.pdf 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/1476635027949686785 https://twitter.com/PierreTerdiman/status/147663502794968678...

Yajirobe 5y ago
eli5 int*** support;
- ragnot 5y ago
  Whats the matter? Never used 3+ levels of indirection on a variable before? /s
  - omoikane 5y ago
    See also: https://wiki.c2.com/?ThreeStarProgrammer https://wiki.c2.com/?ThreeStarProgrammer
    - erwincoumans 5y ago
      Hah, this is actually a FiveStarProgrammer with 5 indirections, rather than https://wiki.c2.com/?FiveStarProgrammer https://wiki.c2.com/?FiveStarProgrammer

openasocket 5y ago

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 https://en.wikipedia.org/wiki/Backtracking

deleted 5y ago
[deleted]
_0ffh 5y ago
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/comparison.pdf https://paulmerrell.org/wp-content/uploads/2021/07/compariso...
max_ 5y ago
The original implementation[0] has a comprehensive description in the README file. [0] https://github.com/mxgmn/WaveFunctionCollapse https://github.com/mxgmn/WaveFunctionCollapse
eutectic 5y ago
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 5y ago

I tried to use this to generate Numberlink puzzles. As the input I gave a solved image from https://github.com/thomasahle/numberlink 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!