Mark Gritter (markgritter) wrote,
Mark Gritter

Wave Function Collapse for Automated Doodling

I've been playing around a little with (actually with the C++ port here: The algorithm is pretty impressive at randomly generating large bitmaps from small examples. And the animated gif's of it in action are an inspired presentation.

But... my first attempt to use it failed entirely, because I picked a very complicated bitmap which, even after simplification, caused the algorithm to engage in lengthy calculations that produced blobby output.

So I tried something simpler, with a pattern I doodle in many of my notebooks:

I was a little surprised to find that 3x3 tiles just couldn't seem to produce a successful example:

It works better with 4x4 tiles, though the success rate is still low:


2x2 works great but doesn't preserve the closed paths. What's going on here? Why is this pattern challenging for the WaveFunctionCollapse algorithm?

One thing to note is that WFC doesn't backtrack. It heuristically picks the most-constrained (lowest-entropy) tile to place next--- in other words, it's basically a greedy search. For many tile sets, greedy search is fine. But when there is a higher-order constraint like a closed loop, some choices might not work out at all. (Or, it might just be something dumb like I need to tell it that my tiles are symmetric. But I don't think so.)

Is there any good way to characterize tile sets for which greedy search always works? Mostly works?
Tags: algorithm, geek
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 1 comment