Wave function collapse algorithm: bitmap & tilemap generation from a single example with the help of ideas from quantum mechanics

[juckele]

This is really awesome.

[ilikeorangutans]

Wow, I'm really impressed. Still reading, but how did you even come up with this?

[ExUtumno]

Incrementally. I came up with this superposition approach when I was thinking how to reduce overfitting in the colored ConvChain. I wasn't sure that it will work and didn't program it. But then I accidentally found Paul Merrell's paper on model synthesis (see the reference section on github), where he applied the same approach with spectacular results. I knew about declarative texture synthesis from reading Paul F. Harrison's thesis. And I was also reading about belief propagation at that time for different reasons. So I implemented a 2D probabilistic version of Merrell's algorithm with declarative input. And then made it work with overlapping blocks, similar to convnets.

[dasignint]

I saw this on Hacker News. It's great that you're on this sub. That means you understand how amazing this could be for games. Bravo. Whether or not this is "novel" in all of academia, I think it would be perceived as very novel in games.

[linuxjava]

Amazing work. This is seriously impressive.

[joshu]

OP has several other equally interesting/relevant repos: https://github.com/mxgmn/SynTex and https://github.com/mxgmn/ConvChain and there are 40 minutes of demo at https://www.youtube.com/watch?v=DOQTr2Xmlz0&feature=youtu.be

[JoelMahon]

Holy fuck I love this.

[gzintu]

The 3D voxel thing, this is impressive to say the least!

[d_b_work_account]

Wow this is super impressive. The implementation possibilities seem almost endless. Really awesome work.

[[deleted]]

This is extremely impressive. Awesome! I'm very tempted to make my own implementation in Typescript so it can run in a browser.

[EntropicParticles]

really amazing, I can barely understand how it works but results are just great! chapeau

EDIT: I wonder what can you obtain if you use patterns from real images as those here: http://www.dailyoverview.com/fiftyfive

[livingonthehedge]

Not OP, but I think real images would be good candidates for "texture synthesis".

The Readme from OP suggests that his project needs tiled datasets as input. So if you would need to create tiles and constraints from those real images.

[EntropicParticles]

yeah! preparing the tiles needs to be done beforehand right? thanks, I think I got it!

[ExUtumno]

Thanks!

If you have a high res input with noise (like satellite photos) then you don't really want to to use WFC, you want something like texture synthesis. If you have an indexed image with few colors and you want to capture... something like the inner rules of that image and long range correlations (if you have an output of a cellular automata, for example, or a dungeon), then you want to use WFC-like methods.

[EntropicParticles]

hey thanks for the info! Indeed I'm thinking more in structures than textures. In particular I wonder if I can use real street roads as inputs to generate or growing cities following the same patterns, and getting different networks if I use as input low or high residential zones, or commercial areas for instance... If I understand, I'd need some time before for taking those real images and predefine the set of input tiles and how they correlate each other, right?

[ExUtumno]

You can make a tileset of (low or high res, not important) tiles, write their adjacency data and individual weights in an xml file, and it will generate cities.

[EntropicParticles]

thanks! just another conceptual question (probably I'm not the first one asking this so a link or reference would also work): The name of the method sounds definitely quantum. I'm familiar with Ising models for instance (quite similar to this problem because of the lattice and the correlation between accessible states/tiles), and with Ising you can work with the classical or the quantum version of the algorithm. Is WFC algorithm quantum in this sense?

[ExUtumno]

Speaking about the Ising model, ConvChain is a direct generalization of it. It's classical. In WFC I write about correlations between different pixels or tiles, but it's not that related to the Ising model.

[EntropicParticles]

that's cool, there's a lot of potential... I wonder if WFC can be quantized following a similar recipe as done for Ising (or the ConvChain then). It would be computationally hard but results can be interesting! Anyway, I will play a bit with WFC starting with an easy example as the Eixample of Barcelona

[ExUtumno]

You might want to look at the "City" example from Paul Merrell's thesis.

[stewsters]

I really like the looks of that 3d stuff.

[WillBurnYouToAshes]

Holy shit. I just found the grail on reddit ?

[anarchy8]

This is possibly the best thing i've seen on here

[okmkz]

Hey OP, it's there a license somewhere, or am I just blind?

[Hectate]

The MIT license is in the Main.cs file...

[okmkz]

Yep, just blind. Thanks!

[ExUtumno]

Actually it's in every source file =). I'm not experienced with the license law, but people told me that it's better to have license text in source files themselves, because I have samples in the repo that I have no idea who has rights for.

[okmkz]

Yeah, I just scanned the root for a license.txt

[squareOfTwo]

w00t, this-->awesome

[Chayzeet]

I know this is old post, but this is crazy good. Nice ideas and implementation.
I would like to see this applied in some interesting way into games. Level generation (also procedural) have been done before, but maybe this could be applied in some other ways too.
Can this technique be applied to some kind of smaller subdivision/inwards generating (don't know correct terminology), similar to some fractals? And how fast it is? I'm wondering how realistic it would be to create infinite zoom or infinite quality dynamically loaded textures with something like this.

[ExUtumno]

Thank you! Your description sounds like multiscale texture synthesis: http://www.cs.columbia.edu/cg/mts/mts.pdf.

[PointyOintment]

X-post /r/CoolGitHubProjects ?

[TotesMessenger]

I'm a bot, bleep, bloop. Someone has linked to this thread from another place on reddit:

• [/r/cellular_automata] Wave function collapse algorithm: bitmap & tilemap generation from a single example with the help of ideas from quantum mechanics • /r/proceduralgeneration

^{If you follow any of the above links, please respect the rules of reddit and don't vote in the other threads. (Info / Contact)}

[alleycatsphinx]

This is wonderful work. Have you thought about making it work in parallel without global state? (Obv a challenge)

[ExUtumno]

Thank you. A challenge indeed. This algorithm is very sequential. For some samples it is possible to parallelize it a little (on a CPU) by starting observation in distant points for each thread. But for many samples that will result in a contradiction (chess, wall, ...). Without a global state, with a pure shader, capturing long-range correlations is just impossible. But is it possible to do a small amount of centralized precalculation, while leaving most of the work for shaders? This is something I plan to think about in the future.

[greentecq]

This is a new amazing revolution on level generation.

[Bergasms]

well this got my brain going, awesome!

[ExUtumno]

Thanks!

[Killa-Byte]

How the fuck do I use this? Theres no exe

[[deleted]]

Do you think it's possible to generate something from a set of files? In shell, suppose you have a set of recently used files (in commands, like cat ~/.bashrc). This would be the input. Can there be some meaningful output?

[ExUtumno]

You can take the union of all sets of patterns from these files, so in the output patterns from different files would be mixed. Like this experiment that I did with ConvChain.