I recently started with the Wave Function Collapse Algorithm (WFC) in three-dimensional space. I made the basics work and now wanted to move on to let the algorithm automatically resolve any future contradictions / error states.
For this, I (inspired by this Oskar Stålberg's Tweet) has created a very small set of tiles that will encounter such contradictions quite often.
(Some examples of levels built in a grid (3x3x3) using this set of tiles.)
Note that this set of tiles, for example, will always run into a contradiction if the number of lower contacts is odd because each pipe that comes out must also end at the bottom. I have now implemented a basic backspace (naive ), which means that each time the algorithm encounters a contradiction, it reverts to the last decision taken cancels it and tries another. It works, however, because the possibility space for the placed modules can get huge, it can be resolved in a very slow generation by trying all possibilities before having gone back far enough to solve the modules that caused this contradiction. (Gif 1, Gif 2)
Now, I'm looking to optimize this algorithm.
I thought about using the jump back instead of the jump back with a jump distance increasing quadratically each time the same contradiction again (first time we go back by 1, then 2, then 4, 8, 16, …). But I don't know how to detect that the first contradiction has been exceeded so that I can then reset the jump distance.