Coding Challenge 171: Wave Function Collapse

[@TheCodingTrain]

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

[@efimov90]

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.

[@psibarpsi]

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.

[@DeathSugar]

actually it looks really like cube/square marching not a wave function collapse

[@Elizabeth-vh6il]

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.

[@Nikarus2370]

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.

[@natyacodes]

you are truly the bob ross of programming, respect to you sir!

[@bastederbeste]

can't believe how accurate this is

[@hugod3919]

Is there in the community of Bob Ross someone who says that his the Coding Train of painting?

[@jameschamblin7120]

"There are no mistakes, just happy little bugs." :D

[@krishnachoubey8648]

@@jameschamblin7120 Chinese people have entered the chat with bug soups

[@ifroad33]

Best description ever

[@hydra4370]

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

[@MattRose30000]

I LOVE the whiteboard editing. Nothing agains Dan's handwriting though 😅

[@ddjazz]

Agreed , loved the editing , must have taken a lot of work

[@jimknopf7219]

agree

[@SpicyMelonYT]

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!

[@TheCodingTrain]

Keep at it!

[@SpicyMelonYT]

@@TheCodingTrain Will do thank you!

[@bradb9635]

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.

[@BarneyCodes]

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!

[@TheCodingTrain]

Hope this helps! It's a long one!

[@BarneyCodes]

@@TheCodingTrain I'm sure it will :)

[@pvic6959]

@@TheCodingTrain Cant wait for the next installment!

[@RaccoonEatingCacti]

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!

[@pvic6959]

and 24:32! lol

[@zachmaw]

This moment precisely is why this new viewer will be subscribing forthwith.

[@noxid86]

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.

[@TheCodingTrain]

Thank you for sharing I’m so happy to hear!

[@burgl001]

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!

[@alecgolas8396]

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.

[@sciverzero8197]

I like using bitmasks for handling binary connections 1111 becomes 15, 1110 is 14, 0111 is 7 etc 0000 is 0. These four sides create a single 4 bit number, 0-15, which covers every possible arrangement of connections on four directions. You can then simply assign your tiles their array index based on what their connections are. Blank will always be index 0 because it has 0000 connections. You ca extend it further to handle diagonals and it becomes a 0-255 number, 8 bits, a standard format, and still handles all possible types of connections. You can extend it all the way to 32 directions this way and still use a standard int to hold the value, but I find 8 (one byte) is usually plenty for most tile based things. Its once you start dealing with weird shaped and inconsistently sized things, like maybe rooms in a floorplan, that's where you run into... logical issues. I don't have a good solution to that which is one reason I'm here now! Maybe I'll find some insight.

[@RupertBruce]

I agree, a bit per edge is all you need. Flip the bits to find the matches, then flip the bits of the matches to find the set of tiles that suit each edge. Avoid concave shapes!

[@PixelThorn]

This approach is used in marching cubes

[@PatrikBergsten]

This is the way to go. Used it for a mazegenerator not too long ago. Would probably have gone crazy if I tried doing it differently

[@Siluni69]

If i have to make collapse function, i'll definitelly go for bitwise operator. less CPU and for/while to write

[@nikolais6452]

isn't this the premise of enums? which provide better naming (am not from a C background so correct me if i'm wrong)

[@SpicyMelonYT]

A continuation of this concept would be amazing. Actually a whole series would be even better but no pressure!

[@Deanin]

This trailer was so good! I kinda want to watch a Coding Train movie now. 👀

[@TheCodingTrain]

Well, this video is 80 minutes long!

[@flabort]

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.

[@TheCodingTrain]

@@flabort Before there was a premiere there actually was a trailer playing, you can find it here! kzbin.info/www/bejne/jqCaZ5aQo9B2jrM

[@lucianchauvin8587]

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.

[@Jaegerminor]

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!

[@telemakotv]

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!

[@TheCodingTrain]

Thank you for you all of your contributions!!

[@blasttrash]

where did you give the talk? In your college or work?

[@telemakotv]

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

[@ItsJustAstronomical]

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.

[@vintagemars4614]

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.

[@draeath]

I can't say I have ever seen someone bring so much enthusiasm to a discussion about entropy, and I love that energy!

[@MiguelArconadaManteca]

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!

[@erik....]

It is used in many games.

[@estousemcriatividadepraumnome]

A lot of rogue like games use systems like this, I recommend checking out GDC's spelunky presentation

[@revimfadli4666]

@@estousemcriatividadepraumnome Unexplored's cyclic dungeon is a notable example

[@lolcat69]

I will use it in my game...

[@andradegilmar]

That video was epic! Loved your persistence, the explanation and the editing. Funny, entertaining and I learned all sort of things about coding

[@chair547]

The sheer number of Errors you get just from using a dynamically typed language makes me want to cry.

[@EpicGamer-ny1fu]

The errors aren't from using a dynamically types language.. it's from using the language wrong

[@Pathdrc]

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.

[@carmenhull6092]

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

[@Zendath666]

I know nothing of programming but this is strangely relaxing and intriguing to watch.

[@klaskallqvist7108]

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)

[@paulkerrigan9857]

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.

[@unchaynd7266]

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!

[@jimmenez3668]

i like that you have no music, this way i can play my own while watching it!

[@SpicyMelonYT]

WOAH the board editing was awesome. Definitely worth what ever extra time that took to do it.

[@WibleWobble]

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

[@DIProgan]

It's great to all these years later have an understanding of how the Diablo series works.

[@Shrooblord]

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

[@hikari1690]

Haha this guy. His outsides might be growing older but his insides are forever young. Love it

[@thomaswesley9037]

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.

[@seven-alpha-ten]

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

[@levioptionallastname6749]

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

[@navibongo9354]

Cant believe how fun you make programming look! Ty for the great tutorial!

[@DemisM]

Thanks for making coding fun! Whenever I watch your videos I get motivated. Your positivity towards the code truly is inspirational.

[@KeithKritselis]

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

[@timothyhumphreys1231]

I absolutely loved the way you explained wave function collapse, I'm an experienced sodoku player and it made total sense!

[@Gonras]

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!

[@pointlessviewer]

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!

[@blahblahblah118]

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

[@mk17173n]

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.

[@HeraldOD]

I first learned programming with your early processing videos, it's crazy to see you're still around! Thanks for all the knowledge

[@coemgeincraobhach236]

That was the best description of entropy I'v ever heard.

[@alakhdar100]

my mind is just blown, I love you and the marvelous work you do, please never stop.

[@0969superman]

rotoscopy and overall editing are on point ! great job whoever edited this :D

[@iamwhatitorture]

Editing by Mathieu Blanchette Animations by Jason Heglund from the description

[@dhollm]

This video kept me and my 14 & 11 year old kids totally engrossed, even kinda late into the evening! Thanks

[@TheCodingTrain]

Wow! So great to hear! Those are the same ages as my kids ❤️

[@patchstep]

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.

[@TheCodingTrain]

Oh such a good tip!!

[@witsepanneels6085]

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

[@eboatwright_]

Such an awesome explanation! Can't wait for the overlapping algorithm

[@skaruts]

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

[@TheCodingTrain]

I'm so glad to hear this! I really need to get to part 2 and the overlapping model

[@skaruts]

@@TheCodingTrain fortunately I only need it for tiles. :) I'm intending to use it for proc-gen roguelike maps.

[@monsieurwieselle]

I enjoyed the editing, good job Mathieu Blanchette!

[@pirateskeleton7828]

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.

[@ThomasLe]

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

[@reardoor]

I've literally being -dying- for a Daniel shiftman tutorial on this!!!!

[@Mrjcowman]

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

[@MikeGillenDuchalais]

yeah that's what i thought

[@fuzzy-02]

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.

[@Brunoenribeiro]

"We are close to the end now" Half an hour later: "I'M A TILE"

[@vorpal22]

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

[@Tordek]

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.

[@OrangeC7]

This video made me realise that Carcassonne is just wave function collapse: the game

[@NeinStein]

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

[@KurtWoloch]

What I'd really like to see is... taking screenshots of various classic games like Pac-Man, Donkey Kong, Burger Time, Mario Bros., Scramble, Zaxxon, Frogger, Marble Madness etc., extracting 8x8 pixel tiles from those screenshots and then limiting the legal combinations to the combinations actually occuring in the screenshot... and then composing new images of those tiles and the inferred rules.

[@TheCodingTrain]

Yes, I love this idea!

[@goodboiadvsp3297]

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

[@almostoptimal4598]

Fascinating topic with so many directions. I would love to see more.

[@rubenlarochelle1881]

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.

[@vincentverweij1053]

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

[@JV-pu8kx]

Now I know how games like SimCity and Minecraft create randomly generated maps! Thank you!

[@justrobin2176]

This could be an excellent way of encryption where the image in output is an encrypted message.

[@Linuxdirk]

I love your "chaotic good" videos 😊 It's also a pretty cool idea and the results are awesome.

[@Sayamak]

Very educational and entertaining. Those 78 minutes are totally worth it!

[@benflightart]

Thanks this actually helped me build my own wave function collapse system in unreal engine.

[@WillEhrendreich]

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.

[@LeeOades]

Just wanted to add my ❤! Great, fun video. Thank you for all your coding and video editing efforts!

[@crumpuppet]

the graphics and editing in this video are really great :) the content on this channel just keeps getting better and better.

[@R67K]

I love this video. And that you managed to learn javascript. You write better code than a lot Senior Devs i met.

[@waltercisneros9535]

What an amazing studio, I want to teach un KZbin just like you, great teaching, I just love it 😍

[@Achelon]

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.

[@Achelon]

oh my, and your video finds backtracking at 1/2 the video end point O.O I'm still some way off :D

[@querela92]

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

[@CarnivalBen]

The Wave Function Collapse is cool, but the whiteboard graphics overlay is even cooler :)

[@subinaypanda9936]

Really you are a very good teacher. And the topics you choose are always very interesting.

[@KnakuanaRka]

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.

[@Palamdrone]

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.

[@TheCodingTrain]

Thank you for this nice and constructive feedback!

[@willtheoct]

its thrilling to see a high skill programmer make high skill algorithms. long live javascript

[@andrewcpu]

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.

[@IgneousGorilla]

Looks amazing

[@MattRose30000]

Teaching the concept of entropy with Sudoku is something I never thought of. I might steal that idea for a lecture :P

[@mr_hexo]

I never even knew this was a thing. Gotta try it out! Love your videos!

[@henriqueers]

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!

[@joshparsons5795]

watching this feels like my college courses but more wholesome and easier to understand.

[@RupertBruce]

Instead of splitting the side into sockets, have a nullable Constraint on each side. Each cell has an array of 4 nullable neighbors and another array of 4 nullable constraints. If the neighbor is null it is an edge (no wraparound). If the constraint is null, the cell is blank. The constraint object satisfies IEquatable interface.

[@roamingcelt]

mind blown. watching this gave me the idea of using Markov chains to save the possibilities.

[@Xlblaze1987]

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

[@papricasix]

You are a very friendly and funny person and I really like your videos! They are so enjoyable and educating! ❤

[@recurvestickerdragon]

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"

[@Illogical.]

I made this in Minecraft today. Minecraft Bedrock edition specifically. it took 12 command blocks. my version is based on which uncreated tile is closest, not which one has the fewest combinations, tough counting and comparing the combinations probably wouldn't be tat difficult if that had been what I was going for.

[@nonamethnx8216]

at 31:20ish the issue with the enums being object keys is cause the object always convert your keys to a string. so youre not passing a variable, youre passing 'BLANK'. you can use the same syntax as you would to call the keys dynamically using square brackets, ie object[key], but to create the object. so if you do { [BLANK]: [array], [UP]: [array], ... } that will create the exact object you want, ie { 0:[array], 1:[array], } (also, I can't believe I started watching you before I knew any programming (3-4 years ago) and now I know enough to leave a helpful comment!)