4 ms·
As others have mentioned, this is "just" constraint propagation. I think much of the success is that it's a simple idea to grasp and implement, that provides ve
by abetusk 4y ago
As others have mentioned, this is "just" constraint propagation. I think much of the success is that it's a simple idea to grasp and implement, that provides very good results, and has a compelling name. I don't want to be dismissive, I think it's very cool.
The original author of "wave function collapse" also has "convchain" [0] which is similarly "just" using Monte Carlo Markov Chains to sample the space. It's also a kind of "staple" algorithm for physicists, theoretical computer scientists, etc but I guess hasn't caught on as much as WFC.
Note that WFC has major problems when the tile set is too constrained. There's a SO question about it [1] and I also happen to have written a small article about it as well [2]().
[0] https://github.com/mxgmn/ConvChain https://github.com/mxgmn/ConvChain
[1] https://stackoverflow.com/questions/72721299/why-can-the-wave-function-collapse-algorithm-fail https://stackoverflow.com/questions/72721299/why-can-the-wav...
[2] https://www.fxhash.xyz/article/lessons-learned-from-implementing-%22wave-function-collapse%22 https://www.fxhash.xyz/article/lessons-learned-from-implemen...
() trigger warning, it's an NFT but please don't let that stop you from reading
- symmetricsaurus 4y agoYou can use it solve sudokus as well [0]. I find the parallel quite enlightening. [0] https://norvig.com/sudoku.html https://norvig.com/sudoku.html
- abetusk 4y agoAh, well, this is of course doing constraint propagation but is doing full backtracking search to find solutions. WFC, as usually presented in the procgen community (that I've seen) is a "one-shot" algorithm without any backtracking. This is not to say that people don't do this or make compromises like running it multiple times, if it fails, but Norvig's solution is doing proper search.
- rullelito 4y agoThe name makes this algorithm so underwhelming, once you see what it actually is.
- BoppreH 4y agoIt might be just constraint propagation, but my Sudoku solver didn't have weights, the concept of close and far neighbors, an entropy calculation, or rules derived from examples. For those reasons I still liked the article.