5
\$\begingroup\$

I just recently got started with the Wave-function-collapse Algorithm (WFC) in 3-dimensional space. I got the fundamentals working and wanted to now move on to let the algorithm automatically resolve possible upcoming contradictions/error-states.

For this, I (inspired by this Tweet from Oskar Stålberg) created a highly constricted Tileset that will run into such contradictions quite often.
(Some examples of constructed Levels in a (3x3x3)-Grid using this tileset.)

Note that this tileset will, for example, always run into a contradiction if the number of bottom contacts is odd since every pipe that comes out must also finish at the bottom.I've now implemented basic (naive) backtracking, which means whenever the algorithm runs into a contradiction, it goes back to the last decision made undoes it and tries another. This does work, however, because the possibility space for placed modules can become huge, it may resolve in a really slow generation trying out every possibility before having backtracked far enough to resolve the modules that caused this contradiction. (Gif 1, Gif 2)


Now I'm looking to optimize this algorithm.

I thought about using Backjumping instead of Backtracking with a quadratically increasing jumping distance each time it runs into the same contradiction again (first time we jump back 1, then 2, then 4, 8, 16, ...). But I'm not sure how to detect the overcoming of the first contradiction to be able to then reset the jumping distance.

I also don't get Oskar Stålberg's solution to this. In the post's comments, he speaks of cutting out Chunks to try and resolve the contradiction but how does he calculate these chunks?

\$\endgroup\$
1

3 Answers 3

7
\$\begingroup\$

I went ahead and replied to Oskar Stålberg's tweet about this technique to ask for clarification. (Try it yourself! Most game developers who post about their work on Twitter are happy to share more details & insights with their peers)

Here's what he said:

In an old implementation of WFC I used to rebuild the possibility space around a contradiction. But I don't think that solution is good in most cases. You can't know when the seeds of the contradiction were sowed. Its usually faster to reset the whole thing.

Another developer, Ebyan Alvarez-Buylla, agreed:

I have only used WFC in prototypes but yeah the lazy “just scrap everything and start over” seemed simple and performant. Similarly with Markov Chain generators, which I’m more familiar with.

So: attempting to identify the specific root cause of the contradiction, by backtracking or even just estimating its location, may be more trouble than it's worth. Bits that appear salvageable might not be, due to long chains of implications that will inevitably lead to the same or new contradictions. Even a perfect solver might spend a lot of time evaluating what to keep, and end up keeping very little for all that trouble.

These devs find it's faster to start over with a blank canvas. The first round of generation is fast to re-do anyway, and it keeps your solution simple. Or as Ripley would say,

Screenshot of Ripley in Aliens, overlaid with the quotation "I say we take off and nuke the entire site from orbit...it's the only way to be sure

Based on their expertise, I'd recommend that you only try to do a more localized backtrack/reset if you have domain-specific knowledge that you can use to bound the problem for the specific tileset you're using.

Say, if you were generating islands in the ocean, and you know contradictions can't occur in ocean tiles because the set of possible adjacencies in your tileset is complete for those cases. In such a case, when a contradiction occurs in one island, it suffices to clear only that one island: flood-filling (erasing) outward until you reach an ocean tile, and leaving the rest of the archipelago intact.

Or in the absence of a hard guarantee like this, if your tilesets tend to exhibit a behavior where "local" contradictions are common, you could apply an escalating response. The first time you encounter a contradiction (with x/n collapsed tiles), erase & reset a 3x3x3 cube around the site of the contradiction and resume. If you hit a second contradiction with (x+f)/n or fewer tiles collapsed, assume it's from the same cause and you needed to undo more: double the size of the region to erase this time. Continue this way, doubling the size of the erased region each time until you manage to get further than (x+f)/n or you've completely reset the map, then bring your eraser size back to the default for the next contradiction you encounter. This lets you solve small touch-ups without massive regeneration, but still falls back on a full wipe in only a logarithmic number of attempts when the "local" heuristic fails you.

But without these types of domain-specific guidance, solving the problem of bounding the contradiction in the most general case seems likely to fail or perform poorly.

\$\endgroup\$
4
\$\begingroup\$

I've found the same issues you have with backtracking, and restarting is often not an acceptable approach for larger generations.

I think backjumping is a fruitful avenue, but I've not seen it expored.

One process that seems to work ok is "Modifying by blocks", which is a specific form of doing WFC in chunks. Unlike more naive reparation approaches, it "locks in" chunks that actually work, which sometimes is better than just guessing where contradictions are.

More information can be found on the authors website, or the writeup on my blog:

\$\endgroup\$
3
\$\begingroup\$

The problem with "scraping everything and starting over" is that if the problem instance is big enough, you might always, or very nearly always, get into a contradiction.

One solution is to use a "block based method". That is, like the original question suggests, earmark a sub-chunk of the original space, re-allow all possible tiles at each of those locations, then run WFC as normal to try and find a solution. If no solution is found, revert to the old chunk, otherwise accept it.

enter image description here

(image above taken from github.com/merrell42/model-synthesis)

The question of what chunk size to use will dependent on the tile set and rules involved. I believe there's a "characteristic length" for any given tile set, potentially complicated by whether it's near a boundary or in the middle-bulk section, where the probability of finding a valid configuration rapidly drops beyond it. Finding the characteristic length for a given tile set it probably difficult so practically this should be done empirically.

Implicit in this algorithm is that you can start from a valid "known good" state. Many tile sets in question have an "empty" tile, so the "all empty" configuration is often a valid one to start from. This might not be a drawback but if an initial condition is needed that's constrained the grid in a certain way, normal WFC might be better suited as solving the initial state might be as much work as finding another, valid, configuration.

Merrell, the original researcher behind/inspiration for WFC, talks about this in his "Model Synthesis" thesis [0], and even has code available [1]. Boris the brave also has an article on using the block based method for a trickier "escher-esque" like tile set [2]. Below is an example from BorisTheBrave.com of an overlapping blocks method on a grass and path tile set:

enter image description here

(image above taken from boristhebrave.com)

  1. "Model Synthesis" thesis by Paul C. Merrell
  2. github.com/merell42/model-synthesis
  3. "Model Synthsis and Modifying in Blocks" at boristhebrave.com
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .