krychu / wfc Goto Github PK

View Code? Open in Web Editor NEW

339.0 9.0 20.0 178 KB

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

Makefile 0.65% C 99.35%

wfc c procedural-generation procgen wave-function-collapse library command-line-tool

wfc's People

Contributors

Stargazers

Watchers

wfc's Issues

stb_write.h is stb_image_write.h

The file mentioned, stb_write.h, seems to not exist. I tried downloading stb_image_write.h instead, which compiled.

Sample not working

Hi, I would love to try this library, but I get a Contradiction occurred message on the sample project.

I dug into the cause, but I couldn't figure it out by myself.

Thanks,

Incorrect Comment

It looks like the comment about wfc_destroy:

wfc/wfc.h

Line 149 in 8367df5

void wfc_destroy(struct wfc *wfc); // Also destroys the image

is incorrect given:

wfc/wfc.h

Line 1143 in 8367df5

//wfc_img_destroy(wfc->image);

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!

We have been running some fuzzers on this program as part of a school project and we found quite a few segmentation faults, in the attachment we added the outputs of these fuzzers aswell as instances of wfc that are compiled with the fuzzers. Most crashes seem to be related to memcpy()

Example ASan output:

=================================================================
==1652==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000031 at pc 0x55555557a947 bp 0x7fffffffde70 sp 0x7fffffffd618
READ of size 8 at 0x602000000031 thread T0
    #0 0x55555557a946 in memcpy (/home/softsec/wfc-honggfuzz-asan/wfc+0x26946)
    #1 0x5555556b483e in wfc_overlapping (/home/softsec/wfc-honggfuzz-asan/wfc+0x16083e)
    #2 0x555555564b07 in main (/home/softsec/wfc-honggfuzz-asan/wfc+0x10b07)
    #3 0x7ffff7ca2d8f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #4 0x7ffff7ca2e3f in __libc_start_main_impl ../csu/libc-start.c:392
    #5 0x5555555650c4 in _start (/home/softsec/wfc-honggfuzz-asan/wfc+0x110c4)

0x602000000031 is located 0 bytes to the right of 1-byte region [0x602000000030,0x602000000031)
allocated by thread T0 here:
    #0 0x5555555f4e17 in __interceptor_malloc (/home/softsec/wfc-honggfuzz-asan/wfc+0xa0e17)
    #1 0x55555568af77 in stbi__load_main (/home/softsec/wfc-honggfuzz-asan/wfc+0x136f77)
    #2 0x5555556adf7b in wfc_img_load (/home/softsec/wfc-honggfuzz-asan/wfc+0x159f7b)
    #3 0x5555555649b7 in main (/home/softsec/wfc-honggfuzz-asan/wfc+0x109b7)
    #4 0x7ffff7ca2d8f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58

SUMMARY: AddressSanitizer: heap-buffer-overflow (/home/softsec/wfc-honggfuzz-asan/wfc+0x26946) in memcpy
Shadow bytes around the buggy address:
  0x0c047fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c047fff8000: fa fa fd fd fa fa[01]fa fa fa fa fa fa fa fa fa
  0x0c047fff8010: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==1652==ABORTING

Uploading Attachments.zip…

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
$

Using as a plugin: bugs and gotchas

Hi.

I've managed to turn this into a (Lua) plugin for Solar2D, and it seems to be working well.

There were a few things I ran across.

This line was causing it to crash: https://github.com/ggcrunchy/solar2d-plugins/blob/master/wfc/shared/wfc.h#L816

So far as I can tell, the cell count is unnecessary in the allocation. (It was giving something like 750 MB totals for a 256x256 output and failing on that.)

I forgot to mark the change, but did a naive exit on the max count: https://github.com/ggcrunchy/solar2d-plugins/blob/master/wfc/shared/wfc.h#L909 Do you have anything fancier in mind?

The gotos here were causing Xcode to complain about scopes: https://github.com/ggcrunchy/solar2d-plugins/blob/master/wfc/shared/wfc.h#L1209 (I tried that before Visual Studio, but suspect the same issue would arise.)

So I just moved the variables up.

I used an alternate RNG that wouldn't stomp on rand(): https://github.com/ggcrunchy/solar2d-plugins/blob/master/wfc/shared/wfc.h#L1044

To avoid an intermediate copy I allowed an image to be passed in to output_image: https://github.com/ggcrunchy/solar2d-plugins/blob/master/wfc/shared/wfc.h#L606. (I supply the space from somewhere else.)

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?

wfc/wfc.h

Line 899 in 38b08ab

CLEANUP:

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.

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.

Contradictions

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

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

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.

wfc/wfc.h

Line 464 in 38b08ab

int a_y = a_offy + y;

Remove dependency on float.h

float.h is used only for DBL_MAX, it should be possible to remove that dependency.

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)

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

Use custom rand()

This is an issue to find the best replacement for stdlib rand(). It'll be great to enjoy all the benefits but care needs to be taken to ensure good quality of the implementation as it directly impact the quality of generated images.

Rationale:

Better performance: speed and quality
Stability across platforms / different stdlibs
Don't alter rand() sequence in case the user app relies on it

Reference material

/cc @ggcrunchy, @ggsg-francis

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 !

wfc.h as an include

I've noticed that if I have wfc.h's implementation in one file, and want to use as a header in another, there are a number of functions without prototypes.

For example, I modified the header to declare some prototypes:

int wfc_export(struct wfc *wfc, const char *filename);
void wfc_destroy(struct wfc *wfc);
struct wfc_image *wfc_output_image(struct wfc *wfc);
void wfc_img_destroy(struct wfc_image *image);

I might be able to come up with a PR for this if you would accept it. I would include wrapping in WFC_USE_STB for functions not present without that flag.

What is the meaning of "expand ... on the bottom and right"

It's not clear what this argument does, or what its use is. Can someone provide an explanation?

krychu / wfc Goto Github PK

wfc's People

Contributors

Stargazers

Watchers

Forkers

wfc's Issues

Recommend Projects

Recommend Topics

Recommend Org