Procedural Generation with Wave Function Collapse and Model Synthesis

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

Рік тому

In this video, I discuss the technical details of the Wave Function Collapse algorithm, and the closely related predecessor, Model Synthesis. I really enjoy both of these algorithms, and like many, I actually use parts of both in my projects. Stick around for more details on implementation in later videos. For now check out the resources below.
Follow me on Twitter.
/ _dv_gen_
Constraint satisfaction wikipedia article.
en.wikipedia.org/wiki/Constra...
Sudoku as a constraint satisfaction problem.
/ solving-sudoku-think-c...
Minesweeper as a constraint satisfaction problem.
lvngd.com/blog/solving-minesw...
Wordle as a constraint satisfaction problem.
towardsdatascience.com/how-to...
Constraint satisfaction techniques in planning and scheduling.
link.springer.com/article/10....
Cognitive dissonance reduction as constraint satisfaction.
psycnet.apa.org/record/1996-0...
BenzAI: A program to design benzenoids with defined properties using constraint programming.
www.researchgate.net/publicat...
Harnessing constraint programming for poetry composition.
helda.helsinki.fi/bitstream/h...
Finding alternative music scales.
public.tepper.cmu.edu/jnh/scal...
Texture synthesis wikipedia article.
en.wikipedia.org/wiki/Texture...
Alexi A. Efros's page on texture synthesis.
people.eecs.berkeley.edu/~efr...
Michele Conni's review of recent advances in texture synthesis.
• Recent advances in tex...
Paul Merrell's website on model synthesis.
paulmerrell.org/model-synthesis/
Maxim Gumin's wave function collapse github.
github.com/mxgmn/WaveFunction...
Cainos pixel art tiles.
cainos.itch.io/pixel-art-top-...
Wikipedia article on Shannon information entropy.
• Entropy and Time
Paul Merrell's video on thermodynamic entropy.
• Entropy and Time
Wikipedia article on arc consistency.
en.wikipedia.org/wiki/Local_c...
Boris the Brave's article on arc consistency.
www.boristhebrave.com/2021/08...
Wikipedia article on backtracking.
en.wikipedia.org/wiki/Backtra...
Boris the Brave's article on modifying in parts.
www.boristhebrave.com/2021/10...
Marian Kleineberg's article on infinite wave function collapse.
marian42.de/article/wfc/
Marian Kleineberg's twitter.
/ marian42_
Rob Lang's Clomper devlog discussing infinite wave function collapse.
• Infinite Wave Function...
Boris the Brave's wave function collapse / model synthesis asset for Unity. This was used to demonstrating some features I have not yet implemented.
assetstore.unity.com/packages...
Boris the Brave's DeBroglie wave function collapse / model synthesis C# library.
github.com/BorisTheBrave/DeBr...
Music:
Pamgaea by Kevin MacLeod
Free download: filmmusic.io/song/4193-pamgaea
License (CC BY 4.0): Standard License
Out Of The Blue by Purrple Cat | purrplecat.com
Music promoted by www.free-stock-music.com
Creative Commons / Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0)
creativecommons.org/licenses/...
The Life and Death of a Certain K. Zabriskie, Patriarch by Chris Zabriskie is licensed under a Creative Commons Attribution 4.0 license. creativecommons.org/licenses/...
Source: chriszabriskie.com/vendaface/
Artist: chriszabriskie.com/
Moonrise by Reed Mathis
UKposts Audio Library
Music: Floating Cities by Kevin MacLeod
Free download: filmmusic.io/song/3765-floati...
License (CC BY 4.0): Standard License
Jellyfish in Space by Kevin MacLeod is licensed under a Creative Commons Attribution 4.0 license. Creative Commons - Attribution 4.0 International - CC BY 4.0
Source: incompetech.com/music/royalty-...
Artist: incompetech.com/
Intuit256 by Kevin MacLeod is licensed under a Creative Commons Attribution 4.0 license. Creative Commons - Attribution 4.0 International - CC BY 4.0
Source: incompetech.com/music/royalty-...
Artist: incompetech.com/
Music: Deep Haze by Kevin MacLeod
Free download: filmmusic.io/song/3633-deep-haze
License (CC BY 4.0): Standard License

КОМЕНТАРІ: 331

@lm5050 6 місяців тому

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. 10 місяців тому

Thank you!

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

@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 ukposts.info/have/v-deo/ZX6QiIp4qpqJyJs.html 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 10 місяців тому

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

@PaulMerrellResearch 10 місяців тому

@@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.

@greysion 11 місяців тому

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.

@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 ukposts.info/have/v-deo/ZX6QiIp4qpqJyJs.html 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 6 місяців тому

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.

@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!

@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!

@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.

@OxAA00 2 місяці тому

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!

@redlogicp3223 6 місяців тому

Your video quality is absolutely incredible. Keep it up!

@tenthlegionstudios1343 10 місяців тому

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 10 місяців тому

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.

@lsf3og 10 місяців тому

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

@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.

@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.

@Karlthuluu 2 місяці тому

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

@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._ :)

@electroAU 8 місяців тому

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 😢

@sebastiendeseille9890 4 дні тому

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

@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 Рік тому

🤣

@tetronym4549 11 місяців тому

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

@dvgen 11 місяців тому

🤣 I knew there had to be others.

@Beefman951 8 місяців тому

Cant wait for next video, great content

@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.

@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.

@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.

@scottcourtney8878 5 місяців тому

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 5 місяців тому

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.

@unitycoder 8 місяців тому

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

@TheGreatLaveen 11 днів тому

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

@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.

@jarrettonions3392 3 місяці тому

This is an amazing video on such an interesting topic!

@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

@NickMaxwell Рік тому

Phenomenal presentation! Thank you for the education.

@the_primal_instinct 10 місяців тому

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.

@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.

@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.

@TheHombresinombre 8 днів тому

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.

@ChronoWrinkle Рік тому

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

@dvgen Рік тому

Thanks, I'm really glad you liked it.

@jumbledfox2098 10 місяців тому

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

@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.

@Cheeseington 11 місяців тому

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.

@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.

@resdek2246 3 місяці тому

This video is awesome. Please keep making them.

@emjizone 9 місяців тому

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 6 місяців тому

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

@GameDevBox Рік тому

Your videos are a hidden gem and thank you

@pepperminty-joe Рік тому

This is so well explained, thank you so much.

@canertwo Рік тому

Literally never clicked so fast. You are amazing!

@dvgen Рік тому

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

@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.

@vek8171 Рік тому

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.

@vek8171 Рік тому

@@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 Рік тому

@@vek8171 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!

@bobov99 Рік тому

Love this channel! Keep up the great work

@dvgen Рік тому

Thanks! Glad you enjoyed it.

@tarck333333rrrr 5 місяців тому

Nice breakdown, thank you!

@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!

@DerSolinski 4 місяці тому

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 👍

@BleachWizz Рік тому

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

@user-fn8wl8de9f 2 місяці тому

Amazing! Waiting for the next video

@sergodobro2569 Рік тому

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

@dvgen Рік тому

I'm really glad you enjoyed it!

@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.

@user-sl6gn1ss8p 11 місяців тому

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

@dvgen 9 місяців тому

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

@darkomen4343 8 місяців тому

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.

@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.

@CadeVoidlighter Місяць тому

Excellently made video!

@TheImpostenator Рік тому

so glad the how its made narrator started making devlogs

@dvgen Рік тому

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

@Void-vn2vf 11 місяців тому

This is really inspiring. Thanks !

@BismuthBorealis 2 місяці тому

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

@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!

@Timo.ohohoh 11 місяців тому

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

@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.

@VioletGiraffe Рік тому

Amazing video and overview!

@amirhm6459 7 місяців тому

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

@noahschenk5399 10 місяців тому

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!

@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.

@lesliejohnrichardson 10 місяців тому

God damn this is a wonderfully informative video

@EEEdoman Рік тому

I was so excited for the next video and you didn't disappoint! Also, love the turtles, are you studying herpetology? Cheers!

@dvgen Рік тому

I'm really glad you enjoyed it. I grew up as an amateur herpetologist. It was my first love. In addition to the sliders, I have some box turtles, rat snakes, and a sulcata tortoise. I'm a massive fan of frogs, and I go visit breeding choruses as often as I can, but I haven't kept any in a long time. I ended up working with birds a lot at zoos, and then insects a lot during my phd. I actually research behavior and learning at a comparative level, so anything goes, but I often trend towards the animals that receive less attention in research. I think I would be happy studying learning in bugs and reptiles. There is a lot to learn there.

@Sofia-rh7ji 10 місяців тому

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 9 місяців тому

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 6 місяців тому

@@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.

@cameron6464 5 місяців тому

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.

@TimmyChUwU Рік тому

Watching this video and your last video made me inspired for my own game. I wanted something that wasn't quite blockey voxel in it's generation but related to it with using Wave Function Collapse. The game would be an RTS/City Management game similar to Rimworld or Stonehearth, and the game would be in 3D. I'd like to go for that idea at some point but I am a complete novice at programming so it's unlikely to happen. I love to model though so I wonder if using existing generation code with Model Synthesis and Wave Function collapse and model my own components would be an effective strategy. I also wonder how well it would deal with caves and cliffs with either algorithm for 3D generation, since Dwarf Fortress is able to do it in 3D space. Thanks for the information you've shared! These videos are truly fascinating and inspiring and make me want to try to learn more about programming to achieve this.

@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!

@forty42two Рік тому

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

@ZadakLeader Рік тому

Perfect Sunday afternoon

@dvgen Рік тому

Could only be improved by more sleeping in :)

@ashersaipe Рік тому

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

@dvgen Рік тому

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

@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.

@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.

@itsSparkky Рік тому

Old comment was deleted, but you might appreciate the anecdote. When I worked on the dragon age keep (I think the url link was what caused my comment to be deleted) I used constraint satisfaction to be able to take 0+ of the players answers and generate a valid world state. Every answers is constrained by being the only answer to a question, and most answers are constrained by a variety of other choices in the game. It took a lot of work to restructure the game's decisions into a list of constraints but once it was working we were able to update the save state in real time, in the browser, despite there being iirc more valid world states than grains of sand on the planet. I had no idea what it was called at the time, it was just the only thing I tried that was even close to being able to handle the task in real time on a browser... and it handled it with time to spare lol!

@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.

@escher4401 10 місяців тому

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 9 місяців тому

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.

@MatterFlow Рік тому

Interesting. I have my own solution to Error Handleing besides the "try again" and "try again in parts". Maybe it's about entropy too. If i don't have a fitting tile, i check what neigbour has the most other "potential variants" and at the same time knocking it out will allow me to fill current tile. So this neugbour tile goes into queue once again, but as a result i did fill the most "problematic" one. This starts a cascade of "fixes" around the problem tile, but it often fixes itself very fast - in 2-5 iterations. Yes, this involves memory for each tile to not go into infinite loop of fixes, but it worked for me.

@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! 😅

@thomasbjarnelof2143 Рік тому

I am (slowly) working on a 4D (x,y,w,time) Procedural "Random" Generation world generation game using "rip up and retry". Time travel makes it really wired to try to remember where and when you where and to avoid paradoxes. Manipulating an object that have been manipulated in a later time results in a "time quake".

@dvgen Рік тому

You are blowing my mind a little. That sounds really interesting. I definitely want to hear more about that when it gets more developed.

@denisgoodman4492 5 місяців тому

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 5 місяців тому

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 5 місяців тому

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

@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

@leimiles18 Рік тому

Awesome, expecting the next video

@dvgen Рік тому

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

@dylancope Рік тому

Really excellent video!

@dvgen Рік тому

Thanks, glad you liked it!

@Queer_Nerd_For_Human_Justice 10 місяців тому

Interesting!

@Genubath1 Рік тому

It would be interesting to see how well AI would be able to make modules for these approaches. One would probably hand craft the more important and common models and AI would help solve the edge cases which can cause constraint errors. For a 2D implementation, the "Modifying in Blocks" function reminds me of Stable Diffusion's inpaint function, which basically "fills in the blanks" that you define in an image. If something like Nvidia's omniverse products could be used for 3d modules in a continuous model synthesis implementation, that would have staggering potential. This also follows that prompts could be used as constraints. A vector database with environmental embedding (Computerphile has a good video on this called "Vectoring Words (Word Embeddings)") could be used to make complex "prompt modules" for AI to generate. AI aside, it might be a good optimization to make a vector database of the relationships and weights between different modules. P.S. I'll probably come back with edits to make this coherant because it is late at night/early in the morning as I write this 🙃

@dvgen Рік тому

You are blowing my mind a little. I agree, modifying in blocks is a little bit of an infill approach. And that approach could also be useful for real-time editing. Probably the best I will make of AI in this case is some help generating visuals and cleaning up some basic code, but there is a lot of greater potential.

@AnotherDuck 2 місяці тому

I'm not even close to start writing code for generated areas (and what I'm currently working on is text-based anyway), but learning new stuff is always interesting.

@Spy653 Рік тому

Worth the wait!

@dvgen Рік тому

Glad you liked it. I'm hoping less waiting in the future though :)

@Spy653 Рік тому

@@dvgen I'm not bothered by wait time for quality content. Personally the thing I think is missing from many similar videos on advanced theories is an actual shown code implementation. Do you plan on going into code specifics or focusing on the supporting theory?

@dvgen Рік тому

@@Spy653 Yep, that is the next one. I'm going to post the code and do a walkthrough, both of use and of the code, but I'm not going to make it a step-by-step tutorial where I write the code during the video. I just have to remove a paid asset (Odin Editor) from my code a clean a few things up first. I'm hoping to hit a good level of usability for people that know how to code a little, but need help with something like this.

@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.

@Jebula999 2 місяці тому

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?

@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.

@Scrogan Рік тому

I wonder if that “modify by blocks” process in model synthesis would look smoother if instead of squares it were done with Gaussian distributions. The value of the distribution at any point would be the probability of regenerating it. Not sure how much you’d overlap them. A Gaussian overlap for a wave function collapse might be a way of eliminating bias towards X/Y patterns as opposed to diagonal patterns, though I’m not sure if that’s an issue.