The Wave Function Collapse algorithm

If you want to make sure your world is traversible, you could start by seeding the map with random meandering pathways of grass before running wavefunction collapse.

A neat property of this generation method is that you can "seed" the map with fixed landmarks, and it will fill in the rest of the space on its own.

You can also make less noisy maps by dynamically weighting the valid terrain based on proximity to similar terrain. So if the lowest entropy tile can be grass, grass to forrest, or grass to water, instead of being 1:1:1 weights (or predefined weights for the whole map), it can be the number of grass, forrest, or water tiles within say 3 tiles from the current tile. This lets you generate larger lakes, for example, while still being mostly grassland.

This ended up on my recommended and I decided to bite the bullet and learn about the big scary name algorithm at 3am. This video explains it so clearly and cleanly at such a nice pace I think I already understand it perfectly which is amazing! I already summarised it to a friend as “it’s like doing a jigsaw by looking at the similar sides and then picking a random piece that seems to fit” 😂

An idea I've been playing with is to create a world of "object impermanence" where we use Wave Function Collapse in a semi-continuous fashion during gameplay. Basically anywhere you're not looking is in a state of flux, and when you look at it, it temporarily pins it down. Imagine placing beacons or torches to cast light in a world of darkness, and only things that are illuminated are fixed. Perhaps some element of "decay" could be added too, so things become increasingly likely to change when you revisit an area the longer you look away. Meaning areas you traverse frequently tend to stay consistent, while new places, or old places you've not returned to in a while will regenerate.

One tiny tip, try making an IntFlag inheriting Enum for the cardinal directions and set their values as North = 1, South = -2, East = 2, West = -3. Then to set the opposite direction you can just use ~direction and it'll work. You can even type check by doing if direction in Cardinal.

Spent an hour debugging because I made my direction enum NORTH, SOUTH, EAST, WEST instead of NORTH, EAST, SOUTH, WEST. I'm kinda glad I did because I got a very deep understanding of how all of these functions and maps are tied together. Thank you for this! I got it working in kotlin :)

I once used wave function collapse for a procedural melody maker about 15 years ago. I didn't even know the algorithm existed. I just set up a system that decides what notes can come next, based on the current note. For example, if it's the 4th note in the scale, it has a higher probability to go to the 1, 5, or 8th note, and a lower probability to go to 2, 3, and 6. And so it just kept plinking along through the endless melodies. Great things happen when you're bored and curious.

Another suggestion for added functionality: Adjust the probabilities as you place each tile. Every time you place a [water] tile, the chance for a [ship wreck] tile gets +1. Every time you place a [ship wreck] tile, the chance for a [ship wreck] tile gets -99. Placing [cliff] → [cave entrance] +1 Placing [forest] → [big tree] set +1 If the chance for placing [grass] is 100, and each time it is placed the chance goes down by 1, then the map should never have more than 100 [grass] tiles.

Fantastic work. Thanks a lot. One of my student is a lot into game dev and I'll be sure to redirect him towards your video so he's motivated to dig a bit deeper in his coding classes

Very nice production and explanation. Thank you!

Thank you for uploading this video! Now I finally understand how wave function collapse works both in theory and code and managed to port it into my own project.

You could also add extra restrictions like how a set of tiles can only be chosen when near some other tile, or changing the weights of some tiles being chosen based on some condition (such as adjusting the probability to have building tiles want to bunch up and be a square with walls around it for a town). Just something that entered into my head, and would probably make the code more unwieldy.

This is something I would find very interesting to implement using F#. I am developing a simulation program in .NET for a research that I'm conducting, and generating terrains with diverse and realistic environment factors is one of the main problems I have to tackle. This video gave me great insight!

Thanks to your video i've got to make my version of wfc finally work

I've been working implementing this with Game Maker 2. I decided the easiest way to get the allowed neighboring tiles for each direction was to draw an example level with the existing tile set where I try to use the tiles to draw every possibility of tiles that can be placed next to each other. Then I have a process that scans the level and ads each allowed neighboring tile and direction to a data structure that I saved as a JSON. It seemed to work and it was more fun than coding all possibilities manually.

Fascinating! Ik ga dit zeker eens proberen gebruiken. Een ander interessant algoritme is met Perlin noise, maar dit lijkt simpeler.

Great educational video! Thanks for posting.

Very awesome layout and explanation of this concept and algorithm

Just started watching and I'm already inspired. Putting a limit on how many times a tile can be used would mean only a certain percentage of the map will ever be that tule, and only if the condition to place that tile is correct. So if I want a small building I would only make 4 corner tiles, top tile, bottom tile, left tile, right tile, center tile. It only makes sense for them to connect to each other. And then I'm thinking the algorithm would look beyond just what's next to each square, otherwise i might start a building that cant be finished