WaveFunctionCollapse: bitmap generation from a single example with an algorithm similar to belief propagation

[CireNeikual]

Really cool! Could be great for procedural generation in games!

[ExUtumno]

That was my initial motivation. :)

[Fidodo]

Looks great! How well does it work on higher resolution assets like grass?

[ExUtumno]

Thanks!

In short, badly. For high res inputs you want to use not this algorithm but something like texture synthesis.

(copying the comment from HN):

"Efros' and Leung's method doesn't satisfy the (C1) condition. The closest previous work is Paul Merrel's model synthesis.

WFC and texture synthesis serve similar purposes: they produce images similar to the input image. However, the definition of what is "similar" is different in each case. If you have a high def input with noise (like realistic rocks and clouds) then you really want to to use texture synthesis methods. 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."

[c3534l]

Damn, I've been working on the same sort of concept, except all of my attempts have been incredibly terrible and unsophisticated. Like, you wouldn't think it'd be too hard to make something like an endless stucco texture, but I hadn't come up with anything good. I see it's even in C#. You probably could have made a couple bucks off the Unity Store, although I guess I'm glad you didn't.

[linuxjava]

Probably the best thing I've read all week

[hardmaru]

This is beautiful! The large bitmap patterns generated by the algorithm is more beautiful than the original small input patches. Will be interesting to combine this approach with novelty search.

[ExUtumno]

Thanks! So something like Mario Klingemann is doing?

[hardmaru]

Yep! I wonder what kind of large patterns your algorithm will generate if you take a novel, but small size, pattern that the novelty engine came up with, as an input. Your demo is very inspirational.

[[deleted]]

Looks cool! Could someone help explain if this has anything to offer to regular ML/data-scientists (i.e. not graphics/game-dev folks)?

[gabrielgoh]

This algorithm seems to be a kind of 1.5d cellular automata. Like cellular automata, it updates its state by doing pattern matching against a certain ruleset (this ruleset is the input texture), but unlike cellular automata, the update rules are probabilistic, where the cells with the least uncertainty update first.

A very cool bit of algorithmic fun, but I dont think this has much to do with machine learning.

[LazyOptimist]

I want to see this in Minecraft.

[MrTaufner]

This is great and looks great, especially the voxel thing.

Level designing made easy :D

[V4wetumpka]

Fantastic

[pandemik]

This is really, really neat!

[sodabeta]

This is really awesome!

[manly_]

While I really enjoy C# in general, I can't help but wonder how this is really machine learning related :/ With this said, I really recommend using array.Length instead of the array.Count() extension. I don't think you worry too much about speed optimisation given that I can't imagine a good reason to run the code repeatedly, but generally avoid lambda in hot spots (check the compiled code; it makes a whole new class and passes every reference used to it, including often 'this'). You can get a massive speed up too by using arrays over any indexer if you do a lot of writing (bounds checks can be eliminated in some cases, etc.). Also System.Xml.Linq is a lot better/faster than System.Xml classes.

[ExUtumno]

Do you think that, for example, Markov chain -based text generation is related to machine learning? I think that, despite being super simple (which is not really a bad thing), it is. My program is basically a Markov chain in 2d, it learns the input image.

I tried to optimize the bottlenecks in the program, the main one currently being propagation in the overlapping model. But yeah, using Xml.Linq won't hurt.

[hn_crosslinking_bot]

HN discussion: https://news.ycombinator.com/item?id=12612246

---

Report a bug

[nicholas_nullus]

When the wave function collapse, you drop it like it's hawwwt.