Coding Challenge 171: Wave Function Collapse
ฝัง
- เผยแพร่เมื่อ 20 พ.ค. 2024
- Straight out of quantum mechanics, Wave Function Collapse is an algorithm for procedural generation of images. In this video (recorded over 3 live streams) I attempt the tiled model and explore a variety of solutions to the algorithm in JavaScript with p5.js. Also, check out WFC's predecessor: Model Synthesis (more info below). Code: thecodingtrain.com/challenges...
🚀 Watch this video ad-free on Nebula nebula.tv/videos/codingtrain-...
💻 Github Repo: github.com/CodingTrain/Wave-F...
🕹️ p5.js Web Editor Sketch: editor.p5js.org/codingtrain/s...
🎥 Previous: • Coding Challenge 170: ...
🎥 Next: • Coding Challenge 172: ...
🎥 All: • Coding Challenges
References:
💡 WFC Challenge Suggestion: github.com/CodingTrain/Sugges...
🗄 Wave Function Collapse Algorithm: github.com/mxgmn/WaveFunction...
🗄 Model Synthesis: paulmerrell.org/model-synthesis/
📣 Wave Collapse Function algorithm in Processing: discourse.processing.org/t/wa...
🗄 Array.prototype.filter(): developer.mozilla.org/en-US/d...
🐞 Encoding tiles symmetry and rotation #14: github.com/CodingTrain/Wave-F...
🐞 The issue with asymmetric tiles and an easy solution #16: github.com/CodingTrain/Wave-F...
🗄 Array.prototype.reverse(): developer.mozilla.org/en-US/d...
Creative Works Featured:
🎨 Oisín: Wave Function Collapse for poetry: github.com/mewo2/oisin
🎨 Townscaper: www.townscapergame.com/
🎨 unity-wave-function-collapse: selfsame.itch.io/unitywfc
🎨 Zelda WFC: observablehq.com/@makio135/ze...
🎨 Wave Function Collapse Demonstration: oskarstalberg.com/game/wave/w...
🎨 Infinite procedurally generated city: marian42.de/article/wfc/
🎨 Generating stairy scenes: exutumno/status/8...
Live Stream Archives:
🔴 Day 1: • Wave Function Collapse...
🔴 Day 2: • Wave Function Collapse...
🔴 Day 3: • Wave Function Collapse...
Videos:
🎥 Solving Wordle with Information Theory: • Solving Wordle using i...
🎥 Pixel Array: • 11.3: The Pixel Array ...
🎥 Arrow Function: • 16.3: ES6 Arrow Functi...
🎥 Higher Order Array Functions: • 16.5: Higher Order Fun...
🚂 Matrix Transformations: thecodingtrain.com/tracks/tra...
🎥 Oskar Stalberg - Wave Function Collapse in Bad North: • EPC2018 - Oskar Stalbe...
Related Coding Challenges:
🚂 10 Maze Generator: • Coding Challenge #10.1...
🚂 162 Self Avoiding Walk: • Coding Challenge 162: ...
🚂 165 Slide Puzzle: • Coding Challenge 165: ...
Timestamps:
0:00 Day 1! Wave Function Collapse!
2:00 Entropy in Sudoku.
5:41 Comparing Sudoku to WFC
9:24 Starting to code.
11:05 Collapsing cells.
13:30 Evaluating entropy.
18:47 Updating entropy after collapse.
22:45 Data structure for rules.
24:50 Implementing rules for next collapse.
36:28 Explaining the rules.
38:45 Day 2! Refactoring the code.
39:26 Create a Tile class
44:57 Generate the rules from Tile objects.
55:40 Using new circuit board tileset.
1:00:40 Day 3! Dealing with asymmetrical tiles
1:01:56 Assigning index values to edges.
1:06:53 Incorporating edges into code.
1:10:05 Change adjacency for assymetry
1:12:06 First assymetric WFC image!
1:12:40 Restart if no valid cell found.
1:15:48 Next steps!
1:18:05 Thanks for watching!
Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound
🚂 Website: thecodingtrain.com/
👾 Share Your Creation! thecodingtrain.com/guides/pas...
🚩 Suggest Topics: github.com/CodingTrain/Sugges...
💡 GitHub: github.com/CodingTrain
💬 Discord: thecodingtrain.com/discord
💖 Membership: th-cam.com/users/thecodingtrainjoin
🛒 Store: standard.tv/codingtrain
🖋️ Twitter: / thecodingtrain
📸 Instagram: / the.coding.train
🎥 Coding Challenges: • Coding Challenges
🎥 Intro to Programming: • Start learning here!
🔗 p5.js: p5js.org
🔗 p5.js Web Editor: editor.p5js.org/
🔗 Processing: processing.org
📄 Code of Conduct: github.com/CodingTrain/Code-o...
This description was auto-generated. If you see a problem, please open an issue: github.com/CodingTrain/thecod...
#wavefunctioncollapse #generativeart #p5js #javascript
![[Full Episode] Hell's Kitchen Thailand EP.15 | 19 พ.ค. 67](http://i.ytimg.com/vi/Mx0ColswPls/mqdefault.jpg)
![CAMPปลิ้น | EP.75[1/2] ชวนแร็ปเปอร์เที่ยวประแสแบบไม่ต้องตามกระแส](http://i.ytimg.com/vi/J5ds2AxDp24/mqdefault.jpg)
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
The sheer number of Errors you get just from using a dynamically typed language makes me want to cry.
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 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!
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!
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.
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!
This approach is used in marching cubes
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
If i have to make collapse function, i'll definitelly go for bitwise operator. less CPU and for/while to write
isn't this the premise of enums? which provide better naming (am not from a C background so correct me if i'm wrong)
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!
"We are close to the end now"
Half an hour later: "I'M A TILE"
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.
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.
Haha this guy. His outsides might be growing older but his insides are forever young. Love it
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! th-cam.com/video/Xo76cZnkCXQ/w-d-xo.html
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...
A continuation of this concept would be amazing. Actually a whole series would be even better but no pressure!
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
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!
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!
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.
Thanks for making coding fun! Whenever I watch your videos I get motivated. Your positivity towards the code truly is inspirational.
I can't say I have ever seen someone bring so much enthusiasm to a discussion about entropy, and I love that energy!
my mind is just blown, I love you and the marvelous work you do, please never stop.
WOAH the board editing was awesome. Definitely worth what ever extra time that took to do 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)!
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 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!
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
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
I first learned programming with your early processing videos, it's crazy to see you're still around! Thanks for all the knowledge
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.
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.
This video made me realise that Carcassonne is just wave function collapse: the game
the graphics and editing in this video are really great :) the content on this channel just keeps getting better and better.
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!
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!
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.
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 never even knew this was a thing.
Gotta try it out!
Love your videos!
rotoscopy and overall editing are on point ! great job whoever edited this :D
Editing by Mathieu Blanchette
Animations by Jason Heglund
from the description
Well done on the editing, marvelous job!
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
I love your "chaotic good" videos 😊 It's also a pretty cool idea and the results are awesome.
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.
I absolutely loved the way you explained wave function collapse, I'm an experienced sodoku player and it made total sense!
This is Brilliant ! I love your energy and the way you teach !!!
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.
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 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.
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
Fascinating topic with so many directions. I would love to see more.
Ended up watching the entire thing! Cant wait for episode two of this specific one :D
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.
I know nothing of programming but this is strangely relaxing and intriguing to watch.
This could be an excellent way of encryption where the image in output is an encrypted message.
Looks amazing
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've been wanting to play with this for a while! great vid
Can't wait for the continuation of this episode!
Absolutely fascinating stuff! Thank you!
This is amazing. Thank you so much for introduce me in such concepts!!!!
Just wanted to add my ❤! Great, fun video. Thank you for all your coding and video editing efforts!
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".
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
What an amazing studio, I want to teach un TH-cam just like you, great teaching, I just love it 😍
I love this video. And that you managed to learn javascript. You write better code than a lot Senior Devs i met.
That was the best description of entropy I'v ever heard.
Really you are a very good teacher. And the topics you choose are always very interesting.
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!
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.
Superb video! Such a joy to watch, and lots of good thingies to think about!
Cant wait.
me too
@@cptryums602 me three
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!!
That was super entertaining, and edumicational too! Now I'm all inspired, thank you coding guy!
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
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"
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.
Yes, I love this idea!
Love the editing. And ofcourse the content as well.
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.
You are a very friendly and funny person and I really like your videos! They are so enjoyable and educating! ❤
I was looking for something exactly like this, thanks for the video
Man, your videos are amazing. Thanks!
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.
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
I enjoyed the editing, good job Mathieu Blanchette!
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.
Absolutely amazing, thanks for the video.
Please make a video about Overlapping Wave Function Collapse!
Yes, I really need to work on this!
so much fun please continue the series!
On my list for 2023!
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
Such an awesome explanation! Can't wait for the overlapping algorithm
from my days messing around with LOD structures... a structure that is really neat here would be a node tree.
usually we use it to subdivide polygons, but its also pretty nifty when you want to lookup neighbor elements in general.
Hey Daniel, you can duplicate the line where the text cursor is, by using alt+shift+down arrow (also works with multiple lines selected)
Thanks for the awesome videos, as always!
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
I've been waiting for this one!!!!
Immediately subscribed. I love the approach.
I've literally being -dying- for a Daniel shiftman tutorial on this!!!!
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.