Home

Writing

Nov 2017

Cellular Automata Caves

Have you ever wanted to create something from nothing? When you are making games, you’ll often find yourself with the desire to autogenerate some part of your game, whether it be a map, character features, or weapon designs. The thing is, randomness is kind of bad. It usually ends up being unwieldy or downright unplayable. This post will teach you a method for generating an infinite number of random but useful game maps. To do this, we will use a generation method called Cellular Automata. Let’s dive in!

Here is a cave generated with almost complete randomness:

Here is the code used to generate this cave:

In this cave, dots are traversable cave floor, and hashtags are non-traversable cave walls. You’ll notice some open spaces here, but it is unlikely this cave would be fun to use in your game; this cave is pretty awful. What we’d like is for there to be interesting features on the map, but we don’t want to hardcode the features. With Cellular Automata, you create a set of simple rules to follow that can produce features of the sort we want.

Changing the floor spawn rate

We want more room to walk around to be more floors than walls in our cave (not a 50/50 split).

RULE: Set the spawn rate of walls to 40% and floors to 60%.

Here is the cave our new rule makes:

The difference may appear subtle, but there are more connected spaces, and the open spaces are larger. While this rule has improved our cave, it’s still pretty unplayable. We want the walls to be more focused, and we want the walking areas to be more contiguous.

Consolidating walls and floors

RULE: If there are between 5–7 walls nearby, make the current point a wall.

Let’s write some code to capture these rules in python:

Here is the map generated by our script:

As you can see, this map looks pretty good. Let’s update the rules for before generation 5:

RULE: Make a point into a wall if we are on the edge of the map before generation 5.

This can produce even better maps:

It has nooks, crannies, even islands, thicker walls, which makes sense because we added a bunch on every iteration. It’s also pretty fast to produce! Is this method perfect? No. It’s more art than science, and you’ll notice that the maps are pretty uninteresting below a certain dimension. Sometimes the maps are still too open. You can play with the different cutoffs, generations, and rules. You will see our method is extremely sensitive to changing any parameter. We can adjust our rules to fix that, but I’ll leave experimentation to the reader. I encourage you to mess around with parameters and to try changing or adding rules.

Conclusion

We started with a random map and then applied some rules to turn that randomness into a structured map. You can also start with some structure and add randomness to it. A great example of this can be found in the indie title spelunky, with some of the best pseudo-random level designs. Here is a video of how spelunky starts with some structure and adds randomness to make each level unique! Enjoy!

If you enjoyed this post, be sure to signup for more.

Signup For More