Coding Challenge 171: Wave Function Collapse

hello and welcome to today's coding challenge wave function collapse this was originally suggested in 2017 on the coding trains github suggestion box the algorithm itself was originally pioneered by mxgmn on github in this wonderful repository with lots of sample imagery and explanation the core idea of the wave function collapse algorithm is to take an input image and generate an output image many output images that all mimic the style the pattern of that original image now you might be thinking aha don't we have giant deep neural networks that can do this yes but this algorithm is incredible because it uses none of that and it is just a joy to watch i should say if you're here thinking oh goody here comes a step-by-step tutorial on how to implement the wave function collapse algorithm it's probably not what you're going to get i have not done it before other than a brief failed attempt that didn't get very far so i'm here to try it again what you're seeing to the left and right of me is hopefully the end result of this video and if i've gotten there if i've succeeded it hopefully looks interesting and like something you might want to watch so stick with me all aboard let's try to make wave function collapse happen in addition to the github repository which has the source code for the original implementation of the algorithm as well as a full explanation of the algorithm as well as many many many links to forks and spin-offs and variations of it the other resource that i am following closely for this challenge is the wave function collapse post on the processing forum itself uh thank you very much to solab who started this thread tons of great information there i highly recommend you take a look at all the explanations and diagrams and source code as well let's begin by answering the question why is it called wave function collapse well this is an algorithm for procedural generative images which could be applied to art and games and so many different kinds of creative things that you might try the term itself comes from quantum mechanics what does it mean to collapse a wave function to answer this question let's talk about another term entropy i want to talk about entropy in the context of information theory if you're a fan of the game mortal there's a wonderful three blue one brown video that goes through how to optimize your solution for any given wordle of the day with the concepts of entropy and information theory i'm going to attempt to explain it to you in the context of a different game sudoku sudoku is a game where you fill an entire board with the digits one through nine each digit needs to appear uniquely in every row in every column as well as every three by three section this means if i have a blank sudoku board every cell has nine possible digits that could be in it the average entropy of this system we could think of as nine what's exciting about the concept of entropy as applied to games like wordle or sudoku is when we know some additional information like aha we see the board comes with one number already filled in like the number nine here then suddenly the entropy is reduced for these two cells all of these cells all of these cells and all of these cells here right all of those cells only have eight possible numbers that could go in them if i were to say that there's a two here then suddenly all of these cells only have seven possibilities in them and how does this relate back to wave function collapse and quantum mechanics the idea of collapse in the context of entropy is to collapse all the possible states down into one remove all the entropy from a single variable of the system so this cell in sudoku is collapsed to nine this cell is collapsed to two as certain cells collapse and their state is revealed to be a single option the entropy is reduced for its neighbors and we can start to make guesses there and further collapse and further collapse and further collapse until we've solved the sudoku board i'm going to start over with an example sudoku board that i got off the internet [Music] the process of solving a sudoku puzzle is exactly the same process that lives inside the wave function collapse algorithm the idea is to start with a set of tiles in this case many of them have been collapsed already and look for the tile with the least entropy meaning the fewest possible numbers that could go in it so i'm going to look at this for a minute here let me use my brain power so i've been going through and noting what numbers are possible in any given tile and as i was working through it i noticed well there has to be an eight down here somewhere and there can't be an eight in either of these two columns because of these two eights there can't be an eight here and there can't be an eight here so the only possible number in this particular cell is an eight so i can collapse it and fill in the eight i'm looking for the tiles with the least amount of entropy collapsing those tiles and then going and looking for the next tile with the least entropy and so on and so forth if at some point i don't have a tile that has only one option left i might just have to make a guess and go with it unless i get it realize i'm stuck and have to backtrack and try a different option [Music] now that i've finally solved this sudoku puzzle we can look at a p5 canvas and try to understand how does the process for solving a sudoku puzzle map to the process for generating an image through wave function collapse now there are two ways to approach wave function collapse there's the tile model and the overlapping model i'm going to start with the tile model the idea of the tile model is that you have pre-made tiles i'm going to first implement a tile model with a simple set of five tiles one will be blank one will have a small line pointing up and a horizontal line across one with a smaller line to the right vertical line smaller line down smaller line to the left my p5 canvas i can think of as a four by four grid that can have any one of these tiles in any spot on the grid so right now the average entropy is uniform across all the tiles there are five possible tiles that could go in any of them maybe i pick this tile then i need to pick one of these random five options let's say i pick one and i fill it in now this is all an arbitrary made-up system that i'm doing right now and trying to keep it somewhat simple the possible tiles for most of these cells is still just five however by placing this tile here i have reduced the entropy for the neighboring tiles the only possible tiles that can go to the right are ones that connect to this line right here that would be tile 4 tile 3 and tile 1. so there are only three possibilities here the only possible tiles that can go here are tiles three two and four i need something to connect to this so three possible tiles and we're gonna see this in all of these so now if i'm looking for the next tile to do i want to pick one that has the least entropy so now i'm only rolling a four-sided die to pick one of these four times let's say i pick this one and i roll the dice and i happen to pick tile four now the entropy for this spot is now also only three let's say i roll the dice and i happen to pick this tile let's look at what is the entropy for this particular tile now i need a tile that has connections on both the bottom and the right look at that only this one now so only this tile can go there by the way i made a terrible error i was just starting to fill all these out i kept i was right about there being three possibilities three possibilities three possibilities this one here actually only has two possibilities because if there is no connector pointing down then the only two options that have nothing connecting to the top are three and zero something with a blank top so this actually had a entropy of two so if i wanted to keep going i could flip a coin maybe i come up with three tile three and this goes here let's see what happens if i keep going and voila i generated this image with wave function collapse i could run this again roll the different dice again and get another image and another and another and another it took me quite a long time to work this out with my brain and draw it hopefully if we can write the code to load these tiles to know which tiles go next to which tiles we can generate these images lickety-split i am finally ready to start writing the code all i need is a blank p5 sketch and then i have here pre-made tiles blank down left right up to start i'll load all the images using preload into an array let's just draw them to make sure they're there whoops i forgot the tiles are in a directory that i called tiles this algorithm even though it feels like my explanation is going around around in circles is quite simple i think the complexity here is figuring out what kinds of data structures do i need to hold on to the information about the grid of tiles as well as which tiles are allowed to neighbor which other tiles let's use an array to store the state of every cell in that grid i want to start with just a four by four grid actually let's be even simpler let's start with just a two by two grid and i'll use this variable dim short for dimensions i'll start with putting in negative one to indicate nothing's been picked yet in every spot on the grid actually no let's not do that let's make an object for every spot of the grid and i'm going to create a variable called collapsed which is false it's not collapsed and then i'll call it options and they each should start with all five options this might be silly but let's set up some like variables to keep track of what these index values are now i can go through every element and draw it if it's been collapsed [Music] [Applause] [Music] all right i didn't mean to do that but i just wrote out a ton of code let me walk you through it step by step so first of all i need to calculate the width and height of every cell on the grid that's the total width of the canvas divided by how many columns and how many rows that dimension variable then i'm going to count through every row and every column find the index into that one-dimensional grid array this is the same thing i do in all of my videos about the pixel array and then if it's been collapsed there's only one option left so find the correct image and draw it otherwise just draw a black rectangle so if i'm doing my job correctly if i were to refresh the page i should see all black rectangles and let's actually give them a white stroke so we kind of see this grid great no cells have been collapsed let's collapse one of the cells manually just by hard coding it and see if the we get the proper result it's collapsed and we should see the up tile in it options is not defined oh cell dot options and we need to make sure we draw the image the right side there we go so what's next here i manually collapse the cell but what i should have done is looked at all the cells evaluated and measured their entropy and picked one that had the least entropy so let's do that i'm thinking about how to do this oh let me sort the array i mean i can't sort the array it'll be out of order but i could sort a copy of the array because i have objects in it oh this was a good thing that i put objects in there because the arrays just point to the object so i get multiple arrays with the same object the same data in them but in different orders oh this is great and in javascript the slice function will just make a copy of the array then i can call the sort function if i was just sorting an array of words it would be easy to do alphabetical order or ascending or descending order but here i've got to define my own compare function order to say how i'm going to sort them if this strange arrow syntax is unfamiliar to you let me refer you to some video i made 100 years ago about the arrow function but essentially this function is defining given two elements in an array a or b how do i define which one goes before or after the other and the number of options left for that particular cell is what defines which one should go first or second let me just hard code that element two only has two options so when i sort this array i should see that third element in the first spot of the array so let me log the regular grid unsorted and the grid copy sorted and let me just add to the end of draw no loop because i only want to do this once right now oh beautiful the first array is 5525 and then the second one is two five five five wonderful now hmm what if there were two cells that only had two options left the wave function collapse algorithm would say take all of the cells with the same amount of entropy and pick randomly amongst them let's go through the array i'm trying to think how to do this i'm going to create a variable called stop and go through the array until i find one that has more options than the one previously okay let's actually let's say length equal grid copy i'm going to have a baseline length which is the length of that first element of the array i'm going to go through the array if any given element has a length of options and i'm always forgetting this greater than what that first element does break out of the array and save that stop index because then i can say grid copy splice starting at the stop index all the way to the end so how many elements splice removes elements from the array and i want to remove from that element all the way to the end there's got to be a more elegant way of doing this but i'll just say grid copy dot length minus stop index there we go i have now sorted the array according to its the entropy of each cell and i have a new array with just the elements that have the least entropy so now i can pick one randomly so i'm going to pick one randomly from the copy of that array and then i need to collapse that one let's call this cell and then this is the pick is now as is always true on the coding train this could all be refactored in many more elegant ways and i look forward to hearing all about it in the comments about how you're doing it but basically i want to pick the cell collapse it pick from its available options and then i'm just overwriting the array the what should be left over is an array with one thing left in it so if i were to do that i should see either element two or element zero with either blank or up in it that's element zero with up element two with up so running this a bunch of times it works it works we're getting somewhere breaking news the live chat on twitch is telling me that in the splice function if i don't give it a second argument it'll just remove everything until the end boy i spent a lot of time working that out this is much simpler we're not that far away i think from the end here [Music] let me get rid of these hard-coded options sketch line 51 oh because the stop index oh my stop index has a flaw in it i will just say if stop index is greater than zero splice it out i removed everything from the array because they were all equivalent okay there we go so now this is its random first pick happening here the next step is to reevaluate all the tiles and reduce their entropy where necessary so for example this tile right here same entropy but the one up top and the one to the right the entropy changes because by picking that tile in the top right it reduces the number of options that go to the left and underneath i need to create a new array which is the sort of next generation of tiles if it's already been collapsed then it's just a copy of what it was before right it can't change it is what it is and i can just bring it over directly otherwise i need to look above look to the right i need to determine what are the valid options based on its neighbor up to the right down and to the left here is where i need yet another data structure i have five tiles what if i had an array where every element of the array stored a list of valid neighbors so what are the valid neighbors for a blank tile oh wait wait wait wait wait wait oh my goodness each element of the array needs to also be an array this should really i could really think of this as a lookup table because i'm using numbers to number the tiles it's really doesn't really matter whether it's an object or an array but you can kind of think of this as a lookup table because the zero blank tile it needs to have things that can connect to it up to the right down or to the left so i'm always going to store the information in this example in a clockwise direction so the tiles that can go next to it pointing up are like a tile that can go above this blank one would be another blank one and then tile one because this does no connection down so zero and one to the right could be a blank one and tile two it's a down could be a blank one and tile three to the left we could put tile four could go there which is or a blank one zero and four so now if i were to look at tile one however and again this is just me coming up with a way of doing this right now there's probably a more standard or optimal way of doing this i'll hopefully address that at some point later in this 700 hour video but here what could go above it for tile number one tiles that could go above it are two three and four but not a blank tile tiles that could go to the right are well another one three or four that could connect below below is blank so it could only be a zero or a three and then to the left what tile can go here two can three can or another one the good news here is i've assigned variable names to each of these tiles so that it'll be easier for me now that i start to write this out in code i don't have to remember the indices i could just think if it's a blank one the things that could go above it are an up or another blank to the right a right or another blank let's start putting that in the code so let me create a variable i don't call it rules let's call it rules let's make it an object now what can go next to a blank tile above it we said could go a tile pointing up or another blank to the right a tile pointing to the right or another blank a tile pointing up above it a tile that goes to the right the left or down is fine let me see if i can just quickly put in the rest of these [Music] all right i fit all of the rules here i believe this is correct i'm going to think about this for a bit and check the chat to see if i mess something up all right here's one that i found is wrong for the tile pointing up below it is either blank or down and then to the left is right up or down let me address something i think i've made this a little bit more complicated than it needs to be for this particular scenario maybe the way i'm doing my data structure is good for all broad set of possible tile arrangements but in this case even though i do have five tiles each with four neighbors each side is only one of two possibilities so really i could say this blank tile can only connect to other tiles that have a blank represented by a zero on any side of it this tile that is pointing up i could say connect to any tile that has a connector a one or that is blank or zero so really for each of these i only need to store four numbers and then zeros need to connect with zeros and ones need to connect with ones i'm not gonna double back and redo mine this way yes i will i'm just going to categorize the edges as a or b or zero or one but this is a good exercise for the viewer looking at it in this simpler way about the kinds of connections that exist so now we need to build what are the remaining options left i need to build up what things i could be by looking at my neighbor and only if j is greater than zero so i'm going to look at the tile above me only if i'm not in the first row now of course i think if you look at the wave function collapse in the original implementation it does wrap around and uh that could be done here but let's simplify things by just not looking at the neighbors above do i start with all the possibilities and then remove them if they don't exist yeah that would be a way of doing it so i'm starting with a baseline of this tile could be anything and this should actually be outside of here because i'm going to do this for all of them now i'm looking at the neighbor above and looking at what possible tiles it could be then valid tiles i could be are from the rules this is the list of valid tiles i'm this tile and i'm looking at the tile above me and maybe the a tile above me only can be like left or right so i need the valid tiles that go below down to a left tile and i need the valid tiles that go below are down to the right tile in the original array up right down left the order is zero one two three so i'm looking for two the rules for that particular tile the ones that are valid down i think i need to rethink my naming but now what i want to do is look at what i have in my range of possible options i'm going to remove them if they're not valid you know what i should do i'm going to make a function we're going to do this so many times check valid options valid so i'm going to pass in these are the existing options and i'm going to pass them into a function to check if any of those options are included as valid so somewhere else in my code right here the this is the array and these are the valid options is that the order i put them in the array is options and what's valid if valid includes array index i great so i want to check or i'll say not if the option that is in that array is not something valid then i should remove it it's confusing what are in these things but let's just remember maybe a valid is blank and right basically what i'm doing is i'm going through every element of this array blank up right down left let me see is it in the valid options oh if it is that's good don't do anything if when i get to up it's not valid let me remove it out of there this would result so hopefully that helps you make sense of it i don't love maybe i should i'll just say like current equals array index i maybe just element so this helps maybe helps you read it a little bit let's look at every element in the array if it's included if it's not invalid get rid of it so now i think i can just do the same thing for all of these looking to the right make sure that i is less than dimension minus one if i'm looking to the right i want to know what's valid to the left of that one which would be up right down left zero one two three let's grab this one for looking down i probably should have checked this with just one of the rules first but i'm just going to put it all out and we'll find out if i've gotten this totally wrong or not i think this is good if it's collapsed i don't need to do any analysis it's done it's picked if it's not start with all possibilities look up to the right look down to the left check that options array and then at the end next tiles index options okay are these new options it's still not collapsed i don't know if i need that or if that's redundant but this is me updating that and then after all of this is done hiles becomes the next tiles and so this can't be a const oh my goodness boy did i just write a lot of code without testing anything let's run this okay write dot options is not iterable iterable oh grid not tiles grid oh my god i was using the images i have an array called tiles which is just the images the array that i'm working with is called grid oh great let's call this next so this can be a const and this has to not be a const all right that's fine still have an error but something slightly better 147. so i just want to look at the rules for a second here there's a flaw the rules is an object so if i were to say rules blank why is that undefined well rules dot blank works i guess i should just make that an array i'm not sure what the best practice is here but if i were to do this this should fix the issue i'm just gonna make this an array since i have everything ordered numerically i don't love this but i think it should be okay oh but now i don't need this i don't need these it's just gonna i just have to have it in the right order well i liked it better when i was referencing it with a name i can't do everything right in this first attempt okay got we got down to 163. we got through all of these next grid index oh next grid doesn't exist so i just need to make it a new object i actually need to create the object it's going to not be collapsed it can be collapsed if there's only one left but that'll happen by virtue of the next round and then give it the options okay no errors amazing i'm just gonna take out these console logs famous last words and let me now add if i click the mouse let me redraw run through draw again so it picked that tile okay sketch.jsjs okay so i got an error the next time through ah this is grid index i forgot it up there so if it's collapsed don't get the image get the other thing there's a flaw in my algorithm let's just look at the grid oh you know i could do i can do console table so console table is a nice thing to just show me the array this is the array none of them are collapsed and they all are five possibilities now when i click it i should see the first one is collapsed and then none of the other ones but what happened in grid copy oh but they still all have five possibilities which is absolutely wrong so there's a big flaw in my algorithm for reducing the possibilities oh by the way when i copy the array i need to filter out any elements that are collapsed filter is a higher order array function that will keep the elements where the function evaluates to true so that should and then so this can't be a const i guess i could make another copy let's look at the grid copy also so now i have all four with five options and now i only have three i got rid of the collapsed ones one which is good but they all seem to have five options still let me look at my check valid function i wonder if this includes is not right this is a list of what's in the array these are the valid ones and so this should be left without a 0 and a 2. oh why do i put those brackets there it's a function that i'm checking if it includes that element these are parentheses not brackets i don't think it worked still oh this needs to be a one splice i took zero zero would take nothing out of the array wait why do i have nothing in the array now oh my goodness ah i need to accumulate all the valid things all together i can't do them individually oh this is totally wrong this is a blank array and then valid options should be itself concatenated with these are the things that are valid put them in the valid options these are the things that are valid put them in the valid options these are the things that are valid put them in the valid options these are the things that are valid put them in the valid options and then check valid options valid options so i've accumulated all of the valid options and then as long as my option is valid across them all then it should be fine is this right i was so confident a second ago no it's giving me all the possibilities wait i was so close for a second there oh no no i still want to check valid individually in each one i want to concatenate all the i was right i was right i just i did it across everything but i need to concatenate for each individual possibility hold on hold on hold on i'm gonna double back explain this there you go that's the correct answer there you go weight function collapse okay hold on like it appeared in my head and i don't know if it appeared in your head also while watching this so let me see if i can go back and explain that this is me i am the tile that's what it's become let's say the tile above me can only possibly be left or right for whatever reason it only has two possibilities so what i need to do is look at all of the valid things that can be below a left tile and a right tile concatenate those together and then as long as anything i can be is included it's fine i think we've all suffered enough that i can change the dimensions to like i don't know let's just try eight well look at that would you look at that that is just absolutely lovely i'm clicking there's no need for me to click i can get rid of no loop and let's let's really go for it people let's make the canvas 800 by 800 and the dimensions i don't know 80 by 80 20 by 20. i've never been so happy to see a result it broke so i have a feeling that i'm gonna need to add some backtracking to this when in doubt take out random seed and run it again so close to making it to the end okay so it can get to the end oh my god i have more to add to this i thought i was done if grid copy dot length equals zero return oh no oh let me put the drawing separately let me draw everything and then if there's nothing left if everything's been collapsed return there we go let's run it again isn't this delightful four days later i'm back a few days later and i know you've been watching what is already like a very long video about wave function collapse and i did get to a point where i made something which is pretty great i'm looking at this example of this printed circuit board seeing that there are 14 tiles there some of those tiles represent four possible rotations looking at the way that i've implemented this code with an element of an array for every tile with all of the possible adjacencies i think it would be incredibly difficult for me to hard code all of the possible tiles and adjacencies for more sophisticated pattern like this so i'd like to keep going and instead of thinking of the tiles that i started with as five possibilities i'm gonna start with just two possibilities and rather than enumerate what's possible here i'm just going to categorize the edges as a or b or zero or one what this means is when i'm going to place another tile next to another one a zero has to match with a zero a one has to match with a one and i could automate the rotation of this tile into its other possibilities and then enumerate all of the adjacency rules with code and i think if i create a tile class that keeps track of what image is it and what are its edges still going in the same order top right bottom left that this will make the code more readable and easier to figure out and work and make for more fun wave function collapsing of everything i think my brain is collapsing so let me start by making the tile class i had used the tiles array to load the images so now i'm going to actually have an array called tile images now that i've done that i only need to load the blank and up tile the first tile can be the blank one with those edges the second one would be the up tile with those edges now what if i allow myself to create new tiles based on previous ones what if there were a function that returned a new tile which is one rotation two rotations or three rotations of another tile the rotate function needs to do two things rotate the image and rotate the edges so i make a blank canvas with the same width and height of the image set the image mode to center rotate by half of pi or 90 degrees times the number of rotations so one would just be one rotation let me store the width and height in separate variables which i think will make our lives a little bit better today i'm going to call this variable new image because i'm getting confused between this dot image which is that tiles image and a new image i have the new image technically it's not a p5 image it's just a p5 graphics object but those two things are going to function the same way so i think it's fine now i need to rotate the edges so each new edge is the previous edge plus the number of rotations or minus is it minus this edge was previously down here and the index values go zero one two three so the new edge is the previous edge minus one however if i'm edge zero minus one isn't negative one it's three it's gotta wrap around and get index three a way i can do that is let's create a variable to store the number of edges i can add that to the total so zero minus one is negative one plus the total number edges of four would be index three but if i'm two two minus one is one plus the total number of edges is four so i'd get five ah so all i then need to do is use the modulo operator and this should give me perfect wrap around always take the previous one but if the previous one is negative you're going to get the higher value and it's not one it's the number of rotations so now i can return a new tile with the new image and the new edges so before i go any further i just want to determine if this at least worked rotating these images the difference now is the image is a property of that tile object something is wrong my rotation is not working so i've made a sort of classic error in p5 here where i didn't think about the origin around which i was rotating so i've rotated the image off the canvas that i'm drawing it to i need to say new image translate to the center then do the rotation then draw the image at zero zero so if you zoom in you'll see that the tiling is a little bit of skew that's really just because when i made the images i didn't make them perfectly symmetrical so the rotation isn't perfect but i kind of actually like the way that it looks with it slightly askew but this is not relevant to the algorithm it's just a matter of designing the tile images and ultimately i'm going to use the tile images from here to see if i can create a more sophisticated pattern so now instead of having this big array that's just a mess of all these rules could i procedurally generate the rules by analyzing the tile objects that i'm creating and as long as i'm doing that why not put in the tile object itself lists of valid neighbors this is terrifying but i'm just going to delete all of this from the code now that i have tile objects looking down here would make sense for me to have a cell object i mean i have cell objects they've got a list of options as well as whether they're collapsed or not but i should make a class with a constructor to generate these these names are no longer relevant the list of options can just be the index values to the tiles array so what i want to pass in is the total amount of tiles there actually are then i can fill the array with if there are five options zero one two three four of course that could be done with some higher order functions like fill and map and from and have a ball doing that i actually just spent a little while doing it myself and it was very confusing and i didn't want to include it in this video but here's what it looks like loaded and created the tiles i built a cell for every spot on the grid and now i need to generate the adjacency rules based on the edges for every tile i'm gonna just write a function called analyze and give it all the tiles all the other tiles so the tile objects gonna have to figure this out let's call this the connection is edges index zero now if we look at all the tiles i mean we should check if a tile can connect to itself that is a valid thing to check so i'm looking at all the tiles regardless so if my connection up is a certain value i need to find all of the tiles that have that same connection pointing down which is index two and i'm sure there's a way that i could not do these as four different loops but i'm gonna do it that way right now and maybe this secondary variable is kind of unnecessary and this is tiled index i and this might actually be easier to read i don't the order of the tiles doesn't actually matter so let tile of tiles so if that particular tile down edge matches the tile that i am my edge which is this dot edges then it's a valid connection so now i just need to repeat this for right down and left oh and i don't need to do a separate loop it can all be in here so right is three is equal to one down is zero is equal to two and left is checking if this tile's edge at three is connected to the tile that it's looking at its edge at one now again there's probably a lot of redundancy here but this is just the way that i'm getting started here trying to recreate what i did originally in a bit more of a generic scalable fashion i think this order makes more sense we're loading the images rotating the ones we need to rotate and defining what all the edges are then we're analyzing all the tiles against each other to see what which tiles can go next to each other then we make a grid full of empty cells each cell could be any given tile to start so drawing doesn't change this however is the part that needs to change before i was looking at my rules array now i need to look at the adjacencies that are defined in the tile objects themselves so up looking at the cell up valid options starts as a blank array then i'll need to look at what are the possible options in up and then get the valid ones now are not rules but tiles dot down anything that i could place where i am has to be something that can be below all of the things that could be next to the tile above me is that the only thing i'm changing look at the tiles and look to the left then look to the tiles up no way it's as simple as that okay cell is not defined okay well that's an error i can fix include the cell file blank is not defined where did i have blank let me by the way change the dimensions to just four by four while we're sort of figuring this out ah so the options are when i'm assuming it could be anything let's use the fancy higher order array functionality thing here i need an array with the number of spots in it as the number of tiles there are i need to fill it with something to start so i'll just dip zero and then i can use the map function to map every value to its index so that's its current value which is zero its index is i if i've done my higher order array functions correctly it's an array that has with five tiles has the values zero one two three and four in them okay cannot read properties of undefined reading up well we can start 137 tiles option up what is going on here hi everybody i've been debugging this for a little bit and part of my debugging i said console logs a grid and i'm looking at the grid and the first time i get four cells because i made it two by two only one option left because that one's collapsed five five five and then suddenly look at this cell then rackety brickety brackety brackety those aren't cell objects because i did something really pretty terrible at the end instead of creating the new cell object for the next generation i'm just making an object literal which is not right so i need to say new sell and the options shouldn't this is when a new cell is made how about i could give it options i'm trying to think of an elegant way to design the constructor now so i just did a little testing in the console here that i could determine if a variable is an array by saying instance of array and i'll get true so i think what i can do here in this cell class is i can say if num is an instance of an array then this dot options equals that array it's no longer num it's the array i mean i don't know what to call that variable i'll still call it a num otherwise i'm filling an array with all of the options according to some total so let's just call this value to be a little bit more generic so these are the two different ways i can create a cell object and if i go back to sketch.js i should be able to say make a new cell out of those options oh that's better i see four cells and four cells i still got this error though something is going very haywire here i'm gonna have to do some more debugging oh please hold if tile zero is collapsed i should see one option there tile one should have three possibilities tile two should have two and not be collapsed and tile three should have all five possibilities still so cell number one which is the one directly to the right of the top left should have three options left and it has zero so the bug is there and cell number one is when i is one and j is zero so i have an index so i can debug some things if index is one let's check looking to the left so if index equals one let me look at the tile to the left the tile to the left is collapsed and it is tile index one so it's valid options should be all of the things that can go to the right of tile index one ah the error is not a logic one it is an apples checking against oranges problem the valid tiles are tile objects but my function that i wrote days ago at this point now in the check valid is checking index values against each other so if i go back to this analyze function i shouldn't be putting the actual tile objects in the arrays that are valid up right down and left i should be putting the index of that tile so i do need to have this a for loop with i in it because the index of the tile is what is indicating what's valid [Music] we did it people wait let's get rid of some of the debugging let me go back and make it 20 by 20. wave function collapse exactly what i had before but now and again again it's not always going to find a solution and i got to talk about how to deal with that but now i don't have to create a massive map of all of the tiles and their adjacencies all i need to do is load tile images and some numeric indicator for what's a valid connection of an edge then i can rotate tiles and infer all of the adjacencies this means i believe i can get this pcb generator going thank you to those who are watching live who sent me fixed tiles and the circuit board tiles i'm going to download those now and see if i can bring them into my sketch so i have the circuit tiles and i have my code i think i'm going to need to kind of draw my own version of these tiles on the whiteboard to enumerate all of the edges so there's a blank gray and a blank green tile let's start with those that's tile zero that's this is zero dot png these numbers by the way aren't really relevant although they will be because they'll be the indices into the tiles array i guess and one dot png so the blank one will have zeros as its connectors edges and the blank green i'm just going to say this is blank and this one is green it'll have ones okay what is two dot png kind of looks like this all this area is green so that's a one a one a one and now we need another thing this is a two and this is like gray so green is one and this is something new it doesn't match this because this is green three three one [Music] so i've worked all this out and there's only actually a few different kinds of sides there's a blank side zero a full green side one a light green connector which is two a light gray connector which is three that's what all of these are except for four dot png and five dot png these are not symmetrical meaning if i flip them i have a different tile which is different than how i'm rotating things so i think i need a whole other mechanism for tracking how these connect so for right now in this process of working this through i'm gonna do this without using these tiles so i have 13 tiles ordinarily i would just write a loop now to load them into the array based on their the number of the file but since i want to skip to i'm going to do it manually okay so you can see i'm loading them into an array of 11 tile images skipping 4 and five now i put in the connections zeros all zeros all ones one two one one one three one three i really want to try this without rotating any of them and see what happens images are in a directory called circuit oh oh i've never seen anything so beautiful in my life that's amazing that's promising so now i just need to do some rotations now looking at these images they don't all need to be rotated four times but i might as well because then i don't have to think about it so let index equals 11 i'm gonna skip obviously zero and one i'm gonna go through all of the tiles one through ten oh i'm not i shouldn't be in preload what am i doing i'm gonna go from 2 all the way to 10 and i'm going to say tiles.push tiles index i rotate 1 1 2 3 so less than 4. so that should go skipping the first two tiles which don't need to be rotated now there's a lot of extra rotations i don't think i need but starting with tile two going all the way down to tile 10 rotating them once twice and thrice oh i don't need this index because i can just push them into the array wow this is wild i guess the blank tile never shows up tile zero it only can connect to tile four let's i i'm so close i think i could get image four and image five in there no i can't one day later welcome to day three this time i'm finally going to complete the wave function collapse algorithm first i need to say a huge thank you to telemacho and garageball who overnight while i was sleeping added some github issues on the wavefunction collapse repository pointing to the keys to unlocking the asymmetrical tiles and placing them correctly that i was struggling with yesterday an incredible demonstration of the solution i'm about to attempt is oscar stahlberg's unity implementation of wave function collapse in it you can interactively start to select tiles and it will visually show to you which tiles are left you can also let it run and watch the process as it selects the tiles and the magic of wave function collapse unfolds over the screen the beautifully designed tiles of this demonstration are not symmetrical along the edges but each edge can be divided into three parts the left part the right part and the middle part and as long as brown matches with brown blue matches with blue half brown half light brown matches with half light brown half dark brown the process will work thanks to the magic of these colorful markers i have redrawn all of these tiles so i think i can make a key to enumerate all of the possible parts with each edge divided into three that could be on any tile symmetrical or not so this first tile which is all black is fully symmetrical along all the edges in all rotations and i think because i've numbered all the tiles it might be easier for me to use letters here so that we can really distinguish what's being matched with what so i'm going to call the black color a white which really is a dark green in the actual tiles i will call b now this side will be a a a a a a one color all around all the parts of the edges same for this but with b finally now with the image number two we will get something a little bit more interesting we've got b's all around these sides those are some very funny b's and then i've got a b here and a b here but now i need a third color for light green we'll call that c the blue color here is actually gray in the image files a new color we'll give that the letter d so now i have b b b b d b and so on and so forth now we've got something pretty interesting the asymmetrical tiles but this system makes them really easy to notate and i can go on and complete the rest [Music] how did i do i think i've got this right one mistake thank you live chat so now back to the code first thing i can turn this into a loop which is going to make all of our lives so much better don't you just feel so much more at ease and relaxed tile images ah no no i'm not relaxed at all in fact i'm totally panicking that would have been very unfortunate to find later but now nonetheless these tile objects still have to be created individually because i'm going to manually notate all of the letters for the edges and by the way there's a key term that i should be using when talking about all of these edges and that is the term socket you can think of each section of an edge as a socket each socket must connect to another socket of the same type for them to match up and by the way i encourage you to try having more than three sockets or fewer than three sockets so many possible things you could do if you we could get this working the one thing that's going to be really confusing is what is the order by which i write the letters for the sockets this side socket is bbb well this side socket is also bbb and i don't have to worry about what order because they're symmetrical but this one i really have to think about this side socket is a b b does it connect to itself well you might think it does right because what it wants to connect to is something that looks like this a matches up with a b matches up with b b matches up with b but if i took this side and put it here i would have to do that by rotating this all the way around and suddenly this side rotated around would look like this these don't match but this side if i were to take this side and bring it up here it would match but this says abb these are not the same while this one says abb and this one says abb those aren't the same orientation i need to make sure i'm notating everything in the same order which means in the clockwise order it's the way i've been thinking about this project all along up right down left up right down left so even though i most definitely want to draw it this way because it'll be way too confusing for me to write bba and not see that match up when i put it in the code i need to notate the sockets as abb bcb bba aaa then edges need to match up with other edges that are inverted so they lock together and i also should note that another way to approach this order would be north east south west which i could have been doing all along but somehow my brain is going up right down left so now as i prepare to enter the edges into the code looking right at the whiteboard for tile zero this is easy it's just going to be aaa in all four spots tile one all b's now with tile index two i've got the top as bbb but i need to make sure i read b c b in this order and b b b in this order oh but these sides are symmetrical so again it's only gonna matter when i get to four and five and here i am at index four abb that's the top bbb that's the right now for this one here even though i'm wired to read it from left to right i need to make sure i enter it from right to left the way that it would look if i had flipped it rotated it so this side were on the top bba and then the last edge is aaa from bottom to top you might be asking yourself isn't there a way to automate this i mean do you really have to enter it in manually one line of code at a time and the truth of the matter is there's probably a way we could look at the color values of the pixels along the edges and generate the sockets based on those color values but that's a project for another time i'm going to stick with doing it manually here let's do the rest of them [Music] sorry one error here with tyler x4 that's bcb so now that everything's in here what else needs to change certainly the way i'm checking if two edges are compatible if the sockets fit together that needs to change let's just run the code and see what happens there's bound to be an error somewhere amazingly i'm not getting an error but i'm also getting a pattern that isn't exactly what i'm looking for well now i got an error because it came up against the tile where it couldn't figure out what goes there and here now we're seeing a strange pattern that i don't even recognize but i do kind of love so what i'm doing currently in the code is checking if one side is equal to another side so can bbb go with bbb yes those sockets connect but back to here can abb go with abb no those don't connect but a b b could go with b b a remember this side is really b b a so all i need to do is instead of checking equality i need to check if one edge is equal to the reverse of another edge and i believe that happens in the checkvalid function no this isn't it it's all about how i generate the adjacency rules checkval is just checking to see based on the adjacency rules so i need to regenerate the adjacency rules which is in this analyze function and here i'm checking if tile dot edges ah here's where i'm checking if one edge is equal to another edge so let's write a function compare edge return a is equal to b is there a string function called reverse there's an array function called reverse so i think i need to write my own string function to reverse the string that's not too hard i could make it into an array i think split takes a string and puts it into an array then i can reverse the array and then join it back together i think that'll work and then now i can just say compare tile edges 2 with this dot edges 0 and that's called compare edge now i want to compare three and one zero and two and one and three all right are we ready is this going to work we're about to find out list list.reverse is not a function oh i've got to give it a empty character from which to split so just like i need to join them with an empty character to put it back into a string i need to split it with that empty character oh no there's a function in p5 called reverse op5 i love you so much you always have these global functions which confuse me so the reverse function in p5 actually does the work of reversing the array but it does say deprecated it will be removed in a future version of p5 because there already is an array.reverse function so that all makes sense and everything is right with the world again i just need to call this reverse string which is more clear anyway all right you've waited long enough let's see oh shoot assignment to a constant variable i made it constant let oh look at that oh it's so beautiful no but that's fine that's just the thing where it gets stuck i'm gonna put my random seed back in just to sort of track the error well that one didn't have an error but it is lovely i can't seem to find the random seed that will give me an error aha there we go we got an error so the error happens on line 136 so tiles option is undefined let's see what's in up dot options this really slows it down to console.log every like thing that it's looking at but we'll see ah there's a weird clue here the array isn't empty like there's no options left it's got one element but that element is undefined and there's only one place that i put manually one element into the array it's this sort of weird way that over here i pick from its options if there's no options left what i pick will be undefined and then place it in the array so i think i have to say if not any pick what do i do start over let's just say no loop and return see what that gives us so i think there's some optimization and cleanup i could do in the code and ultimately implementing backtracking going back and trying a different solution would make sense here but i'm just going to keep things simple and have it start over i'm going to write a function called start over in setup i create all the tile objects i put them into a big tiles array i analyze all the adjacency rules and then create a new grid i think i could just start over by creating a new grid so we'll call start over also in setup then create the new grid and start over so if we ever get down to a cell with no options we'll start over there we go so let's see how many times i have to run this before it fills i got one but the chat is rightfully pointing out something that i didn't consider which is that if not pick is causing a lot of false positives because one of the options it could legitimately pick is zero so i have to just actually say if pick is not equal to undefined just make sure it's not undefined then you can keep going or if it is undefined sorry if it is undefined you could keep going no if it is undefined start over if it's not undefined keep going i think we finally have it people let's run it one more time yeah now it's getting further along before it will reach that error there now it got the error and now it's going there we go i think this is our second attempt yay and we did it on the second attempt amazing now let's do something really exciting let's get rid of random seed so that it'll do it differently each time we run the canvas is 800 by 800. let's try upping the resolution to 40 by 40. my guess is it's going to run very slow because i haven't bothered to think about are there ways to optimize the performance but let's see what happens [Music] wave function collapse we have it everybody there is so much more to do here first of all i haven't even attempted the overlapping model i'm gonna wait until you're sometime in the future actually watching this this is a video on youtube so i can get a lot of comments and feedback because i'm sure there's lots of things that i've done in sort of strange and odd ways that i might want to think about and address before i move on to the next version of the algorithm which detects the tiles and adjacencies in a way based on doing a pixel analysis that's a little hand wavy but that's the general idea i also have left out a key element of the algorithm which is explained really nicely in this processing forum post from solid the process doesn't stop to the four direct neighbors of the collapsed cell and has to be extended recursively to the neighbors of the neighbors and so on until all constraints are propagated i'm kind of getting it to work anyway because i'm just doing a full pass through everything every time through draw but ultimately i could reduce the entropy by recursively propagating the cells as their options start to collapse now in truth this tile set that i'm using doesn't really need this because a tile when it's collapsed only affects its immediate neighbors and that doesn't really ripple out in the same way that it might in say sudoku but this is definitely something that i would want to add to the algorithm in a future version of this so give me your tips and thoughts about how to do that in the comments of course there's backtracking would love to add that and then but really this is what i'm here for this is why i made this video what possible tiles could you design and what patterns and beauty could you create by just using my code exactly as is not changing anything but just designing your own tiles creating your own key of sockets and just running it and letting the beauty follow i want to see this so badly not to mention this algorithm can be applied in 3d and whoa there are so many amazing implementations of wave function collapse in 3d youtube videos websites i'll try to link a whole bunch of them put them up on the screen oh there's just too many to mention so comment on the video go to the coding train website where there is a place that you can submit your version of this tag me on social media i want to see the world full of beautiful wave function collapse algorithmically generated images and stay tuned for the next coding challenge or sometime in the future when i tackle the overlapping model [Music]

Channel: The Coding Train

Views: 413,637

Keywords:

Id: rI_y2GAlQFM

Length: 78min 36sec (4716 seconds)

Published: Sun Jul 03 2022