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`

.

*This code is also available on my Github page.*

# ca_maze.py import numpy as np from scipy.signal import convolve2d import matplotlib.pyplot as plt # Create a maze using the cellular automaton approach described at # https://scipython.com/blog/maze-generation-by-cellular-automaton/ # 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: print('{}/{}'.format(i,nit)) im = ax.imshow(X, cmap=plt.cm.binary, interpolation='nearest') plt.axis('off') plt.savefig('ca_frames/_img{:04d}.png'.format(i), dpi=dpi) plt.cla()

## Comments

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

There are currently no comments

## New Comment