A lot of things in mathematics are beautifully simple and intuitive. It's just that mathematicians are really bad at explaining things. Or to be more exact, they are really good at explaining things to other mathematicians.
@@ocaly Yes but interestingly, you can also see the sudoku as a 3d problem. You have an X and Y axis, but given that any number from 0 to 9 can be on the same space at the same time you can also represent this as a Z axis.
Well, the explanation is super simple because it completely glosses over/ignores what happens when the constraint propagation fails and you need to backtrack or start over. There is a split second at 12:04 where two big pink exclamation points show a failed propagation -- what to do with that is not explained at all, and in fact is the most difficult part of designing a WFC algorithm that doesn't run for hours or fail 99% of the time.
@@OMGclueless Well, Ok that's a fair point & I did notice that but didn't quite understand what they meant, but for an explanation on how it generally works, I've found a lot of other explanations to be super complex or not very intuitive, especially when compaired to this explanation.
@@OMGclueless Backtracking is not part of WFC itself and is thus probably just outside this video's scope - the original WFC implementation quits when it encounters a contradiction. Backtracking just happens to be a very helpful addition to WFC :] That said, the fundamentals of backtracking are fairly simple to explain and probably could've been mentioned - you push every collapse and the pre-collapse state onto a stack, and if the collapse causes a contradiction, you pop that collapse and remove that candidate from that cell's candidate list and propagate that. If that removal also causes a contradiction, you pop yet another collapse off the stack, and so on. The difficulty comes from storing the pre-collapse state in such a way that it won't eat all your memory or require recalculating most of the state at each Undo, and that's definitely beyond this video's scope.
This is one of the most well-presented videos, on a technical subject, that I have ever watched on youtube. Great work, looking forward to more content.
Normally my brain hurts when I try to grasp new concepts, but that just didn't happen now. You have a way of explaining things making the concepts very easy to understand
This is super useful for generating levels with a set number of points of interest. You add whatever things you want to have in a level at random points and maybe add roads between them and after that you can make this algorithm do its magic to fill in the details. Very nice!
Watched more than 3 hours of implementations and explanations about wave function collapse, Can confirm that this one was the best from every aspect, Thank you!.
Terrific explanation! I recently finished reading "Doors of Eden" (by Adrian Tchaikovsky), a novel in which wave function collapse influences the plot outcome significantly. I'm going to share the link for this video with my wife and a friend who've also recently read the book but who are both humanities scholars rather than techies, because if they simply stop at the beginning of the programming section, they will get an extremely lucid and approachable explanation of the theory. Well done, and thanks for sharing.
The idea to just analyze an example level to determine valid sockets is great. I did not even think about that. Makes it much easier to create complex rules and have the computer imitate the style of a human Level Designer.
That was mind-bending! Really some food for thought! And you've convinced me to take up Sudoku! I really love that you relate Sudoku to wave function collapse in this way! Really helped something *click* in my brain; thank you!
Agreed. Definitely brings this ‘WFC’ that we have been seeing from the likes of Oskar Stalberg since some years now to humanly possible understandable levels. The Sudoku explanation is quite straightforward to grasp the concept, at least for me. Deserves the patron support hands down.
Nicely presented! I thought you were going to talk about physics but I watched the whole video because this algo idea is so fun, and all the info was a good mix of visual demo and technical details, perfect for morning coffee :D
heck, you explained wave function collapse so beautifully in just two minutes. i am sticking around for the rest of the video of course but even so i had to compliment you on being so succinct
I've been reading about wave function collapse for a few days, and four minutes into your video I already understand it better than everything else I've seen combined. Fantastic job
If you add recursive backtracking to this algorithm, you'll end up with a classic algorithm for SAT solving, called DPLL. Also, DPLL is very old and outdated, so if your constraints are too complex to find a solution with it, consider taking inspiration from CDCL algorithm, or just use the off the shelf SAT/SMT solver, like Z3.
I'm working on creating a complex sudoku solver for variant sudoku rules, and my current algorithm that I came up with seems to reduce to DPLL. Do you know of some elementary resources where I could learn some more about CDCL to make my algorithm faster? I got a minor in comp sci, but most of the resources that I've seen are borderline graduate CS level.
@@sweetcornwhiskey I learned about that algorithms from presentations of Emina Torlak from her Washington University course, you can google that course. Once you get through the notation, that should be understandable.
@@sweetcornwhiskey there's been a SAT competition for the past 20 years: see SAT RACE / SAT COMP. You will find an assortment of different solvers source codes to look at/reference. A lot of the content is dense/state of the art, but the assorted info over the years is probably the best resource for speeding up SAT solving. You might find a PhD dissertation/Survey or two where the "preliminaries" or "background” section explain completely the ideas, reasoning behind it, etc. before jumping into what is likely more difficult.
this is awesome, you explained the concept so well that it just intuitively clicked for me. i feel like the number of tools in my mental toolbox as a programmer has increased after watching this video
Wow, this was amazing. So well organized, articulated, and indeed respectful of my time. You sir have earned a sub + bell. Thank you for this I'm sure I'll end up referring back to this one day.
This is by far the clearest and most detailed explanation i saw on the subject, thanx a lot ! I was wondering, just like for sudoku, is it possible that the algirithm runs into a dead end by selecting a combination of tiles that doesn't allow a suitable neighbour in some cases? Is there a strategy for the algorithm to backtrack and correct that, or is it better to start over again or carefully craft a tileset that allows every possible combinations?
This can absolutely happen. Backtracking is a good option definitely, but I never got around to implementing anything like that. My implementation just starts the whole process again if any cell ends up completely empty of options. Making sure your tileset covers all bases definitely helps avoid contradictions.
I was thinking that for each axis we might store a growing list of changes, so more recent changes are at the end. Then we could do a targeted backtrack looking only at the values which directly constrain a given location. I haven’t worked out how that would fit with the required propagation steps yet… it wouldn’t be as clean as a simple backtrack everything (breadth first search) but it feels like it should be hugely faster.
@@j.j.maverick9252 If you only remove selected changes, there could be issues where the algorithm would prefer certain patterns of cells to be faaar more used than other patterns. Especially if a constraint is quite old, it would have influenced the choices for a lot of other cells. You could absolutely consider this intended behavior, but a small change in your tiles could cause quite large repercussions on the average outcome.
@@jessiejanson1528 It absolutely can get stuck. You're talking about a FIFO Stack (First In First Out) for cell determination which is what this video shows, so long as you are leveraging squares (as in this example) you can run into impossible scenarios. In example, look at your number pad, take 2, 4, 6, and 8 to be South, West, East, and North respectively. You pick a determinate cell for North. You're now acting on East (clockwise), and just like North you have all the same options. Fast forward a bit and now deal with "North East" Your cell now has 2 restrictions applying to it to which you may have contradictory rules (See the example at 5:35). This is just hypothesis at the point of writing this but I suspect that one of three things can help mitigate this: 1) Hexagonal Cylinders (making all surrounding cells directly relate to an immediately previously set cell's face) 2) Writing an algo to parse your "tile set" and make sure you have Tile Sets that fulfil all iterable conditions (so assuming outwards propagation, 2 faces for a 2d square tileset, 3 faces for a 2d hexagon tileset and, atleast 3 faces for a 3d tileset) 3) Making sure no Tile Face Socket exists only twice. (for the same reason as #2, if a face only has one possible match you're significantly more likely to enter a dead end.
I’m a nuclear physicist who misread the title & assumed this was about quantum wavefunctuions… don’t think I’ll ever do anything with this information, but got interested & stuck around anyways. Incredibly engaging & high-quality video, & an excellent explanation even for someone who doesn’t do much with algorithms! :)
The way you break down the software is perfect for learning key concepts on a functional level. In my eyes, you are the gold standard. You can bet that I will be watching everything you'd ever made over the upcoming days
This may be one of the best videos on this topic I've ever seen. Its explanatory power is breathtaking. This just shows the principle so well with so little wasted effort.
I’m from the complete other side of the spectrum, I’m a physics student in their penultimate year of their undergraduate and I know and understand superposition and collapsing a wavefunction in quantum mechanics, but have never seen it used for mapping. That’s awesome!
Excellent! I'll be eagerly watching your future videos. Are you also using Doom Emacs with the gdscript layer? If you have any suggestions for improvements they're welcome on the repository.
I guess im asking the wrong place but does anyone know a tool to get back into an Instagram account..? I was stupid lost the password. I would love any tips you can offer me
@Sylas Casey i really appreciate your reply. I got to the site on google and I'm trying it out atm. Looks like it's gonna take a while so I will get back to you later when my account password hopefully is recovered.
I saw the Bad North inspired island generation in the thumbnail :) Love the game! I can understand why Oskar is so stuck on the idea (He keeps going back to it on Twitter)
Thank You! This video helped it all make sense! I love your "wax on, wax off" trick about teaching us Wave Function Collapse through sudoku! Right when I'm like wait, I want to learn about Wave Function Collapse, you have already tricked me into learning it! I knew karate the whole time.
That explanation of sudoku could be a video all of its own. Very clear and precise! It didn't just explain the rules; it highlighted both how you should play, what you should pay attention to, and why it's the way it is in just two minutes.
Absolutely loved this video, especially love how in the beginning you compared it to something that everyone can understand before going more in-depth.
Wow! Thank you for a great explanation and for mentioning all these references! I realized that when developing something like a tile engine I can avoid making an editor to create test levels (at least at the beginning) and use WFC to generate levels automatically.
I have never watched any video related to wave function collapse but youtube really wants me to watch a whole bunch of videos on wave function collapse lately.
This is a great example of how failing to explain some incidental details, which are not relevant to the topic but which have been arbitrarily chosen for illustration, leaves the audience confounded and unable to fully engage with what otherwise seems like a clear explanation of the topic. I mean, what the hell are these tile maps? What am I looking at? What am I supposed to intuit from these images? I don't understand the relation between the various tile images, so I am unable to recognise the patterns that are supposed to be illustrative. Not only does this fail to illustrate the explanation, it confounds it. I can't process the audio while my brain is trying to decode the impossible visual. But the Sudoku was such a perfect illustration that I understood that part instantly. Cheers.
I believe that description is done at 4:33, but is slightly poor as it doesn't expressly point out the incongruity of the "negative space" the "isn't" tile creates.
Very nice and compact video, makes me want to program my own implementation from scratch. Also, the comparison of the wave function collapse to sudoku was what made it click for me, very well done :)
This is the best explanation I've seen for WFC - it's got me thinking about where I can apply it, and I don't write games. I also accidentally watched all your back-catalogue. Pity there aren't more - they're all really well explained!
AWESOME video! Thank you so much for the extremely detailed overview of this algorithm! I definitely feel like I have a grasp on how to implement and modify it. Thanks again!
This is a fantastic video. I'm half asleep and still understood what was going on. Going to implement something similar in my next game. Honestly kinda weird that this showed up on my front page 🧐
Thank you! I'm trying to make my own game featured infinite level generation, This will help me a lot !! Your explanation is so well, even a none English speaker like me can understand :D
Very interesting, thanks Martin. An extension to this would be to add a fourth dimension of time and use the algorithm to create valid random transitions along the dimension of time. Examples could be the creation of rivers via erosion, houses decaying, new constructions appearing in empty lots etc. Since the algorithm doesn't care about the direction of the dimension you could do some crazy stuff like simulate erosion _in reverse_, or a decayed destroyed city turning into a beautiful ancient metropolis as time travels backwards.
Explaining wave function theory is usually quite the challenge, but you managed to do it really nicely by using Sudoku! I'm definitely gonna use this analogy next time I find myself talking about quantum mechanics (whenever that happens, haha).
I'm so glad I found your channel. You really remind me of Sebastian Lague! Your content is phenomenal, I really hope your channel picks up more traction soon. Cheers!
This algorithm reminds me a lot of differential equations, where you are trying to find a function that satisfy a set of rules laid out by the equation, while also satisfying some boundary conditions. In fact, I wonder if a approach similar to differential equations, using some interpolation techniques, can be use to procedurally generate terrain in a way that doesn't use tiles as a alternative to terrains generated by perlin noise. This could also be potentially used to generate non-repeating textures I'd imagine. If you wanted to have more agency over what's generated you could also implement some additional boundary conditions. Maybe set a few tiles from the start (like having all the outer tiles be walls, for instance), or even make that some coordinates are not allowed to be certain tiles. You could for instance force a river to pass through the middle of the level by forcing a river start and a river end to exist in the right and left edges of the screen, while disallowing any tiles too far away from the center from being river tiles and disallowing any other tiles to river ends. Of course, the more complex the boundary conditions, higher the chance of generating a invalid solution, which may introduce some problems if these thing need to be generated on the fly, so applying some backtracking and doing some manual optimizations may be required. This could also be modified to work with a seed, allowing certain levels to be replayed. This could be used in the final product like Minecraft does, or even just for testing purposes. I'm not a game dev, by the way, but I do know a good amount of programming and find game dev topics fascinating.
As you mentioned, adding weights is important for a more practical usage. You can go a different direction if you really lean into depending on weights. You can have cells that are not adjacent weigh in on what cell type a cell should be. This can help limit behavior like too many house cells or never having a large ocean, since you can have ocean cells make other ocean cells very likely to be chosen if they are nearby or in certain land/ocean patterns. You could even add a property to your ocean cells indicating the depth, which affects the probability of other cells (no land cells within X cells of a X-hundred foot deep ocean cell).
Besides the name, what is it that makes "wave function collapse" different from general constraint propagation? Or is it just a name for a particular way to propagate constraints?
I was thinking the same thing. I'm quite accustomed to quantum mechanics, so the terminology is perfectly intuitive for me, but I don't see how making this analogy would be all that helpful for the average game developer. Seem like an unnecessary abstraction. I'm guessing the main purpose is to make you sound like you're doing something more clever and complicated than you really are.
@@egodreas It's very possible that it is a reinvention of the wheel with a different name. Game development can be somewhat disconnected from a lot of "traditional" computer science, especially for the more sciency parts of CS.
The analogy becomes a bit clearer once you add more additional constraints. Entropy (number of allowable states) and coupling constants (weights). E.g. Entropy can be a somewhat non local constraint. Yes, this is all JUST constraint propagation (as all of physical is JUST mathematics) but the analogy is more natural. We don't choose arbitrary constraints, but such constraints that mimic behavior of physical system and by which, by experience, create more "natural looking" results.
@@michaelrenper796 After making that comment, I went ahead and looked a bit more what this was about. It's as much about constraints, as it is about random generation (if my memory serves me right). I think it makes sense for it to have its own name. Maybe not so much for the way it's done. More for the fact that it's applied with a specific purpose, and thought of as a specific technique for that.
One cool thing about this algorithm is that it’s easy to have a bit of control over what it generates. For example, in a video game level, you could include a starting point, a goal, and a few key tiles, then let the algorithm solve the rest of it automatically
I guess that's more useful for people looking for coding help from this video instead of people looking for a simplified explanation but... The bulk tileset shown at 8:10 can be reduced *drastically* if your algorithm takes rotation into account. You can see that the 4 closest rows are the same geometry just rotated anywhere between 90 and 270 degrees. Their "Match Sockets" never differ compared to the geometry. You can also include overhangs, and cave-like systems with additional rotational checks in your algorithm. Lastly, you don't need to process these checks over and over again for each tile placement. You only need to iterate over your whole tileset once and store the available mappings (Tile Option + any rotation [axis + degree] required). You can even export this data so that instead of a "running process" it becomes a Constant Configuration Variable and *completely separate* from the rest of the game you're coding. Basically, separating out the "map relational code" into it's own product that is run only when the map tileset is updated. Allowing reuse between game projects.
With a name like Wave Function Collapse, I was expecting some really advanced mathematics, but this is actually beautifully simple and intuitive.
A lot of things in mathematics are beautifully simple and intuitive. It's just that mathematicians are really bad at explaining things. Or to be more exact, they are really good at explaining things to other mathematicians.
i dont know about beautiful, but simple for sure.
Just like the Universe.
@@Piotrek7654321 i dont know about Universe, but you for sure.
@@rawallon A stranger on the Internet just called me beautiful? Aww, thank you
Never thought about comparing it to sudoku, that's such a smart way of describing it!
I thought of the game carcasone.
@@m4rt_ 2D representation for something that looks complicated in 3D. Nice!
@@ocaly Yes but interestingly, you can also see the sudoku as a 3d problem. You have an X and Y axis, but given that any number from 0 to 9 can be on the same space at the same time you can also represent this as a Z axis.
@@lucadeacha you could look at it from that way and there are many sudoku variants even using that (f.e. "skyscraper sudokus").
@@lucadeacha or cubedoku's which is precisely what you're describing. but skyscraper sudokus is more well-known example among the online sudoku peers.
This is literally the best explanation for how this algorithm works.
Well, the explanation is super simple because it completely glosses over/ignores what happens when the constraint propagation fails and you need to backtrack or start over. There is a split second at 12:04 where two big pink exclamation points show a failed propagation -- what to do with that is not explained at all, and in fact is the most difficult part of designing a WFC algorithm that doesn't run for hours or fail 99% of the time.
@@OMGclueless Well, Ok that's a fair point & I did notice that but didn't quite understand what they meant, but for an explanation on how it generally works, I've found a lot of other explanations to be super complex or not very intuitive, especially when compaired to this explanation.
@@OMGclueless Agreed. I was just about to reply with this same question.
I see Martin, i like
@@OMGclueless Backtracking is not part of WFC itself and is thus probably just outside this video's scope - the original WFC implementation quits when it encounters a contradiction. Backtracking just happens to be a very helpful addition to WFC :] That said, the fundamentals of backtracking are fairly simple to explain and probably could've been mentioned - you push every collapse and the pre-collapse state onto a stack, and if the collapse causes a contradiction, you pop that collapse and remove that candidate from that cell's candidate list and propagate that. If that removal also causes a contradiction, you pop yet another collapse off the stack, and so on. The difficulty comes from storing the pre-collapse state in such a way that it won't eat all your memory or require recalculating most of the state at each Undo, and that's definitely beyond this video's scope.
This is one of the most well-presented videos, on a technical subject, that I have ever watched on youtube. Great work, looking forward to more content.
I could never wrap my mind around Wave Function Collapse until I saw this. Thank you
Normally my brain hurts when I try to grasp new concepts, but that just didn't happen now. You have a way of explaining things making the concepts very easy to understand
This is super useful for generating levels with a set number of points of interest.
You add whatever things you want to have in a level at random points and maybe add roads between them and after that you can make this algorithm do its magic to fill in the details. Very nice!
though it would be different for every user unless you have some way to define what goes where specifically by the coordinate.
@@jessiejanson1528 as long as your pseudorandom selection process is consistent then it shouldn't be an issue
Watched more than 3 hours of implementations and explanations about wave function collapse,
Can confirm that this one was the best from every aspect,
Thank you!.
Terrific explanation! I recently finished reading "Doors of Eden" (by Adrian Tchaikovsky), a novel in which wave function collapse influences the plot outcome significantly. I'm going to share the link for this video with my wife and a friend who've also recently read the book but who are both humanities scholars rather than techies, because if they simply stop at the beginning of the programming section, they will get an extremely lucid and approachable explanation of the theory. Well done, and thanks for sharing.
The idea to just analyze an example level to determine valid sockets is great. I did not even think about that. Makes it much easier to create complex rules and have the computer imitate the style of a human Level Designer.
That was mind-bending! Really some food for thought! And you've convinced me to take up Sudoku! I really love that you relate Sudoku to wave function collapse in this way! Really helped something *click* in my brain; thank you!
the amount of math and editing required for this video is insanely impressive
Best WFC explanation I've watch. Thanks !
It really is! And even provides links to all the further reading you want. Great video.
Agreed.
Definitely brings this ‘WFC’ that we have been seeing from the likes of Oskar Stalberg since some years now to humanly possible understandable levels. The Sudoku explanation is quite straightforward to grasp the concept, at least for me.
Deserves the patron support hands down.
This is honestly not only extremely well explained, but also beautiful too
When i saw this title i realized, i have implemented WFC for Sudoku without realizing it. Amazing :)
That was just enough information to be able to write it and not be lost. Thank you for not over or under explaining it like most videos do.
Nicely presented! I thought you were going to talk about physics but I watched the whole video because this algo idea is so fun, and all the info was a good mix of visual demo and technical details, perfect for morning coffee :D
you're the master of making difficult-to-understand things become much easier ones.
holy shit this makes it make so much sense, i wouldnt have known this comparison would work so well! Good discovery!
Wow, comparing it to sudoku was smart. That made it so much easier to wrap my head around!
v0_0 is how my face looks when looking at the astonishing amount of informative data in this video. Kudos on how well presented this is too!
heck, you explained wave function collapse so beautifully in just two minutes. i am sticking around for the rest of the video of course but even so i had to compliment you on being so succinct
I've been reading about wave function collapse for a few days, and four minutes into your video I already understand it better than everything else I've seen combined. Fantastic job
Best WFC Explanation never thought of comparing it to Sudoku. Nice Vid!!
If you add recursive backtracking to this algorithm, you'll end up with a classic algorithm for SAT solving, called DPLL. Also, DPLL is very old and outdated, so if your constraints are too complex to find a solution with it, consider taking inspiration from CDCL algorithm, or just use the off the shelf SAT/SMT solver, like Z3.
I'm working on creating a complex sudoku solver for variant sudoku rules, and my current algorithm that I came up with seems to reduce to DPLL. Do you know of some elementary resources where I could learn some more about CDCL to make my algorithm faster? I got a minor in comp sci, but most of the resources that I've seen are borderline graduate CS level.
@@sweetcornwhiskey I learned about that algorithms from presentations of Emina Torlak from her Washington University course, you can google that course. Once you get through the notation, that should be understandable.
@@sweetcornwhiskey CSE 507
@@luck3949 Thanks!
@@sweetcornwhiskey there's been a SAT competition for the past 20 years: see SAT RACE / SAT COMP. You will find an assortment of different solvers source codes to look at/reference. A lot of the content is dense/state of the art, but the assorted info over the years is probably the best resource for speeding up SAT solving. You might find a PhD dissertation/Survey or two where the "preliminaries" or "background” section explain completely the ideas, reasoning behind it, etc. before jumping into what is likely more difficult.
Excellent video! Thanks for sharing! Also, you are the reason I created a Patreon and you're the first person I'm sponsoring! :) Great job!
Thank you so much!
this is awesome, you explained the concept so well that it just intuitively clicked for me. i feel like the number of tools in my mental toolbox as a programmer has increased after watching this video
Wow, this was amazing. So well organized, articulated, and indeed respectful of my time. You sir have earned a sub + bell. Thank you for this I'm sure I'll end up referring back to this one day.
This is by far the clearest and most detailed explanation i saw on the subject, thanx a lot ! I was wondering, just like for sudoku, is it possible that the algirithm runs into a dead end by selecting a combination of tiles that doesn't allow a suitable neighbour in some cases? Is there a strategy for the algorithm to backtrack and correct that, or is it better to start over again or carefully craft a tileset that allows every possible combinations?
This can absolutely happen. Backtracking is a good option definitely, but I never got around to implementing anything like that. My implementation just starts the whole process again if any cell ends up completely empty of options. Making sure your tileset covers all bases definitely helps avoid contradictions.
I was thinking that for each axis we might store a growing list of changes, so more recent changes are at the end. Then we could do a targeted backtrack looking only at the values which directly constrain a given location.
I haven’t worked out how that would fit with the required propagation steps yet… it wouldn’t be as clean as a simple backtrack everything (breadth first search) but it feels like it should be hugely faster.
@@j.j.maverick9252 If you only remove selected changes, there could be issues where the algorithm would prefer certain patterns of cells to be faaar more used than other patterns. Especially if a constraint is quite old, it would have influenced the choices for a lot of other cells. You could absolutely consider this intended behavior, but a small change in your tiles could cause quite large repercussions on the average outcome.
seems like the best solution is just to solve it in a circular pattern going around the starting point. i cant imagine it would ever get stuck.
@@jessiejanson1528 It absolutely can get stuck. You're talking about a FIFO Stack (First In First Out) for cell determination which is what this video shows, so long as you are leveraging squares (as in this example) you can run into impossible scenarios.
In example, look at your number pad, take 2, 4, 6, and 8 to be South, West, East, and North respectively. You pick a determinate cell for North. You're now acting on East (clockwise), and just like North you have all the same options. Fast forward a bit and now deal with "North East" Your cell now has 2 restrictions applying to it to which you may have contradictory rules (See the example at 5:35).
This is just hypothesis at the point of writing this but I suspect that one of three things can help mitigate this:
1) Hexagonal Cylinders (making all surrounding cells directly relate to an immediately previously set cell's face)
2) Writing an algo to parse your "tile set" and make sure you have Tile Sets that fulfil all iterable conditions (so assuming outwards propagation, 2 faces for a 2d square tileset, 3 faces for a 2d hexagon tileset and, atleast 3 faces for a 3d tileset)
3) Making sure no Tile Face Socket exists only twice. (for the same reason as #2, if a face only has one possible match you're significantly more likely to enter a dead end.
I’m a nuclear physicist who misread the title & assumed this was about quantum wavefunctuions… don’t think I’ll ever do anything with this information, but got interested & stuck around anyways. Incredibly engaging & high-quality video, & an excellent explanation even for someone who doesn’t do much with algorithms! :)
As someone looking to do a wave function collapse implementation the really helped me understand
The way you break down the software is perfect for learning key concepts on a functional level. In my eyes, you are the gold standard. You can bet that I will be watching everything you'd ever made over the upcoming days
This is the best wave function collapse video out there. By far. 10/10
Man you're so good! cant believe this channel is so small :O really helped me out with my next project :)
This may be one of the best videos on this topic I've ever seen. Its explanatory power is breathtaking. This just shows the principle so well with so little wasted effort.
I’m from the complete other side of the spectrum, I’m a physics student in their penultimate year of their undergraduate and I know and understand superposition and collapsing a wavefunction in quantum mechanics, but have never seen it used for mapping. That’s awesome!
Our teacher added this as our study material on a course lol. Very informative!
This makes me unreasonably proud, thank you for sharing! 🙏
@@MartinDonald You should!
I really appreciate the effort you put in to explain what I once thought was a really difficult algorithm to understand. Great Job!
This is the best explanation video on WFC I have found! Alone with the example at the beginning I could conceptualize the algorithm. great work!
Excellent! I'll be eagerly watching your future videos.
Are you also using Doom Emacs with the gdscript layer? If you have any suggestions for improvements they're welcome on the repository.
I'm actually using pycharm but I can see why you'd think that, the colour schemes are almost identical. I'll definitely look into it though.
I guess im asking the wrong place but does anyone know a tool to get back into an Instagram account..?
I was stupid lost the password. I would love any tips you can offer me
@Sylas Casey i really appreciate your reply. I got to the site on google and I'm trying it out atm.
Looks like it's gonna take a while so I will get back to you later when my account password hopefully is recovered.
@Sylas Casey it did the trick and I actually got access to my account again. I am so happy!
Thank you so much you saved my account !
@Kingsley Langston no problem :)
It took me longer than I'd like to admit to realize this wasn't about Thomas Young's double slit experiment.
This channel is ridiculously underrated
wow
I saw the Bad North inspired island generation in the thumbnail :) Love the game! I can understand why Oskar is so stuck on the idea (He keeps going back to it on Twitter)
Thank You! This video helped it all make sense! I love your "wax on, wax off" trick about teaching us Wave Function Collapse through sudoku! Right when I'm like wait, I want to learn about Wave Function Collapse, you have already tricked me into learning it! I knew karate the whole time.
By far the best introduction to and explanation of WFC I've come across...! Thank you for taking the time to make this.
Of all the videos that I watched on wave function collapse, yours is by far the best at explaining it.
That explanation of sudoku could be a video all of its own. Very clear and precise! It didn't just explain the rules; it highlighted both how you should play, what you should pay attention to, and why it's the way it is in just two minutes.
Absolutely loved this video, especially love how in the beginning you compared it to something that everyone can understand before going more in-depth.
Wow! Thank you for a great explanation and for mentioning all these references!
I realized that when developing something like a tile engine I can avoid making an editor to create test levels (at least at the beginning) and use WFC to generate levels automatically.
Hands down the best explanation for WFC I've ever seen. Kudos!
I have never watched any video related to wave function collapse but youtube really wants me to watch a whole bunch of videos on wave function collapse lately.
This is a great example of how failing to explain some incidental details, which are not relevant to the topic but which have been arbitrarily chosen for illustration, leaves the audience confounded and unable to fully engage with what otherwise seems like a clear explanation of the topic.
I mean, what the hell are these tile maps? What am I looking at? What am I supposed to intuit from these images? I don't understand the relation between the various tile images, so I am unable to recognise the patterns that are supposed to be illustrative. Not only does this fail to illustrate the explanation, it confounds it. I can't process the audio while my brain is trying to decode the impossible visual.
But the Sudoku was such a perfect illustration that I understood that part instantly. Cheers.
I believe that description is done at 4:33, but is slightly poor as it doesn't expressly point out the incongruity of the "negative space" the "isn't" tile creates.
Really nice explanation and visuals!
wow.. this is the most amazing explanation ever.. Please Please keep making high quality videos like this.
Looked at some of your other videos as well. Brilliant content! Subbed.
Very nice and compact video, makes me want to program my own implementation from scratch.
Also, the comparison of the wave function collapse to sudoku was what made it click for me, very well done :)
good explanation. Highly appreciated.
marian42 is such a champ for making that repository available for free ;-)
Holy crap, I just stumbled upon this channel randomly and I'm stunned. Amazing content, thank you for this.
dude, this video is so good, I've looked at explanations on WFC for ages and this one really made me understand it
Thank you for the fantastically clear, intuitive, and well-articulated explanation 🙂 Much appreciated ❤️
this was brilliant! come back, make more, please!!
Wow, very well explained!
So, the constraints of reality lead to the collapse of wave function.
This is the best explanation I've seen for WFC - it's got me thinking about where I can apply it, and I don't write games.
I also accidentally watched all your back-catalogue. Pity there aren't more - they're all really well explained!
good video! haven't found many good channels like this explaining algorithms or CS concepts, have subbed!
just got my own implementation working in unity, this video was a massive help!
I spent time trying to find a fast Sudoku solving algorithm, and I never realized that I was using this exact function! Lol
AWESOME video! Thank you so much for the extremely detailed overview of this algorithm! I definitely feel like I have a grasp on how to implement and modify it. Thanks again!
Despite this not being a video on quantum mechanics like I thought, it was still quite enjoyable
WOW, this is an incredibly well-made video. You've done such a good job teaching and choosing your metaphors.
I entered with no expectations and I didn't even know what are you going to talk about. But i was impressed by the video so to the next video we go
First explanation of WFC that I actually understood, thanks!
Very informative, thank you. I’ve been considering implementing wfc in music composition, and this explanation helps me grasp it. Have a pleasant day.
Hey thanks for this video. I just spent the better part of my day creating a Tilemap generator using the knowledge gained from this video.
Brilliant, concise, informative and fun! A truly exquisite piece of education.
This is so great! The presentation is excellent! Will share on LinkedIn soon.
I came expecting a new set of Advanced Sudoku rules, and found a game level generation algorithm.
I am pleased.
This is a fantastic video. I'm half asleep and still understood what was going on. Going to implement something similar in my next game. Honestly kinda weird that this showed up on my front page 🧐
Thanks for this high density video! Beautiful masterpiece, you earned my subscription!
Thank you!
I'm trying to make my own game featured infinite level generation, This will help me a lot !!
Your explanation is so well, even a none English speaker like me can understand :D
Very interesting, thanks Martin. An extension to this would be to add a fourth dimension of time and use the algorithm to create valid random transitions along the dimension of time. Examples could be the creation of rivers via erosion, houses decaying, new constructions appearing in empty lots etc. Since the algorithm doesn't care about the direction of the dimension you could do some crazy stuff like simulate erosion _in reverse_, or a decayed destroyed city turning into a beautiful ancient metropolis as time travels backwards.
Explaining wave function theory is usually quite the challenge, but you managed to do it really nicely by using Sudoku! I'm definitely gonna use this analogy next time I find myself talking about quantum mechanics (whenever that happens, haha).
Woah, I'll have to do a tier in your patreon, this is so well explained
I'm so glad I found your channel. You really remind me of Sebastian Lague! Your content is phenomenal, I really hope your channel picks up more traction soon. Cheers!
This algorithm reminds me a lot of differential equations, where you are trying to find a function that satisfy a set of rules laid out by the equation, while also satisfying some boundary conditions. In fact, I wonder if a approach similar to differential equations, using some interpolation techniques, can be use to procedurally generate terrain in a way that doesn't use tiles as a alternative to terrains generated by perlin noise. This could also be potentially used to generate non-repeating textures I'd imagine.
If you wanted to have more agency over what's generated you could also implement some additional boundary conditions. Maybe set a few tiles from the start (like having all the outer tiles be walls, for instance), or even make that some coordinates are not allowed to be certain tiles. You could for instance force a river to pass through the middle of the level by forcing a river start and a river end to exist in the right and left edges of the screen, while disallowing any tiles too far away from the center from being river tiles and disallowing any other tiles to river ends.
Of course, the more complex the boundary conditions, higher the chance of generating a invalid solution, which may introduce some problems if these thing need to be generated on the fly, so applying some backtracking and doing some manual optimizations may be required. This could also be modified to work with a seed, allowing certain levels to be replayed. This could be used in the final product like Minecraft does, or even just for testing purposes. I'm not a game dev, by the way, but I do know a good amount of programming and find game dev topics fascinating.
I came out with this algorithm and a friend of mine linked me this video, why are all great ideas already discovered
Really kinda surprised this channel isnt bigger
As you mentioned, adding weights is important for a more practical usage.
You can go a different direction if you really lean into depending on weights. You can have cells that are not adjacent weigh in on what cell type a cell should be. This can help limit behavior like too many house cells or never having a large ocean, since you can have ocean cells make other ocean cells very likely to be chosen if they are nearby or in certain land/ocean patterns. You could even add a property to your ocean cells indicating the depth, which affects the probability of other cells (no land cells within X cells of a X-hundred foot deep ocean cell).
If there’s one thing this video taught me it’s how to play sudoku
Besides the name, what is it that makes "wave function collapse" different from general constraint propagation? Or is it just a name for a particular way to propagate constraints?
I was thinking the same thing. I'm quite accustomed to quantum mechanics, so the terminology is perfectly intuitive for me, but I don't see how making this analogy would be all that helpful for the average game developer. Seem like an unnecessary abstraction. I'm guessing the main purpose is to make you sound like you're doing something more clever and complicated than you really are.
@@egodreas It's very possible that it is a reinvention of the wheel with a different name. Game development can be somewhat disconnected from a lot of "traditional" computer science, especially for the more sciency parts of CS.
The analogy becomes a bit clearer once you add more additional constraints. Entropy (number of allowable states) and coupling constants (weights). E.g. Entropy can be a somewhat non local constraint.
Yes, this is all JUST constraint propagation (as all of physical is JUST mathematics) but the analogy is more natural. We don't choose arbitrary constraints, but such constraints that mimic behavior of physical system and by which, by experience, create more "natural looking" results.
@@michaelrenper796 After making that comment, I went ahead and looked a bit more what this was about.
It's as much about constraints, as it is about random generation (if my memory serves me right).
I think it makes sense for it to have its own name. Maybe not so much for the way it's done. More for the fact that it's applied with a specific purpose, and thought of as a specific technique for that.
@@frechjo "constrained level generation" sounds more apt to be
One cool thing about this algorithm is that it’s easy to have a bit of control over what it generates. For example, in a video game level, you could include a starting point, a goal, and a few key tiles, then let the algorithm solve the rest of it automatically
Sudoku example was brilliant, Thank you so much .🙏.
What a great way to explain this! Wonderful video
I thought it was a 50k subs channel. Those animations are awesome !
Don't worry, we'll get there!
@@MartinDonald Nice
(honestly I don't think I've pressed subscribe this quickly before) amazing video ♥️
I guess that's more useful for people looking for coding help from this video instead of people looking for a simplified explanation but...
The bulk tileset shown at 8:10 can be reduced *drastically* if your algorithm takes rotation into account.
You can see that the 4 closest rows are the same geometry just rotated anywhere between 90 and 270 degrees. Their "Match Sockets" never differ compared to the geometry.
You can also include overhangs, and cave-like systems with additional rotational checks in your algorithm.
Lastly, you don't need to process these checks over and over again for each tile placement. You only need to iterate over your whole tileset once and store the available mappings (Tile Option + any rotation [axis + degree] required).
You can even export this data so that instead of a "running process" it becomes a Constant Configuration Variable and *completely separate* from the rest of the game you're coding. Basically, separating out the "map relational code" into it's own product that is run only when the map tileset is updated. Allowing reuse between game projects.
You did a fantastic job of explaining this concept. Thank you so much!
I had no idea this was about game dev, so I'm quite ecited to learn this
Thanks Martin, as a Unity developer, It's also useful to me :)
Looking forward to your content, Wave Function Collapse algorithm is awesome, can't wait to try out in game.