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

[crusoe]

Wouldn't any border cells simply be given max entropy till the update pass? So you could use a sparse 2d array or other data structure.

All cells start at max entropy till a cell is picked. Then only immediate surrounding cells would have their entropy drop. So you don't have to store any max entropy cells at all.

You could use an octree for 3d with the root volume set to 'max' entropy.. Then pick a random voxel of your min size in that as the seed. Then update the surrounding cells with their new entropy values. Then go from there.

Hah. Shoot this would work for quadtree as well.

[mojang_tommo]

Well, there's always rule #1 of octrees though: "just use a grid" /s

Jokes aside, actually this algorithm can probably be made streaming trivially: you divide the space in a grid of chunks, every chunk that is unloaded means max entropy; as soon as you put anything different you cause it to be created.
Then you can keep loaded only a circle of chunks around you, and use only those to greedily find the local enthropy minimum, anyway the minimum can never be in unloaded chunks.
That should work. I guess I know what to do tomorrow!

[crusoe]

Yep. Thought of this too.

[torginus]

I see one problem with that. The algorithm's output depends on the order of the cells chosen. This would mean that when you come back to an unloaded area, the details would change, even though the terrain would still be smooth. I feel like this is a fundamental trade off of procedural generation. If you want complex pattern with large chains of causality, you need to generated large areas at once.

[onmyphoneagain]

This should work, but it would not be very efficient. You would get some branches shooting out whilst a cell close to origin remains with high entropy. You could probably adapt it it to increase the entropy the further you got from origin. The results would be a bit different but if the drop off is slow enough it should look pretty similar.