What are Cellular Automata?

hello this week I created artificial life but the command prompt of course just look at how complicated and sophisticated this life is I've got clusters of individuals forming families and groups fighting for resources and competing for space they're breeding and multiplying and occasionally you'll see them sending out a member of the family to go and interact with other clusters I am of course talking about the British mathematician John Conway's Game of Life which is a class of cellular automata now you might think that a really complicated behavior like this would take several thousands of lines of code to implement in fact it doesn't it takes about three and this is why cellular automata are really cool you can take a very simple rule set spread it across a hugely parallel processing substrate and the resulting emergent behavior can exhibit all sorts of really complicated phenomena like several of my other videos this video we'll use the OLC console game engine and you can click the little link above to see more details about that but essentially all it does is wrap up the command prompt in a display buffer so I can draw to it easily to use the console game engine you need to create a class that inherits from it and overwrite two methods which are on user create and on user update I've called this class the game of life and in our in main function now all we need to do is create an instance of the class the game of life class and tell it what dimensions of the console we want so to start with I'm going to use 160 characters across by 100 down and each character is going to be 8 by 8 pixels I then call the start function which will then repeatedly call the unused update function this algorithm holds a particularly special place in my heart as long as there have been computers there were people programming John Conway's Game of Life for them now for a number of years I worked in academia and I worked in a field where we developed a technology called cellular processor arrays these are highly parallel processing devices and to test them we would always run game of life because if we saw that it could run life it could probably do all the other complicated things we needed them to do I'm not going to go into the history of game of life there's an excellent Wikipedia article that will do just that and we'll be using this article as a source of inspiration to try out different patterns the sheer amount of research again flight is vast mathematicians love it computer scientists love it and people have proven that it's got all sorts of fantastic properties for example it's quite possible to set up a pattern where the little critters will move around and implement a fully functional computer the marula patterns which can emulate circuits and people are using it for generating music and all sorts of interesting sequences but fundamentally the whole phenomena stems from very simple rules and I mean very simple rules and this is why it's such an interesting algorithm how do you get all this complex we call it emergent behavior after such a simple rule set so how do we make cellular automata well the first thing you're going to need is a grid and in this case I'm using a 2-dimensional grid of squares where a cell is directly connected to its immediate neighbors every cell in the grid executes the program and all of these programs are identical but they operate on local data each cell contains a memory which can be used to store its current state and for game of life this is very simple it's simply on or off but it could be much more complicated each cell has the ability to interact on communicate with its neighbors and finally but this is the most important part all of the cells run a program but they all run the same program and they all run the same program synchronized with each other this gives way to the SIMD paradigm single instruction multiple data where a single instruction is broadcast across the whole processing array but it uses these local data to operate on so this SIMD approach coupled with a neighbor communication gives rise to cellular automata the program for game of life is very simple step one we count our neighbors so let's assume I am this cell in the middle here and I have some alive neighbors and I was going to be indicated by red dots we can only talk to the neighbors in our immediate vicinity so this gives us a 3x3 square around the active cell and we can count how many red dots are in this square so in this case it's three now this is where we introduce some very simple rules let's consider the rules when the cell is alive ie its output is set to one so it's got blue dot or it's a red dot II if the cell is alive and has less than two neighbors it dies from loneliness if it has greater than three neighbors it dies from overcrowding otherwise the cell has a good number of neighbors and is happy we'll put a smiley face on and it stays alive now let's consider a dead cell it's not outputting anything but in the weird world of John Conway if a cell has three neighbors and it's dead those three neighbors get together and produce a living cell and so in this instance this cell now becomes active in fact so does this one because it - also has three active neighbors and that's it that really is how simple the rule set is but there is one more important thing to do we have to do everything at the same time we cannot scroll through the cells one by one and update them as necessary instead we have to treat all of the cells as if they're in one Epoque of time as we carry on scrolling through the cells we can't count the ones that have already been set on this epoch or else this one would also become alive and then this one would also become alive and these are incorrect results having seen how simple the rule set is it's time to do this in code and I'm going to do this by creating two two dimensional arrays one that represents the output and one that represents the current state of the cell so the output is what basically we'll see on the screen and the state is the current memory within the cell in the unused create function I'm going to now allocate the memory for my two two dimensional arrays and I'm going to use the screen width and screen height so that's the 160 by the 100 characters that we set before and this means I can choose a console of any size and life should function appropriately just for good practice I'm then going to set both of these arrays to zeros now I'm working with 2d arrays it's often easier to work with two-dimensional coordinates so I'm going to create a little lambda function here to make it a little bit easier for me to access the array and in this case I want this lambda function to return the value of the output array depending on my x and y coordinates I'm using the screen width here to multiply by the way I'm going to treat the on user update function as if it's a single epoch so every time this function is called we're going to do a full update of the entire array but before we start to modify the state of the array we need to store it in the output so now we're free to interrogate the output and change the state of the cell I'm going to use two nested for loops to iterate through all of the cells and you'll notice I'm starting them from the coordinates 1 and I'm going to the screen with minus 1 on the screen height minus 1 I'm doing this to avoid reading memory which isn't there there are actually several approaches in cellular automata so what to do with the boundaries in this case I'm just ignoring it they're going to remain fixed but some people do actually prefer to have ongoing periodic so as the cells activity goes up one side it appears on the other the first part of the algorithm said we need to count the number of cells in our immediate neighborhood well I can use the cell lambda function that I created before to help me with this so it's just the current coordinate minus one and this is the northwesterly cell now because the value is either a zero one I can just keep adding these and count them as I go so in this case I'm not moving along in the x axis I'm going to put a plus zero in here just to keep it consistent but I'm still on the row above and I do this for all of my neighbors so here is the North West and here is the South East I then need to behave differently depending on whether the current cell is alive or dead and we do that by just checking the output so if the current cell is alive it's set to 1 now if I'm alive and I have 2 or 3 neighbors as said before I'll remain alive I'll carry on being alive however in any other condition I'll die so here I've got a little boolean check and I'm kind of cheating I'm forcing a boolean to be an integer value in this case so if I've got two neighbors or three neighbors I remain alive because that'll return true anything else will return false and kill the cell if I'm not alive then I only become alive if the number of neighbors is equal to three since we're iterating through all the cells in a nested for loop I might as well take advantage of this opportunity to draw them and to do this all I'm going to do is again check whether the current cell is alive or not and if it is I'm going to draw a white character and if it isn't I'm going to draw a black character and that's it the highlighted code is all we need to implement game of life let's run it and see what happens so you can see the console is popped up but hang on there's no life oh dear well that's because we haven't got any starting cells we initialize all of our memory to zero to begin with well we need some cells to breed to produce a new cell to test if the algorithm works or not I'm going to go through each cell and set the state randomly to zero or one let's try again perfect there we go we can see life quite happily living I'm going to add a little bit of input handling code here to check whether I'm holding down the space key because I only want life to evolve if I'm holding the key down this allows us to stop it and analyze it so I hold the space down and let go and we can see life stops as people began to study the game of life they realize that certain patterns exhibited certain behaviors the Wikipedia article lists some of these and I thought it would be fun to try and study them more closely so instead of starting with a random state for all of the cells I'm going to manually set the state of some of the cells now I could do this like so where I manually specify the coordinates of the cells and put them into the array however this will make it a bit tedious to enter the patterns so I'm going to try something a bit more visual as before I'm going to create a little lambda function except this time it's resetting the value of the cell so again it takes an X and a y-coordinate it also takes a type string the contents of this lambda function will iterate through the string character by character and if the character is a hash it specifies a 1 in that state location otherwise it's a 0 this leaves us now with a much nicer syntax for specifying starting shapes where I can visually see what the shape should look like to start with let's have a look this is the our pentomino I don't like the space bar thing now instead I'm just going to slow the Fed down with a wait so from that starting point we can see it grow and we can see we've got some spinners and some gliders the gliders are the ones that travel a great distance let's try something a bit more interesting the gospel glider gun this is an example of an automatic producing something with a more usable output let's take a look so here we can see there's some bouncing back and forth between two starting points but it continuously emits gliders our little life-forms have managed to create a sequence and don't forget this really complicated behavior is influences with just two if statements mathematicians also found out that it's possible to have patterns which exhibit infinite growth let's have a look at this one this one's all implemented in a single line I like the symmetry of this one cellular automata on a sequential machine like my desktop PC can be quite demanding of the processor so I'm going to set it back to just doing a random start and I set it to release mode and I'm going to double the resolution of my console but half the size of the font and just let it run away cellular automata is an intriguing field of research and I've only shown one very simple algorithm out of many many hundreds it's not just interesting to mathematicians and computer scientists people are now searching for it in biology and there's some evidence to suggest that cells in the body might also interact in this way whatever you might think I think there is a definite Beauty to the emergent behavior from such a simple rule set as usual all the source code is going to be available on github if you've enjoyed this video give me a big thumbs up I will think about subscribing and I'll see you next time

Channel: javidx9

Views: 44,881

Keywords: C++, learning, john conway, game of life, cellular automata, onelonecoder, one lone coder, algorithms, emergent behaviour, coding

Id: E7CxMHsYzSs

Length: 14min 14sec (854 seconds)

Published: Mon Jul 17 2017