Thesis: Markov Chain-based Wave Function Collapse algorithms

The most interesting demo of WFC I saw was the 3D demo from a few years back: https://marian42.itch.io/wfc

(discussed @ https://news.ycombinator.com/item?id=18443311 4 years ago)

Poorly named algorithm

It looks like this thesis is mostly about making the preprocessing step to create the constraints XML for WFC for a tiled instantiation (as opposed to an overlapping instantiation) automatically from a given image.

The thesis seems interesting enough and I think there's enough there to be worthy of looking for anyone interested in the subject but there are some things that jump out as being problematic or wrong.

They claim they convert hours to milliseconds because their algorithm automates the constraint file generation, with the idea that hours of labor needs to be done in order to make the XML. This is pretty disingenuous as, if a constraint file is being generated, this is most likely being done programatically. This is how I've done this in the past and I would expect other people to do the same.

For example, Quantogram [0] looks to be doing exactly what this thesis is proposing, without, I suspect, the need to hand curate any XML constraint files.

Another is the "castle" example. The output shows little blocks in isolation as a result of their WFC implementation (or constraints file generation?). This makes me pretty uneasy as that block is not in the source file image. I didn't really catch a good justification of why that singular block should be there.

Any discussion of WFC should, in my opinion, discuss the severe limitations of the method. At one point, the video presentation says that WFC can create circuit diagrams. While it can certainly create circuit like pictures from the example tilemap, WFC absolutely will fail to create a complex routed circuit if the problem is set up with correct constraints. This is because WFC is only resolving local constraints. If a problem space has a tile set that's too constrained, WFC will almost surely fail.

Understanding what "too constrained" is might be difficult and I only have the barest of intuition about it. The Quantogram link has a "Pacman" tileset that looks to have significant trouble converging [1]. I did write an article about some problems with a (tiled) implementation of WFC in case anyone is interested [2] [^]

[0] https://zaratustra.itch.io/quantogram

[1] https://zaratustra.itch.io/quantogram?width=32&height=32&ima...

[2] https://www.fxhash.xyz/article/lessons-learned-from-implemen...

[^] trigger warning, the link is to an NFT, but you shouldn't let that stop you from reading it