Coding Challenge #89: Langton's Ant

okay here we are a coding challenge to this coding challenge I'm gonna do in processing and it's cool I'm going to attempt to implement this thing called Langdon's and now one thing I might recommend is go back and watch my game of life coding challenge because there's gonna be a lot of similarities between these two this is an example of another cellular automata system however I'm gonna do this one in processing so we just sort of see a different environment I will of course make a port to JavaScript so if you make your own variation of this and want to share it on the web you can look at the p5.js version of this so what do I need what I need with this first cellular automata system just like and is it atomic ah is it at um I could never get this right I need to have a two-dimensional array and this is actually a place where I'm kind of happy that I'm using Java in processing where I can say I can make this grid a new two-dimensional array and you know what though guess what I'm gonna do I'm gonna have every cell be an individual pixel because processing is pretty fast I could do individual pixel setting so let's instead of having like a grid of squares that are a larger size I'm gonna actually do it on the pixel by pixel level let's see how that goes so let's just decide in advance actually I don't need to decide in advance I'm going to create I'm gonna have a window that's let's just do like 200 bytes 400 by 400 to start and then so the array is going to be a new array of integers which the same nonresponse width and height and it's actually going to just fill that whole thing with zeros so I don't actually even need in Java if I was doing this in JavaScript I've got to like fill it with zeros but I could just I could just assume that it's filling it with zeros great now we should really learn what license it is let's go take a look so it's a it's a system souther automata system that will produce interesting patterns and I need to follow these rules okay so squares on a plain or colored variously either black or white so we'll say white if the ant hasn't hasn't been there that'll be oh well I guess zero it's black white is one I don't know we'll figure that out we arbitrarily identify once as the aunt so let's start that let's have the aunts location we're just gonna call that we're gonna have that just be x and y and the aunt is gonna start at 200 200 okay that's where the ants going to start I probably should say with / - whatever so I'm going to say grid X y equals 1 that's where the ant is and actually to be honest with you maybe I should have that be the value 2 so I kind of 0 for what let's let's keep going here so the ant moves according to the role rules below at a white square it turns 90 degrees white right ok so actually what I want to do is each time and let's make a background of white I need to figure out what is the state of the current spot where the ant is right so this is the state of the current spot where the antis so if the ant we can look at these rules if the ant is at a white square okay and we need to keep track of its direction which way is it moving so I also need a direction and let's just be let's do something goofy and do like these because I think you're supposed to like it kind of make constants you may be you say final or something but I'm just gonna call them cap I'm gonna say like up oh that's a reserved word in in in processing ant up is 1 2 0 ant down is 1 and right is 2 this might be really silly the way that I'm doing this ant left is 3 so I'm gonna make up some constants to keep track of the direction and I need a variable called ant direction and I can just call that direction so I have I already have that I have the ants XY location and its direction it's probably nicer way of doing that but I'm gonna keep going with what I have its direction I'm just gonna start by going up that's its direction so now if add a white oh you know what I should have those in clockwise order because then I could just add one is adding one is turning right subtracting one is turning left so this should actually be up is zero right is two is one down is two and left is three so if the state is white and I'll have white be one no white should be zero because they're all starting a zero because I'm filling it with white so if the state is zero the ant should turn right meaning ant oh just Direction plus plus and I'm gonna what I'm actually going to do is I'm going to almost in a silly way write a separate function for turning right because I can I need to deal with like so this is ant this is Direction plus plus but if Direction E is greater than ant left then Direction equals ant up right so I could use modulus but I'm just gonna be sort of silly about this you can all do your nice refactoring and I'm gonna say - - and if it's less than ant up it's ant left so this will account for when 0 goes to negative 1 it should be 3 when 3 goes to 4 it should be 0 and again I could have done this all on one line of code with modulus but that's fine so if state is 0 turn right and then what's the next thing flip the color of the square and move forward one unit okay so then state grid X why should now be one right that's flipping and move and then move forward needs to be a function so I'm now going to write a function called move forward which is if Direction is up then Y minus minus again I could use a switch statement a case statement all that if Direction is right I could do this with all sorts of fancier ways else if but I'm just going to really try to I'm gonna really try to be long-winded about this to understand it if it's down y plus plus else if direction is left then left is X minus minus then I need to account for the edges so if X is greater than width then x equals 0 if X is else if X is less than 0 then x equals with minus 1 and again I could use modulus but I'm just gonna be super long-winded about this and I'm gonna do this for Y and I'm gonna change that to height and put Y in here and here we go ok so now I have this crazy long function a crazy long function for moving forward it should change the x and y value based on its current direction and it should wrap around the edges ok so now move forward ok else if what what could the other if it's the state is already one if there's really only one other possibility but I'll be I'll check else if state is 1 turn left turn change the state to zero and then move forward I think we're done let's just run this it's not gonna draw anything let's just run this and see if we get any errors I usually don't like to write so much code without running at first okay it's running but let's now see now all I need to do is visualize this grid and I should have probably made this the pixels are in a one dimensional array but I'm now going to loop through and I is every export column I plus plus J is every why I don't want to use x and y because I already used those for the ants and then and I could actually you know what I really could be so efficient about this because I could make this is very silly I could make an image I only have to change one pixel each frame it's really silly for me too so let's do this I can't bear I mean this let's do it this way first but I am going to refactor this because this is really ridiculous what I'm about to do so the pixel location is I times width plus J and this is a formula that I have used in countless videos and I'm going to call this pics for pixel so the actual pixel location in the window is all the pixel colors are stored in a one dimensional array and so I but I'm gonna operate on those pixels I need to say load pixels and I also need to say update pixels so I will refer you to my video tutorials about pixels in processing they'll be a if this is not infinitely to you I'll I'll link to those tutorials but basically what I need to do now is just say pixels index pix equals something like if I say color random 255 what you're gonna see here is whoops when I run this sketch is every pixel is a random color now what I want to do is I want to say if grid I J equal zero then set that pixel to white otherwise if it's equal to one but that's the only other possibility set that pixel to black and we should see this is just rendering the results of Langston's ant with each and every pixel as a cell in the grid so let's run this and we can kind of zoom in and see is this the correct pattern can anyone confirm or deny for me that this is the correct pattern let's see if it looks kind of like so this is what it should look like after eleven thousand steps all right let's stop this and I'm gonna do something I'm gonna say I'm actually just going to do this all at once I'm gonna say for int N equals zero and is less than 11,000 n plus plus I just want to know that I did this correctly I'm gonna just run through the whole algorithm 11,000 times then I'm gonna render it and I'm gonna say no loop so it's only gonna do it once okay so this is instead of watching it animate that looks pretty good right that looks exactly like hopefully dad yep I can verify that these well it's flipped but that's fine because Y is up what you could you could flip it if you want I flipped it fine okay great so that is working we're done yeah but this is this is making me crazy because I've only changed one pixel every frame so I can't bear to leave it this way I'm gonna do one there's so much refactoring of this that you could do and actually I'm going to leave that in here because one thing but just having this in here by the way and taking out the no loop like this is this I can make it appear to run much faster like this is doing five five five cycles per frame of animation so to make this more clear what if I did 100 cycles per frame of animation whoops you can see that this is happening much faster now Oh Oh whoops we have an error array out of bounds exception okay where did I not what did I not do correctly uh if it's greater than with minus 1 greater than height minus 1 okay good thing I check that let's try this again yeah there we go so we're gonna get some pretty crazy patterns after a while and I'm sure you could be clever and think about like modifying the rules to use color maybe get of multiple states so this is actually running super fast because processing can really handle doing it at this resolution but you know we could asked like what if I do this at like 1200 by 800 like ooh so we also had an error if it's not a square so I have to fix that I times width plus J oh my goodness I have this totally wrong had for me worked that's why I was on its size I had this formula wrong the whole time ah I referenced my tutorials and everything I just did it really quickly that formula was wrong I need to look at the row I mean sorry the column and then add to it the row times the width well glad I checked so now this is right so let's what I want to show you is what happens if I go to like 1200 by 800 which is probably beyond the Wow so you know processing it really is not having a problem doing this super fast but I could make this much more efficient so one way that I'm going to do that is I'm going to make a P image and I'm gonna call that ant and I'm gonna say ant equals create image width height RGB so I want an RGB image and I want that to be white to start with so there's probably a way for me to do this more efficiently but I'm just going to set every pixel of that image to white so so I'm gonna set every pixel to white and I'm gonna say aunt dot load pixels and update pixels and then I'm going to instead of doing all this I'm just going to draw that image so that's me drawing the image now the only thing I need to do is change whatever change the state here so what I need to do is like I need to do it though before I move forward but we're always going to move forward right so that move forward doesn't actually have to be in there can be down here and I can now find that pixel location as X plus y times ant dot width right that's the pixel location in that image and now if I say ant I might not even need the load pixels what I'm going to put it in here any ant dot pixels and you know what I could just use set because I'm just doing one pixel at a time set will in-turn the set function internally calls load pixels and update pixels for you so I could just say ant set the XY to the color and so I'm gonna say if if grid x y equals zero then the then the color should be black so we're going to assume the color is white and we're going to make a color we're going to assume the color is white if it's zero we're gonna set it to black and then we're gonna set that pixel so this is me just doing that one pixel at a time cuz I only change one pixel per per frame or per cycle here I'm actually doing 100 you can see this is the same exact thing did I did it work correctly let's let's go back to let's let me just see here I think I might have a slight issue let's double check let's go let's double check that this is right by resetting this back to 400 by 400 doing this eleven thousand times and then saying no loop and let's see here did I get is this location correct let's see now let's take a look at that as compared to the Wikipedia again I'm doing like a mirror image of it but yeah that looks right so I think it's right so now we could let it run again the same way like let's do like we could probably do like five hundred perfect the thing is that fact that I'm doing five hundred so really if I want it I should really be smart about this and say aunt load pixels to be the the most optimized I shouldn't use set and I should say aunt low pixels aunt update pixels at the end of all of this and then I should say the location is X plus y times aunt ton dot width and I should say aunt dot pixels that picks location is that color so this would actually be the most optimized so I'm only calling up little pixel an update pixels once only changing the pixels that need to be changed and then I should be able to do this and what did I miss oh I have no loop in here still I should be able to do this at very high resolutions really fast so for example I can change this now to fullscreen and run it and it should have no problem doing this super fast so let's let this run for a little while I'll be back in a minute or two this will be it and you'll see me again after this ran for a while I'm back from you waiting because I think I got this wrong it should be black if it's one so hold on a sec let's run this again there we go and this is going to run for a while and then I'll be back to see what the pattern is okay so this is what it got - you can sort of think it's sort of zoom in here and see like what sort of interesting beautiful patterns are here someone in the chat told me there's a number file video about Langston's ant which you can get more of the background the history of it and the possibilities I would encourage you here's some things you could do you could refactor my code to make it more efficient you could think about how would you make this have color in an interesting way maybe maybe the grid isn't isn't just pixels maybe it's not even just squares maybe it's a grid of interesting shapes or patterns you use color in some way what kind of beautiful thing can you make from lenghtens and and if you want to make this run on the web take a look I'll also create a JavaScript version of this but again if I think if you want to get this sort of like fullscreen speed of it you're probably going to want to do it in processing so thanks everybody and see you soon [Music] you

Channel: The Coding Train

Views: 131,567

Keywords: live, programming, daniel shiffman, creative coding, coding challenge, tutorial, coding, challenges, coding train, the coding train, live stream, itp nyu, class, langton's ant, langton's ant processing, processing coding challenge, challenge, ant, codingtrain, cellular automata, processing, code challenge

Id: G1EgjgMo48U

Length: 20min 57sec (1257 seconds)

Published: Mon Jan 08 2018