Why I'm Using Wave Function Collapse for Procedural Terrain | Unity Devlog

Minesweeper is a game where humans practice collapsing waveforms.

Just for the record, a physicist would just call this monte carlo sampling rather than wavefunction collapse. We use similar algorithms all the time for solving lattice models in statistical mechanics for example (see the Ising and six vertex models for examples). There are ways to make this kind of process much faster if you have some kind of scaling behaviour as well. That class of algorithms is referred to as renormalization group methods by physicists, where you start with lower resolution sampling and then gradually increase the resolution. An example of that is that if you want to generate terrain with 100 different height levels for example and heights of adjacent tiles would be within 1 height level of each other, then you can simulate 10x10 blocks first and sample them randomly with the constraint that their average height has to be within 10 height levels of each other. This is a hundred times cheaper to do. Once that is done you fill in the inner squares using that information, but since the average heights per block are already constrained, in each block each square has only 10 possible values to pick from instead of 100, and long range constraints have already been taken care of by the earlier lower res pass. Of course, not every system can be handled in that way, but many can. And you can also decide to have different rules at each resolution scale if you want to model richer behaviour. For example, for procedural terrain generation you can use the lower res for picking biomes, and then do increasing resolution to get transitions between biomes, and then increase resolution to do the actual terrain.

Immediately I notice that the algorithm can be applied to a partially filled grid, which makes me think that one really cool application of this would be to combine it with manual placement. The idea is that a level designer could place tiles of interest to shape the "general feel" of an area, and then run the algorithm on that initial state to fill in the rest. This could also be done in chunks - suppose the designer is able to select a region of cells in the grid to apply WFC to, some of which can be partially filled to start with. This feels promising enough that I might try to make a tool for it in my engine of choice sometime in the next month or so. I could see this being SO useful for speeding up the creation of areas which feel at the same time both hand-crafted and "naturally generated".

4:40 thats actually a part of procedural generation that I love; I really like spending ages finding a way to have my artistic vision generated programatically, rather than setting it in stone myself. I think I enjoy the difficulties of trying to figure out how to define my imagination

I can really see major utility in combining this with my existing procedurally generated island system to help me navigate designing and placing village prefabs in a natural way. Thanks a lot for sharing

Funnily enough, the WFC algorithm for procedural generation actually is based on the wave function collapse in quantum mechanics. Like the whole thing is basically setting each cell to a superposition of all states, then collapsing nearby cells by adjusting their probability distributions by adjusting the possible eigenstates. So it goes from a mixed system to a classical one.

This is right up my alley! Looking forward to your next release

This is an awesome video!! I love Oskar’s posts. Can’t wait for your next video :)

This algorithm feels like a huge advancement in procedurally generated maps! Thank you for sharing it Of course it won’t be right for every situation, but it has so many possibilities. For a first person game, I wonder if it would make sense to combine Wave Function Collapse with the 3D noise underlying marching cubes? Something like at the start, you’d restrict which tiles are placable at each location based on the noise value there. I’ll have to play around with this!

Awesome video! This is an excellent explanation of wave function collapse. Thoroughly enjoyed watching it and am looking forward to your next video. Keep it up! :)

Awesome video! Excited to see what’s coming!

I'm a new programmer and I've always wondered about how world generation was implemented in games. This video is AMAZING and answered every question of mine. The production quality, too- just wonderful. Thank you.

Actually, as far as I can tell, the wave function collapse generation method is the same as quantum mechanical wave function collapse, except we randomly generate measurements (determining the boxes type) to reduce the domain (literally the same terminology, use tensor product space if feeling fancy) until we are left with one possible wavefunction (generated mesh). If we want to get fancy, we can describe it as a) wavefunction in the tensor product space of all the tiles' possibilities (so all the number 5's in each tile being almost independent of each other. If one wants more jargon, then 5 in each tile would be the Schmidt rank of the partial trace which eliminates everything except that tile) b) an operator which takes any possibility which is incompatible with our constraints to 0, while letting all other possibilities alone. This is the information propagation stage in the code. So eigenvalues are 0 and 1, and we demand that our wavefunction be a 1-eignevalue of the operator, so we apply it repeatedly in discrete steps c) the random hit generator which pins down the tile is just a simple projective measurement I see no reason why one couldn't possibly generate more complex structures from this, except that any property which is non-local (not entirely dependent on direct neighbours) like connectivity in a maze, the propagation step gets very complicated very quickly.

Really liked how you showed all the progress you made and explained everything, keep it up!

I wrote a caves/maze map generator thing with basically this idea, without ever having heard of it before, so watcing this video kind of surprised me. I think thats pretty cool. My own name for my version was erosion mapping, because it carves out space from a world full of solid blocks, then removes any walls that're only touching other walls, so the new eroded space is perfectly surrounded, ergo maze/cave generation as opposed to world generation.

Hey man I watched both of your videos and I must say, I'm a fan!!! I'd love to see more such content, so PLEASE make more!

Dawg, 8:52 your pixel art is fantastic! Your control of contrast and form is unmatched dude. Don’t underplay yourself, you are talented!

Even for me who does not use Unity at all, your charming voice is so lovely to hear with the explanations you do. Gorgeous!

Really nice and interesting video, looking forward for the next one!

i genuinely love seeing videos like this -- really nicely made passion projects. you're not afraid of showing off your pixel art even if you think it needs some more practice, and the explanations are really well done and visual