ฝัง
- เผยแพร่เมื่อ 15 เม.ย. 2023
- 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
TH-cam 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 - เกม
![ไม่ต้องมีที่ที่ให้ฉันอยู่ แต่ขอแค่มีฉันอยู่ก็พอ (Spaceless) - getsunova [SHORT FILM]](http://i.ytimg.com/vi/MuT0d_cvJkc/mqdefault.jpg)
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!
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.
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.
@@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.
@@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.
@@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
@@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.
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
Thank you!
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 th-cam.com/video/-N_TTAsdXgg/w-d-xo.html and Section 3.4.2 of my dissertation.
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.
Are you telling me 4D space can be used to store the equivalent of a "sprite sheet" for 3D models?
@@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.
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 !
Glad to have you here again! You found my channel at a good time I think :)
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.
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 th-cam.com/video/-N_TTAsdXgg/w-d-xo.html and Section 3.4.2 of my dissertation."
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.
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.
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!
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.
@@dvgen I can't wait to see it!
I have close to zero skills in programming. But I could watch this for days. So interesting. Thanks
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!
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!
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!
Your videos are a hidden gem and thank you for the interesting information! Looking forward to what else is in store
Thanks, I'm glad you enjoyed it.
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
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.
@@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
Another nice solution.
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!
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.
Your video quality is absolutely incredible. Keep it up!
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.
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.
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
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.
This is one of the best and most interesting videos on procedural generation I've seen.
That is a huge compliment. Thanks! More to come.
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.
Hello, I just finished your vlog on Procedural Generation. I really appreciated your explanation of the algorithm. Thank you very much.
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._ :)
Wow man, last part is so inspiring, thank you for great content!
Thanks, I'm really glad you liked it.
Phenomenal presentation! Thank you for the education.
Literally never clicked so fast. You are amazing!
Thanks for that. This comment puts a smile on my face.
Great video! Looking forward to seeing your code and implementation! Especially looking forward toward how you handle entropy!
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 😢
Oh my god that "large mindsweeper grid" thing just punched me through time and I flew back to my childhood.
🤣 I knew there had to be others.
Best educational video in TH-cam! 🏆🏆🏆 *and i've watched (or tried to watch) thousands of them..
This is amazing! You've done a lot of research, this is like listening to a quality conference talk. Also, 🐢!
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, 🐢 🐢!
@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
@@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.
Love this channel! Keep up the great work
Thanks! Glad you enjoyed it.
Love the video, you are great at explaining! Thank you for teaching us!
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!
Thats pretty impressive for high school! I barely knew anything about programming back then.
@@dvgen Thanks :) The things kids do to make Minecraft mods! lol
This is an amazing video on such an interesting topic!
Wow! This was useful! And the explanation is very good! I love such videos!
I'm really glad you enjoyed it!
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
Very interesting dive, thanks for taking me on this journey!
Glad you liked it! I was a little worried this might be too technical compared to my last one.
@@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.
@@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!
This video is awesome. Please keep making them.
so glad the how its made narrator started making devlogs
Hahahah. I used to think he sounded like John Goodman.
This is so well explained, thank you so much.
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.
Your videos are a hidden gem and thank you
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.
I love this video, youtube make me watch it every few week ^^
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.
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.
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.
Amazing! Waiting for the next video
Nice breakdown, thank you!
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.
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.
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.
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.
Excellently made video!
Cant wait for next video, great content
Perfect Sunday afternoon
Could only be improved by more sleeping in :)
This video has been really interesting to me, and I think I might get into wfc for a personal project. Tomk tomk!
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.
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!
This is really inspiring. Thanks !
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!
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.
awesome dude.
I was thinking... applying the modifying in blocks with the wave function algorithm sounds very trivial
great video bro! once again, really interesting :))
Thanks, I'm glad you liked it. :)
Amazing video and overview!
God damn this is a wonderfully informative video
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!
Thank you very much for the interesting video! I am looking forward to the opportunity to experiment with your code myself.
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.
Really excellent video!
Thanks, glad you liked it!
Awesome, expecting the next video
Glad you like it, and I'm actually working on it now. :)
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.
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.
How do you insure that the new rules learned are true rules and not by chance?
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 👍
thanks for the video, learning a lot from this. Want to implement wave function collapse for my proc gen
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.
Haha, thats great. I didn't know about that. I can totally see myself doing that as a kid.
I wish half the channels dealing with science would cite their sources as well as this : )
I teach, so I would feel like a hypocrite if I didn't!
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
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.
@@dvgen Will be interesting to watch a code implementation (may be simple example) of wave function and Model Synthesis in Unity ()
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.
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.
I was so excited for the next video and you didn't disappoint! Also, love the turtles, are you studying herpetology? Cheers!
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.
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!
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
🤣
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.
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!
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.
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.
@@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.
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.
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.
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.
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.
Worth the wait!
Glad you liked it. I'm hoping less waiting in the future though :)
@@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?
@@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.
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.
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.
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.
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.
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.
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.
@@Pfaeff I know, right? I already started a set of notes and ideas just from this video's comments.
Man, you don't upload often! See you in 2024!
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! 😅
Interesting!
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
완전히 이해는 못 했지만
대략적인 개념은 배워 갑니다.
This was an interesting watch, thanks youtube algorhythm
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!
Ttomk tompk for the detailed explanation
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.
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.
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 🙃
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.
Hi your videos about prosedural 2d stuff are awesome!
Did you consider explaining how colisions would work in prosedural generation 2d?❤
Basically, they would behave the same as in manual 2d generation: if the tile is passable, then the player gets to pass on it.
Even if you think of some Z-level tiles (that makes your game 2.5D-like), the actual collision is baked in in the tile itself, only difference I can think of is that it isn't specifically handplaced, it just apears to also satisfy some Z-level constraints at this location. (That Z-level notion may lead to a lot of generation failures, but, hey, constraints are what they are: constraints. You would face the same while manually placing things with said constraints in mind. Though *you* are not tied to those contraints, you can decide to teleport a player in an unreachable location via scripting, and/or place arbitrary unconstrained or overconstrained tiles. Hence, tile generators behave exactly same as constrained manual 2d generation.)
i would love if you did a in depth video for falling sand simulations in unity