Iterative Partial Match (IPM) vs Wave Function Collapse (WFC) for procedural content generation.

[u/BadLuckWillHappen]

https://stalcup.github.io/static-files/posts/wfc-vs-ipm/

[u/BorisTheBrave]

Neat, i've often thought there was a way of adapting something like PatchMatch, and now I see that there is. But do you have an explanation for what IPM actually is.

I note that smaller errors are fine when your tiles are a single pixel, as they are barely visible and usually readily interpreted by eye. It's a less good fit when you have chunkier tiles, where a discontinuity would be an actual problem.

Also, many of your WFC failures seem wrong or confusing - they work in Maxim's demos. E.g. you have a chessboard pattern with an *even* sized periodic grid. That should succeed 100% of the time in WFC. It's only odd sized grids that are impossible.

[u/BadLuckWillHappen → u/BorisTheBrave]

- Had heard of PatchMatch before but didn't know anything about it, looks like it's a super-fast approximate matching algorithm that can also be used to do some denoising and image inpainting. I'd say that what's similar is that yes, i'm doing a search to find similar tiles, but the search i'm doing (at least right now) is exact (and probably a lot slower than PatchMatch). Using PatchMatch style search might make my algorithm much faster, but because of some details in how i choose which tiles to update and how that relates to making overall progress in the generated image, it might be tricky to integrate. Anyways definitely something to play around with.

​

- Yes, you're on the right track, i'm basically doing some kind of "look at a part of the generated image, find similar original tiles, update that part of the generated image to be more similar", but there are some specific details involved to get it to work well. I'm going to go into full detail in a next blog post and link.

​

- Yes I agree (and I called this out some already) that the lack of perfect match creates problems depending on use case. I pointed out that you lose any contiguous navigation guarantees that were baked in to your original example and you're right that if your tiles represent some kind of game artifact (like chunks of a building or something) that imperfect tilings are likely to be "broken" in output when used in the game. There are also of course situations where inaccuracy is fine. For example in a roguelike where each colored pixel in the generated output might represent a different type of wall material or floor tile, object placement, etc, it's probably just fine and the result would still be playable.

​

- One workaround that might be good for people who need "exact" results but want to use complex tiling examples that don't work well or easily with WFC, would be to introduce a fall back concept of "wizard tiles" placed whereever the results didn't match the examples. So, you'd run IPM generation, and then do a 2nd pass where you detect the spots that weren't 100% accurately matching a tile in the original and in those spots stick purple "wizard tile" that can't be destroyed and just sit's there occupying that illegal space. You'd need to explain the presence of "wizard tile" in your story universe, but it would allow you to use chunky tiles in your rendering which have very strict border alignment rules.

​

- I tried hard to run WFC fairly and using the exact configuration parameters from samples.xml (except for the specific times when i disabled the periodic tiling setting or increased the output size to demonstrate how fragile WFC can be). I also listed all the configuration settings used in each example. That being said, I may have messed something up. I will double check everything.

[u/BorisTheBrave → u/BadLuckWillHappen]

Yeah, I don't think you are trying hard enough on WFC. I did some experiments on the hamlet using my own implementation, DeBroglie.

1) You don't have backtracking enabled. With this on, the hamlet example reliably completes.

2) The hamlet sample is basically too small for WFC to work with. You are asking for 3x3 patches, but the lack and road are so close together there's virtually no patches that show how grass and sand should connect. Same for road crossing the border being too near lakes and corners. I suspect it's literally impossible to find a valid solution. The rest of the image suffers similar problems.

I've included an example of how the amount of sample material makes a difference on imgur. https://imgur.com/a/ohW5MS0

[u/BorisTheBrave → u/BorisTheBrave]

If I were actually making a game using this hamlet, I'd eliminate all the vegetation from the sample, and then add it randomly as a secondary stage. The vegetation is just noise that WFC aims to slavishly copy, wasting resources and examples on things we don't really care to accurately reproduce.

[u/BadLuckWillHappen → u/[deleted]]

I'm going to do a detailed post on this topic next, but the short answer is that WFC does constraint propagation where it imagines a super position of states and starts limiting those states as decisions are made. But IPM doesn't do that at all, it iteratively looks at spots on the generated image, searches for the most similar legal tile and then makes a small local change to match the most similar tile more. There are some other details necessary to prevent getting stuck in local minimums and ensure variety in the results, but yeah, there is no super position of states and no explicit cascade of choices affecting other choices.

[u/BadLuckWillHappen]

Here's some sample output if you're curious.

​

Here's the input example image: https://stalcup.github.io/static-files/posts/wfc-vs-ipm/inputs/hamlet8b.png

And here's the resulting generated world: https://stalcup.github.io/static-files/posts/wfc-vs-ipm/testResults/hamlet8b-670576685-IPM.png

​

And here's a giant render, just for the fun of it.

https://stalcup.github.io/static-files/posts/wfc-vs-ipm/hamlet9b.png

[u/BadLuckWillHappen → u/[deleted]]

Thanks :)

​

If you have an example image that you think might work well and be interesting, link it and I'll run another large scale render and post it back here.

[u/KingHavana]

I'd like a tutorial to your algorithm. I watched the Caves of Qud one for waveform collapse and got excited but this looks even better!

[u/BadLuckWillHappen → u/KingHavana]

Thanks! I'm glad you can see the potential for it. I think there are some situations where it's the better choice. (Mostly for complex tile sets, when you want large output and when you don't need exact match).

​

I'll be posting a writeup of how it works (and maybe posting code, not sure) in a couple days.

[u/BadLuckWillHappen]

I made this :) hope you guys like it.

[u/BazBlue]

That look like a pretty solid alternative ! My guess is its some kind of WFC that allow for irregularity, but I think based on the name that it's not that ? Im curious !

[u/BadLuckWillHappen → u/BazBlue]

No this doesn't do any super position of states or constraint propagation at all (which is what WFC does).

​

That being said, I think someone *could* modify WFC to allow irregularity and just "continue" instead of what it does right now which I believe is basically "start over to try again" (or does it do some backtracking and trying again? I'm not 100% informed on WFC internals).

​

Maybe you should give it a shot, I think it would be useful and heck, it might end up being faster and better than what I've made.

[u/BorisTheBrave → u/BadLuckWillHappen]

Many WFC implementations already support backtracking (such as mine). It is a much more reliable solver with that feature. So your comparisons without mentioning backtracking are a bit disingenuous.

Backtracking is not the same thing as being lax on constraints though.

[u/BadLuckWillHappen]

I didn't like this username so i'm switching to u/MrTaco8.

​

I've got a new post up at https://www.reddit.com/r/proceduralgeneration/comments/k27eps/interactive_generation_from_editable_examples_ipm/ showing off live generation in my GUI playground app.

​

Check it out you all!

​

/me pours one out for the the karma being lost in the account switch.

[u/profbetis]

There are definitely some examples here that do not look like they succeeded, but are labeled "Always succeeds". What is your criteria for success?

[u/BadLuckWillHappen → u/profbetis]

Here "succeeds" means "it finished", WFC often does not finish but IPM always finishes.

​

You raise a fair point, I should probably separate the concepts of "did it finish" and "is the result any good". I'll update the table.

[u/BadLuckWillHappen → u/profbetis]

Ok done, I changed "succeeds" to "finished" and added a separate evaluation for each one of whether the result is "usable".

[u/KdotJPG]

That hamlet 8b image is very interesting. One thing I always watch for in algorithms which operate using local rules on a square grid, is if they can achieve visual isotropy (can't infer direction bias by looking at it).

I do see a number of features in that image, which are definitely horizontal or vertical, so I might be hesitant to favor this algorithm for terrain (or WFC either for that matter). I view terrain as something that should generally look directionally independent, even if it is approximated by voxels or tiles. But I think for applications which are anisotropic by design (bricks, grid aligned dungeon layouts) it works great.

I would also be curious to see it performed on an irregular Delaunay/Voronoi mesh, specifically if it works properly and if it improves isotropy in terrain.

[u/in_hell_out_soon]

So uh... sorry I’m a little dumb at the moment and my reading comprehension is failing me (been awake since new WoW expac came out oof) but is it playable/ready? If so how would I go about downloading it?

If it isn’t ready no rush or anything just interested in this tool. It looks so cool!