Using as a plugin: bugs and gotchas

[ggcrunchy]

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

[krychu]

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?

This is a good catch. I did some optimisations in the past that don't add duplicate propagations which puts a hard limit on how many propagations can be queued. Theoretically there shouldn't be more than cell_cnt * 4 propagations. So I'd propose to go with:

struct wfc__prop *props = (struct wfc__prop *)malloc(sizeof(*props) * cell_cnt * 4);

Instead of 720mb this should give you ~3mb. In practice a situation where all possible propagations are queued is extremely unlikely, but better to stay on the safe side, especially that the memory required is acceptable (I hope) :)

wdyt?

[krychu]

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 think this is a legitimate complain. We might be jumping to CLEANUP before the variables were defined. Moving them up is a good solution. I'd only suggest that we initialize base_tile_cnt to 0.

[krychu]

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

looks good

[krychu]

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

The user should now ideally call wfc_srand right? Shouldn't we call wfc_srand(time(NULL), time(NULL)) here: https://github.com/ggcrunchy/solar2d-plugins/blob/master/wfc/shared/wfc.h#L1128? It would not impact rand() and would give us a more randomized initial state?

[krychu]

Thanks for creating the plugin. I'll be happy to link to it from the main doc.

@ggcrunchy would you be so kind to create PR with your changes? I'd be great to have you recorded in the history of contributors :) Otherwise I can do it of course.

[ggcrunchy]

"Instead of 720mb this should give you ~3mb." That definitely sounds better! 😄

"The user should now ideally call wfc_srand right? Shouldn't we call wfc_srand(time(NULL), time(NULL)) here:" Yes, that should be fine. I was allowing a user-provided seed, but in hindsight that probably wasn't very useful; I didn't do anything with it myself. I also haven't done any promotion or documented anything yet (I'm TERRIBLE about this 😃), so nobody should miss it.

This is my current test; I'll probably migrate it over to this docs / samples repo sooner or later. (The plugin may be found here, although without many details.)

I'll see if I can put together a PR in a couple days.

[krychu]

Thanks, no rush! but would be nice if the PR came from you.

I was allowing a user-provided seed, but in hindsight that probably wasn't very useful; I didn't do anything with it myself.

We might drop wfc_srand for now then. Perhaps we can add a seed later as an argument to wfc_run, perhaps it fits there better, have to think about this one. Generally it might be nice to provide a specific seed that always results in the same image.

I also haven't done any promotion or documented anything yet (I'm TERRIBLE about this 😃), so nobody should miss it.

:)

Have you done something with wfc so far? Seems like you're building a game?

[ggcrunchy]

I saw in the discussion of the PR that it was also dealing with random numbers, so I could omit that bit in case you or @ggsg-francis want to deal with it.

For the record, I also only chose the algorithm I did (Marsaglia with carry) because I had it on hand. I'm fine with any choice.

"Have you done something with wfc so far? Seems like you're building a game?" Every now and then I work on a game, but seem to do a lot more on tooling. I have a couple friends making editors, so it might find its way there. 🙂

Digression:

I actually began writing or wrapping a lot of libraries after discovering colored corners + graphcut textures. (A different approach to texture synthesis. Very eye-opening at the time!) Sean Barrett makes reference to them in his paper on Herringbone tiles, but I forget if I learned about stb this way, or the tiling and textures from it. 😄

Anyhow, I was trying to implement those techniques, but it was far too intensive to do with just stock Lua, so sent me down a lot of rabbit holes.

Random question! In the test I linked I used another thread and just fetched the image at the end. Would it be at all feasible to also have an incremental API? (One function to step, say, and maybe another to get the in-progress image, assuming the intermediate state wasn't usable by the existing image APIs.) It's pretty impressive watching a texture or whatever take shape, like this. Also shows that the process isn't stuck, if long-running. Not a necessity by any means, though.

[krychu]

I've created an issue to work on the selection of a new rand() implementation: https://github.com/krychu/wfc/issues/27. I'm already doing some tests and will be posting more info there. I'm quite excited about it. In early tests I already see nice performance improvements with equally good results.

Every now and then I work on a game, but seem to do a lot more on tooling. I have a couple friends making editors, so it might find its way there.

It'd be extremely nice to have it in an editor. In any case glad it might be useful, and always very curious to see it in action. So if you have anything to share / show at any point, please reach out :)

I actually began writing or wrapping a lot of libraries after discovering colored corners + graphcut textures. (A different approach to texture synthesis. Very eye-opening at the time!) Sean Barrett makes reference to them in his paper on Herringbone tiles, but I forget if I learned about stb this way, or the tiling and textures from it. 😄

Anyhow, I was trying to implement those techniques, but it was far too intensive to do with just stock Lua, so sent me down a lot of rabbit holes.

I haven't come across these techniques, Herringbone Wang Tiles looks interesting. How do you compare its complexity to say wfc implementation-wise? Have you come across any other "amazing" techniques that are useful for generating maps?

Random question! In the test I linked I used another thread and just fetched the image at the end. Would it be at all feasible to also have an incremental API? (One function to step, say, and maybe another to get the in-progress image, assuming the intermediate state wasn't usable by the existing image APIs.) It's pretty impressive watching a texture or whatever take shape, like this. Also shows that the process isn't stuck, if long-running. Not a necessity by any means, though.

Yes possible, and it crossed my mind in the past. The API I thought about would require you to provide a callback and a number of iterations. The callback would be then called after say every 30 iterations with the current image. You can display the image, or perhaps assemble an animated gif and save it at the end.

I can also see how this could be useful in an editor. Instead of waiting for 2-3 mins with no feedback, you could progressively show how the image is being generated.

[ggcrunchy]

I watched (and enjoyed) the GDC video. I've also wondered, like he does toward the end, about the strange RNG / noise dichotomy—and have done the "increment, hash" thing.

I was never attempting to write or use the Herringbone stuff directly, so can't really say. (Library that goes with that article is here, though.) Colored corners itself wasn't too bad: I had (ancient) code to use here. Coming up with the color fit is more involved; Sean covers some of that in part 2 of his second article, and says "the boundaries between each pair of colors may be generated through a stitching algorithm or human effort".

The "graphcuts" are one of the former. Basically, you take some blob of pixels and overlay it on one of those colored regions. You then convert this region to intensities. (I believe what you actually use is the difference in intensities, between the original and new pixels.) Every node (pixel) is connected to its neighbors; there are also two special nodes (source and sink) that are connected to every one of these. You then run a maximum flow algorithm that will also supply the minimum cut: splitting the pixel region into "use the new pixels" and "keep the old ones", with the least jarring border. And you can iterate on it a bit.

There are probably a ton of other techniques if I stopped to think about them. 😄 I actually happen to be skimming this gTangles paper lately, though with no real goal in mind. Earlier in the year I'd also been looking at hextiling; that actually was shortly after I'd first played with wfc, and I was considering that it might be a way to eke further use out of the result. (The actual hextiling code is really meant for a shader, so I rather lamely got scared off because I didn't want to implement textureGrad(), although I suspect even a naive implementation would get passable results.)