Cellular Automata & Moore Neighborhood
Cellular Automata and the Moore Neighborhood smoothing algorithm are two simple AI implementations that work extremely well together in order to generate 2D or 3D tile- or cube-based levels for games with great flexibility. My goal with this blog post is to help you understand the power of the two algorithms when they work together and how you could possibly use them in your own game. Keep reading as I will also provide helpful resources from other sources if you want to explore these algorithms further.
Cellular Automata is used to generate a set of random level data with a fill limit. You can tell the formula that you want 40 percent of your level to be terrain which will leave 60 percent of it open. In many of my examples I left the value somewhere between the default of 50 percent and 45 percent. You don't want to adjust this value too much as the Moore Neighborhood algorithm will do most of the terrain forming (smoothing).
The Moore Neighborhood algorithm is a smoothing algorithm which pairs nicely with Cellular Automata to turn your crazy-looking tile generation into normal-looking blobs of terrain. The Moore Neighborhood algorithm works by identifying the eight neighbors of each cell. We call these neighbors N, NE, E, SE, S, SW, W and NW as in the compass directions. The algorithm checks each of the (up to) eight neighbors to see if it is enabled (green in my example) or disabled (gray in my example). If the number of enabled neighboring cells is greater than the default value of 4, the center cell that we are examining gets enabled. If not, that cell gets disabled. We repeat this for each cell in our tilemap, turning them on or off, until we have finished. Now, our tilemap will look much more normal and could even be functional in a game at this state.
The final but optional step is to continue to smooth this new tilemap. The nice thing about how the Moore Neighborhood algorithm is written is that it can just be run again and again to create a smoother and smoother finished product. In my implementation (linked below), I have a simple public integer variable visible to the designer in-editor that controls how many times the smoothing algorithm is to be run. As a warning, you may want to be careful with this variable if you have a smaller level like mine as it will become pointless to smooth it more than a few times before it stops making any meaningful changes; if I set my smoothing algorithm to run 10,000 times, it will take 20-30 seconds to run and look no better than the same algorithm if it ran 10 times, but for a larger tilemap it may make more sense to run it additional times. Whatever you do, you should end up with a nicer looking tilemap like the following example.
If you are looking to implement this algorithm in 2D like I did, I would highly recommend checking out the Unity blog post written by Ethan Bruins (linked below) as it does a great job explaining the importance of everything and has some great code samples. If you want to understand the smoothing algorithm further or want to implement it in a language other than C#, I recommend checking out the Wikipedia page for Moore Neighborhood (linked below) as it includes some great pseudo-code. If you are more interested in the technical, mathematical aspects of either of these algorithms, I would check out their respective pages on MathWorld (linked below), both written by Eric Weisstein.
My favorite thing about these two algorithms is how flexible they can be. They could easily be run on lower powered devices like smartphones or handheld game consoles, or be greatly modified for much more complex levels whether they are in 3D and/or have more than just an ON and OFF state. As stated earlier, these algorithms work great for 2D top-down terrain (as seen in my examples) or almost any other situation. You could choose to not force walls and generate platforms instead. Or you could take this to a whole other level and use these algorithms in three dimensions.
If you would like to try out the demo seen in the images above, here is a link to my GitHub repository: https://github.com/averyfollett/CellularAutomata
References:
Bruins, Ethan. “Procedural Patterns to Use with Tilemaps - (Part II).” Unity Technologies Blog, 7 June 2018, blogs.unity3d.com/2018/06/07/procedural-patterns-to-use-with-tilemaps-part-ii/.
“Moore Neighborhood.” Wikipedia, Wikimedia Foundation, 16 Sept. 2019, en.wikipedia.org/wiki/Moore_neighborhood.
Weisstein, Eric W. "Cellular Automaton." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/CellularAutomaton.html
Weisstein, Eric W. "Moore Neighborhood." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/MooreNeighborhood.html
Cellular Automata is used to generate a set of random level data with a fill limit. You can tell the formula that you want 40 percent of your level to be terrain which will leave 60 percent of it open. In many of my examples I left the value somewhere between the default of 50 percent and 45 percent. You don't want to adjust this value too much as the Moore Neighborhood algorithm will do most of the terrain forming (smoothing).
The Moore Neighborhood algorithm is a smoothing algorithm which pairs nicely with Cellular Automata to turn your crazy-looking tile generation into normal-looking blobs of terrain. The Moore Neighborhood algorithm works by identifying the eight neighbors of each cell. We call these neighbors N, NE, E, SE, S, SW, W and NW as in the compass directions. The algorithm checks each of the (up to) eight neighbors to see if it is enabled (green in my example) or disabled (gray in my example). If the number of enabled neighboring cells is greater than the default value of 4, the center cell that we are examining gets enabled. If not, that cell gets disabled. We repeat this for each cell in our tilemap, turning them on or off, until we have finished. Now, our tilemap will look much more normal and could even be functional in a game at this state.
If you are looking to implement this algorithm in 2D like I did, I would highly recommend checking out the Unity blog post written by Ethan Bruins (linked below) as it does a great job explaining the importance of everything and has some great code samples. If you want to understand the smoothing algorithm further or want to implement it in a language other than C#, I recommend checking out the Wikipedia page for Moore Neighborhood (linked below) as it includes some great pseudo-code. If you are more interested in the technical, mathematical aspects of either of these algorithms, I would check out their respective pages on MathWorld (linked below), both written by Eric Weisstein.
My favorite thing about these two algorithms is how flexible they can be. They could easily be run on lower powered devices like smartphones or handheld game consoles, or be greatly modified for much more complex levels whether they are in 3D and/or have more than just an ON and OFF state. As stated earlier, these algorithms work great for 2D top-down terrain (as seen in my examples) or almost any other situation. You could choose to not force walls and generate platforms instead. Or you could take this to a whole other level and use these algorithms in three dimensions.
If you would like to try out the demo seen in the images above, here is a link to my GitHub repository: https://github.com/averyfollett/CellularAutomata
References:
Bruins, Ethan. “Procedural Patterns to Use with Tilemaps - (Part II).” Unity Technologies Blog, 7 June 2018, blogs.unity3d.com/2018/06/07/procedural-patterns-to-use-with-tilemaps-part-ii/.
“Moore Neighborhood.” Wikipedia, Wikimedia Foundation, 16 Sept. 2019, en.wikipedia.org/wiki/Moore_neighborhood.
Weisstein, Eric W. "Cellular Automaton." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/CellularAutomaton.html
Weisstein, Eric W. "Moore Neighborhood." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/MooreNeighborhood.html
Comments
Post a Comment