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.

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 :)

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.

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.

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.

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

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

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.

Great educational video! Thanks for posting.

Very awesome layout and explanation of this concept and algorithm

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!

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

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.

yall make this sound too simple, took me 4 months to make my own implementation. nonetheless, all videos i watched were great, but this one stands out to me because its about wfc and wfc only. 👍

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.

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

Incredible project

under rated channel

This video blew up congrats :D KZfaq algorithm liked this one. Wish you make more complex algos like this

A point that I feel is missing from the beginning of the video is that wave function collapse generation plays very well with already existing tiles, generated by other means or placed manually. To be plain it just works as long as those tiles have information for which tiles can be placed next to them. As an example, let's say you have a few exits to other maps and a couple of landmarks on this map. You just place those first, connect them with tiles that allow a player movement between them and then run wave function collapse for the rest of the still un-generated tiles.

Great explanation and presentation quality!

You have just presented a world gen algorithm to me that perfectly fits a game idea i had a couple years ago. I should implement that instead of working on my bachelor thesis.

Thanks for the detailed explanation, now I understand the concept and how Sid Myers would have done all those great games :)

Cool generator. One thing that came to mind is what about removing getLowestEntropy and instead using a priority queue, containing the adjusted nodes. This way we don't iterate over the entire grid every step and we get a fast min value.

Nice video. Another idea to create larger "biomes" would be another tile-set of randomly chosen biomes where each tile represents one biome and contains maybe 10x10 terrain tiles, adjusting the probabilities of all available terrain within that section of the map. Basically you could just check for the coordinates of each tile, which biome that tile is in and use appropriate probabilities. That way you can have a mix of near infinite amount of combinations of probabilities of your base tiles. And you can go even further and create super-sets of biomes that only allow biomes within certain parameters within it to create large structures like climate-zones, continents, ocean, archipelagos etc. that still allow for an arbitrarily large or small range of different biomes within them.

Personally, I think a full water tile should make other full water tiles more likely so as to get bigger ponds/oceans.

Brilliant!

Both the video and the comments are really precious for me because I'm working on a procedural generated 3D world right now and I was having some difficulties about how I should fill the terrain. Thank you and thanks for all that commented!

Awesome video!

This is pretty much how a level is randomly generated in minesweeper I believe. Nice video!

Catch the deadlocked tile and output what tile would be needed there 8) that way it can also make sure you've made all the tiles.

I really like this video and will use the algorithm in godot.

would be nice to look at ALL possibilities for a given tile set for small maps

Its also a tree, so we could paint tiles onto the map and only regenerate the affected tiles

interesting. we used this algo for texture synthesis back in the late 80s/early 90s.

Thanks for the instructional video and source code. It's spot on what I was working towards for a fixed tile map method (but not in python, so trying to work through your coding methods). I didn't notice in your talk or via the code what the correct way would be to extend the current "single adjoining NESW" tile option to more than just 1 possible match per tile direction? For example, my tile set has possibly 20 tiles that could match up against my "grass" tile in different directions. As there are various terrain types and transition tiles and other grass types, etc. Would this need a separate tileRules_N & tileRules_S, etc ?

Thanks, I've made one WFC algorithm too, maybe not so good as your, I have no backward steps to solve unsolvable situations.

Isn't this essentially reverse Minesweeper

Somehow, looks like an improved version of the Minesweeper game :)

Mooi

Is this what they refer to as "procedural generated" worlds like in MineCraft, Dead Cells, and No Man's Sky? This was a really neat video.

He talks a Dutch version of the English language

A relief map could influence the direction of water as to form rivers. Flat terrain would yield lakes, but a water tile in a descending position would force more water in that direction.

Have you explored using non-uniform probabilities for the tiles? For example, you could use an image spanning the terrain as inout, on which you can paint e.g. where you want to have more or less water.

i think it would be cool to add a few pass on the algorithm, like generating a small map (16*16 for example) and then use the small map to create a big map using the tile type to weight the possible output in the entropy, Or i would implement a convex hull algorithm to make "rounder" lake and remove the skinny coast to coast line that appears ! i would also add a chance for each now defined lake to generate a island! we could also combine a marching square algortithm or djikstra pathfinding to create towns and road, and bridges ! i may try to make all of that

What method should be used to ensure all generated terrain is path-able? I've been thinking on this for a bit, and (assuming dead ends are a valid tile choice) I can't think of a good way to ensure generation will connect all endpoints and/or prevent "islands" from forming. A simplification of my intended use case is a maze.

can this be used for biomes cus it doesnt seem like it would?

Could you increase the chances of having the same tile show up next to itself to favor bigger areas and do the same in reverse to make them smaller?

I wonder if you could adjust the probability based on the total of each terrain in the world and the neighbouring tiles.

hmmm this could also be used to generate terrain heightmaps

very cool

So if you have n tiles and m possible values, that would be m^n possible combinations, but we want to find one that satisfies the rules. I have heard of that. CSP?

You're making your computer play minesweeper against itself to buuod a world.. nice

Would be neat to see how to code this so that there's always an unobstructed walking path. No good if the map can trap the player in a forest.

Thanks for the video! Considering the code editor and the absence of coding convention I assume you're new to Python. If so, welcome!

thi is like reverse minesweeper

I like the algorithm, but parts of your coding choices seem odd to me :D How long are you working with this? Examples that got me: What's the point in waveFunctionCollapse to return an integer that is always either 1 or 0 als always just checked for it being a value? Why not return the boolean value of that comparisson instead. That way, you could just call done = waveFunctionCollapse. Also, for the non-interactive loop, I would just not bother with done at all. I would just make something like while True: if not waveFunctionCollapse: break Why do you compare booleans against boolean constants? Why not just use if foo and if not foo: instead of if foo == True: and if foo == False:? Especially since the way you make it by putting the true/false at the end makes it harder to grasp whether a value should be true or not. Why do you have a stack class if it does nothing that array itself couldn't already do? Also, why does getLowestEntropy has so many ifs instead of just doing lowestEntropy = min(lowestEntropy, tileEntropy)?

Isn't there a possibility that you could have a series of rational steps which lead to an irrational result though? For example, a loop which creates a situation where there are ungenerated tiles with zero entropy?

I remember getting a shit grade 2 years because I was making a bullet hell game and got sidetracked by spending wayyy too much time implementing WFC for the world generation😭 I thought I'd be able to do it super fast so I remember being so down because it was the first time I was really disappointed with my programming skills.

I would suggest maybe cleaning the code up. also also do you have any tests?

I review the code for the World generation and i see some improvements to do

You can seed it by seeding the RNG. but you cannot seed this with multithreading. while it always generates the same thing, it does so by nature of the RNG, which you cannot replicate across threads. This also cannot add different terrain features (think biomes, structures) without multiple passes and significantly more layers / complexity. So, this is fine for something very simple -- and in fact works quite well for something very simple -- but it cannot ever be anything more than simple. Now, if you use this as a smaller tool in greater world generation, it would work amazingly well for filling in the minor details in already-generated maps. You could use this for clutter/accent placement, as a map maker's tool for filling areas in with random terrain/clutter (for ideas/filler), etc.

i assume you could also do this in reverse? wave genesis function for reaching a "goal" randomly by starting with all 0s and choosing a location to increase entropy. i think the solution space would need to be more confined at the outset though.

I wish you had gone over building that dict more. It's the more complicated part then the code

I wonder how useful this would be for Screeps.

Could you like combine this with perlin noise or some other "smooth" noise function to modify the random number generator in order to modify terrain type to create "smooth" transitions between "biomes?" Also the O(n^2) traversal to find smallest element was pain, you could just keep an array of length max entropy and then add and subtract to indices of that array to keep track of the counts of each entropy

it seems like if this was used in a chunk based game similar to minecraft it would generate terrain differently based on the direction you approach it from right?

Tell me you're a hollander without telling me you're a hollander 😂

Cool algorithm, but is it really more efficient than other options to generate a world? You still need to reduce _X * Y * Tiles_amount_ ( eg: _X * Y * 35_ Eg: at 3:33 ) into a _X * Y * 1_ amount, that is MANY (quantum-)tiles that needs to be updated, to generate a world.

you have 30 seconds to explain how this is any different to a markov chain.

Ah, so it's multidimensional reverse Minesweeper

Seems doomed to create tons of bodies of stagnant water with a nary a river to be seen

wait this is literally Carcassonne

Just because a game has a generated world that doesnt make your game more unique or interesting I mean how much does it make a difference if the tile is a grass texture tile or a tree I think indie game developers are still struggling with what makes a game interesting

Cool video.

This is amazing, though not to nitpick too much it's not super useful for set level games. If you only have 7 levels it's easier to just build a map editor and plan out your maps - writing the logic to pull in the tiles, separate them by type and class is hard enough let alone writing up rules for their interactions. That said, this is amazing for games that have hundreds of maps and levels (or a dwarf fortress kind of game)

very interesting. please complete create magic forest tutorials first

This is Pokemon

I really don't get this approach. Would it not be far better to build up your list of possibilities? The need to store and sort all tiles not yet defined, in order to find the one with the lowest "entropy", is slow and wasteful. Plus if you moved through it in a standard way (left to right, top to bottom), you would only need a max of 3 lookups. Your list of possibilities would simply be the overlap of the lists for the surrounding tiles. So while it's always good to know more ways to accomplish something, I don't think this solution fits the problem.

Why did they bot farm boost this?

Looks like a Warcraft 2 map

3:36 Nothing is random especially after the fact.

Unless you are doing something dirty with `__eq__` , you should _never_ compare eq against `True` or `False` . You do so on line 91.

This has nothing to do with quantum wave functions, or any collapse thereof. If you want a physical analogy, consider how liquid water freezes to ice. The relevant physical jargon (if you really feel the need for such pixie dust) would be “phase change” and “symmetry-breaking”. But of course “quantum” somehow makes everything sound extra-cool, doesn’t it.

can it play minesweeper?

See _Wang Tiles._

You did not go through any back tracking. If it cannot find a solution it needs to undo some amount of assumptions

wow that stack class does nothing :P

From the accent i feel like you from Belgium maybe dutch speaking one

do i smell dutch?

noise is better and faster

Bad name choice: "Wave function" refers to the complex probability amplitude seen in quantum physics. Meanwhile this has nothing to do with quantum physics. It's only about classical probability - no Wave function involved. The name probably just comes from some random programmer who wanted to sound cooler than he actually is by implying he is doing something "quantum".

Minecraft ☠️

That's what we want. More generated garbage.

A good video but this has nothing to do with wave functions, entropy or collapsible states ... So unfortunately all that is 'tech clickbait'. What's being referred to as entropy is closer to the complete opposite of entropy for example.