The Wave Function Collapse algorithm
HTML-код
- Опубликовано: 26 авг 2024
- Generating random worlds using the wave function collapse algorithm.
This video explains how the WFC algorithm works, and explains how to implement the WFC algorithm in python code.
☕️ ☕️ No coffee, no coding! 🔥 🔥
If you like to support my work with a small donation:
www.buymeacoff...
Thank you!!
You can find the source code, and tile set here:
github.com/Cod...
Music: Imagine by Auixe is licensed under a Creative Commons License.
creativecommon....
Support by RFM - NCM: bit.ly/2xGHypM
Music: Imagine by Auixe
Soundcloud: / auixe
RUclips: / @auixemusic4618
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.
Interesting! I didn't think of seeding at all..... But I was wondering about how to do the next step, like roads and rivers. This could work I suppose!
Nah, who needs that :D
I'm curious if it's worth doing multiple wave function collapses to just add pathways and shift terrain to accommodate them with a specific rule set. Because a world generated around paths sounds much more artificial then paths that are adjusted to the world. We clear forests and build bridges. If a water body is long or wide we are more likely to cut through then go around
@@xCCflierx I like this solution
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.
Nice way to make the world more diverse and interesting! Thanks!
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.
Interesting solution!
Or you simply decrease the probability of choosing the mixed-terrain tiles, then you don't have to look at neighbors when computing probabilities. If you penalize boundaries, you will get bigger connected regions too.
@@landsgevaer True, although the effect will be slightly different. Just reducing the probability of borders means if you have a bit of grass with trees on one side, you are equally likely to get more trees or water on the other side (but most likely to get more grass). If you look at the nearby terrain, you are more likely to get trees than water, and possibly more likely to get trees than grass. Doing both, you could be more likely to get trees than water, but more likely to get grass than trees _or_ water.
@@yellingintothewind Not sure I get exactly what you mean, but I certainly agree that it doesn't result in the same types of patterns. Both are ways to promote larger patches of the same terrain type.
I would just give each grid position a different probability for each terrain type
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.
I think you can add a timestamp value to each tile when it gets out of sight..... then after a certain time has passed without re-visiting you could reset the entropy of the tile to maximum. But when re-visiting the wavefunction co0llapse algorithm will generate a different world. However that seems exactly what you want.
I have one concern... you will need a very fast WFC implementation to do this all on-the-fly. Not sure this will be easy.
One good thing is that you only need to apply WFC to tiles that are about to become in sight.
@@CodingQuest2023 thats kind of my thought, yeah.
Like the Shroedinger cat.
@@nifftbatuff676 pretty much yeah, the idea with Schrodingers cat was the superposition of two valid states. Dead or alive. Either fits reality. Just like the WFC algorithm can only produce results that match its rules. You can't have grass next to water without coast in between them.
anyone got potential name ideas for this?
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” 😂
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.
Nice one! That would indeed make the code more compact and smart!
However to keep the code easy to read and requiring less explanation in the video, I may stick with the less compact code sometimes
I've run into suddenly wanting intercardinals multiple times so I'd just go with vector offsets.
@@downstream0114 That's what's really fun. I recently found out that you can do that by using the | operator and apparently you can set the values using auto() and set them in relation to each other. For instance, North = auto(); South = ~North; East = auto(); West = ~East; NW = North | West; SE = ~NW; et cetera.
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 :)
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.
Interesting ideas.... but maybe these things you would like to control even further.
For example the chance of having ship wrecks is higher near the coast line.
And larger cities maybe more often concentrated near the sea or rivers....
And cave entrances shouldn't be too close to each other... etc
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.
The current code probably has plenty of room for optimization. I think indeed using some data structure to keep track of tiles that had their entropy updated by the constrain method, will make getLowestEntropy much faster. But it will add some complexity to keep track of all tiles in that data structure and their up-to-date entropy value. Let me know if your idea can speed things up 👍
queues need more memory. and you want randomness, because this method will regularily fail to fil lthe whole area and have to roll back or retry from the start, with other random choices being made till some attempt fills the whole area. this must not be too deterministic.
@@ollllj Yes some memory will be used, but a pq in this situation will internally contain an array of coordinates and a hashmap, so it's not something dramatic. All it would be doing is speed up the process of grabbing the node with the lowest entropy, not affecting other parts of the system.
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!
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.
I like your idea! But you will need a lot of tiles to connect the tile types of one biome to the tile type in another biome.
Maybe grassland in one biome will be a snowy plane in another connecting biome. But you will need to place a transition tile from grass to snow on the edge of one biome.
You will get a very large tile set! But the worlds will definitely become more interesting!
Thanks for the idea!
i think this could better be solved by using perlin noise to generate probability biases. another factor that would contribute to this would be to simply have a tileset where biome transition tiles are much less likely to be selected. Consider, for example, if your water tiles had 5 depths and you could only ever go up or down one depth at a time. a randomly selected deep water tile would cascade to a very large ocean biome, whereas a coastline is very unlikely to give rise to an ocean, even without biasing the probabilities.
@@CodingQuest2023 of course you will need more transition tiles, but to avoid going from deep frozen snowy mountain chains to dry hot deserts (or to require transition tiles for each possible combination of tiles and terrains), you can make rules, that snowy regions can only connect to f.e. grasslands, and then grasslands can connect to desert or tropical terrain.
You can apply general rules like our world has, the more north of the whole world, the colder the biome becomes, the more south, the warmer, and either more tropical (warm and wet) or more desert (warm with decreasing chance of water). But you usually don´t have snow in one tile, and then desert within the next two or three tiles... well, unless you are in New Zealand...
So a temperature map and maybe a moisture map will help in creating those different biomes and climate zones etc. or maybe throw in a type of underground map, like, mostly sand, mostly rock, mostly clay, etc. and what types of vegetation can grow there.
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
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.
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.
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.
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. 👍
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.
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.
Personally, I think a full water tile should make other full water tiles more likely so as to get bigger ponds/oceans.
Like 7:49 but more specific to full waters next to full waters, maybe you could have a duplicate full water tile that can't be next to anything but another full water tile? Of course, you'd probably want to swap it for one that can be next to other tiles when you place it to prevent any issues.
If you did this for all of the tiles you should get bigger patches of everything without making one thing more common than the other.
It would also be neat if there were more custom options for what blocks can be next to what blocks, for instance making it possible for water to spawn next to other water but if it's too far away it can't spawn but also making sure that the waters don't interfere with each other so that you don't have two bodies of water right next to each other.
I think you can only easily control directly neighboring tiles, with the weight values for controlling the chance and the tiles rules to control which tiles can be next to each other. Not sure how complicated things will get when you start to look at more distant tiles in the constrain method. But an interesting idea!
This you can control using the weight value for the full water tile to increase the chance of it being picked by the collapse method. You could also reduce the chance of coast line tiles to be chosen, to push for larger water areas.
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.
You should! But after working on your bachelor thesis 😉
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!
Great to hear you like the video 😊 Also check out noise based procedural generation, like Perlin noise!
@@CodingQuest2023 I'm using Perlin noise for the base terrain, I'm now working on generating rivers so I had some ideas but it always feels a bit wrong. I'm trying to mimic the real life rivers. Your video gave me some ideas how I might do it, unlucky I don't have much time right now to try it out.
Thanks to your video i've got to make my version of wfc finally work
One thing I noticed, that might be difficult to achieve, is probably deterministic maps. e.g. like in minecraft you can set a seed for the randomizer, and will get the same map for the same seed everytime.
With WFC, this will probably work fine if you generate the entire map right from the beginning and just set random.seed(...) at the beginning.. but if you want to dynamically grow the map (again like in minecraft where the world grows in the players walking direction), then you'll likely run into the issue that tiles might result in different outcomes, depending on from what direction you approach them.
Addition: So WFC would no longer choose the tile with the lowest entropy *globally*, but limited to the players proximity. In a sense a nice feature, because it adds a source of randomness (player movement), practically guaranteeing that no map is like the other, but it also loses this nice feature of the ability to share a seed.
But all the other features you can play around with, that have already been mentioned in the comments, are certainly worth to try it out.
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!
Thanks for the detailed explanation, now I understand the concept and how Sid Myers would have done all those great games :)
Glad I could help! 🙂
no sid meyer game uses this, because this is an inefficient map generator, that cares for a LOT of detail or options, that is not needed for sids games.
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.
Isn't this essentially reverse Minesweeper
Kind of looks like it. For sure this algorithm can be used as a Sudoku solver
This is pretty much how a level is randomly generated in minesweeper I believe. Nice video!
Actually, generating solvable minesweeper levels is a LOT more complex than this. There's a great example written in C you can easily find online; but essentially to generate Minesweeper levels that can be solved, you also need to write an algorithm to solve them; and then use that algorithm to generate a game of minesweeper. This is because it is very hard to create minesweeper grids that are actually 100% solvable by a human.
under rated channel
This video blew up congrats :D RUclips algorithm liked this one. Wish you make more complex algos like this
Yeah I'm a bit surprised 😀
I think I will try more videos about algorithms in the future!
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)?
Haha, good points. I have no excuse for most of the points you mentioned.
Next time I shall do a better job cleaning and simplifying the code!
It's my first video that gets so many views!! I should strive for a higher quality from now on!
wrt to getLowestEntropy, you can get rid of one IF, but you should keep the check for > 0 I think
Thanks for the feedback!
@@CodingQuest2023 It should be easier to keep track of the lowest entropy.
Instead of going through the whole world in a double for loop, you could create a sorted list (by entropy) of tiles that were just updated.
This should make the entire algorithm faster.
You can either choose to randomize the equal entropy tiles in the list or you can keep them in order of when they were inserted in the list.
The latter option should also prevent more deadlocks I think, because it is harder for the algorithm to create holes on the map.
EDIT: oh I see now that TalicZealot suggested something similar 🙂
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
Wow, big plans 🙂 I wrote down some of the algorithms you mentioned, maybe I can think of some topic for a future video. Thanks!
"and then use the small map to create a big map using the tile type to weight the possible output in the entropy," sorry i'm not clearly understanding what you are suggesting here, care to explain again?
@NinjarioPicmin So you can't have a super hot environment next to a snowy one. So on the very first pass it would be like picking a biome. You don't know what tiles are placed where yet, but you know it'll be desert oriented or plains oriented. Each biome will have different weights for certain pieces. Plains might have some trees, but forests will have a higher weight for them. You then run the algorithm again giving each of those grids a certain size. So your first pass could have a 16x16 square grid of biome tiles. Each biome tiles could have another 16x16 grid of tiles inside them. This way you get a variety of terrain and it doesn't shift from the arctic to a plains to a desert in 5 tiles.
In short. First pass picks your biomes
Second pass fills in the details
@@piercexlr878 yes exactly what I was thinking
Funny, I was literally working on something like this in Unity. I am also thinking of using layers of perlin noise to determine possible options.@@kaawan3201
Thanks, I've made one WFC algorithm too, maybe not so good as your, I have no backward steps to solve unsolvable situations.
I also didn't need the backward steps. It depends on the tile set you are using. Sometimes you just cannot reach any deadlock situation.
Or you may be able to add another tile to the tile set to avoid deadlocks.
@@CodingQuest2023by the Coding Theain was an implementation of WFC, it makes circuits and it cannot have any transitions, some of them are impossible.
Its also a tree, so we could paint tiles onto the map and only regenerate the affected tiles
hmmm this could also be used to generate terrain heightmaps
Very awesome layout and explanation of this concept and algorithm
Hi i got two improvements but they are optional. Lets say u have a sprite for the tileMap which is bigger in size than the tileSize than the unit cant´go between lets say a coast north tile which has grass in the north an a forest north tile which has gras in the south cause its too big. So i figured that out with some lines of cde that between every partial grass tile and another partial grass tile always one grass tile is place so theres always enough space for bigger sized sprites to pass between those two partial sprites. And the other thing is, its just a tiny thing, when the connectors in the constrain method are added there dont need to be duplicates in the connectors cause the resulting connectors list only is a comparison list where a value like "0" only needs to be in once.
Great educational video! Thanks for posting.
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?
Yeah, you need to implement a catch for when something like that happens. The 3 ways I know of are to have a back tracking system where you backtrack and mark what you did as impossible. Back track several steps with no update. Or to just restart. If your weights are decent and it's not an overly complex piece, then you shouldn't have it restart too much.
Yes indeed this is possible. I think the easiest solution is to create more tile types to avoid dead locks. If this is not possible, you will need to extend the algorithm to catch the situation in which the constrain method results in an entropy of 0. And then the more simple solution is to just start all over... which is probably very slow. Or backtrack, and retry...
interesting. we used this algo for texture synthesis back in the late 80s/early 90s.
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.
Minecraft and No Man’s Sky use Perlin Noise to generate the worlds, and I just made another video about that topic! 😆 You should check it out
@@CodingQuest2023 I will do that. Thanks!
holy crap I am glad I am not the only one doing y, x
would be nice to look at ALL possibilities for a given tile set for small maps
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.
The relief map itself could be created first using a similar wave collapse algorithm.
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?
Yes, I think you can do that with the weight values.... so for example if you want large lakes you can increase the weight of the full water tile, and reduce the coast lines tile weights. Something similar for full grass tiles if you want large planes. In that case increase the weight of the full grass tile, and lower the weights of coast and forest tiles.
By making the weight of coast line tiles larger and lowering the full water tile weight, will create very small lakes....
Somehow, looks like an improved version of the Minesweeper game :)
I really like this video and will use the algorithm in godot.
Great explanation and presentation quality!
Thanks!
Incredible project
can this be used for biomes cus it doesnt seem like it would?
I wonder if you could adjust the probability based on the total of each terrain in the world and the neighbouring tiles.
yes you can, for each tile individually, andOr you can increase the kernel-size to care for more than direct-neighbors, and use a small template that sets probabilities for larger areas over more than direct neighbors.
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.
Interesting idea, so make the probabilities region specific? Haven’t looked into that. Others have mentioned seeding the map with some tiles before running the algorithm, which could also lead to different looking regions in the world
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?
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 ?
If you have like 20 different grass tiles, I think you don't need to create different tile types for each of them. I think you could just stick to 1 tile type, but when you actually draw the map you could just randomly choose from 20 different tiles in the tile sheet for a grass tile. Right?
As long as the connection rules don't change, I would stick to only 1 tile type.
@@CodingQuest2023 The tile-edge variations I am working on are more about changing terrain, like to "snow" or "mountain" or "different forrest" or "road", so there's definitely a need for more options. I think my version is needing to have a list of options for each edge. I will consider some more about it. Thanks for your input.
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.
I'm wondering the same. This method is also not ideal for parallelization since there are scenarios where you would run into impossible boundaries, although it might be cheaper to parallelize and re-generate problematic chunks
I don't think this is a very efficient way indeed.... especially when you have a tile set that could lead to deadlocks, and you need to retry certain parts. Maybe I will create a video about Perlin noise world generation in the future, also a very interesting algorithm.
It works well in some environments and poorer in others. It won't beat perlin noise in elevation generation for instance but if you want to generate dungeons procedurally there's not a lot of noise algorithms that handle it as well as this one can.
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.
Not sure I get what you want to achieve by this. What application would you get from this?
modelling probably more organic initial conditions @@CodingQuest2023
Awesome video!
Thanks!
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.
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.
As someone who is interested in this topic but never actually made this algorithm before. My best guess is doing a second pass over the terrain using a path-finding algorithm and if you find a walk-able tile with no valid path, try overwrite part or all of the boundary of the problem area.
I review the code for the World generation and i see some improvements to do
Yeah some other people also pointed out I should have done a better job cleaning up the code 😉
And I'm sure there could be some improvements to efficiency of the implementation as well.
Feel free to use the code as starting point and make it better! 👌
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.
you have 30 seconds to explain how this is any different to a markov chain.
Markov chains use probability to determine a stable state rather than generate a random state if memory serves. Correct me if I'm wrong they aren't my strong suit.
After more thought. This could probably be reduced to a Markov chain, but not all Markov chains can be described as this. Similar to how all squares can be called rectangles but not all rectangles are squares. It's a specialization of a much broader idea.
you are wrong @@piercexlr878
@@piercexlr878You can. But you shouldn't.
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.
Thanks for the video! Considering the code editor and the absence of coding convention I assume you're new to Python. If so, welcome!
True, quite new to Python.... used to do a lot more C++ programming.
But I love how quickly you can create stuff in Python!
Need to improve my coding indeed, already got some feedback on this.
Feel free to point out the things that are most annoying to you 😉
@@CodingQuest2023 There's nothing wrong with your code. I like to see how other people write and structure their code, so I almost never get annoyed, quite the contrary, I enjoy it. It's just a matter of style.
In case you plan to get more familiar to the language, I would like to recomend you to read Python's PEP8. It's the python enhancement proposal number 0008 and it focuses on coding conventions. When I started with Python, it took a while for me to discover this PEP, so a lot of my early code had conventions from other languages too. It may be useful to you.
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
Yeah I suppose Perlin would be perfect for making a smooth biome map.
Good solution to improve the performance of finding the lowest entropy tiles 👌
Brilliant!
You're making your computer play minesweeper against itself to buuod a world.. nice
thi is like reverse minesweeper
He talks a Dutch version of the English language
I would suggest maybe cleaning the code up. also also do you have any tests?
Sorry, I have no test.... And yeah I should have done a better job cleaning up the code a bit. Thanks for the feedback!
I wish you had gone over building that dict more. It's the more complicated part then the code
Mooi
I wonder how useful this would be for Screeps.
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
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.
I didn't make up this algorithm myself. It is an existing algorithm loosely based on the quantum mechanics world's waveform collapse.
But indeed that makes it all extra cool 🙂
@@CodingQuest2023 It is not based at all on how waveforms collapse. Remember that quantum wave functions are not probabilities.
Unless you are doing something dirty with `__eq__` , you should _never_ compare eq against `True` or `False` . You do so on line 91.
It doesn't really hurt. Whatever makes the code more readable.
It's my habit to do so in C-code, although there also not necessary.
You are not the first commenting on this, will try to avoid this in the future. Thanks for the feedback!
@@CodingQuest2023As you say, there it is also not necessary. It *can* be worth checking identity against `True`, but that still raises "code smell" warnings to me. It is worth noting that python's polymorphism means you can have `if foo` and `if foo == True` _not_ have the same result, if someone did something funky to `foo` .
can it play minesweeper?
That is your homework!
Actually, not sure if this algorithm can solve minesweeper..... but it is an excellent Sudoku solver!
@@CodingQuest2023It can solve minesweeper as well as it can be solved. There are impossible situations in minesweeper.
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?
Yeah, I assume you want to destroy the chunk again after a while? In that case it will re-generate differently depending on the neighbor tiles on the edges of the then existing neighbor chunks.... even if you would save the random seed. It would only regenerate the same if you start generating with the same tiles on the neighbor chunks (and the same random seed(
@@CodingQuest2023 thought as much I ended up going with overlapping perlin noises one for height and like 4 for which biome, then a seed based on the x and y coordinates of the chunk so its guaranteed to be identical no matter what direction you come from
Yeah Perlin noise should only depend on the random seed. But with a per-chunk random seed, will Perlin not give you a mismatch in terrain height at the chunk borders? I suppose for Perlin you use one random seed for the whole world?
Why did they bot farm boost this?
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.
very cool
Tell me you're a hollander without telling me you're a hollander 😂
It's that obvious? 😅
North or South? Can you guess the city also?
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)
Sure if you only want a limited set of levels in your game, I would be better to design them yourself. Human creativity will produce better results than procedural generation. But I think a strategy game for example, should next to a few scenarios also have a random world generator. Because playing the same scenarios over and over won't be much fun in the long run.
You just use larger chunks then it works
You did not go through any back tracking. If it cannot find a solution it needs to undo some amount of assumptions
3:36 Nothing is random especially after the fact.
Ah, so it's multidimensional reverse Minesweeper
wait this is literally Carcassonne
This is Pokemon
Looks like a Warcraft 2 map
Seems doomed to create tons of bodies of stagnant water with a nary a river to be seen
very interesting. please complete create magic forest tutorials first
Yeah, next video will be about that topic again 👍
See _Wang Tiles._
Nice! Yes you can use this algorithm to fill a plane with Wang tiles to check if they are able to fill the entire plane or not..... checking for repetitive patterns will be more complicated 😉
wow that stack class does nothing :P
From the accent i feel like you from Belgium maybe dutch speaking one
You almost guessed right... I am from the Netherlands 😀
@@CodingQuest2023haha well 80% of the time it was Dutch sometimes I heard French accent. So I though Flemish haha.
noise is better and faster
Yeah I might make a video about Perlin noise in the future, if I can manage to avoid too much maths to explain it 🙂
perlin is awful@@CodingQuest2023
there's too many 45-90 degree artifacts in perlin noise, something like simplex is better because then you don't need to use stuff like domain rotation@@CodingQuest2023
Never looked into that one yet, will check it out! Thanks!
do i smell dutch?
Yes you do 😆
Cool video.
Thanks!
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.
Thanks for liking my video! 😊
I had some similar feedback already. Just want to tell I didn't invent this algorithm or came up with the quantum physics analogy. 😅