0x- Python Caves: Cellular Automata

Often when you are making games, you’ll find yourself with the desire to autogenerate some part of your game, whether it be a map, character features, or weapon designs. True randomness is bad. It usually ends up being unwieldy or downright unplayable. I’m going to teach you a method for generating an infinite number of random but valuable game maps. We will use a generation method called Cellular Automata. Let’s dive in!

Here is a cave generated with hashes and dots made with near-complete randomness:

Here is the script used to generate this cave:

import random
import numpy as np
def display_cave(matrix):
for i in range(matrix.shape[0]):
for j in range(matrix.shape[1]):
char = "#" if matrix[i][j] == WALL else "."
print(char, end='')
print()
# the cave should be 42x42
shape = (42,42)
# walls will be 0
# floors will be 1
WALL = 0
FLOOR = 1
# create a random map choosing
# walls 40% of the time, floor
# 60% of the time.
new_map = np.ones(shape)
# for each row
for i in range(shape[0]):
# for each column
for j in range(shape[1]):
# choose a number between 0-1
choice = random.uniform(0, 1)
# choose a wall or a floor
new_map[i][j] = WALL if choice < 0.5 else FLOOR
display_cave(new_map)
view raw rand_cave.py hosted with ❤ by GitHub

In this cave, dots are traversable cave floors, and hashtags are non-traversable cave walls. You’ll notice some open spaces here, but this cave would be un-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 them. With Cellular Automata, you create a set of simple rules to follow that can produce features we want.

Changing the floor spawn rate

We want more room to walk around and 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%.

shape = (42,42)
WALL = 0
FLOOR = 1
# set the probability of filling
# a wall at 40% not 50%
fill_prob = 0.4
new_map = np.ones(shape)
for i in range(shape[0]):
for j in range(shape[1]):
choice = random.uniform(0, 1)
# replace 0.5 with fill_prob
new_map[i][j] = WALL if choice < fill_prob else FLOOR
display_cave(new_map)
view raw floor_cave.py hosted with ❤ by GitHub

Here is the cave our new rule makes:

The difference may appear subtle, but there are larger and more connected spaces. While this rule has improved our cave, it’s still non-traversable. We want the walls to be more consolidated, 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.

shape = (42,42)
WALL = 0
FLOOR = 1
fill_prob = 0.4
new_map = np.ones(shape)
for i in range(shape[0]):
for j in range(shape[1]):
choice = random.uniform(0, 1)
new_map[i][j] = WALL if choice < fill_prob else FLOOR
# run for 6 generations
generations = 6
for generation in range(generations):
for i in range(shape[0]):
for j in range(shape[1]):
# get the number of walls 1 away from each index
# get the number of walls 2 away from each index
submap = new_map[max(i-1, 0):min(i+2, new_map.shape[0]),max(j-1, 0):min(j+2, new_map.shape[1])]
wallcount_1away = len(np.where(submap.flatten() == WALL)[0])
submap = new_map[max(i-2, 0):min(i+3, new_map.shape[0]),max(j-2, 0):min(j+3, new_map.shape[1])]
wallcount_2away = len(np.where(submap.flatten() == WALL)[0])
# this consolidates walls
# for first five generations build a scaffolding of walls
if generation < 5:
# if looking 1 away in all directions you see 5 or more walls
# consolidate this point into a wall, if that doesnt happpen
# and if looking 2 away in all directions you see less than
# 7 walls, add a wall, this consolidates and adds walls
if wallcount_1away >= 5 or wallcount_2away <= 7:
new_map[i][j] = WALL
else:
new_map[i][j] = FLOOR
# this consolidates open space, fills in standalone walls,
# after generation 5 consolidate walls and increase walking space
# if there are more than 5 walls nearby make that point a wall,
# otherwise add a floor
else:
# if looking 1 away in all direction you see 5 walls
# consolidate this point into a wall,
if wallcount_1away >= 5:
new_map[i][j] = WALL
else:
new_map[i][j] = FLOOR
display_cave(new_map)
view raw rules.py hosted with ❤ by GitHub

Here is the map generated by our script:

As you can see, this map looks pretty good. Let’s do one more thing and update the rules before generation 5.

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

if wallcount_1away >= 5 or wallcount_2away <= 7:
new_map[i][j] = WALL
else:
new_map[i][j] = FLOOR
if i==0 or j == 0 or i == shape[0]-1 or j == shape[1]-1:
new_map[i][j] = WALL
view raw update_gen_5_rule.py hosted with ❤ by GitHub

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 below a specific size, the maps are uninteresting. Sometimes the maps are too open. You can play with the different cutoffs, generations, and rules. You will see our method is susceptible to changing input parameters. We can adjust our rules to fix that, but I’ll leave experimentation to you. Mess around with parameters and 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 do the reverse. You can start with some structure and add randomness to it.

If you enjoyed this, share it with a like-minded friend!

Share

Links:

If you want more on level generation, here is a video of spelunky (an indie platformer) level generation.