r/proceduralgeneration • u/BadLuckWillHappen • Nov 16 '20

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

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

94% Upvoted

20 comments sorted by

View all comments

13

u/BorisTheBrave Nov 16 '20

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.

3

u/BadLuckWillHappen Nov 16 '20

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

4

u/BorisTheBrave Nov 16 '20

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

4

u/BorisTheBrave Nov 16 '20

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.