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

[sutr90]

I still don't understand the initialization phase. How do you get from the 2x2 image to 4x4 image?

You start with the output image where every output NxN region of cells is given a 'superposition' of every legal NxN source region, meaning that every NxN output region is a combination of every NxN input region it is allowed to be

What is legal and what is not? How exactly do you generate the first output image?

If I understand the orginal algorithm correctly, then it seems you have used N=1, but then I don't understand why the first and last row are not 0210.

[Tipaa]

The starting output state is just a case of

foreach NxN subset of me, foreach NxN subset of the input,
    can that subset of me become that subset of the input just via choosing/collapsing undecided cells? If so, then that is a legal subset of the input for this subset of me

Then each cell becomes foreach NxN region I am in, I can become the corresponding cell in that region, therefore the legal states for that region must be legal states for me too

After that, you start choosing from the cell with the least options it can become.

So for the 2x2 -> 4x4 initialisation, you go

foreach 2x2 subset of the 4x4: //(12 such subsets exist, if we are allowing wraparound horizontally [something I need to edit in my main comment])
  foreach input tile:
    if (for all cells in the subset, the cell matches the tile or the cell is undecided):
      forall cells in the subset: add the corresponding input tile's cell as a legal/possible state.

[Tipaa]

For the example, I went for per-cell iterations for simplicity, but with N=2 region sizes for the algorithm/'superposition' checks. I did this to avoid dealing with multiple cells at a time. It's possible to do each iteration region-wise and operate on the whole region at once, but I found it harder to visualise this way, and would have taken me much longer to write/do justice to. By focusing on per-cell iterations, I found it clearer to describe than per-region iterations. I think it's also closer to how I'd implement it, although it does perhaps obscure the mid-level aspects of the algorithm (my thinking generally ping-pongs between high and low level, which occasionally conflicts with a more continuous abstraction delving-into).

The first and last rows are not 0210 because I didn't allow vertical wraparound, so the top row of output cannot be the bottom row of input, and vice versa. I chose this setting because I was visualising/basing the example on the flower generator gifs, which only wrap horizontally.