Procedural Generation with Wave Function Collapse and Model Synthesis | Unity Devlog

[@lm5050]

This video has the same level of quality of a great university lecture - starting with building an intuitive foundation of the theory (constraints) - introducing the body of work/research using academic papers (opening up rabbit holes for me to explore further) - implementing theory with practical examples Great video!

[@arkdirfe]

Something that could be interesting for larger maps (like world maps) would be a multi-step process of generating macroscopic features first, so land and ocean, then using different rules within those zones to further refine with as many steps as needed.

[@dvgen]

I totally agree. A "hierarchical wave function collapse" would be really fun, plus the name sounds fun too. I haven't seen anyone do something like this yet, but it seems like there could be a lot of potential.

[@OnceSecond]

​@@dvgen I am actually doing something like that in my wave function collapse implementation on Unreal, I don't use lowest antropry though because I never found it necessary which might be a mistake I don't know. I will explain the process, btw that's a 3d implementation. I am generating environments but I have a car that is going lineraly on a path that goes though this environment, because I need to make sure that the path is viable I do a first wfc to generate the path using tiles I know are right to make the path. Once the path is done I get the resulted tiles and overlap them with the terrain tiles, so I set in my terrain wfc all the tiles for the path like if it was a constraint, I then resolve the wfc for each of the tiles of my path (so it will resolve all its adjacent tiles till there is no tiles to resolve). Once this is done I resolve the entire wfc, at this point I have obviously less stuff to resolve since some of it was done with the path. This is very usefull for me because it allows me to resolve partial wfc that end up being in a bigger one. So I am taking the opposite approach of what @Arkdirfe is describing, I first generate the macroscopic features, refine them and once they are done I push them into a bigger one.

[@EEEdoman]

@@dvgen Actually what I'm working on right now for my game! My method is probably a bit too strict though, as I've had to wrangle with the edges between regions a bit.

[@dvgen]

@@OnceSecond Interesting approach. I think lowest entropy and smallest domain are both pretty good methods. Sometimes lowest entropy seems to make smarter decisions, but it's hard to quantify. Linear scanline can produce artifacts, unless you are doing something else. Your methods might prevent artifacts. Have you seen Boris the Brave's work on path constraints? I don't know the details about how it works, but it sounds like something that might interest you. twitter.com/boris_brave/status/1615134425687199744

[@OnceSecond]

​@@dvgen Very cool link thank you ! I think I could do a mix between his method and mine where I would path find only once and set the tiles from here. My resolving process is simple, take first tile, take the ones around and resolve them recursively so if they change I resolve the ones around them too untill there is no changes anymore. They are being resolved based on the one before so I just update the possibilities not based on the neighbors but on the one that initiated the update. It's pretty efficient honestly and it allows me to avoid errors very easily because they all start each time from a "parent" so if the resolve fail I retry the parent and so on and so forth.

[@summatim]

0:01: Introduction 0:30: Constraint Satisfaction 0:40: Puzzle Games 2:55: Constraint Programming 3:12: Real-Life Constraint Problem 4:16: Applications of Constraint Solving 6:30: Texture Synthesis 7:07: Model Synthesis 9:09: Wave Function Collapse 14:39: Flattening Arrays 15:35: Entropy 17:38: Charm of wave function collapse 18:15: Propagation step 18:50: Generation failures 20:12: Modifying in blocks 23:13: 2D and 3D generation

[@Capa2.]

Thank you!

[@dvgen]

I invited Paul and Maxim to make some comments or corrections. Here is a comment from Maxim about the propagation step and arc-consistency: "Both Paul and I used the AC-3 algorithm at the time of publication. In 2018, Mathieu Fehr and Nathanael Courant rediscovered a faster propagation scheme known as AC-4: github.com/math-fehr/fast-wfc AC-4 is orders of magnitude faster than AC-3 for large tile sets. Today, the fastest WFC implementations use AC-4. This was a nontrivial discovery, because AC-4 had a reputation of being a *slower* algorithm in practice in the constraint solving community: ijcai.org/Proceedings/93-1/Papers/034.pdf" Paul also clarifies that AC-4 is faster for large tile sets on his website. See the "Propagation" section of this article: paulmerrell.org/wp-content/uploads/2021/07/comparison.pdf The particulars of AC-3 and AC-4 are just a little beyond me right now, so I'll defer to Maxim and Paul's suggestion here. Paul also noted a 4D demonstration in another comment: "Excellent video! It's a great introduction to the subject and summarizes my PhD work very well. To answer your question at 9:54, yes, we can do this in 4D. In 2007, I created four-dimensional space-time cubes to generate a 3D model that changes over time. For more info, see kzbin.info/www/bejne/Y3_ChYd3qMmLnck and Section 3.4.2 of my dissertation."

[@TheExileFox]

Please look into simulating gears and pipe the result into some form of animation sequence that can just be viewed, without having to run the physics checks again. This would allow the gears to properly mesh, rotate at the correct speed and etc with very little performance required to achive the same result. This doesn't have to involve torque or gravity.

[@quickdudley]

This has me wondering: what if we used a path consistency algorithm instead? At first guess it would probably be slower, but maybe for some tile sets it would reduce enough additional entropy from some cells to be faster overall.

[@tetronym4549]

Oh my god that "large mindsweeper grid" thing just punched me through time and I flew back to my childhood.

[@dvgen]

🤣 I knew there had to be others.

[@ykey7146]

I literally discovered your channel last week and was sad because there weren't a lot of videos. So thanks for the great content and glad to see you back !

[@dvgen]

Glad to have you here again! You found my channel at a good time I think :)

[@MattyDoesGameDev]

Seeing your examples of WFC being implemented was super helpful. I've watched dozens of videos on WFC, but they all felt like they were only explaining the concept, but your video felt like it was showing how to implement it. Thanks for the hard work, please keep it up!

[@dvgen]

I'm glad it was helpful. We will be going deep into the implementation in the next video. Right now I'm working on polishing some code and tools in Unity for that.

[@MattyDoesGameDev]

@@dvgen I can't wait to see it!

[@scottcourtney8878]

Your work is really interesting, and the citations to original papers are appreciated. Since generation failure happens when a cell's domain size becomes zero, one way to prevent that is to have at least one tile that matches unconditionally, and apply a very low weight to it so it won't overload the map. If you are generating outdoor terrain, a small area of bare dirt, pebbles, etc., could fit almost anywhere. For mountainous terrain there might need to be different match-any variants for nearly-flat, sloping, or steeply sloping surrounding cells. Anyone who's used premade non-tiling assets (such as rocks from Quixel Megascans) to kitbash a cave level knows that "a big rock can hide a multitude of sins" when other modules just don't quite match up. :) In some ways, this is the same as the modify in place mode if you pre-populate the map with an unconditionally acceptable tile and then seek every possible opportunity to replace it with something more interesting -- but accept that this won't always happen. The goal is to transition from an algorithm that usually succeeds but sometimes fails, to one that always succeeds but may sometimes produce a less pleasing result. Many years ago I did some printed circuit board (PCB) design, first by hand and then with the automated tools that were available at the time. Your backtracking methods remind me a lot of the discussions around various rip-and-retry algorithms used in the PCB CAD tools when they reached a topological dead. Circuit boards can have many layers, allowing traces to cross, but every additional layer adds *significantly* to the cost of manufacture, so you absolutely don't want to have a layer with only a few traces on it. PCB design was a hard problem back then, and it's even more so now because increasing clock speeds impose constraints. The signal traces behave less like simple "wires" and more like radio frequency transmission lines, antennas, and/or waveguides -- whether or not you wish them to! I've been out of that field for a long time, but I seriously doubt anyone is laying out circuit boards by hand any more.

[@dvgen]

Oh thats interesting. I've done some electronics work, but never had to do it so much that I needed to make my own PCBs. I can definitely see how some of those issues might add a whole layer of constraints to work around. Personally, I found I like coding much better than electronics. It's much easier to press undo than it is to order new parts.

[@PaulMerrellResearch]

Excellent video! It's a great introduction to the subject and summarizes my PhD work very well. To answer your question at 9:54, yes, we can do this in 4D. In 2007, I created four-dimensional space-time cubes to generate a 3D model that changes over time. For more info, see kzbin.info/www/bejne/Y3_ChYd3qMmLnck and Section 3.4.2 of my dissertation.

[@dvgen]

Oh cool! I just missed that somehow. I think I saw another 4D example, with the 4th dimension being time, somewhere on Twitter. I tried to find it for a while, but I haven't been able to find it. I'm really glad you enjoyed the video.

[@mesmercricket6720]

Are you telling me 4D space can be used to store the equivalent of a "sprite sheet" for 3D models?

[@PaulMerrellResearch]

@@mesmercricket6720 I'm not sure a sprite sheet is the best analogy. I think of it as any another tile or cube, but one that is changing over rather than changing over space. If a character is moving forward, they disappear out the end of one tile and emerges into the next tile. It's not following the character around like a sprite would.

[@TheMasonX23]

I would love to see another in this series, or whatever you've been working on! These were such great videos!

[@benjoe1993]

Great video! I enjoyed it a lot, thank you. WFC error handling? Just do Bomberman. Whenever there's an error, select a number of neighboring tiles (like a 5x5 area) from where the error happened and recalculate their entropy as if they were never solved and just continue the generation. The bigger the selected area the more likely the error won't happen again (you can increase the size with each consecutive error in the same area), but obviously it'll take more time to recalculate and adds to the overall generation time. But so does restarting the generation, which is what I read/heard from most WFC tutorials :D

[@dvgen]

Thanks, glad you like it. I think the "bomberman" method could also be good for editing an already generated region. It's something I want to play with later.

[@benjoe1993]

​@@dvgen Yeah, that's totally true. I'm already imagining the totally unnecessary but way to satisfying to leave out little animation where you destroy part of the terrain and regenerate it :D

[@MatterFlow]

Another nice solution.

[@lsf3og]

I have close to zero skills in programming. But I could watch this for days. So interesting. Thanks

[@greysion]

One of the most thrilling explanations of an extraordinarily fascinating topic I have ever come across. Thanks for putting this one in the oven for us, appreciate all of the work you've done to make this somewhat digestible.

[@Awelmann1]

I had already thought that i needed to consider all the combinations of possible neighbours instead of just looking at single neighbours but your video is the first i have seen that explicitly mentions tiled vs overlapping wfc. Thanks for clearing up some things, guess i have some more work todo

[@neil_from_future]

This video and the comments are wonderful! I will save this to "much watch later" playlist. So maybe one day I will come up with this.

[@canertwo]

Literally never clicked so fast. You are amazing!

[@dvgen]

Thanks for that. This comment puts a smile on my face.

[@TheImpostenator]

so glad the how its made narrator started making devlogs

[@dvgen]

Hahahah. I used to think he sounded like John Goodman.

[@OxAA00]

Wow great video! I was looking for a general introduction into Wave Function Collapse and came across your video. Very well put together. Thank you so much for taking your time to make this great video!

[@zmike9831]

finally, a video that addresses gamedev problems while choosing solutions that arent overcomplicated and explaining how you did it! because things like image quilting for example is not that complicated for what it is but is still overkill for most gamedev projects.

[@connor4440]

This is one of the best and most interesting videos on procedural generation I've seen.

[@dvgen]

That is a huge compliment. Thanks! More to come.

[@PrimerBlobs]

Very cool video! Love the midjourney as stock photo technique as well. :)

[@monkeywrench677]

This gives me an idea for a survival system, where when a block sections leaves the view frustrum it is regenerated, leaving the player withnrw terrain. Coupled with some area the player can teleport to, to build permanent structures, it could make for a very interesting experience

[@dvgen]

Thats an interesting idea. I'm not sure how Marian Kleineberg's infinite approach works, but I DO think that is how Rob Lang's generation works in Clomper. If I recall correctly, if you move outside of the play area, the previous content is gone and will regenerate if you come back. If the persistent area is the right size, it could make sort of an interesting infinitely changing wasteland approach. I think having some permanent areas, either generated or established by the player would be a great addition.

[@pagarsky]

This overlapping WFC method got me thinking of convolutional neural nets for some reason :D It's kinda exciting to see similar techniques/approaches in different branches of computer science. Btw those infinite cities give off strong liminal spaces vibe and that looks awesome!

[@dvgen]

Oh yeah, I could definitely see those infinite cities as little buildings on the surface of a massive star cruiser or something too. Convolution is another thing I think a little more about. I haven't got to mess with convolutional neural networks for image analysis much, but I'm kind of fascinated how our retina and brain also essentially use convolution for image analysis. I think the neuroscientists call it "convergence" instead. But from what I understand, its really the same thing!

[@SethDrebitko]

Wanted to thank you for the excellent video. As a Godot dev I almost skipped it in my feed, but there was so many non-unity specific gems.

[@dvgen]

I'm really glad to hear that. I'm going to try to keep my content as engine agnostic as possible. I will have to focus on engine specifics from time to time, so that will have to be Unity. Godot looks great, but I don't have time to learn a second engine right now.

[@davecgriffith]

Wow, this was super interesting! Great video. The pacing and depth were just right. I even loved the background music, which I usually find distracting. Seriously, nice job.

[@dvgen]

I appreciate that, especially the comment on the background music. I payed really close attention to a few critical comments about the music from the last video. It was helpful to have that constructive feedback, and I'm glad you feel like I hit the right balance on this one.

[@yds6268]

This is amazing! You've done a lot of research, this is like listening to a quality conference talk. Also, 🐢!

[@dvgen]

Thanks! I guess that is what I was going for. I'm still trying to figure out what I want to do with this channel, so I'm glad you liked it. Also, 🐢 🐢!

[@yds6268]

@DV Gen btw, I had that same turtle for several years (a single one). It wasn't easy taking care of him. I had to give him away eventually. Can't imagine caring for so many at once

[@dvgen]

@@yds6268 I might have gotten a little too excited about getting a whole bunch to study their behavior. Since I'm moving, I'm rehoming all but my favorite four now (two of them are in the video). I grew up with a lot of animals, so I'm bad about getting too many for one reason or another. It's always something I'm working on. Sometimes, less is more.

[@potatoTomato277]

Very well made, thank you for the detailed well presented explanation and for the resources in your description. :)

[@j0tah47]

I think this is my first ever KZbin comment but I just want to say that I love your video(s)! The perfect mix of theory, intuition, research (including references!), application and examples. Excited for more! I would love to see how pathfinding can be taken into account as a constraint, to create worlds where each tile can be reached by an agent.

[@wesleybantugan5604]

Your videos are a hidden gem and thank you for the interesting information! Looking forward to what else is in store

[@dvgen]

Thanks, I'm glad you enjoyed it.

[@user-sl6gn1ss8p]

I wish half the channels dealing with science would cite their sources as well as this : )

[@dvgen]

I teach, so I would feel like a hypocrite if I didn't!

[@sebastiendeseille9890]

Hello, I just finished your vlog on Procedural Generation. I really appreciated your explanation of the algorithm. Thank you very much.

[@ChronoWrinkle]

Wow man, last part is so inspiring, thank you for great content!

[@dvgen]

Thanks, I'm really glad you liked it.

[@redlogicp3223]

Your video quality is absolutely incredible. Keep it up!

[@Vek-Game]

Very interesting dive, thanks for taking me on this journey!

[@dvgen]

Glad you liked it! I was a little worried this might be too technical compared to my last one.

[@Vek-Game]

@@dvgen I think it definitely depends on who your audience is. If the audience are just regular gamers then it probably is too technical. But for any novice to experienced programmer this is like a perfect first step. I really like how this makes the idea using reading research papers feel far more approachable. Normally they’re very overwhelming.

[@dvgen]

@@Vek-Game Thanks, I appreciate the feedback! I do remember having a very hard time with papers on dual contouring, especially on an octree, myself. Some of those technical papers can be tough!

[@TheHombresinombre]

Woah, this video is awesome. I am starting to learn about procedural generation methods and this video rocks. I would love to watch the next ones, but sadly they seem deleted.

[@GrandpaWho]

I was working on a WFC algorithm, thinking I was very smart, without knowing it was a thing.^^ I then read some articles about it and saw demos. But for me, WFC was too slow (crashed my PC on 1000x1000 tiles) so I decided to find a faster method. Then I came up with a much faster approach, thinking I am very smart again. And then I saw your video and recognized, it is called model synthesis ... It turns out, I am not so smart after all. 😂 Edit: Okay I decided to add more info, because it someone may find it interesting/helpful. I am creating an RTS and a Puzzle Game and want to use the algorithm for both. Thus it needs to have features like guaranteed paths for the RTS or guaranteed solutions for the puzzles. This all became overwhelming, therefore I split the generation in multiple passes. There is for example a "height" pass only generating the heightmap in 3D, a "solution" pass that generates a solvable puzzle before filling in some "noise" to distract the player and a "spawn" pass that uses all the information of the passes before and generates the model at the end. Now in my case having multiple simple passes isn't much slower than having one very complex. And I can combine linear passes with entropy passes for better performance. Entropy for example for the solution pass, linear for the spawn pass.

[@ashersaipe]

great video bro! once again, really interesting :))

[@dvgen]

Thanks, I'm glad you liked it. :)

[@tenthlegionstudios1343]

Appreciate this content a lot. Love in depth stuff. Keep it up man! just watched three of your videos back to back. I really appreciate the notes to articles as well - thanks!

[@tenthlegionstudios1343]

I am definately going to mess around with all these concepts in Bevy with Rust. Whats great here too is that for 2d tiled games this seems especially straightforward, with lots of little tweaks you can make. I am highly interested in orthographic versions of some of these as well.

[@ZadakLeader]

Perfect Sunday afternoon

[@dvgen]

Could only be improved by more sleeping in :)

[@unitycoder]

Best educational video in KZbin! 🏆🏆🏆 *and i've watched (or tried to watch) thousands of them..

[@BismuthBorealis]

overlapping method reminded me a bunch of markov chains, where higher chain lengths are more similar, and lower less so. ... although from another perspective perhaps markov chains would simply be a 1d equivalent to the 2d overlapping bushes

[@Karlthuluu]

Great video! Looking forward to seeing your code and implementation! Especially looking forward toward how you handle entropy!

[@bobov99]

Love this channel! Keep up the great work

[@dvgen]

Thanks! Glad you enjoyed it.

[@apostolidispeter2499]

When there are no tile configurations possible, you could just redo the algorithm with smaller overlap on the modules. If you can't find a configuration: Retry with an even smaller overlap. If you can: Then you paint that, and try with the original overlap all over again. Repeat. That should get rid of all artifacts, while keeping the overlap value mostly the same, thus keeping the generation looking how you want it to look. Amazing ideas, thanks for sharing!

[@Ivorforce]

That's so cool! This video made me realize I was working on an algorithm in the same problem class (component based maze generation) as Paul did in his PhD, at the same time too! I was still in high school then, so I didn't get any further than an optimized brute force approach. It's pretty nice to know that finally there is a good solution out there!

[@dvgen]

Thats pretty impressive for high school! I barely knew anything about programming back then.

[@Ivorforce]

@@dvgen Thanks :) The things kids do to make Minecraft mods! lol

[@PreRendered]

Phenomenal presentation! Thank you for the education.

[@muuubiee]

Half way in, but gotta say this is a great video! And I was recommended this, so maybe you're in for a spurt growth.

[@goranjosic]

Great video!! I really like that you included the documentation in the video entry, so I spent twice as much time searching for all the interesting things on the links. _Tomorrow I will start with my hobby version of wave function collapse in JS and Python - I've been wanting to do that project for a long time, but I can't get there because of the work and lack of time._ :)

[@TheGreatLaveen]

Love the video, you are great at explaining! Thank you for teaching us!

[@DerSolinski]

Ha... never thought about weights for modifying the entropy. Changing them on the fly should allow for much more seamless terrains. All kinds of statistics could have an influence on those, yay another rabbit hole. So thanks, learned something today 👍

[@resdek2246]

This video is awesome. Please keep making them.

[@HansMilling]

Very interesting project and analysis of the algorithms.

[@emjizone]

Note: you can do *much better than simple backtrack* to speed up generation while handling errors cases you don't want to pre-compute. Here is how: *error state memoization.* It consist of extracting constrains rules from error states, backtrack, then apply the learned rules in future propagations. This way, the program don't go back twice for the same reason: your program *learns* to avoid errors several steps in advance, using *implicit* constraints that it has discovered and that you, as designers, may not even have thought of when entering *explicit* constraints. The advantage of this approach is that if, with certain random seeds, the generation does not encounter an error of a certain type, even though such an error is still possible in the general case, it will not test for this error, thus saving a great deal of time. However, it is still guaranteed to handle all errors if at least one general solution exists. Feel free to cite me for that in your projects, or to call me for collaborations on such self-optimizing algorithms.

[@timonix2]

How do you insure that the new rules learned are true rules and not by chance?

[@SandTurtle]

was so disappointed when i saw there was no uploads so many months after the last video, happy i came back and saw this vid, i plan to use the general concepts from each approach in my own generator. the fact you can get such complex behavior from what's essentially a weighted rng function is crazy, I've never really liked the idea of using a noise image for procedural generation, and this is great. im thinking that a similar type of algorithm could also be used to make a biome map, where it decides the boundaries between two sets of weights. maybe it could make an "intensity map" where it could mark areas where the biome is "thick" or "thin" (how extreme the weights become), and this system could also be used to blend two sets of weights between boundries of biomes. after the biome/intensity map is generated, a second pass could be done where the majority of the weight is given to a "no change tile", with a small amount of weight given to a "structure tile" to place structures inside biomes. you could weight these tiles to favor less extreme parts of biomes, and shy away from areas with many interacting sets of weights. they could be pre-programmed sets of tiles that just plop down centered on the "structure tiles" or they could have a pass where they snake out to decide what area they will overwrite (basically a mini intensity map with harder cutoffs), and then another pass to either place prefabbed rooms or a bunch of more intensity maps that decide on even more intricate details, influenced by each former pass. after structures are created you can go through a similar process for the rest of the environment (which would ideally take the structures into account (why i said them first!)) and be as general or specific as you want for each step! tldr the basic idea is to make an algorithm that randomly generates a map of how extremely each tile should follow which set of pre-programmed weights using its own set of weights to make the shape of biomes more believable, and give certain characteristics like the max/min intensity size shape and location of variance between the lightest and thickest part of a biome, if how far and what features it blends into neighboring biomes (can even be influenced by what biome its mixing into), and many many more factors that let you influence how the final algorithm (the actual part where it places visible tiles) works. okay real tldr; use the same algorithm as you are using to place the tiles, to decide the exact weights on each x and y location to make it more precise this has a few flaws such as taking exponentially more time, and being much more prone to those impossible situations you described, although as they have a larger range of possible values (anywhere from no weight to 100% weight for each biome) they won't fail exponentially more, but they may create conflicting rules that could cause some unexpected results. it also has the problem of having to manually tune every single pass which could be very hard to intuitively try to figure out for certain things. (maybe you could analyze a set of tiles to generate some weights like in the video), id like to hear if any of you have any feedback on any of these concepts ah yeah didn't know where to insert this but if the map ends up looking disjointed you could run a pass on itself that replaces a tile if its chance to be there with the current weights (of which some were not there due to it being generated afterwards) is below N to "smooth" outliers, hopefully fixing the very shallow puddles that like to crop up.

[@the_primal_instinct]

Another way to look at the cell with most options as the one with lowest enthropy is that no matter how we tile the rest of the map it's highly likely that we'll find a fitting value for this cell since we have more options available.

[@ninoeme8264]

This is super interesting! Waiting on your next video :D

[@jarrettonions3392]

This is an amazing video on such an interesting topic!

[@Timo.ohohoh]

I love this video, youtube make me watch it every few week ^^

[@janiszusevics2768]

WOW. Amazing video. Fascinating topics. Definitely subscribing

[@sutech]

This was a great video. Reminded me my algorithm for map generation for a game I wanted to make. I did a prototype in php that would create a map with starting point and endpoint, connect them those points with traversable blocks and the branch out from them to generate various ways that ended either reconnected to the main path, or just stopped in a cul-de-sac type area. Something like Diablo did. So the player could explore a sprawling labyrinth of a post-apocalyptic urban area, while still able to progress in the game by reaching the end of the level. The blocks even had their own levels (jumping from ledges was possible in the game design) with ledges and ramps. I should find the php file and revisit the game design.

[@maksy09]

Hi, thanks for another great video! In one of Oscar Stalbergs videos he talks about a connector system on 3D tiles. If I understand correctly you get those connectors by analising the mesh itself, which lets's you create the tiles but you don't have to worry about constraint setup. Might be interesting and I'd love to see your approach and explanation on that topic. I've read a lot about WFC but still can't wrap my head around it in unity. Your videos are truly amazing in explaning and showcasing the different methods. Keep it up!

[@dvgen]

I'll try to cover this in the next video. There are a few ways to make the constraints, and this is one of them. I don't use this myself, since sometimes I might not want to modules to match just because the meshes match. Right now I'm cleaning up the code a bit and pulling out paid assets so I'll be able to share it when I'm done, and then I'll start piece together the next video.

[@electroAU]

Great video! Really good to see the comparisons between the different types. It looks like you've got them all going fairly elegantly, I'm very curious to see how it's all structured.. my efforts so far have been a disastrous mess 😢

[@andressmartin8410]

Hi there! I wish you were still making videos. Your game is turning out great and the information you show in your channel is priceless. I like your teaching technique and everything is super interesting. I hope everything's alright, take care.

[@2dozen22s]

You might be able to combine multiple approaches for different scales/layers. (EG: biomes bias-> geographic features/terrain -> structures/paths -> decoration/fine placement ) constrain the constraints! Each layer feeds the next with information. After geographic features/terrain, using biome information and height map data, accurate rivers could be generated, or a bias for quests/needed paths/gameplay elements/etc So it ties together on a macro scale better. Some parts could probably be multithreaded if you split up the domains. EG: determining in another layer what tiles/voxels will be a forrest vs a town. No overlap so each can safely run independently.

[@dvgen]

A lot of people have suggested layer-based methods. I definitely think it could be a good idea. I have some fun noise generation with erosion algorithms that I'd love to incorporate as a base level for constraint-based generation. I haven't thought about multithreading that way though. It's worth looking into. I have seen some attempts to multithread parts of WFC / MS, but I'm not sure it has really worked out. Perhaps a chunk based approach like I showed at the end could support multithreading.

[@sergodobro2569]

Wow! This was useful! And the explanation is very good! I love such videos!

[@dvgen]

I'm really glad you enjoyed it!

[@Magnogen]

This video has been really interesting to me, and I think I might get into wfc for a personal project. Tomk tomk!

[@dvgen]

Thanks. It has been a really fun thing for me. It may not be the best approach for everything, but it's at least an enjoyable project to develop.

[@Sofia-rh7ji]

I think that an interesting idea would be to combine wave function collapse with smoot pseudo-random noise, like simplex or perlin noise, that determines the probability of the generation of certain tiles. For example, you could have a noise map that interpolates between the tile weights of different biomes or something like that. This could also help reduce some of the weirdness that you can get from wave function collapse without the copy/paste look that you can get from the overlapping system, like in the case of a coast, where you may have it so that the chance of generating a water module is dependent on a noise texture, causing for there to be a smooth coastline that would also have the benefit of being able to be fractal only at the edges. You could also use this with deciding where you change height, either keeping track of the height at different points and comparing that to the value of your noise texture, which, depending on how it's implemented, could be a form of error handling in it of itself, or by weighing the chances of height changes based off of the delta of your noise texture, which wouldn't have the benefit of the potential error handling, but would reduce the memory used by in the generation process and could possibly be more flexible to complex rulesets. And if you don't want to use noise, the same code that would work with this could quite easily be used to make a relatively easily editable map generator system that you draw on the oceans and different biomes for.

[@dvgen]

I think combining some of these features would be really interesting. I'm not sure I'll have time to get into it, but there is definitely potential there.

[@doltramir]

​@@dvgen a simple and interesting variant would be to just use some smooth noise (perlin or whatever) for the entropy weights. Plus, if you combine (maybe just add together) noises from different weights - the resulting weight may easily represent the edge between biomes, or some property, that unifies or differentiates some of the biomes. That way, you can even split all the generation into several passes. One for biomes, next one for structures, then one more for plants. And you can even differ their grid resolutions. Plus every next pass will know actual weights and result of previous ones. That could be a very powerful tool.

[@BleachWizz]

awesome dude. I was thinking... applying the modifying in blocks with the wave function algorithm sounds very trivial

[@justalonelypoteto]

I was today years old when I found out quordle exists, and it somehow perfectly satisfies my urge to work on several monitors while being too broke to buy another one

[@dvgen]

🤣

[@MaxIzrin]

I also used the cheat code for mine sweeper when I was a kid. The cheat turns a single pixel in the corner of your screen black, or white, depending on what's under your cursor.

[@dvgen]

Haha, thats great. I didn't know about that. I can totally see myself doing that as a kid.

[@GameDevBox]

Your videos are a hidden gem and thank you

[@Omhetehmo]

Amazing! Waiting for the next video

[@denisgoodman4492]

Thank you for sharing knowledge, will wait next videos and will be interesting to look your code in Unity, because some things not very clear

[@dvgen]

Let me know if there is something specific you would like me to clarify, and I'll add it to my notes for the next video.

[@denisgoodman4492]

@@dvgen Will be interesting to watch a code implementation (may be simple example) of wave function and Model Synthesis in Unity ()

[@jumbledfox2098]

God your videos are so inspiring! The way you describe these things makes them so easy to grasp and makes me want to try making something like this myself

[@lolzasouruhm179]

This is very interesting and understandable I’m going to pass this to some of my friends who are thinking of doing some procedural generation of 3D asteroids for a sort of space trucker game. I could incisions using generation by blocks and adding some randomization to weighting for specific rocks could be used to generate almost all unique asteroids!

[@DH-Dev-]

I've been tinkering with 3D WFC for a while and I've always had trouble with failed generation. The modifying in blocks approach might be what I'm looking for, as I had considered breaking the problem down into smaller chunks but didn't know how to deal with unsolvable shapes on the borders of neighbouring chunks. The overlapping method seems like it would solve this nicely.

[@Beefman951]

Cant wait for next video, great content

[@pepperminty-joe]

This is so well explained, thank you so much.

[@Cheeseington]

Super interesting stuff! I ended up giving simple tiled a go in Unity, and I've found it can have some interesting implications when using 2D rule tiles as opposed to just basic sprites.

[@tarck333333rrrr]

Nice breakdown, thank you!

[@CadeVoidlighter]

Excellently made video!

[@AssortedFern]

Overlapping seems like a neat way to get desired patterns, but overly constrained. With WFC you can use constraints to ensure that only valid topologies are generated, and then use weights to make the output look more like the desired input (maybe using 2x2 or 3x3 example patterns). The weights can be dynamic too - I once made a maze generator that would alternate from horizontal to vertical obstructions as a function of X and Y.

[@dvgen]

Ooo, thats a neat approach. Rob Lang, from Clomper, alters weights as a function of biome, which is such a simple and obvious approach, but one I never considered before. I'll have to think more about the cases where dynamic weights would be useful. I think the first outside WFC/MS constraint I want to formally implement is reading an approximate height value from a texture. I have parts of that working already. But I'd love to be able to feed in some nice noise and erosion algorithms I already have to get things started.

[@Pfaeff]

I love how this comment section already contains some great ideas. I'd love to play around with WFC at some point if I find the time.

[@dvgen]

@@Pfaeff I know, right? I already started a set of notes and ideas just from this video's comments.

[@Void-vn2vf]

This is really inspiring. Thanks !

[@the0neskater]

Great video, for your interest (and others) on constraint solving & problems, I'd highly highly recommend looking into Sentient (a programming language), which is a built in logic constraint solver, allowing you to write programs that define the constraints of your problem and the language itself will solve it. Super cool!

[@escher4401]

It would be interesting to see the intersection between these kinds of procedural generation and Neural Radiance Fields. If someone combines this with a way to infer constraints based on input it would be a good way to generate infinity dream-like worlds from photos.

[@dvgen]

Neural Radiance Fields were new to me, and I have to say, wow that is an impressive technique! I understand the data structure, but not much more than that, so I'm not sure how constraint techniques could be used with something like that. It would be a good question for someone that knows more about it. I'll have to read more on it. Thanks for the suggestion.

[@darkfafi]

Absolutely love the insights! The music along with your comfortable narrative makes it a pleasure to watch! I will look into each of the papers respectfully. While watching the video I was thinking that with the linear approach, you also face the risk that some constraints are never met. Such as a constraint that requires a specific element above it. If you generate from bottom to top, that constraint is never met. And so various constraints could never be met with various generative methods. How do you look at this dependency of execution? The low Entropy at some stages may occur simply because the generative method limits the algorithms full potential.

[@dvgen]

Thanks. I'm glad you liked it. You might be right about the linear approach. For the module sets I was making, the linear approach seemed to be a bit less prone to error, but I don't have a good way to quantify that. The modules used do matter a lot. I had not considered it before, but it sounds very reasonable that certain linear iteration orders could interact with the types of constraints you have.

[@Imevul]

One option for error handling with WFC might be to assign the least offending tile to the invalid cell, and then propagating changes out from that one to overwrite surrounding tiles until a satisfying solution has been found. Can even introduce a max propagation size for the error correction, and restart with the next least offending tile if it should fail, or if the number of invalid cells could be partially reduced just restart with the new set of cells. Not sure if it will work though. Just an idea. I'm not an expert, but the problem with invalid cells screams Four Color Theorem at me for some reason.

[@dvgen]

That sounds like a smart idea. I don't recall anyone implementing that specifically, but I would not be surprised if someone tweaked the algorithm to prefer a least offending module.

[@Ryrzard]

Instead of assigning weights to the tiles from the tileset, you could assign weights to the neighbour constraints of each tile. This way you can also generalise constraints by having forbidden neighbours have a weight of zero. I think this approach may enable you to generate less uniform and chaotic maps/terrain. Especially when using a varied tileset containing more than 1 biome. For example, if you have a forest, sand and water tileset, the sand/grass neighbour rule would have a much lower weight than a grass/grass or grass/tree rule so random patches of sand and water are less likely to generate in the middle of a dense forest. If you have large enough example maps to generate the rule sets you could also generate those weights by analysing what tiles are likely to appear next to other tiles. Or even include directions to make the maps less isotropic.

[@dvgen]

I've gotten a few comments like this, and I've had some of the same thoughts. It might be something I try later. I can sort of imagine how to develop the code, but I also wonder if it would really create a substantially different feel to generation. Intuitively, I would think it should. But the right adjustments of module weights might still end up creating something similar.

[@leimiles18]

Awesome, expecting the next video

[@dvgen]

Glad you like it, and I'm actually working on it now. :)

[@noahschenk5399]

Love the explanations, when will we see that implementation, I have been trying and struggling with my own, would love to so how you did it!

[@lesliejohnrichardson]

God damn this is a wonderfully informative video

[@Mathenarus]

At 23:18 when you talk about having a hard time deciding between 2d and 3d, an idea occurred to me (that I'm sure has been had and implemented) about using a generated 2d space to inform the generation of the same space in 3d. Like making a map, then using that to build the world I guess? I suppose the same could be done in reverse, using the 3d space to inform the 2d generation. Bit random, but interesting - a bit like your video showing up in my recommendations! 😅

[@Jebula999]

I've climbed on the game dev bandwagon quite recently, Fell down the rabbit hole of world gen. Came across your video and the result you get at 23:40 is AMAZING and would love to have something similar in Godot. Been trying to find information on how to implement on Godot but the info is scarce. I got excited when you mentioned you will do a walkthrough and share your code in your next video, then I saw this was posted +- 10 months ago 😭 Will an update to this video still be coming out?

[@forty42two]

Thank you very much for the interesting video! I am looking forward to the opportunity to experiment with your code myself.

[@Cormorant42]

20:49 There's a much simpler way to solve the failure to generate problem: have a tile that fulfills all constraints, or, in other words, a "default" tile that can work with everything.

[@dvgen]

That is a great point, and one that some variants of modifying in blocks build upon. Often its a default section, not just a default tile. I'm going to add that to my wishlist of features.

[@dylancope]

Really excellent video!

[@dvgen]

Thanks, glad you liked it!

[@Ziraya0]

There's a really interesting tiny nuance to minesweeper that's maybe somehow at a stretch relevant to the video. When you click the first time on a board, in any competent minesweeper program, that cell is guaranteed to be empty. You can't hit a mine right out the gate, because that wouldn't be fun. So the board cannot be set before you have clicked. You could do something like generate a board then shift & wrap it so that your click is a random valid first square; but also it's not very hard to generate a small 2D array of booleans and compute the adjacency values on the fly when revealing cells. You could use that first click as a seed in a wave function collapse, setting it to a random valid first adjacency value and finding where the mines should go. That method would need to do something I've not seen yet, which is add global factors to the wave function resolution; you can only have 10 mines, you're not allowed to collapse a board and find an 11th mine along the way. Expanding on that, in high level play the complexity of the board is judged by an analysis called 3BV which put simply is count all isolated zones of contiguous 0s, including the directly adjacent non-zero cells, plus all the non-zero non-mine cells which are not adjacent to a 0 cell. In the super easy mode example your 3BV is 1, you have 1 zone of 0s, and nothing else. You won't win any world records with a 3BV that low. The current world record according to the site you go to if you care about this, for the fastest, highest 3BV beginner board is a 3BV of 10 in 9.09 seconds. Using global factors, one might be able to make a board generator that produces a designated 3BV on demand

[@amirhm6459]

thanks for the video, learning a lot from this. Want to implement wave function collapse for my proc gen

[@cameron6464]

It would be so cool to see someone create a relation tree of letter combinations to run through the wave collapse function to see what kind of regular words it can put together.

[@1DemiRaven]

This is a very interesting video with a lot of knowledge. Unfortunatly some of the math and nominclature are over my head. But this gives me some excitement and hope for my own personal project. Im curious how you would incorporate this into something like caves, and also as you mentioned, with water. Mostly flowing rivers. Thank you very much for sharing.