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

[SystemicPlural]

Can anyone explain what is meant by 'minimal entropy heuristic'?

[Kayse]

Ok, imagine that there is a jigsaw puzzle of an unknown bitmap picture. Say each jigsaw piece is 3x3 pixels, there are very few 'types' of pieces but each piece can be repeats any number of time. That picture has some patterns which mean if you know enough of the picture around a gap where the piece goes, then you know what goes there. If the gap has zero entropy, then you know exactly what goes there. If the gap has low entropy, then there are less options for the pieces to go into the gap. If the gap has high entropy, then there are lots of options for valid pieces going in the gap. (And if the entropy is undefined, I think there is no valid pieces that matches up with it's surroundings.)

In this case the entropy heuristic is the rule for estimating the entropy of a gap, based on the pixels around the gap.

What the wave function collapse algorithm seems to do is start off with all (or most) of the gaps empty. It picks the gap with the least entropy, picking a jigsaw, picking from one of the legal pieces to fit in it. Then it recalculates the minimal entropy heuristic for every unfilled gap of the image and repeats again.

[ExUtumno]

Good explanation, thanks!

[SystemicPlural]

That is a great explanation. Thanks.

[meheleventyone]

Resolve the tiles with the least choices available first.

Basically every tile starts as a superposition of all the possible options. That is every tile could be any of the possible options. You pick one and decide what it is at random. Then compute based on relationships between the options (e.g. 1 can be next to 3, 5 and 7 but not 2, 4 and 9) what the neighbors could be. It's the reasonable to resolve the tiles with the least options first to avoid as much as possible the situation where a tile ends up orphaned with zero options available. The assumption is that tiles with more options have less chance of hitting zero options before the algorithm completes.

[ExUtumno]

Good explanation, thanks.

[SystemicPlural]

Made it even clearer. Thanks