I've seen one or two videos on wave function collapse before, and it's always been one of my favourite ways to generate terrain. Definitely glad to see one of my favourite TH-camrs using it in a real project
I absolutely love using WFC as a means of world generation! I've always wanted to do this in my voxel game, but each dimension makes the algorithm exponentially slower. I'd definitely look into using it with an LOD perspective; stuff like biome meshes can be generated first in low detail and rendered as a placeholder while structures and environment details are generated in the background.
you could maybe also try an approximate approach - collapse/propagate some of the wave elements and use that as an LOD while saving the data for when the player moves closer? 🤔
yea i’ve thought about this for a game i’d like to make eventually. start out with low detail plate tectonics sim for planet-scale coherence, then use wfc to refine the base height and roughness a bit, then figure out biomes, then further refine height and roughness using biome info as well, then do stuff like individual mountain peaks, valleys, small lakes, etc, then probably another pass for final features (still above the scale of individual voxels), and then get a smooth voxel output of the terrain for most stuff with either wfc or noise for detail on rougher areas
Use layers of WFC. Im working on a game that you start as a quark and the cause / effect generates a playable universe where you can "control" anything. But WFC is not "slow" just stop trying to do everything in a superfunction. break up your 1 WFC into 50 different smaller ones and only run them as you actually need them. I am able to process literally TB worth of data like this in real time. Theoretically scaling up to PB via cassandra.
i didn't understand a single thing because all of this is way above my level, but i still watched the whole thing because good music and code flashing across screen
Wave Function Collapse has actually existed for decades. Age of Empires and Starcraft both used a similar technique in their map tile selection. It just hadn't been named until a couple of years ago.
I'm making a AOE style game and use Perlin noise. Because IM better
2 ปีที่แล้ว +301
People that don't code are being tricked into thinking people code an entire program like this without testing its small pieces a thousand times throughout the process (and at times changing the logic multiple times half-way through haha)
@@player111q7 He just has put lots of hours into doing it so he doesnt need to double check anymore. It takes lots of effort to get to this level dont just play it off "yeah he is smoret boi lkr dog"
@@branthebrave It helps to know that practice makes perfect here. My first programs were relatively simple ones that didn't work as I expected them to. Right now, I can write 1000~2000 LoC of relatively simple logic (low cyclomatic complexity, no recursion) without any mistakes. For code that's heavy on while loops with undefined iteration count, recursive functions (esp. not pure ones), and heavy maths (optimization and whatnot), I still need to think a lot (pen and paper, as jdh shows himself doing in this video) before I write it, and I usually still miss one or two edge cases.
I spent some time with this algorithm myself. It's deceptively simple once you understand what's going on but man when you start getting into the third dimension the thing bogs down hard. Hard enough that I'd probably advocate for pregenerating many random iterations from it in development instead of generating it during end user gameplay.
yeah it can get very slow, especially for larger pattern sizes (size 3 -> size 5 more than doubles the time to process each pattern 😬). I've tried parallelising it without success in making it noticeably faster, but pregenerating is definitely a good solution, maybe even storing many partially-collapsed datasets and then doing the last bit of process on demand and with a little bit of randomness.
Isn't that a bit of the excitement that comes along with the thought of quantum computers? When we can cost effectively compute and render 3+ dimensional wave collapse algorithms in real time the kind of expansive interactive digital content we will be able to create will be WILD.
@@tendies Tbf, I'm fairly certain its not an original thought lol. I can't remember for sure, but I vaguely remember reading an article somewhere a couple years ago about the unique possibilities for applications of quantum mechanical computational systems beyond just search algorithms like Shor's or cryptography that is typically discussed, and the usefulness of realtime higher dimensional wave collapse algorithm computation is the one that really stuck with me. Of course what I'd latch onto is how it could help make better games lol
I love your style if presentation. Judging from your previous videos I expect you going down this rabbit how and designing your own quantum computer doing wave function collapse on breadboards :P
For a second there I thought you were going to say "I need a physics engine and the best way to do that is from scratch. So here's how I implemented quantum mechanics..."
Your game is really coming together! It looks amazing already and I can’t wait to see what else you have to implement and the furthering of your terrain generation process.
It's nice to see more progress since the serializer stream. I've been looking more into C/C++ since then, but concepts (the C++ thing, not concepts as in "ideas") still confuse me. Looking forward to the next video in two months!
I find it really interesting that you went back to oop approach after you initially started with it then transitioned to entity component. Makes me realize why its there in the first place
@@jdh Soon™. I got a little delayed taking a second job this summer. Also I get distracted by the technical details, so it is going to have to be a couple of videos. I'll link back to your video one when I talk about implementation.
I tend to prefer levels design that's not randomly generated, but I have a black and white pixel tileset I had spent weeks creating a ton of cool and complicated geometric designs and structures and variations. Kinda got stuck moving on to creating actual level design with them though, but I think I'll use WFC to construct a bunch of potential level layouts- and I'll take the most promising ones and build more handcrafted levels again from there! I went wild creating a ton of elements I don't have a specific plan for, but I think this algorithm will at least present me with combinations I may not have expected that I can make what I want out of!
I have no earthly idea what's going on in this video but I still somehow find it interesting. I really love this type of game and seeing the actual work that goes into making it happen makes me even more interested in it. Can't wait to see the finished product.
I'm starting my first year at university in a couple of months and I have no clue what the things you said mean. I'll come back to this video again when I know more stuff and see if I can understand lol
THANK YOU FOR CREATING THIS I SPENT WAY TO LONG TRYING TO DO SOMETHING LIKE THIS AND FAILING. this video very well explains a topic that I had trouble with.
I think this algorithm could quite easily be modified somewhat to dictate the overall shape of the entire map by modifying the function that chooses which pattern to collapse a cell into. Say you want to create an objective for a dungeon map (the dungeon map is just a full size image like the ones you generated), and want it to be somewhere in the middle. You can simply look at the distance from the map border when looking at a cell to collapse, and make it so that the further away from the border it is, the higher the chance for it to collapse into the objective. You could even make a minimum distance from the border to become a particular type of cell. You could also overlay a noise map onto the entire grid and vary the chance of a cell's collapse based on the value of the noise map in that spot. Imo, that would be really interesting and (should be) possible to program.
I'm working on a roguelike shooter and we're doing that by doing 2-3 levels of WFC generation. Each level defines the tileset/example bitmaps for the level below it.
Can you do a video explaining why you abandoned the ECS in favor of the standard OO approach? From my understanding you can have both with a Component?
I really like the effect fading out the wall in chunks gives! One thought I had was that it would be cool if instead of just the walls immediately around the player, walls the character is facing (up to a certain distance) would also fade so you don't need to run along the entirety of a back wall to see what's hidden behind it.
This might be a huge task, but the blinking light on your characters head, it would be an amazing way to ray tracing / some kind of ambient lighting to add some immersion to your levels, right now his headlight seems a bit too distinct from its surroundings
I've been working on an implementation recently as well. I decided it would be interesting to take the famous dancing links (DLX) sudoku solver and attempt to use it for constraint solver in WFC
The non-descriptive template parameters with the comments describing what they are made me cry.. why not just name them something similar to that TYPE, DIMS (maybe even DIMENSIONS) PATTERNS, BITSETS ?
12:19 Did you code a visualisation to visualise coding. Very cool - you made the coding part just as compelling as the visual as it was easy to follow along.
Im deeply interested in this procedural generation techniques but the more games i play where the map was designed by a person the more i wish we would have more games like that.
Just a suggestion regarding the player visibility through walls. If you are making a mask of the player, why do the extra step of raycasting when you can just overlay the player sprite over everything with a bit of transparency. Also, awesome vid, learned a lot! :)
hey jdh! your videos are aewsome and insipiring, I have always wanted to tinker with a lot of the stuff regarding computer science such as the stuff you do on this channel but a big problem I usually face is the lack of math knowledge and for me a 16 yo guy these stuff can seem aggravating so can you tell where and how can I learn the neccessary MATH needed for CS? and THx
I still can't stop marveling your coding skills, it seems impossible. Like how could you think of the whole WFC algorithm implementation and code it real time, it takes me many tries and iterations to code even a simple algorithm, i can't keep it all in my mind all at once
This is awesome, love the series! I was wondering - you mention you wrote an 'ultra fast mesh instancer' - in terms of speed/optimisation of code is this something you simply learned over time or are there key principles that you follow when writing your code to make sure you are always writing optimally? Cheers!
A beginners guide to making your first simple game!
Chapter one: quantum physics
You made me lol xD
Chapter 2: Probabilistic String Theory
Chapter 3: Relativity
😂😂😂
Chapter 4 Subatomic Quantum Mechanics
I've seen one or two videos on wave function collapse before, and it's always been one of my favourite ways to generate terrain. Definitely glad to see one of my favourite TH-camrs using it in a real project
so who's one of your favourite youtubers than?
@@someonewithsomename jdh
@@gachastorys5129 smc
Jdh: "I wanna generate new content without having to do Much Work"
Also Jdh:
@Creepi why waste 10h manually doing the work when you can write a program in 10h that will do that work in 2 minutes
@@bosch5303 More like 5h of manual work saved. Or 2h. But that's how we be. xD
I absolutely love using WFC as a means of world generation! I've always wanted to do this in my voxel game, but each dimension makes the algorithm exponentially slower.
I'd definitely look into using it with an LOD perspective; stuff like biome meshes can be generated first in low detail and rendered as a placeholder while structures and environment details are generated in the background.
you could maybe also try an approximate approach - collapse/propagate some of the wave elements and use that as an LOD while saving the data for when the player moves closer? 🤔
yea i’ve thought about this for a game i’d like to make eventually. start out with low detail plate tectonics sim for planet-scale coherence, then use wfc to refine the base height and roughness a bit, then figure out biomes, then further refine height and roughness using biome info as well, then do stuff like individual mountain peaks, valleys, small lakes, etc, then probably another pass for final features (still above the scale of individual voxels), and then get a smooth voxel output of the terrain for most stuff with either wfc or noise for detail on rougher areas
Use layers of WFC. Im working on a game that you start as a quark and the cause / effect generates a playable universe where you can "control" anything. But WFC is not "slow" just stop trying to do everything in a superfunction. break up your 1 WFC into 50 different smaller ones and only run them as you actually need them. I am able to process literally TB worth of data like this in real time. Theoretically scaling up to PB via cassandra.
i remember going down the wave function collapse rabbit hole a while ago, i was surprised at how ingenious it was
same
basil pfp tho
i didn't understand a single thing because all of this is way above my level, but i still watched the whole thing because good music and code flashing across screen
jdh Is an Indie GOD Developer. You keep impressing me with each and every single video that comes up.
Wave Function Collapse has actually existed for decades. Age of Empires and Starcraft both used a similar technique in their map tile selection. It just hadn't been named until a couple of years ago.
I'm making a AOE style game and use Perlin noise. Because IM better
People that don't code are being tricked into thinking people code an entire program like this without testing its small pieces a thousand times throughout the process (and at times changing the logic multiple times half-way through haha)
He's just smart
@@player111q7 He just has put lots of hours into doing it so he doesnt need to double check anymore. It takes lots of effort to get to this level dont just play it off "yeah he is smoret boi lkr dog"
Good, I need every ego boost I can get.
He's already made this, like he said
@@branthebrave It helps to know that practice makes perfect here.
My first programs were relatively simple ones that didn't work as I expected them to. Right now, I can write 1000~2000 LoC of relatively simple logic (low cyclomatic complexity, no recursion) without any mistakes. For code that's heavy on while loops with undefined iteration count, recursive functions (esp. not pure ones), and heavy maths (optimization and whatnot), I still need to think a lot (pen and paper, as jdh shows himself doing in this video) before I write it, and I usually still miss one or two edge cases.
I spent some time with this algorithm myself. It's deceptively simple once you understand what's going on but man when you start getting into the third dimension the thing bogs down hard. Hard enough that I'd probably advocate for pregenerating many random iterations from it in development instead of generating it during end user gameplay.
yeah it can get very slow, especially for larger pattern sizes (size 3 -> size 5 more than doubles the time to process each pattern 😬). I've tried parallelising it without success in making it noticeably faster, but pregenerating is definitely a good solution, maybe even storing many partially-collapsed datasets and then doing the last bit of process on demand and with a little bit of randomness.
Isn't that a bit of the excitement that comes along with the thought of quantum computers? When we can cost effectively compute and render 3+ dimensional wave collapse algorithms in real time the kind of expansive interactive digital content we will be able to create will be WILD.
@@newtonbomb That is some great insight
@@tendies Tbf, I'm fairly certain its not an original thought lol. I can't remember for sure, but I vaguely remember reading an article somewhere a couple years ago about the unique possibilities for applications of quantum mechanical computational systems beyond just search algorithms like Shor's or cryptography that is typically discussed, and the usefulness of realtime higher dimensional wave collapse algorithm computation is the one that really stuck with me. Of course what I'd latch onto is how it could help make better games lol
I love your style if presentation. Judging from your previous videos I expect you going down this rabbit how and designing your own quantum computer doing wave function collapse on breadboards :P
For a second there I thought you were going to say "I need a physics engine and the best way to do that is from scratch. So here's how I implemented quantum mechanics..."
Your game is really coming together! It looks amazing already and I can’t wait to see what else you have to implement and the furthering of your terrain generation process.
It's nice to see more progress since the serializer stream. I've been looking more into C/C++ since then, but concepts (the C++ thing, not concepts as in "ideas") still confuse me. Looking forward to the next video in two months!
Are you talking about operator overloading or templates?
If you mean pointers and all the other abstract concepts you get used to them after a couple hundred lines of code, try it :)
I've never seen wave function collapse before, this is so cool!
I find it really interesting that you went back to oop approach after you initially started with it then transitioned to entity component. Makes me realize why its there in the first place
Very nice. I'm also very onboard with the plant loving robot theme!
glad you approve! when’s the next devlog coming out though 👀
@@jdh Soon™. I got a little delayed taking a second job this summer. Also I get distracted by the technical details, so it is going to have to be a couple of videos. I'll link back to your video one when I talk about implementation.
I tend to prefer levels design that's not randomly generated, but I have a black and white pixel tileset I had spent weeks creating a ton of cool and complicated geometric designs and structures and variations. Kinda got stuck moving on to creating actual level design with them though, but I think I'll use WFC to construct a bunch of potential level layouts- and I'll take the most promising ones and build more handcrafted levels again from there! I went wild creating a ton of elements I don't have a specific plan for, but I think this algorithm will at least present me with combinations I may not have expected that I can make what I want out of!
I have no earthly idea what's going on in this video but I still somehow find it interesting. I really love this type of game and seeing the actual work that goes into making it happen makes me even more interested in it. Can't wait to see the finished product.
Those stylized electron orbitals were my desktop background for a while; now it's footage of Venus's surface from the Vanera Lander
I'm starting my first year at university in a couple of months and I have no clue what the things you said mean. I'll come back to this video again when I know more stuff and see if I can understand lol
THANK YOU FOR CREATING THIS I SPENT WAY TO LONG TRYING TO DO SOMETHING LIKE THIS AND FAILING. this video very well explains a topic that I had trouble with.
I watched this first when I was incredibly sick, watched it again now and it made just about as much sense
It's always a good day when jdh uploads
Awesome video :D
You are one of the greatest coding TH-camrs of all time. You make your videos extremely interesting and I learn a lot from them. Legend.
I think this algorithm could quite easily be modified somewhat to dictate the overall shape of the entire map by modifying the function that chooses which pattern to collapse a cell into.
Say you want to create an objective for a dungeon map (the dungeon map is just a full size image like the ones you generated), and want it to be somewhere in the middle. You can simply look at the distance from the map border when looking at a cell to collapse, and make it so that the further away from the border it is, the higher the chance for it to collapse into the objective. You could even make a minimum distance from the border to become a particular type of cell.
You could also overlay a noise map onto the entire grid and vary the chance of a cell's collapse based on the value of the noise map in that spot.
Imo, that would be really interesting and (should be) possible to program.
I'm working on a roguelike shooter and we're doing that by doing 2-3 levels of WFC generation. Each level defines the tileset/example bitmaps for the level below it.
Brain Collapse Function
This guy is the reason why Google is getting mad over their employees
true
i don't get it ?
@@gokusaiyan1128 this guy is way smarter than google guys
Can you do a video explaining why you abandoned the ECS in favor of the standard OO approach? From my understanding you can have both with a Component?
I really like the effect fading out the wall in chunks gives! One thought I had was that it would be cool if instead of just the walls immediately around the player, walls the character is facing (up to a certain distance) would also fade so you don't need to run along the entirety of a back wall to see what's hidden behind it.
Unbelievable C++ skill ever seen...
So happy I subscribed to you a week ago.
I like your words magic man
If it fails, just try again until it doesn’t fail. Works every time.
NEW JDH VIDEO LETS GOOOOOOO
U can use wave functions to define a probabilty space where the player mive in. Player measurment chqnges the map
You have officially made me feel dumb… I needed this. Thank you.
Your videos has always this 5 head vibe that I really like
This is so past my knowledge I barely understand it, I love it.
As someone whos been doing code maintenance on a project they did not start I see this as nightmare fuel
When programmers stack more words onto something like "Wave Function Collaspe algorithm", I can't tell if I understand more or less
I love how I have absolutely no idea what is going on, yet it is somehow entertaining
bro please teach us on youtube or a course or whatever man , you are a legend
I wrote my entire wfc mechanism in 50 lines of code. Works flawlessly.
OMG he uploaded
I actually love how this looks. Great job! 👍
This might be a huge task, but the blinking light on your characters head, it would be an amazing way to ray tracing / some kind of ambient lighting to add some immersion to your levels, right now his headlight seems a bit too distinct from its surroundings
I have no idea what you're saying but you do it really well
honey wake up new jdh video just dropped
I've been working on an implementation recently as well. I decided it would be interesting to take the famous dancing links (DLX) sudoku solver and attempt to use it for constraint solver in WFC
yay new devlog :D i just rewatched the other ones the other day.
Hm. First video that I genuinely didn't understand. Congrats JDH, you finally did it!
May your gardens be vibrant and plentiful, brave little robot
Haha, I like your magic words, funny man
Lots of people making videos on wave function collapse lately, interesting to see the different way they explain it though
WOW! Nice original idea I've never seen a video like this one before
Jdh is one of those drop what you are doing and watch the new video type TH-camr
Annunciation will help your viewers' comprehension immensely
I'm simple: I see vim, I subscribe.
i'm simple: I see comment about vim and I reply with enthusiastic approval
love wave function collapse, so cool
The non-descriptive template parameters with the comments describing what they are made me cry.. why not just name them something similar to that
TYPE,
DIMS (maybe even DIMENSIONS)
PATTERNS,
BITSETS ?
I can't even make a start menu and this guy is using quantum physics...
He started somewhere just like you did so if you work long enough you can get here too
Fantastic to see the generation happening!
Very nice video. I will show it to my students.
I somehow understand less than nothing about this, but I'm still very interested in following along and learning from you haha
12:19 Did you code a visualisation to visualise coding. Very cool - you made the coding part just as compelling as the visual as it was easy to follow along.
no clue what you just said but i like it
Im deeply interested in this procedural generation techniques but the more games i play where the map was designed by a person the more i wish we would have more games like that.
Feels like some kind of 2D Markov's chain.
Just a suggestion regarding the player visibility through walls. If you are making a mask of the player, why do the extra step of raycasting when you can just overlay the player sprite over everything with a bit of transparency.
Also, awesome vid, learned a lot! :)
The generated map at 2:55 makes me want to play a dungeon crawler where each dungeon takes weeks to complete.
That is awesome, never seen that before and eager to give it a go! Thank you :)
Idk what i just watched but im impressed
this guy making an entire commercial quality game using native code:
me struggling to make a game in godot:
hey jdh!
your videos are aewsome and insipiring,
I have always wanted to tinker with a lot of the stuff regarding computer science such as the stuff you do on this channel but a big problem I usually face is the lack of math knowledge
and for me a 16 yo guy these stuff can seem aggravating so can you tell where and how can I learn the neccessary MATH needed for CS?
and THx
Same bro (im so bad at math)
Sounds simple enough, now to teach it to middle schoolers in Scratch
Love your stuff! Big help!
very cool. I wonder if you can combine different Maps to get some more interesting stuff.
I still can't stop marveling your coding skills, it seems impossible. Like how could you think of the whole WFC algorithm implementation and code it real time, it takes me many tries and iterations to code even a simple algorithm, i can't keep it all in my mind all at once
He did not code it in one go as seen in the video. It is mentioned at 12:11.
It's all got out of my mind but looks cool
This is badass!
So basically, you have the best minesweeper ai make video game maps
This is so cool! Where did you get the idea to use wave function collapse for level generation like this?
Wave function collapse? Oh yeah, super easy! [opens vim]..
I love this thing
i like your funny words magic man 😂
that is actually so cool what
So you’re just future future proofing
This is awesome, love the series! I was wondering - you mention you wrote an 'ultra fast mesh instancer' - in terms of speed/optimisation of code is this something you simply learned over time or are there key principles that you follow when writing your code to make sure you are always writing optimally? Cheers!
@jdh I also want to know
Thank you, bro!
When you stumble onto an awesome channel out of nowhere
Wow never heard before that somebody would get rid of a ECS before that's a first.
But I guess it can be cumbersome.
I too dabble in a bit of quantam physics when making my game
amazing work
Bad summary: *complex circuit board generator*
Who knew an algorithm could be viral
Man... the amount of time to practice coding until he reach that level is probably insane.
*A R E Y O U **_C L I C K I N G_** I N V I M ?*
you should call it robotanist