Wave Function Collapse library in C, plus a command-line tool

Overview

wfc

Single-file Wave Function Collapse library in C, plus a command-line tool

  • License: MIT
  • Version: 0.01

This is an early version that supports the overlapping WFC method. The method takes an input image and generates output image which is locally similar to the input image. Here're a few examples of input/output pairs:

For a good read on WFC see this article. It's particularly useful for procedural generation of game levels.

HOW TO USE THE LIBRARY

One file in your project should include wfc.h like this:

        #define WFC_IMPLEMENTATION
        #include "wfc.h"

Other files can also include and use wfc.h but they shouldn't define WFC_IMPLEMENTATION macro.

Usage:

        struct wfc *wfc = wfc_overlapping(
            128,             // Output image width in pixels
            128,             // Output image height in pixels
            input_image,     // Input image that will be cut into tiles
            3,               // Tile width in pixels
            3,               // Tile height in pixels
            1,               // Expand input image on the right and bottom
            1,               // Add horizontal flips of all tiles
            1,               // Add vertical flips of all tiles
            1                // Add n*90deg rotations of all tiles
        );

        wfc_run(wfc, -1);    // Run Wave Function Collapse
                             // -1 means no limit on iterations
        struct wfc_image *output_image = wfc_output_image(wfc);
        wfc_destroy(wfc);
        // use output_image->data
        // wfc_img_destroy(output_image);

By default you work with struct wfc_image for inputs and outputs.

        struct wfc_image {
            unsigned char *data;
            int component_cnt;
            int width;
            int height;
         }

data is tightly packed without padding. Each pixel consists of component_cnt components (e.g., four components for rgba format). The output image will have the same number of components as the input image.

wfc_run returns 0 if it cannot find a solution. You can try again like so:

        wfc_init(wfc);
        wfc_run(wfc, -1);

Working with image files

wfc can optionally use stb_image.h and stb_write.h to provide convenience functions for working directly with image files.

You will normally place stb_image.h and stb_write.h in the same directory as wfc.h and include their implementations in one of the project files:

        #define STB_IMAGE_IMPLEMENTATION
        #define STB_IMAGE_WRITE_IMPLEMENTATION
        #include "stb_image.h"
        #include "stb_image_write.h"

Further, you will instruct wfc.h to use stb:

        #define WFC_IMPLEMENTATION
        #define WFC_USE_STB
        #include "wfc.h"

Usage:

        struct wfc_image *input_image = wfc_img_load("input.png");
        struct wfc *wfc = wfc_overlapping(
            ...
            input_image,
            ...
        );

        wfc_run(wfc, -1);    // Run Wave Function Collapse
                             // -1 means no restriction on number of iterations
        wfc_export(wfc, "output.png");
        wfc_img_destroy(input_image);
        wfc_destroy(wfc);

Extra functions enabled by the inclusion of stb:

        struct wfc_image *image = wfc_img_load("image.png")
        wfc_img_save(image, "image.png")
        wfc_export(wfc, "output.png")
        wfc_export_tiles(wfc, "directory")
        // don't forget to wfc_img_destroy(image) loaded images

COMMAND-LINE TOOL

The command-line tool uses the library and allows to generate WFC images. The tool depends on stb_image.h and stb_write.h. Place both files in the same directory as wfctool.c.

        make
        ./wfc

Run ./wfc to see available options

Basic usage:

        ./wfc -m overlapping -w 128 -h 128 input.png output.png

THANKS

Thanks for using wfc. If you find any bugs, have questions, or feedback please let me know. Also, if you'd like to share your works it's very appreciated.

samp.krystian at gmail.com

Issues
  • Contradictions

    Contradictions

    What are some techniques for avoiding contradictions? I'm trying to do a wfc on nyan cat: nyan3

    But sooner or later it always seems to exit citing that some contradiction occurred. For example:

    ./wfc -m overlapping -w 256 -h 256 -W 3 -H 3 -x 0 -e 1 -y 0 -r 0 nyan.png output5.png
    
    method:               overlapping
    seed:                 1641508864
    
    input image:          nyan.png
    input size:           44x33
    input components:     4
    tile size:            3x3
    expand input:         1
    xflip tiles:          0
    yflip tiles:          0
    rotate tiles:         0
    tile count:           566
    
    output image:         output5.png
    output size:          256x256
    cell count:           65536
    
    cells collapsed:      275
    Contradiction occurred, try again
    
    
    opened by MayorUshanka 8
  • Memory Leak

    Memory Leak

    I was running valgrind on a project that I am using this library in, and I noticed some significant memory leakage. I ended up trying the same thing with the sample program, and noticed leaking memory there as well. I'm still trying to track down the exact issue, but it looks like the memory allocated for the wfc struct is not properly freed when wfc_destroy() is called. This occurs both during contradiction and successful output creation.

    Valgrind output:

    ==19741== HEAP SUMMARY:
    ==19741==     in use at exit: 13,380 bytes in 446 blocks
    ==19741==   total heap usage: 649 allocs, 203 frees, 78,916,584 bytes allocated
    ==19741==
    ==19741== Searching for pointers to 446 not-freed blocks
    ==19741== Checked 114,832 bytes
    ==19741==
    ==19741== 600 (240 direct, 360 indirect) bytes in 10 blocks are definitely lost in loss record 2 of 7
    ==19741==    at 0x4845899: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
    ==19741==    by 0x1365C0: wfc_overlapping (in /home/user/Workspace/wfc/wfc)
    ==19741==    by 0x10A5DF: main (in /home/user/Workspace/wfc/wfc)
    ==19741==
    ==19741== 1,560 (624 direct, 936 indirect) bytes in 26 blocks are definitely lost in loss record 4 of 7
    ==19741==    at 0x4845899: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
    ==19741==    by 0x13730B: wfc_overlapping (in /home/user/Workspace/wfc/wfc)
    ==19741==    by 0x10A5DF: main (in /home/user/Workspace/wfc/wfc)
    ==19741==
    ==19741== 3,840 (1,536 direct, 2,304 indirect) bytes in 64 blocks are definitely lost in loss record 5 of 7
    ==19741==    at 0x4845899: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
    ==19741==    by 0x1370BF: wfc_overlapping (in /home/user/Workspace/wfc/wfc)
    ==19741==    by 0x10A5DF: main (in /home/user/Workspace/wfc/wfc)
    ==19741==
    ==19741== 7,380 (2,952 direct, 4,428 indirect) bytes in 123 blocks are definitely lost in loss record 7 of 7
    ==19741==    at 0x4845899: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
    ==19741==    by 0x13678C: wfc_overlapping (in /home/user/Workspace/wfc/wfc)
    ==19741==    by 0x10A5DF: main (in /home/user/Workspace/wfc/wfc)
    ==19741==
    ==19741== LEAK SUMMARY:
    ==19741==    definitely lost: 5,352 bytes in 223 blocks
    ==19741==    indirectly lost: 8,028 bytes in 223 blocks
    ==19741==      possibly lost: 0 bytes in 0 blocks
    ==19741==    still reachable: 0 bytes in 0 blocks
    ==19741==         suppressed: 0 bytes in 0 blocks
    ==19741==
    ==19741== ERROR SUMMARY: 4 errors from 4 contexts (suppressed: 0 from 0)
    opened by NullCGT 4
  • Results are too periodic

    Results are too periodic

    https://github.com/nothings/stb/blob/8e51be04dc7dcee462e1f09e410faceab52cc6d2/stb_image_write.h https://github.com/nothings/stb/blob/8e51be04dc7dcee462e1f09e410faceab52cc6d2/stb_image.h

    $ ./wfc -m overlapping -w 128 -h 128 input.png output.png
    

    input

    output

    input

    output

    opened by Nakilon 4
  • Incorrect Comment

    Incorrect Comment

    It looks like the comment about wfc_destroy: https://github.com/krychu/wfc/blob/8367df511191a30ad5aebcac132dd88c6d33306e/wfc.h#L149

    is incorrect given: https://github.com/krychu/wfc/blob/8367df511191a30ad5aebcac132dd88c6d33306e/wfc.h#L1143

    I don't know why this line was commented out, so I won't suggest a solution either way, but it seems like the comment or the code should be changed.

    Btw, thank you for this library! I have been looking for a simple, C implementation of WFC!

    opened by nsmryan 3
  • Const Function Parameters

    Const Function Parameters

    I added 'const' qualifiers for function arguments that are not modified. I did a pass through the code, but it is possible that I missed some arguments. However, I did find 17 parameters that can be 'const'.

    There appears to be no effect on performance.

    If you don't prefer to mark const parameters, feel free to reject the PR. This is my personal preference when writing C.

    opened by nsmryan 2
  • Some small improvements

    Some small improvements

    • Add missing -lm math library flag to Makefile
    • Add a "clean" target to the Makefile
    • Fix error in Readme.md (stb_write.h should be stb_image_write.h)
    • Declare internal functions static to avoid polluting global namespace
    • Allow wfc.o to be built in case someone prefers a more traditional .o file to link against

    Feel free to cherry pick any of these you like and ignore any (or all) you don't like.

    opened by smcameron 2
  • Wrong entropy calculations

    Wrong entropy calculations

    • Entropy calculations should involve probabilities, not rough frequencies. These values are passed to log which gives different sign for probabilities (<1) and frequencies (>1).
    • I don't see how equations in the original implementation relate to entropy, use Shannon formulation instead.
    • Current implementation runs into rounding issues due to the use of int instead of double.

    All in all this impacts the selection of the next cell to collapse. With the fix the frequencies of tiles in the output image should match that of the input image.

    opened by krychu 1
  • Allowed Tiles Field

    Allowed Tiles Field

    This PR turns the global static variable allowed_tiles into a field of wfc.

    I came across a problem with my Rust wrapper https://crates.io/crates/wfc-rs where my unit tests crashed occasionally. I tracked this down to the fact that the unit tests run in parallel, and one test would free allowed_tiles while another was using it. I figured that the way to resolve this is to avoid any globals whatsoever, and allowed_tiles is the only one I can find in wfc.h.

    This PR simply moves the variable and the comment into wfc. I don't know if there was a reason to leave allowed_tiles as a global, but this change seems to work to me.

    I make the associated changes in functions that use allowed_tiles as well.

    opened by nsmryan 1
  • Compiling requires -lm for some targets

    Compiling requires -lm for some targets

    On ubuntu x64 20.10:

    $ make
    cc wfctool.c -g -DWFC_TOOL -o wfc
    /usr/bin/ld: /tmp/ccsapR95.o: in function `stbi__ldr_to_hdr':
    /home/user/workspace/wfc/wfc_c/stb_image.h:1849: undefined reference to `pow'
    /usr/bin/ld: /tmp/ccsapR95.o: in function `stbi__hdr_to_ldr':
    /home/user/workspace/wfc/wfc_c/stb_image.h:1875: undefined reference to `pow'
    /usr/bin/ld: /tmp/ccsapR95.o: in function `wfc__propagate_prop':
    /home/user/workspace/wfc/wfc_c/wfc.h:995: undefined reference to `log'
    /usr/bin/ld: /home/user/workspace/wfc/wfc_c/wfc.h:998: undefined reference to `log'
    /usr/bin/ld: /tmp/ccsapR95.o: in function `wfc__init_cells':                                 
    /home/user/workspace/wfc/wfc_c/wfc.h:1082: undefined reference to `log'                      
    /usr/bin/ld: /home/user/workspace/wfc/wfc_c/wfc.h:1084: undefined reference to `log'         
    collect2: error: ld returned 1 exit status                                                   
    make: *** [Makefile:2: make] Error 1
    $
    

    whereas:

    $ make
    cc wfctool.c -g -DWFC_TOOL -o wfc -lm
    $
    
    opened by vwood 1
  • CLEANUP Label Never Reached

    CLEANUP Label Never Reached

    The wfc__create_allowed_tiles function has a CLEANUP section that is not reachable. There is a return before this label, and no goto to jump to it. Is there are missing check that should jump to this label, such as on the return of malloc?

    https://github.com/krychu/wfc/blob/38b08ab7a276ba0e4266c3b85ef7f32cc59d4bce/wfc.h#L899

    opened by nsmryan 0
  • GCC Warning- a_y and b_y are unusued

    GCC Warning- a_y and b_y are unusued

    Building this library on Manjaro Linux within the wfc-rs Rust crate warns that a_y and b_y are unused.

    Apparently some additional warnings are enabled, at least -Werror.

    https://github.com/krychu/wfc/blob/38b08ab7a276ba0e4266c3b85ef7f32cc59d4bce/wfc.h#L464

    opened by nsmryan 0
  • Ability to specify some tiles

    Ability to specify some tiles

    Thanks for this great library ! I wanted to give a try to this method and your simple library / cli tool is just perfect for a newbie like me. I have read more about WFC and found that is possible to fix some tiles in advance, and let randomness fill the rest. This is an important feature for game maps (placing walls, chest, some authored content) , and will allow to generate images with better borders, by allowing only tiles that are on the sides of the input image on the sides of the ouput image. I am refering to the part name 'fixed tiles' in this article : https://www.boristhebrave.com/2020/02/08/wave-function-collapse-tips-and-tricks/

    Thanks again for this amazing work !

    opened by cppmadguy 0
  • Add more parameters to the API

    Add more parameters to the API

    Examples include:

    • Strategy to select next cell to collapse: Entropy, First available, MRV (minimum remaining values)
    • Strategy to select tile in a cell: Input image frequency, LCV (least constraining value), uniform
    • Place to start: random, center, corner
    • Seed

    wfc_overlapping already has quite a few parameters. It'd be a good opportunity to re-think the API.

    opened by krychu 0
Owner
krychu
krychu
Superposition Wave Function Visualization for free particle

Superposition Wave Function Visualization for free particle This is a cross platform software that visualizes the Amplitude(the square root of PDF) an

Mohammad Ali 3 Feb 19, 2022
Get Next Line is a project at 42. It is a function that reads a file and allows you to read a line ending with a newline character from a file descriptor

Get Next Line is a project at 42. It is a function that reads a file and allows you to read a line ending with a newline character from a file descriptor. When you call the function again on the same file, it grabs the next line

Mhamed Ajjig 3 May 17, 2022
Icopack - A simple command line tool to create multi-frame ICO files from PNG source images

Optidash is a modern, AI-powered image optimization and processing API. We will drastically speed-up your websites and save you money on bandwidth and

Optidash AI 59 Jun 15, 2022
A small, fast codeforces command line tool for competitive programming.

chainsaw: A Codeforces Commandline Tool chainsaw is a small and faster drop-in replacement for your copy and paste while attending Codeforces contests

Jiawei Wang 40 Mar 13, 2022
Command line tool for offline shader ISA inspection.

Intel Shader Analyzer Intel Shader Analyzer is a tool for offline static analysis of shaders for Intel GPU Architectures. It allows a user to compile

null 114 Apr 21, 2022
OS X command line tool to inject Frameworks and dylibs on mach-o binaries (iOS & Mac Apps).

macho-inject OS X command line tool to inject Frameworks and dylibs on mach-o binaries. It does the injection of the framework and the codesigning. It

Jon Gabilondo 3 Feb 12, 2022
fx is a workspace tool manager. It allows you to create consistent, discoverable, language-neutral and developer friendly command line tools.

fx is a workspace tool manager. It allows you to create consistent, discoverable, language-neutral and developer friendly command line tools.

null 18 Jun 2, 2022
Comparing the performance of Wave Digital Filter implementations

WDF Bakeoff Comparing performance between Wave Digital Filters implemented in C++ and Faust. Building First clone the repository and submodules: git c

null 10 Jun 19, 2022
The HarmonicExciter is based on a half wave clipper, allow to add harmonics to the source by mix them in.

HarmonicExciter.lv2 The HarmonicExciter is based on a half wave clipper, allow to add harmonics to the source by mix them in. Dependencys libcairo2-de

Hermann 9 Jan 2, 2022
Sandbox binary and source code for the Siggraph 2017 paper "Water Wave Packets" by Stefan Jeschke (NVIDIA) and Chris Wojtan (IST Austria)

----------------------------- Manual for wave packet viewer ----------------------------- System requirements: Windows8/8.1/10 with DirectX runtime e

Stefan Jeschke 35 Feb 10, 2022
Use the spline-interpolation method to a origin sine-wave data(40 MHz) captured by 250M sampling rate

Spline-Interpolation-Project Goals When we obtain some data that is discrete data, eg: from the the Analog-to-digital converter card, we need to resto

Yi-Jan Huang (Eason) 1 Jan 20, 2022
Collection of DLL function export forwards for DLL export function proxying

dll-exports Collection of DLL function export forwards for DLL export function proxying. Typical usecase is for backdooring applications for persisten

Magnus Stubman 34 Jun 26, 2022
C-function for traversing files/directories effectively and calling a given function with each encountered file and a void-pointer as parameters

C-function for traversing files/directories effectively and calling a given function with each encountered file and a void-pointer as parameters

null 1 Jan 22, 2022
Tuibox - A single-header terminal UI (TUI) library, capable of creating mouse-driven, interactive applications on the command line.

tuibox tuibox ("toybox") is a single-header terminal UI library, capable of creating mouse-driven, interactive applications on the command line. It is

Andrew 8 May 31, 2022
Command line C++ and Python VSTi Host library with MFCC, FFT, RMS and audio extraction and .wav writing.

______ _ ___ ___ | ___ \ | | | \/ | | |_/ /___ _ __ __| | ___ _ __| . . | __ _ _ __

Leon Fedden 279 Jun 18, 2022
this project is a function in c to take the next line of a file or a file descriptor. this is a project of 42 school.

Get Next Line of 42. Make with ❤︎ for Luiz Cezario ?? Index What's this Repo? List of Archives Technologies How to Run Find a Bug? Or somenthing need

Luiz lima cezario 7 May 21, 2022
Lightweight C++ command line option parser

Release versions Note that master is generally a work in progress, and you probably want to use a tagged release version. Version 3 breaking changes I

null 3.1k Jun 22, 2022
The command line interface for Piccolo

Piccolo programming language A fun, easy to embed high-level programming language. This repo contains the code for the Piccolo CLI. The core Piccolo c

null 7 Feb 14, 2022
A simple DPDK application that calculates stats for dropped and forwarded packets depending on the command line.

The DPDK Stats Description A small DPDK application that increments a basic packet counter for TCP or UDP packets depending on what's specified in the

Christian Deacon 10 Jun 15, 2022