search

mxgmn / WaveFunctionCollapse

Bitmap & tilemap generation from a single example with the help of ideas from quantum mechanics
Other
23.05k stars 1.23k forks source link

Deadlock when collapsing #64

Closed 1Hyena closed 3 years ago

1Hyena commented 4 years ago

This is not directly related to this particular implementation of WFC but more of a theoretical and a general problem. Recently I started developing my own implementation of WFC that operates on an unbounded output and tolerates contradictions (algorithm does not stop at a contradiction but instead provides contradictions as part of the solution). While my algorithm is generally working as expected and I am happy with its results, there are certain edge cases where the Shannon entropy heuristic causes a valid non-controversial deadlock to happen (see gliders in Conway's Game of Life). It is not a contradiction but the output is garbage for all practical purposes because the distribution of tiles in the output does not reflect the distribution of the respective tiles in the input at all. You can imagine two lines of certain tiles extending themselves into infinity as they mutually enforce each other. A typical oscillation loop.

Please help me brainstorm for ideas how to overcome this artifact. If I don't get any better ideas then I'm going to deal with this as oscillations are typically dealt with in engineering --- by adding random noise. I would make sure that the output is randomly observed a small distance away from the area that is currently being processed according to the Shannon entropy heuristic. As a result the whole output is scattered with occasional single observations, which would act as an obstacle to the Shannon entropy heuristic. I'm in a situation where a contradiction is the lesser evil than the deadlock.

mxgmn commented 4 years ago

Could you give an example of this behavior? The choice of a pattern is still random, even with a deterministic heuristic.

1Hyena commented 4 years ago

Yes, sure. I made a bunch of screenshots. I hope this explains the situation.

This is the input: archetype

This is the expected output (you can see contradictions as empty tiles surrounded by question marks): expected

And here is how the the deadlock happens typically: deadlock-1

deadlock-2

deadlock-3

deadlock-4

deadlock-5

1Hyena commented 3 years ago

@mxgmn no explanation why closing?

mxgmn commented 3 years ago

Because I don't have anything to add to what you wrote.