Game Development Tutorial | Cellular Automata and Procedural Map Generation

hello and welcome to my cellular automata and procedural map generation game development tutorial in this video we'll be talking about the cellular automata algorithm what it is how it works and how to implement it cellular automata are simply methods of rearranging a randomized grid of values into a more organized and aesthetically pleasing grid of values from a game development perspective these values are usually tiles on a tile map for example in this tutorial we're going to be using a white tile in the black tile the white tile indicating a floor and a black tile indicating a wall of course in practice we can use more meaningful tiles like trees or cave interiors but for the sake of simplicity we'll be sticking to this very basic visual example there are two images on screen the image on the left displays a whole bunch of randomized floor and wall tiles this is what we call a noise grid it's literally just a bunch of noise on a grid the image on the right displays a more organized layout of floor and wall tiles believe it or not this more appealing layout actually spawned directly from the noise grid by utilizing a cellular automaton cellular automata have been used in countless video game titles as well as in other areas such as mathematics and biology the image on the left is a screenshot of a procedurally generated world in a game called dwarf fortress of course not all of it was generated using cellular automata but some of it was the image in the center shows something called conway's game of life which is a cellular automata that self perpetuates and evolves as time progresses in my mind it's a sort of simulation of natural selection based on how its rules are defined the image on the right is just a bunch of really cool designs that were generated purely through various cellular automata it's really amazing how something so complex and beautiful can spawn out of such a simple concept so how do cellular automata work they're actually way simpler to understand than you might expect cellular automata transformed tiles based on their neighbors by neighbors i mean the neighboring tiles to the tile in consideration take a look at the 3x3 grid on screen let's do a quick run-through of how the algorithm would transform the center tile highlighted in green the first thing we have to do is take a look at the eight neighboring tiles we see that there are four white tiles and three black tiles and remember the white tiles indicate a floor while the black tiles indicate a wall all we have to do in order to transform the middle tile is follow the conditions on screen if more than four of its neighbors are walls then the center tile should also be a wall otherwise if four or less of its neighbors are walls then the center tile should be a floor so in this case the center tile would transform into a floor since it's surrounded by only three walls now let's take a look at the tile on the top right corner of the grid in order to decide what it should transform into we need to look at all eight of its neighbors since this tile only actually has three neighbors since it's on the border of the grid we'll go ahead and consider the positions outside of the grid to also be wall tiles keeping this in mind we can count that there are seven neighboring walls and only one neighboring floor therefore this tile should become a wall let's do one more the bottom center tile is a floor once again checking its neighbors we see that there are five walls and three floors therefore this tile should also become a wall note that we don't have to use this exact rule of greater than four or less than or equal to four but this is a very common rule to use in game developments and is proven to provide some really nice results also note that the terminology for considering all eight immediately surrounding neighbors is called a more neighborhood now we're going to quickly run through another example but this time we're going to proceed exactly as a computer would we have a grid on the left side of the screen this will be our tile map it consists of a 3x3 area of floors we're going to start at the top left and work our way rightward and downward recall that if a tile has more than four neighbors that are walls it also becomes a wall let's get started looking at the top left tile first how many of its neighbors are walls well there are five positions to consider outside of the grid so we have to tack those onto the wall count the others are all floors therefore since more than four of its neighboring tiles are walls this tile should also become a wall before we look at the top center tile notice how i didn't overwrite the original grid with that new wall tile instead i placed it on the right side of the screen and what will become a new grid this is crucially important when we implement this algorithm we need to remember to save our results in a grid separate from the one we're using for our floor and wall comparisons if we don't the algorithm will quickly break down and pretty much consider every single tile to be either a wall or a floor okay now let's continue onto the top center tile it has three neighboring walls and five neighboring floors therefore it becomes a floor the top right tile has five neighboring walls and three neighboring floors therefore it should become a wall when we hit the edge of the map we simply go down to the next row and continue until all tiles have been covered and that's it we just completed an entire iteration of the automaton like i said it's a surprisingly simple idea that can show some really awesome results of course a 3x3 map isn't going to do much so let's get a little bigger we're going to jump into the actual implementation now but before we do i want to go over a few things all the code shown on screen will be pseudocode this is to ensure that i'm not being biased towards any particular programming language everything done here can be achieved in every language it's just a matter of understanding the concept and translating the code my personal example will be built in the default game engine because that's what i'm most familiar with additionally after we cover the implementation i'll show off an interactive html5 demo that you can navigate to and play around with this demo will allow you to manipulate various properties of the cellular automaton discussed in this video to gain a better intuition for how it works all of my source code can be found on github totally for free if you're interested in seeing exactly how i wrote the program the first steps implementing the algorithm is generating a noise grid remember that the noise grid is simply a randomized set of values which matches the desired size of your final map the important thing to know here is that we need to set a particular noise density when creating the grid the noise density refers to how much of the grid will start as walls instead of floors it's most intuitive if your density value is between 1 and 100 so that we can interpret it as a percentage for example the top image shows a noise grid of density 50. approximately half of its cells are walls and half of its cells are floors the middle image shows a noise grid of density 10 approximately 10 of its cells are walls and 90 are floors similarly the bottom image shows approximately 90 walls and 10 floors realistically you never want a density value this extreme in either direction from experience procedurally generated maps look best between maybe some density value of 45 to 65 again you'll be able to get a better intuition for this stuff by playing with the demo now let's actually generate a noise grid in code line 1 defines the make noise grid function which takes a density value between 1 and 100 line 2 initializes a 2 dimensional array that matches the width and height of our desired map this is the array that will hold all of the grid values line 3 generates a random value between 1 and 100 now we're going to loop through our noise grid array and begin initializing its values line 5 checks if our randomly generated value is greater than our density argument if it is then the current tile in the noise grid becomes a floor otherwise it becomes a wall once the whole grid is populated with floors and walls we return the noise grid so we can use it later now we can move on to the second step in the implementation which is the cellular automaton itself the animation on screen shows a noise grid being fed through a cellular automaton if you look at the bottom of the gif you'll see that the noise density for this map was set to 60 meaning it started with approximately 60 of its cells as walls you'll also notice that there's a variable called iterations this refers to how many times we want to feed the noise grid through our cellular automaton algorithm when we perform cellular automata we don't just do it once we do it multiple times remember that exercise where we scan the 3x3 grid from left to right and top to bottom that's considered to be one iteration when we have a really big map like the one shown on screen we need to run that same scanning procedure multiple times in order to achieve an appealing result you'll notice that as the iterations increase the generated map begins to look smoother and smoother the amount of rigidness slowly starts to fade as we increase the iterations this is an important intuition to have if you're looking for a map that contains a lot of small corridors and obstacles then maintaining a low iteration value is probably what you want to do otherwise if you're looking for a map that's more open and expansive then consider maintaining a high iteration value here's the routine in its entirety we start by defining a function that takes two arguments those being the noise grid that we generated from the noise grid function and the number of iterations we want to do labeled here as count the for loop on line two serves to repeat the algorithm for the specified number of iterations we start each iteration by copying our grid into a temporary grid the temporary grid will be used for scanning the map from top to bottom and left to right and counting the neighboring walls the actual changes to the grid will be applied to the original grid array line 4 and 5 begin looping through our tile map from left to right and top to bottom on line 6 we initialize a variable called neighbor wall count this is a counter variable that keeps track of exactly how many of the current cells neighbors are walls just like we did in the examples the following two for loops check the current cell's neighbors from left to right and top to bottom if the current neighbor is not within the tilemap bounds then we consider it a wall and we increment the wall count otherwise if the current neighbor is within the tilemap bounds then we continue on to line 10. here we check if the current neighbor is equal to the current cell we have to include this check because we don't want to mistakenly consider the current cell as one of its own neighbors that would be wrong and it would lead to a situation where we have potentially nine neighbors instead of eight finally we check if the current neighbor is a wall tile if it is we increment the wall count those inner for loops will continue until all of the current cell's neighbors have been checked and tallied once this process is complete we move down to line 15. here we check if the finalized wall count is greater than 4. if it is then the current cell should be a wall if not then the current cell should be a floor and that's it this procedure of scanning each cell and its neighbors will continue until we reach the bottom right portion of the map for the specified number of iterations now let's put it all together thinking on a more macroscopic level there are three components to getting a procedurally generated map up and running first we create a noise grid with some density value second we apply our cellular automata to the noise grid for a number of iterations finally we draw the tile map onto the screen and observe the results okay so here's an example of that interactive demo i was talking about you'll be able to find the link to this in the description of the video and the first thing i want to show off is the strip of instructions at the bottom you'll see that there's a noise density there's an iteration count then there's the controls and then gym rat games which is my studio name so let's start with the controls you can press 1 which will increase the noise density so here we can see that we have it's set to iteration zero so it's not actually running the cellular automata algorithm um instead it's just doing the noise grid and then displaying it out of the screen and if we increase the noise density say to 70 you can see that the walls are becoming more apparent than the floors and if we decrease the noise density let's go down to say 30 then you'll see that the floors start to overtake the walls the parameters that you use for the noise density and the iterations are going to change depending on the size of your map so if you have a really big map like this one you're going to want more noise density and more iterations but if you have a smaller map you're going to probably want maybe around 50 for your noise density and then maybe around three or four for your iterations so let's go on to the other controls three and four are grouped together uh the three will increase the iterations by one every time you click it so you can see that we're applying cellular automata our algorithm that we implemented in the video every time we increase the iterations it generates a new map and it runs the new noise grid through say five iterations of cellular automata and now it's six iterations now it's seven iterations and you can see as we increase the iterations the smoothness what i like to call the smoothness of the map increases so if we go up to say 15 all of a sudden everything's really smoothed out so if we press 4 we can decrease the iterations so here we have very long narrow corridors note that every time you can increase the iterations the algorithm does run a tiny bit slower because it has to do it has to scan the map more times let's go up to 10 and then if you hit the five button it'll actually just regenerate a noise grid and a new map with the current settings so the settings won't change um and you can just generate maps that all look kind of similar to see if you like this setting that and you want to use it for your own game and if you hit the button six on your keyboard it will actually step up to the next iteration without generating a new map let's just go with two the same exact map without generating a new one we can click six and it will do one more step of cellular automata one more step one more step one more step so you can kind of see how the map evolves as the algorithm as the noise grid is fed to the algorithm and uh like i mentioned or i will be mentioning all of the source code will be on github in order to open the source code in a proper editor you have to be using the default game engine that's what i wrote this in but you can also just open up there's a folder called example and then there's a script called main.script and if you open that up you'll be able to see all of the primary code like the actual implementation of the algorithm so if you're interested you can look in there for that that's everything i wanted to cover if you like this video please click the like button if you're interested in watching more tutorials like this one consider subscribing this was my very first tutorial and i plan to do a whole lot more in the coming years i love all the technical challenges that come with game development and sharing them helps me to learn more and support what i already know thank you so much for watching and i'll see you next time

Channel: Klayton Kowalski

Views: 15,078

Keywords: Klayton Kowalski, Gamedev, Tutorial, Cellular Automata, Procedural Map Generation, Procgen, Indiedev, Defold

Id: slTEz6555Ts

Length: 15min 50sec (950 seconds)

Published: Sat Sep 19 2020