Please visit the new website, the page for each video includes all source code, links, and references mentioned in the video! thecodingtrain.com/challenges/171-wave-function-collapse
I really enjoy it. After i see it i think about why can't we generate rules of neighbourhood by code? With pixel analyzing by just stripping 1px width strip from side, so we can use any tileset with any dimentions just by feed it to algorithm. Actually this will not work well if you use diagonal and any angle kind tiles, but it's not a big deal. However there are one more problem: if you don't want things like tiny grey dots (like at circuit generated in this video) you should have more complex rules for neighbourhood.
Love your videos. Have been watching them since 2016 (on and off, lol). I would really love it if you could do a video about yourself. Like your background and stuff. I have loved watching your videos, and now would love to watch a video about the maker of these videos. Please.
One of the things about Sudoku is that you often end up with states where two cells (say A & B) contain the same two possible numbers but no others (say {1,2}) and a third cell C contains both of those two numbers plus one other (e.g. {1,2,3}). Thus you can deduce what number C should collapse to even though you can't yet collapse A or B and none of the sets contain only value.
So, I've done this all before when messing around with roguelikes back in college for map generation. But damn, this is the best video I've seen on the topic.
I love your newer editing so much! You've always been about making programming fun, entertaining, and accessible, so the editing is just another axis in which you express your vibrant character :)
All the issues in coding this that you went through, I also went through. Its so funny to watch the same struggles come up. But you actually solved it all and I didn't . True inspiration!
As a professional software developer, I can attest that the montage with the ever-increasing error counter and holding your head in your hands is very true to life.
I was watching your videos when I was a dog walker 2 months into comprehending javascript. Now it's been like 4-5 years and I'm a web dev on salary and I'm still watching your videos. Thanks for everything.
I loved the bit at 18:14. "We're not that far away (i think) from the end here." I laughed out loud. It's been awhile since I've caught one of your videos, but the quality has only gone up. Really interesting topic too!
I wish there were videos like yours for C#. I find myself consistently watching your videos and I'm not even learning Java!! Your enthusiasm and energy are unrivalled!
So happy to finally have been able to be part of the process and even collaborate with a PR and suggestions. I recently gave a talk on Neural networks fundamentals based on your videos and it was a blast, everybody loved it! You're an inspiration!
@@blasttrash work yeah, we do talks to share stuff we are working on and when asked about topics I suggested NN. I remade some examples from Daniel's videos: genetic algorithm writing monkeys, evolving steering triangles, perceptron and ending with a Flappy bird clone made with phaserjs that was solved with Tensorflow.
🎯Course outline for quick navigation: [00:01-01:37]1. Wave function collapse -[00:01-01:03]Wave function collapse algorithm generates output images mimicking original image style without using deep neural networks. -[01:17-01:41]The transcript discusses algorithm explanation and resources for wave function collapse challenge. [01:37-18:44]2. Understanding wave function collapse -[01:37-02:06]Algorithm for generative images derived from quantum mechanics, explaining wave function collapse and entropy. -[02:52-03:23]The average entropy of the system is nine, and knowing additional information reduces the entropy. -[03:40-04:32]Entropy collapse reduces possible states, solving sudoku with wave function collapse. -[05:39-06:10]Solved sudoku puzzle, exploring process of wave function collapse for image generation. -[09:23-09:50]Image generated with wave function collapse, can be generated quickly with code. -[12:29-13:25]Count through grid, collapse cells, draw image or black rectangle. -[13:50-14:35]Objects in array allow multiple copies with same data, but in different orders. sort function requires custom compare function. -[16:49-17:37]Array sorted by entropy, pick one randomly, and collapse it to leave one element. [18:44-29:15]3. Reducing tile entropy and validating options -[18:44-19:13]Random pick reduces entropy, creating new array of tiles. -[19:51-20:20]Using an array to store valid neighbors for five tiles as a lookup table. -[21:46-22:17]Tiles 1, 3, and 4 can go to the right, with options for 0 or 3 below. variable names assigned for easier coding. -[24:11-24:40]Tiles can connect based on four numbers; zeros connect with zeros, ones with ones. categorizing edges as a or b, zero or one. -[27:06-27:40]Pass existing options into a function to check for validity. -[28:13-28:41]Removing invalid elements from the array to improve readability and functionality. [29:15-43:28]4. Debugging and wave function collapse -[35:52-36:58]Explaining the process of concatenating valid possibilities for left and right tiles. -[38:47-39:15]Discussed implementation of code for printed circuit board with 14 tiles and 4 rotations. -[39:53-40:49]Automated tile rotation with adjacency rules will enhance code readability and fun wave function collapsing. [43:28-51:05]5. Image rotation and tile objects -[43:28-44:24]Using modulo operator for perfect wraparound, handling rotations and image properties, encountering an error in image rotation in p5. -[44:47-45:17]Designing tile images to create a more sophisticated pattern and procedurally generate rules based on tile objects. -[45:35-47:21]Creating a class to generate options and adjacency rules for tiles based on grid edges, using higher order functions like fill, map, and from. -[46:34-47:06]Generating adjacency rules for tiles based on edges and analyzing connections. [51:05-01:01:18]6. Debugging and implementing algorithms -[51:35-52:27]Improving code to create new cell objects and handle options elegantly. -[55:00-55:34]Discussing a 20 by 20 grid, wave function collapse, and simplifying tile connections. -[58:15-58:55]Manually loading 11 tile images, skipping 4 and 5, with specific connections and values. -[01:00:26-01:01:18]Striving to complete wave function collapse algorithm with help from telemako and garasbalg, aiming to implement oskar stahlberg's unity solution. [01:01:19-01:09:12]7. Interactive tile selection and wave function collapse -[01:01:19-01:02:22]Interactive demonstration of wave function collapse with visually represented tiles and color matching process. -[01:04:27-01:04:50]Tile objects created individually for edge letters, referred to as sockets. [01:09:13-01:18:26]8. Tile edge comparison and wave function collapse -[01:09:41-01:10:36]Revamping adjacency rules and implementing edge comparison in code. -[01:11:38-01:12:05]The reverse function in p5 is being deprecated and will be removed in a future version due to the existence of array.reverse function. -[01:13:31-01:13:56]Discussing optimization and cleanup in the code for creating tile objects, analyzing adjacency rules, and creating a new grid. -[01:15:26-01:16:19]Experimenting with 40x40 resolution, seeking feedback for algorithm optimization. -[01:17:49-01:18:26]Wave function collapse algorithm can be applied in 3d with numerous implementations. encourages viewers to submit their versions for algorithmically generated images and teases a future challenge on the overlapping model. offered by Coursnap
I never thought live(ish) coding could be entertaining and informative. You are amazing, nothing feels contrived and the editing is spot on. Really great presentation of your ideas and process. This isn't even some trivial subject matter which makes it all the more impressive. Bravo!
This was amazing. I was thinking that this could be applied to tile games like Carcassone, where the edges are field, path or city, to create random boards. Amazing video!
Took an online job interview of some major IT company. They offered me 10 minutes to complete an algorithm, and I failed to make it. I grew my confidents back after watching your video. Even an experienced talented code guru makes mistakes. We don't need coding machines, we need mentors teaching and inspiring others, like you. Great job.
Once I saw your original video on this I decided to make it and it is so crazy how I literally had all of the exact same problems and same reactions to them.
This is so weird but this video wants me to have a kid and go through coding challenges with them like this. It just seems like such a unique bonding experience.
Hahah, calling this a trailer. This is a good advertisement for the channel, though - it came up in my recommendations, and is right up the alley of what I like to play with. A little advanced for what I am able to do, but still simple enough to follow along, and does the stuff that I like to see.
no matter what cool new idea i want to try, there is ALWAYS a coding train video. LOVE that I finally caught something relatively new.. THANK YOU LOVE YOU FOREVER
Thank you for this. Videos giving specific steps to perform simple to complicated tasks, have their use. However videos like this (not that I have seen anyone else work through solutions like this) not only get your (at least my) mind working toward a solution, but also act almost like a one-way collaboration, giving the viewer a different way to think about the problem, and show that coding is work - NOT something you instantly know and if you can't figure it out the first two or three times, or within a short period of time, then you are a bad coder.
Not sure if I did exactly what you did or not, because I got inspired after watching a few minutes (and JavaScript programming, unless it's FP, is kinda painful) and wrote where I thought this was going in functional programming in Kotlin. I'm at 16:00 and the way I structured it was: 1. Set of nodes to be assigned (e.g. positions in the grid) of type T 2. Possible assignments (e.g. the five road blocks) of type V 3. A set of rules: If, for a node t, you assign a value v, then how does this affect the choices of assignments to all the other tiles? So my typealiases / data structures are: - Assignment - Possibilities - Then the rules are: Map
when working in vscode, you can use F2 to refactor any name (function, variable class etc) recursively, meaning it'll change the declaration AND all its references in all files in the workspace.
I've been watching your videos on and off for years. You've inspired me, more than once, to code fun projects in my spare time, rather than just for my day job.
Love it, love it, love it. I got inspired 3/4ths way through when you name-dropped 'sockets' on how to implement this in 3D. Can't wait to try. What an algorithm! Love your presentation. Big fan
For anybody wondering: the problem with undefined lookups in the rules object at the ~30min mark was that the keys get parsed as the strings UP, BLANK, DOWN etc instead of the numerical values the variables with those names contained. Defining the object as this instead should've worked the same as switching to an array: rules = { [BLANK]: [], [UP]: [], ...etc } (point being that square brackets are needed around the keys to use the values from within variables with those names as keys in an object instead of just the regular strings)
This is a great video and I appreciate you leave in the mistakes and happy accidents, as that is a fundamental part of the discovery of coding. It's like the Bob Ross of coding (edit: I didn't even see the top comment saying this exact thing...)
I want to say how much I appreciate seeing you struggle. I feel its important to make people aware that that is very much a part of programming. Keep in mind ive never been a professional programmer. Went to college for it then never got a job with it
I watched the original live streams(which were a bit of a roller coaster), so I didn't think I would end up watching this whole video.... but you got me... :) Great work, you and your editor(s)!
Excellent video as always. I could absolutely see this merging with a Conway's Game of Life system to create dynamic changes, for example to illustrate a pixellated lava or water pool.
it helps allot watching you ACTUALLY solve this, Then comparing that to how I do it, then I can see how I Think/feel in relation and if I am in the right path
i love the production value of these videos. I haven't watched one of your videos in a few months so not sure how new this is, but it's awesome. Great work! I love coding and teaching and have wanted to do something like this myself but have no idea how to start. :)
I just found your channel, I do agree with the comments, you are the bob ross of Computer science! So chill and non-perfectionist, playful way of coding and working with concepts!
This is exactly what I'm trying to do with Excel VBA - fitting 27 unique 1 × 14 patterns to fill a 64 × 14 grid under several constraints/criteria. Many thanks for the insights
It's so interesting watching someone go through these challenges, I really appreciate how you go through from beginning to end, not editing out the iteration, the working out of each logical step, the experiments, the mistakes, how you learn from those mistakes, etc. One aspect is painful to watch though, because it makes me feel bad for you having to do everything the hard way. The number of issues that you run into just because you're a human being and can't possibly keep every single detail in your conscious attention at once is very illustrative, and highlights the advantage of using a strongly typed language. In FSharp for instance, almost all of these little "gotcha!" moments would have been impossible to run into, because if you write it idiomatically, if you make types that only work if everything is correct, all of the logic that interacts with those types would have been checked by the compiler, and if it isn't correct it wouldn't even build. It makes me incredibly grateful I don't have to work in JavaScript, lol. That's not a knock on you or anything close to it, I love these videos, and find them extremely helpful in learning how to take big problems and cut them up into bite size chunks, you're a fantastic educator and a joy to watch. I just feel bad you're working harder than you have to, because the compiler isn't giving you any support against a very human lack of omniscience.
I always love the interaction of quantum physics, math, programming and logic. I hope to become a quantum computer researcher one day. Keep up the amazing work.
I think a better way to handle some of these is to have a list of possible edges for the tiles, and then have some lists/an adjacency matrix of which edges can be paired with which other edges. For example, to handle the issue with the narrow black boxes in the circuit board one, you can have two kinds of edges, chipEdge (used in any block that borders a chip) and chipBody (used in the all-black one). Then you can have chipBody-chipBody pair, and chipBody-chipEdge, but not chipEdge-chipEdge. That way you won't have two chipEdge tiles line up to make a narrow chip, but wider ones will work. This also handles asymmetrical edges well; you can have L and R versions of the edge, and have L-R match but not L-L or R-R.
quick question: At 5:20 when you supposedly pick the first tile with the lowest entropy, imho that's not really what you're doing. You're solving by ruling out other possible locations for an 8. Because this tile's possible states are [2,8], in a real algorithm we'd probably have picked the 2 and would have backtracked at some point (if entropy is really the only thing we're checking for)
OMG OMG OMG! The other day in Unity Engine I was cooking up a maze game with random tiles each time. What I did was have each tile or room of my maze have a 0 for the walls and a 1 for the doors. Using that I wanted to randomly select possible rooms to connect to, such that the 0s are connected and the 1s are too. I ultimately failed my fun little project. The fun thing is that I was trying to reinvent the wheel,as what I did was exactly wave function collapse but I didn't know it exists! I was watching my coding idol here and be like "Waiita second... Am a genuis or what?... Too bad I failed." I love your vids my man! You really are my programing hero/idol/ look up to. Always enthusiastic and explain the logic behind it.
When you're talking about the sockets that can fit together and needing to read the bottom lines backwards, you could simply always read the sockets left to right and top to bottom and keep the equivalence check to match them up (rather than flipping them for every check). The only place you'd need to worry about flipping them is in the rotate function; the sockets that pass from the right to the bottom or from the left to the top need to be inverted. Still, that's a one-time string flip at initialization rather than a repeated flip every loop of the analyze function, and it makes entering the socket mapping easier
I've been coding my own implementation and let me tell you it feels good for you to say "We're not that far away" and "I'm not going to redo my code like this.." because thats exactly what happened to me too, and I also found out the edges thing like you, but only after starting to create a spreadsheet with 27 different tiles and their possibilities. I found out that in my tiles I could categorize all the corners with height indexes 0-1-2. I'm now at the point that I need to create some kind of way for the system to store a state and then if it finds a tile that has no possible answers it backtracks to the last "save" if needed.
Man, this video actually gave me some direction on how to tackle this algorithm now. I tried to wrap my head around it before, but my brain just melted. Now I can see a light at the end of the tunnel. :)
Watching this I get flashbacks to my go at a Tetris implementation. A 2D grid with cells where the allowed movement and rotation of the current tetromino is checked against its neighbors. Sounds like a fun afternoon, but took me a week of afternoons to get my grips around all the edge cases and those damn index checks
re 1:17:00 that's exactly the reason why you had the [undefined] bug: since your constraints weren't completely propagated, you ended in a position where an invalid choice was made. That's why the algorithm doesn't need backtracking; it's pushing all its constraint out to prevent an invalid state.
A future version of this 😲 can't wait for it to be uploaded! This helped me get a good grasp of what WFC is actually doing. I tried reading the articles, but it came to me as super complex. Now it's still complex but understandable! Thanks
May be jumping the gun as only half way through, but why not, when you draw a tile, remove the options from the surouunding tiles rather than re-evaluating the whole grid
I am making a game that procedurally generates everything. using Perlin for the terrain, but I hadn't het figured out how I was going to make the cities. You, sir, have solved that problem.
5:20 - There are techniques in sudoku to avoid needing to guess (in the vast, vast majority of sudoku puzzles you will never need to guess if you know the proper techniques for how to eliminate options in other cells). One of the most basic techniques is called a "pointing tuple" or "pointing pair" where if one of the options appears within a particular house (3x3 subgrid) only twice and both of those are in a single line (row or col) , then that option can be eliminated from the rest of the line it is "pointing" down. There's a ton of specific named techniques like that, a few other common ones are "hidden pairs", "y-wing", "x-wing", "locked candidates", "swordfish", "forced chain", etc. It would be really interesting to try to create a solver using actual techniques. Possibly even show something like which techniques it had to use during the solve.
I made a sudoku solver a couple of years ago when a started to learn programming, today I learned I (semi) successfully implemented the wave function collapse model to make that sudoku solver
Wow it's incredible that I just learned how Bad North implemented WFC in it's procedural generation and I had no idea how that could happen so I'm glad I can learn about it now
Things left to be done: - Recursive entropy reduction: Once a cell's entropy is reduced, that in turn could also reduce the entropy of other cells. And that could reduce the entropy of other cells, and so on. Dan didn't account for this in the video. - Shannon entropy: Shannon entropy is basically a much more sophisticated way to calculate entropy than just "number of possibilities". It takes more things into account like how likely each individual outcome is. - -Backtracking- : What happens when the algorithm gets stuck. Dan wanted to implement this previously, but actually, most implementations don't do this. Instead, they just start over when they get stuck. - Overlapping model: This is an entirely different algorithm. It's also called "wave function collapse", and it works very similarly to the alg that Dan implemented in the video, but there's one difference: you don't have to give it rules to work with. You just give it an example image, and it just generates it for you. I know, MAGIC. Unnecessary code stuff: - I think you can do away with the collapsed field entirely. Instead, just check if a cell has only 1 option. Then it's collapsed. - When you did the entropy reduction, you started with every new grid cell from scratch with every single option. Why not just use the options list that has already been narrowed down previously? (Super) minor things which I want to point out for no reason at all: - 3:30 At the bottom left of the sudoku grid, why does it say the possibilities are 1-8 and not 1-9? You made a similar mistake at 8:20 where some other cells should have their entropy reduced which you didn't reduce the entropy for. Again, super minor mistakes, but they're tickling my brain so I just want to mention them. - 14:13 Something you might not know: the sort() function, by default, ALWAYS sorts in alphabetical order. So if you have an array like [10, 3, 1, 5, 16], sort() will sort it to [1, 10, 16, 3, 5] unless explicitly stated otherwise with a comparison function. - 1:08:02 Automating that would also have a disadvantage since if you did that, you'd have to work with the constraint that tiles with the same edge colors, and ONLY tiles with the same edge colors, would match together. You might not want that, for example if you put a border around all the tiles so it makes for a nice grid pattern over the entire output, then all the sockets would end up being the same which is not fun.
A couple points. The lowest entropy heuristic makes little difference and in fact only causes the algorithm to fail more often. The original algorithm did not have it: paulmerrell.org/wp-content/uploads/2021/07/comparison.pdf Backtracking only helps slightly. A better solution in the original algorithm (Model Synthesis) is create to a large set of tiles by modifying in parts. The overlapping model is not really a different algorithm. All you need to do is to look at a 2D array of pixels and decide if the each array is the same or different.
Great explanation. Also helped me with understanding entropy in another context: template sentence detection. A single word can have a lot of possible candidates (high entropy) while the remaining words are primarily static (low entropy). E.g. auto-generated sentences like "User A logged in on B".
I hate to suggest it, but! Have you considered using the p5.js with Typescript package? A few of these bugs were type bugs and it might reduce some of the debug time. I've never actually used p5 with Typescript so I can't vouch for the actual package itself, but these kinds of issues are absolutely what Typescript is here for
if you store tiles in priority queue, and push again only ones that entropy changed, you'll dont have to update entire table, resulting in speedup. Instead of sorting the list and figuring out what is the number of tiles with smallest entropy, you can offset each entropy by a random number between 0 and 1. Finally you can hold a stack holding guesses you made which will faciliate resetting. After all WFC is just DFS with priority of graph searches given by entropy.
At 1:05:23, shouldn't tiles be able to match the unrotated sockets as well, as long as they line up? Or will this perhaps break the algorithm? I'm thinking mirrored that regular, mirrored and rotated tiles should be checked for a full collapse?
Thanks for the vid! As a long time developer, your video seems to always rekindle my passion for coding whenever I feel burnt out! One minor suggestion (nitpick), maybe try to use encode your states (UP, DOWN, LEFT, RIGHT) into bits e.g. 0001, 0010, etc. You can then easily check for states using bitwise operation.
This code can be upgraded by adding the functionality of finding and naming the sockets automatically. And furthermore, it could take an image and extract the tiles automatically. Nice video, congrats!
I'm at 25:45, so I might eat my words, and this might apply only to this weird case of a finite set of options, but it seems that the element of probability-ordering is missing. With no confluential factors, the base probability of all options is equal, but no options are eliminated. As confluential factors are added, they may become reassigned probability, which back-propagates through the network each time the reassignment changes the most probable, potentially cascading recursively, till a tail appears as a non-reordering assignment. No idea how to best optimize that in JS without jumping to a WASM binary, but in Go or Rust, I'd go packed bitmap as 64bit int slice/vec with bitwise operators. It seems like that is actually the gist of wave-function collapse, though not implementing an example, I'd suppose tracking mutations and backtracking might be more effective for large matrices.
At 1:16:57 you say that your function doesn't need recursive collapsing but that's exactly what would stop your algorithm from needing to restart/backtrack.
I think that to determine the possibility of the neighborhood of different elements, you can use the Fourier transform, applying it to pairs or triplets of points on the line of contact. After conversion, there should be no high-frequency components, or perhaps it is possible to define some threshold value for their number.
I self-discovered wave function collapse methods while playing minesweeper. "hmm, of this one's a two, and this adjacent one with a larger range is also two... so that means those extra boxes don't contribute to the number of mines and therefore must be empty"
Please visit the new website, the page for each video includes all source code, links, and references mentioned in the video! thecodingtrain.com/challenges/171-wave-function-collapse
I really enjoy it.
After i see it i think about why can't we generate rules of neighbourhood by code? With pixel analyzing by just stripping 1px width strip from side, so we can use any tileset with any dimentions just by feed it to algorithm. Actually this will not work well if you use diagonal and any angle kind tiles, but it's not a big deal. However there are one more problem: if you don't want things like tiny grey dots (like at circuit generated in this video) you should have more complex rules for neighbourhood.
Love your videos. Have been watching them since 2016 (on and off, lol).
I would really love it if you could do a video about yourself. Like your background and stuff. I have loved watching your videos, and now would love to watch a video about the maker of these videos.
Please.
actually it looks really like cube/square marching not a wave function collapse
One of the things about Sudoku is that you often end up with states where two cells (say A & B) contain the same two possible numbers but no others (say {1,2}) and a third cell C contains both of those two numbers plus one other (e.g. {1,2,3}). Thus you can deduce what number C should collapse to even though you can't yet collapse A or B and none of the sets contain only value.
So, I've done this all before when messing around with roguelikes back in college for map generation. But damn, this is the best video I've seen on the topic.
you are truly the bob ross of programming, respect to you sir!
can't believe how accurate this is
Is there in the community of Bob Ross someone who says that his the Coding Train of painting?
"There are no mistakes, just happy little bugs." :D
@@jameschamblin7120 Chinese people have entered the chat with bug soups
Best description ever
I love your newer editing so much! You've always been about making programming fun, entertaining, and accessible, so the editing is just another axis in which you express your vibrant character :)
I LOVE the whiteboard editing. Nothing agains Dan's handwriting though 😅
Agreed , loved the editing , must have taken a lot of work
agree
All the issues in coding this that you went through, I also went through. Its so funny to watch the same struggles come up. But you actually solved it all and I didn't . True inspiration!
Keep at it!
@@TheCodingTrain Will do thank you!
As a professional software developer, I can attest that the montage with the ever-increasing error counter and holding your head in your hands is very true to life.
I was watching your videos when I was a dog walker 2 months into comprehending javascript. Now it's been like 4-5 years and I'm a web dev on salary and I'm still watching your videos. Thanks for everything.
Thank you for sharing I’m so happy to hear!
I've also had a few failed attempts at the WFC algorithm, you've made me very excited to try again! You're an inspiration as always!
Hope this helps! It's a long one!
@@TheCodingTrain I'm sure it will :)
@@TheCodingTrain Cant wait for the next installment!
I loved the bit at 18:14. "We're not that far away (i think) from the end here." I laughed out loud. It's been awhile since I've caught one of your videos, but the quality has only gone up. Really interesting topic too!
and 24:32! lol
This moment precisely is why this new viewer will be subscribing forthwith.
I wish there were videos like yours for C#. I find myself consistently watching your videos and I'm not even learning Java!! Your enthusiasm and energy are unrivalled!
So happy to finally have been able to be part of the process and even collaborate with a PR and suggestions. I recently gave a talk on Neural networks fundamentals based on your videos and it was a blast, everybody loved it! You're an inspiration!
Thank you for you all of your contributions!!
where did you give the talk? In your college or work?
@@blasttrash work yeah, we do talks to share stuff we are working on and when asked about topics I suggested NN. I remade some examples from Daniel's videos: genetic algorithm writing monkeys, evolving steering triangles, perceptron and ending with a Flappy bird clone made with phaserjs that was solved with Tensorflow.
🎯Course outline for quick navigation:
[00:01-01:37]1. Wave function collapse
-[00:01-01:03]Wave function collapse algorithm generates output images mimicking original image style without using deep neural networks.
-[01:17-01:41]The transcript discusses algorithm explanation and resources for wave function collapse challenge.
[01:37-18:44]2. Understanding wave function collapse
-[01:37-02:06]Algorithm for generative images derived from quantum mechanics, explaining wave function collapse and entropy.
-[02:52-03:23]The average entropy of the system is nine, and knowing additional information reduces the entropy.
-[03:40-04:32]Entropy collapse reduces possible states, solving sudoku with wave function collapse.
-[05:39-06:10]Solved sudoku puzzle, exploring process of wave function collapse for image generation.
-[09:23-09:50]Image generated with wave function collapse, can be generated quickly with code.
-[12:29-13:25]Count through grid, collapse cells, draw image or black rectangle.
-[13:50-14:35]Objects in array allow multiple copies with same data, but in different orders. sort function requires custom compare function.
-[16:49-17:37]Array sorted by entropy, pick one randomly, and collapse it to leave one element.
[18:44-29:15]3. Reducing tile entropy and validating options
-[18:44-19:13]Random pick reduces entropy, creating new array of tiles.
-[19:51-20:20]Using an array to store valid neighbors for five tiles as a lookup table.
-[21:46-22:17]Tiles 1, 3, and 4 can go to the right, with options for 0 or 3 below. variable names assigned for easier coding.
-[24:11-24:40]Tiles can connect based on four numbers; zeros connect with zeros, ones with ones. categorizing edges as a or b, zero or one.
-[27:06-27:40]Pass existing options into a function to check for validity.
-[28:13-28:41]Removing invalid elements from the array to improve readability and functionality.
[29:15-43:28]4. Debugging and wave function collapse
-[35:52-36:58]Explaining the process of concatenating valid possibilities for left and right tiles.
-[38:47-39:15]Discussed implementation of code for printed circuit board with 14 tiles and 4 rotations.
-[39:53-40:49]Automated tile rotation with adjacency rules will enhance code readability and fun wave function collapsing.
[43:28-51:05]5. Image rotation and tile objects
-[43:28-44:24]Using modulo operator for perfect wraparound, handling rotations and image properties, encountering an error in image rotation in p5.
-[44:47-45:17]Designing tile images to create a more sophisticated pattern and procedurally generate rules based on tile objects.
-[45:35-47:21]Creating a class to generate options and adjacency rules for tiles based on grid edges, using higher order functions like fill, map, and from.
-[46:34-47:06]Generating adjacency rules for tiles based on edges and analyzing connections.
[51:05-01:01:18]6. Debugging and implementing algorithms
-[51:35-52:27]Improving code to create new cell objects and handle options elegantly.
-[55:00-55:34]Discussing a 20 by 20 grid, wave function collapse, and simplifying tile connections.
-[58:15-58:55]Manually loading 11 tile images, skipping 4 and 5, with specific connections and values.
-[01:00:26-01:01:18]Striving to complete wave function collapse algorithm with help from telemako and garasbalg, aiming to implement oskar stahlberg's unity solution.
[01:01:19-01:09:12]7. Interactive tile selection and wave function collapse
-[01:01:19-01:02:22]Interactive demonstration of wave function collapse with visually represented tiles and color matching process.
-[01:04:27-01:04:50]Tile objects created individually for edge letters, referred to as sockets.
[01:09:13-01:18:26]8. Tile edge comparison and wave function collapse
-[01:09:41-01:10:36]Revamping adjacency rules and implementing edge comparison in code.
-[01:11:38-01:12:05]The reverse function in p5 is being deprecated and will be removed in a future version due to the existence of array.reverse function.
-[01:13:31-01:13:56]Discussing optimization and cleanup in the code for creating tile objects, analyzing adjacency rules, and creating a new grid.
-[01:15:26-01:16:19]Experimenting with 40x40 resolution, seeking feedback for algorithm optimization.
-[01:17:49-01:18:26]Wave function collapse algorithm can be applied in 3d with numerous implementations. encourages viewers to submit their versions for algorithmically generated images and teases a future challenge on the overlapping model.
offered by Coursnap
thanks
I never thought live(ish) coding could be entertaining and informative. You are amazing, nothing feels contrived and the editing is spot on. Really great presentation of your ideas and process. This isn't even some trivial subject matter which makes it all the more impressive. Bravo!
This was amazing. I was thinking that this could be applied to tile games like Carcassone, where the edges are field, path or city, to create random boards. Amazing video!
It is used in many games.
A lot of rogue like games use systems like this, I recommend checking out GDC's spelunky presentation
@@estousemcriatividadepraumnome Unexplored's cyclic dungeon is a notable example
I will use it in my game...
Took an online job interview of some major IT company. They offered me 10 minutes to complete an algorithm, and I failed to make it.
I grew my confidents back after watching your video.
Even an experienced talented code guru makes mistakes. We don't need coding machines, we need mentors teaching and inspiring others, like you.
Great job.
Once I saw your original video on this I decided to make it and it is so crazy how I literally had all of the exact same problems and same reactions to them.
That video was epic! Loved your persistence, the explanation and the editing. Funny, entertaining and I learned all sort of things about coding
This is so weird but this video wants me to have a kid and go through coding challenges with them like this. It just seems like such a unique bonding experience.
I can't say I have ever seen someone bring so much enthusiasm to a discussion about entropy, and I love that energy!
This trailer was so good!
I kinda want to watch a Coding Train movie now. 👀
Well, this video is 80 minutes long!
Hahah, calling this a trailer. This is a good advertisement for the channel, though - it came up in my recommendations, and is right up the alley of what I like to play with. A little advanced for what I am able to do, but still simple enough to follow along, and does the stuff that I like to see.
@@flabort Before there was a premiere there actually was a trailer playing, you can find it here! ua-cam.com/video/Xo76cZnkCXQ/v-deo.html
"We are close to the end now"
Half an hour later: "I'M A TILE"
no matter what cool new idea i want to try, there is ALWAYS a coding train video. LOVE that I finally caught something relatively new.. THANK YOU LOVE YOU FOREVER
It's worth mentioning that this algorithm is based on and nearly the same as the Model Synthesis algorithm published nearly a decade earlier in 2007.
Thank you for this.
Videos giving specific steps to perform simple to complicated tasks, have their use.
However videos like this (not that I have seen anyone else work through solutions like this) not only get your (at least my) mind working toward a solution, but also act almost like a one-way collaboration, giving the viewer a different way to think about the problem, and show that coding is work - NOT something you instantly know and if you can't figure it out the first two or three times, or within a short period of time, then you are a bad coder.
A continuation of this concept would be amazing. Actually a whole series would be even better but no pressure!
Not sure if I did exactly what you did or not, because I got inspired after watching a few minutes (and JavaScript programming, unless it's FP, is kinda painful) and wrote where I thought this was going in functional programming in Kotlin.
I'm at 16:00 and the way I structured it was:
1. Set of nodes to be assigned (e.g. positions in the grid) of type T
2. Possible assignments (e.g. the five road blocks) of type V
3. A set of rules:
If, for a node t, you assign a value v, then how does this affect the choices of assignments to all the other tiles?
So my typealiases / data structures are:
- Assignment
- Possibilities
- Then the rules are:
Map
Haha this guy. His outsides might be growing older but his insides are forever young. Love it
when working in vscode, you can use F2 to refactor any name (function, variable class etc) recursively, meaning it'll change the declaration AND all its references in all files in the workspace.
Oh such a good tip!!
I've been watching your videos on and off for years. You've inspired me, more than once, to code fun projects in my spare time, rather than just for my day job.
Love it, love it, love it. I got inspired 3/4ths way through when you name-dropped 'sockets' on how to implement this in 3D. Can't wait to try. What an algorithm! Love your presentation. Big fan
WOAH the board editing was awesome. Definitely worth what ever extra time that took to do it.
For anybody wondering: the problem with undefined lookups in the rules object at the ~30min mark was that the keys get parsed as the strings UP, BLANK, DOWN etc instead of the numerical values the variables with those names contained.
Defining the object as this instead should've worked the same as switching to an array:
rules = {
[BLANK]: [],
[UP]: [],
...etc
}
(point being that square brackets are needed around the keys to use the values from within variables with those names as keys in an object instead of just the regular strings)
rotoscopy and overall editing are on point ! great job whoever edited this :D
Editing by Mathieu Blanchette
Animations by Jason Heglund
from the description
I know nothing of programming but this is strangely relaxing and intriguing to watch.
This is a great video and I appreciate you leave in the mistakes and happy accidents, as that is a fundamental part of the discovery of coding. It's like the Bob Ross of coding (edit: I didn't even see the top comment saying this exact thing...)
my mind is just blown, I love you and the marvelous work you do, please never stop.
i like that you have no music, this way i can play my own while watching it!
I want to say how much I appreciate seeing you struggle. I feel its important to make people aware that that is very much a part of programming. Keep in mind ive never been a professional programmer. Went to college for it then never got a job with it
I watched the original live streams(which were a bit of a roller coaster), so I didn't think I would end up watching this whole video.... but you got me... :) Great work, you and your editor(s)!
Excellent video as always. I could absolutely see this merging with a Conway's Game of Life system to create dynamic changes, for example to illustrate a pixellated lava or water pool.
so easy to tell how much you love doing this, even with the struggle! I find it much easier to learn when the instructor loves what they do
Cant believe how fun you make programming look! Ty for the great tutorial!
Thanks for making coding fun! Whenever I watch your videos I get motivated. Your positivity towards the code truly is inspirational.
I can see how this kind of thing could be used to generate seamless, non-repeating textures from a small sample image for 3D art or game development!
I absolutely loved the way you explained wave function collapse, I'm an experienced sodoku player and it made total sense!
it helps allot watching you ACTUALLY solve this, Then comparing that to how I do it, then I can see how I Think/feel in relation and if I am in the right path
I first learned programming with your early processing videos, it's crazy to see you're still around! Thanks for all the knowledge
i love the production value of these videos. I haven't watched one of your videos in a few months so not sure how new this is, but it's awesome. Great work! I love coding and teaching and have wanted to do something like this myself but have no idea how to start. :)
I just found your channel, I do agree with the comments, you are the bob ross of Computer science! So chill and non-perfectionist, playful way of coding and working with concepts!
This is exactly what I'm trying to do with Excel VBA - fitting 27 unique 1 × 14 patterns to fill a 64 × 14 grid under several constraints/criteria. Many thanks for the insights
It's so interesting watching someone go through these challenges, I really appreciate how you go through from beginning to end, not editing out the iteration, the working out of each logical step, the experiments, the mistakes, how you learn from those mistakes, etc.
One aspect is painful to watch though, because it makes me feel bad for you having to do everything the hard way.
The number of issues that you run into just because you're a human being and can't possibly keep every single detail in your conscious attention at once is very illustrative, and highlights the advantage of using a strongly typed language.
In FSharp for instance, almost all of these little "gotcha!" moments would have been impossible to run into, because if you write it idiomatically, if you make types that only work if everything is correct, all of the logic that interacts with those types would have been checked by the compiler, and if it isn't correct it wouldn't even build.
It makes me incredibly grateful I don't have to work in JavaScript, lol.
That's not a knock on you or anything close to it, I love these videos, and find them extremely helpful in learning how to take big problems and cut them up into bite size chunks, you're a fantastic educator and a joy to watch.
I just feel bad you're working harder than you have to, because the compiler isn't giving you any support against a very human lack of omniscience.
I always love the interaction of quantum physics, math, programming and logic. I hope to become a quantum computer researcher one day. Keep up the amazing work.
Thanks this actually helped me build my own wave function collapse system in unreal engine.
I think a better way to handle some of these is to have a list of possible edges for the tiles, and then have some lists/an adjacency matrix of which edges can be paired with which other edges.
For example, to handle the issue with the narrow black boxes in the circuit board one, you can have two kinds of edges, chipEdge (used in any block that borders a chip) and chipBody (used in the all-black one). Then you can have chipBody-chipBody pair, and chipBody-chipEdge, but not chipEdge-chipEdge. That way you won't have two chipEdge tiles line up to make a narrow chip, but wider ones will work.
This also handles asymmetrical edges well; you can have L and R versions of the edge, and have L-R match but not L-L or R-R.
"We're not that far from the end here!"
*Boss music starts playing*
quick question: At 5:20 when you supposedly pick the first tile with the lowest entropy, imho that's not really what you're doing. You're solving by ruling out other possible locations for an 8. Because this tile's possible states are [2,8], in a real algorithm we'd probably have picked the 2 and would have backtracked at some point (if entropy is really the only thing we're checking for)
Thanks
thank you for the support!
the graphics and editing in this video are really great :) the content on this channel just keeps getting better and better.
I love this video. And that you managed to learn javascript. You write better code than a lot Senior Devs i met.
OMG OMG OMG!
The other day in Unity Engine I was cooking up a maze game with random tiles each time.
What I did was have each tile or room of my maze have a 0 for the walls and a 1 for the doors.
Using that I wanted to randomly select possible rooms to connect to, such that the 0s are connected and the 1s are too.
I ultimately failed my fun little project.
The fun thing is that I was trying to reinvent the wheel,as what I did was exactly wave function collapse but I didn't know it exists!
I was watching my coding idol here and be like "Waiita second... Am a genuis or what?... Too bad I failed."
I love your vids my man! You really are my programing hero/idol/ look up to.
Always enthusiastic and explain the logic behind it.
When you're talking about the sockets that can fit together and needing to read the bottom lines backwards, you could simply always read the sockets left to right and top to bottom and keep the equivalence check to match them up (rather than flipping them for every check). The only place you'd need to worry about flipping them is in the rotate function; the sockets that pass from the right to the bottom or from the left to the top need to be inverted. Still, that's a one-time string flip at initialization rather than a repeated flip every loop of the analyze function, and it makes entering the socket mapping easier
yeah that's what i thought
It's great to all these years later have an understanding of how the Diablo series works.
I've been coding my own implementation and let me tell you it feels good for you to say "We're not that far away" and "I'm not going to redo my code like this.." because thats exactly what happened to me too, and I also found out the edges thing like you, but only after starting to create a spreadsheet with 27 different tiles and their possibilities. I found out that in my tiles I could categorize all the corners with height indexes 0-1-2. I'm now at the point that I need to create some kind of way for the system to store a state and then if it finds a tile that has no possible answers it backtracks to the last "save" if needed.
oh my, and your video finds backtracking at 1/2 the video end point O.O I'm still some way off :D
Man, this video actually gave me some direction on how to tackle this algorithm now. I tried to wrap my head around it before, but my brain just melted. Now I can see a light at the end of the tunnel. :)
I'm so glad to hear this! I really need to get to part 2 and the overlapping model
@@TheCodingTrain fortunately I only need it for tiles. :) I'm intending to use it for proc-gen roguelike maps.
Watching this I get flashbacks to my go at a Tetris implementation. A 2D grid with cells where the allowed movement and rotation of the current tetromino is checked against its neighbors. Sounds like a fun afternoon, but took me a week of afternoons to get my grips around all the edge cases and those damn index checks
That was the best description of entropy I'v ever heard.
I love your "chaotic good" videos 😊 It's also a pretty cool idea and the results are awesome.
re 1:17:00 that's exactly the reason why you had the [undefined] bug: since your constraints weren't completely propagated, you ended in a position where an invalid choice was made.
That's why the algorithm doesn't need backtracking; it's pushing all its constraint out to prevent an invalid state.
A future version of this 😲 can't wait for it to be uploaded! This helped me get a good grasp of what WFC is actually doing. I tried reading the articles, but it came to me as super complex. Now it's still complex but understandable! Thanks
May be jumping the gun as only half way through, but why not, when you draw a tile, remove the options from the surouunding tiles rather than re-evaluating the whole grid
I never even knew this was a thing.
Gotta try it out!
Love your videos!
I am making a game that procedurally generates everything. using Perlin for the terrain, but I hadn't het figured out how I was going to make the cities. You, sir, have solved that problem.
The sheer number of Errors you get just from using a dynamically typed language makes me want to cry.
The errors aren't from using a dynamically types language.. it's from using the language wrong
5:20 - There are techniques in sudoku to avoid needing to guess (in the vast, vast majority of sudoku puzzles you will never need to guess if you know the proper techniques for how to eliminate options in other cells). One of the most basic techniques is called a "pointing tuple" or "pointing pair" where if one of the options appears within a particular house (3x3 subgrid) only twice and both of those are in a single line (row or col) , then that option can be eliminated from the rest of the line it is "pointing" down. There's a ton of specific named techniques like that, a few other common ones are "hidden pairs", "y-wing", "x-wing", "locked candidates", "swordfish", "forced chain", etc.
It would be really interesting to try to create a solver using actual techniques. Possibly even show something like which techniques it had to use during the solve.
I made a sudoku solver a couple of years ago when a started to learn programming, today I learned I (semi) successfully implemented the wave function collapse model to make that sudoku solver
Wow it's incredible that I just learned how Bad North implemented WFC in it's procedural generation and I had no idea how that could happen so I'm glad I can learn about it now
Things left to be done:
- Recursive entropy reduction: Once a cell's entropy is reduced, that in turn could also reduce the entropy of other cells. And that could reduce the entropy of other cells, and so on. Dan didn't account for this in the video.
- Shannon entropy: Shannon entropy is basically a much more sophisticated way to calculate entropy than just "number of possibilities". It takes more things into account like how likely each individual outcome is.
- -Backtracking- : What happens when the algorithm gets stuck. Dan wanted to implement this previously, but actually, most implementations don't do this. Instead, they just start over when they get stuck.
- Overlapping model: This is an entirely different algorithm. It's also called "wave function collapse", and it works very similarly to the alg that Dan implemented in the video, but there's one difference: you don't have to give it rules to work with. You just give it an example image, and it just generates it for you. I know, MAGIC.
Unnecessary code stuff:
- I think you can do away with the collapsed field entirely. Instead, just check if a cell has only 1 option. Then it's collapsed.
- When you did the entropy reduction, you started with every new grid cell from scratch with every single option. Why not just use the options list that has already been narrowed down previously?
(Super) minor things which I want to point out for no reason at all:
- 3:30 At the bottom left of the sudoku grid, why does it say the possibilities are 1-8 and not 1-9? You made a similar mistake at 8:20 where some other cells should have their entropy reduced which you didn't reduce the entropy for. Again, super minor mistakes, but they're tickling my brain so I just want to mention them.
- 14:13 Something you might not know: the sort() function, by default, ALWAYS sorts in alphabetical order. So if you have an array like [10, 3, 1, 5, 16], sort() will sort it to [1, 10, 16, 3, 5] unless explicitly stated otherwise with a comparison function.
- 1:08:02 Automating that would also have a disadvantage since if you did that, you'd have to work with the constraint that tiles with the same edge colors, and ONLY tiles with the same edge colors, would match together. You might not want that, for example if you put a border around all the tiles so it makes for a nice grid pattern over the entire output, then all the sockets would end up being the same which is not fun.
A couple points. The lowest entropy heuristic makes little difference and in fact only causes the algorithm to fail more often. The original algorithm did not have it: paulmerrell.org/wp-content/uploads/2021/07/comparison.pdf
Backtracking only helps slightly. A better solution in the original algorithm (Model Synthesis) is create to a large set of tiles by modifying in parts.
The overlapping model is not really a different algorithm. All you need to do is to look at a 2D array of pixels and decide if the each array is the same or different.
Just wanted to add my ❤! Great, fun video. Thank you for all your coding and video editing efforts!
This video kept me and my 14 & 11 year old kids totally engrossed, even kinda late into the evening! Thanks
Wow! So great to hear! Those are the same ages as my kids ❤️
Great explanation. Also helped me with understanding entropy in another context: template sentence detection. A single word can have a lot of possible candidates (high entropy) while the remaining words are primarily static (low entropy). E.g. auto-generated sentences like "User A logged in on B".
Very educational and entertaining. Those 78 minutes are totally worth it!
Me: gets interested in wave function collapse and starts exercising
The Coding Train: uploads a video the next day
I think I might love you.
Really you are a very good teacher. And the topics you choose are always very interesting.
This video made me realise that Carcassonne is just wave function collapse: the game
You are a very friendly and funny person and I really like your videos! They are so enjoyable and educating! ❤
I hate to suggest it, but! Have you considered using the p5.js with Typescript package? A few of these bugs were type bugs and it might reduce some of the debug time. I've never actually used p5 with Typescript so I can't vouch for the actual package itself, but these kinds of issues are absolutely what Typescript is here for
Such an awesome explanation! Can't wait for the overlapping algorithm
I enjoyed the editing, good job Mathieu Blanchette!
if you store tiles in priority queue, and push again only ones that entropy changed, you'll dont have to update entire table, resulting in speedup.
Instead of sorting the list and figuring out what is the number of tiles with smallest entropy, you can offset each entropy by a random number between 0 and 1.
Finally you can hold a stack holding guesses you made which will faciliate resetting.
After all WFC is just DFS with priority of graph searches given by entropy.
At 1:05:23, shouldn't tiles be able to match the unrotated sockets as well, as long as they line up? Or will this perhaps break the algorithm?
I'm thinking mirrored that regular, mirrored and rotated tiles should be checked for a full collapse?
Thanks for the vid! As a long time developer, your video seems to always rekindle my passion for coding whenever I feel burnt out! One minor suggestion (nitpick), maybe try to use encode your states (UP, DOWN, LEFT, RIGHT) into bits e.g. 0001, 0010, etc. You can then easily check for states using bitwise operation.
Thank you for this nice and constructive feedback!
Looks amazing
This code can be upgraded by adding the functionality of finding and naming the sockets automatically. And furthermore, it could take an image and extract the tiles automatically.
Nice video, congrats!
I'm at 25:45, so I might eat my words, and this might apply only to this weird case of a finite set of options, but it seems that the element of probability-ordering is missing. With no confluential factors, the base probability of all options is equal, but no options are eliminated. As confluential factors are added, they may become reassigned probability, which back-propagates through the network each time the reassignment changes the most probable, potentially cascading recursively, till a tail appears as a non-reordering assignment.
No idea how to best optimize that in JS without jumping to a WASM binary, but in Go or Rust, I'd go packed bitmap as 64bit int slice/vec with bitwise operators.
It seems like that is actually the gist of wave-function collapse, though not implementing an example, I'd suppose tracking mutations and backtracking might be more effective for large matrices.
I just thought that it would be great to create a wave function based scrolling background (and terrain) to build an endless Mario like game!
At 1:16:57 you say that your function doesn't need recursive collapsing but that's exactly what would stop your algorithm from needing to restart/backtrack.
What an amazing studio, I want to teach un UA-cam just like you, great teaching, I just love it 😍
I think that to determine the possibility of the neighborhood of different elements, you can use the Fourier transform, applying it to pairs or triplets of points on the line of contact. After conversion, there should be no high-frequency components, or perhaps it is possible to define some threshold value for their number.
I've literally being -dying- for a Daniel shiftman tutorial on this!!!!
I self-discovered wave function collapse methods while playing minesweeper.
"hmm, of this one's a two, and this adjacent one with a larger range is also two... so that means those extra boxes don't contribute to the number of mines and therefore must be empty"
I think the world of programming is driving all of us to madness and existential crises, whilst also teaching us the secrets of the universe.