Maze Generation by Cellular Automaton


Cellular automata (CA) can be used to generate mazes, as described on the LifeWiki. A commonly used algorithm operates like John Conway's Game of Life in that a cell is born if it has exactly 3 neighbours but the survival rule is more liberal: a cell survives if it has 1–5 neighbours (rulestring B3/S12345).

The following code generates a maze using to this approach. The CA rules are implemented using SciPy's convolve2d algorithm to count neighbours. The code generates frame images of the growing maze every nit iterations, as animated below. The frames are saved to a subdirectory ca_frames.

Cellular automata maze by rulestring B3/S12345

This code is also available on my Github page.

import numpy as np
from scipy.signal import convolve2d
import matplotlib.pyplot as plt

# Create a maze using the cellular automaton approach described at              
# The frames for animation of the growth of the maze are saved to               
# the subdirectory ca_frames/.                                                  
# Christian Hill, January 2018.

def ca_step(X):
    """Evolve the maze by a single CA step."""

    K = np.ones((3, 3))
    n = convolve2d(X, K, mode='same', boundary='wrap') - X
    return (n == 3) | (X & ((n > 0) & (n < 6)))

# Maze size
nx, ny = 200, 150
X = np.zeros((ny, nx), dtype=np.bool)
# Size of initial random area (must be even numbers)
mx, my = 20, 16

# Initialize a patch with a random mx x my region
r = np.random.random((my, mx)) > 0.75
X[ny//2-my//2:ny//2+my//2, nx//2-mx//2:nx//2+mx//2] = r

# Total number of iterations
nit = 400
# Make an image every ipf iterations
ipf = 10

# Figure dimensions (pixels) and resolution (dpi)
width, height, dpi = 600, 450, 10
fig = plt.figure(figsize=(width/dpi, height/dpi), dpi=dpi)
ax = fig.add_subplot(111)

for i in range(nit):
    X = ca_step(X)
    if not i % ipf:
        im = ax.imshow(X,, interpolation='nearest')
        plt.savefig('ca_frames/_img{:04d}.png'.format(i), dpi=dpi)
Current rating: 4.6


Comments are pre-moderated. Please be patient and your comment will appear soon.

There are currently no comments

New Comment


required (not published)