In this article we generate mazes using jupyter notebooks, numpy, matplotlib,
and the scikit-image
Almost since I could first draw I’ve been fascinated with creating and solving mazes. Graph paper and mechanical pencils were some of my favorite gifts. Recently I’ve rediscovered some of that same childlike excitement by designing a homebrew cpu, and the next game I’m building for it needs some custom mazes.
There are lots of existing maze generating algorithms but I wanted something that filled cells (not grid edges) and that is fast and simple to do in Python so it would be easy to tweak and customize.
“Flood fill” functions work like the paint bucket tool in an image editing program. They start from one pixel in an image then expand to all connected pixels of the same color, replacing them with a new color.
If we start a flood fill from any pixel in an image and it covers all pixels with the same color then they must all be connected, like the path in a maze from the beginning to the end.
First install jupyter and a few common Python libraries, and launch jupyter notebook:
$ pip install jupyter matplotlib scikit-image $ jupyter-notebook
This jupyter notebook file includes all examples in the article:
We use numpy for efficient array operations, matplotlib for visualization, and scikit-image for image manipulation. Imports are at the top of the project, as usual. If you get any errors running these imports make sure you have the dependencies above installed:
import numpy as np import matplotlib.pyplot as plt import matplotlib.patches as mpatches import matplotlib as mpl from skimage.segmentation import flood_fill from skimage.io import imread, imsave from skimage.color import rgb2gray from skimage.transform import resize from skimage.filters import threshold_local
Our maze needs a border wall, a starting location, and an ending location. Let’s represent our maze with a numpy array where the border wall is marked with 1’s, the starting and ending locations are marked with 2’s and everything else is set to 0.
We follow numpy’s (y, x) convention for coordinates, so our “box” height comes first:
def box(height, width): arr = np.zeros((height, width), dtype=np.uint8) # walls top, bottom, left, right = 1 arr = arr[-1] = arr[..., 0] = arr[..., -1] = 1 # start and end locations = 2 arr[0, 1] = arr[-1, -2] = 2 return arr b = box(6, 6) b
array([[1, 2, 1, 1, 1, 1], [1, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 1], [1, 1, 1, 1, 2, 1]], dtype=uint8)
Let’s visualize our array with matplotlib. Choosing “inferno” as a nice a bright palette, we create a legend with color patches, and draw arrays with this “show” function:
palette = mpl.cm.inferno.resampled(3).colors labels = ["0: unfilled", "1: wall", "2: passage"] def show(arr): plt.figure(figsize=(9, 9)) im = plt.imshow(palette[arr]) # create a legend on the side patches = [mpatches.Patch(color=c, label=l) for c, l in zip(palette, labels)] plt.legend(handles=patches, bbox_to_anchor=(1.1, 1), loc=2, borderaxespad=0) plt.show() show(b)
Very nice! We can see the starting and ending locations at (y=0, x=1) and (y=5, x=4).
Lay of the land
Instead of hard-coding the starting location and ending locations we can find them
np.where(b == 2)
(array([0, 5]), array([1, 4]))
This gives us arrays with the y coordinates and the x coordinates of each location. For our program we need the y and x values for just one of these locations:
tuple(coord for coord in np.where(b == 2))
Next we collect the unfilled coordinates in the box:
np.where(b == 0)
(array([1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4]), array([1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]))
Again we want the (y, x) coordinates not an array of y’s and an array of x’s
np.swapaxes(np.where(b == 0), 0, 1)
array([[1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [3, 1], [3, 2], [3, 3], [3, 4], [4, 1], [4, 2], [4, 3], [4, 4]])
These are the coordinates that will become walls or passages in our maze, but first we’re going to need a bigger box, with many more coordinates to fill:
a = box(30, 30) show(a)
Here’s our first flood fill maze generation algorithm “maze1”:
- take all the unfilled coordinates and shuffle their order
- save the starting coordinates (anything marked as a passage)
- set all the existing passages to unfilled so the whole array is 0’s or 1’s.
- for each of the unfilled coordinates
- set it to a 1 (wall) and try flood filling the maze from the starting coordinates with 2’s (passage)
- if any part of the maze remains a 0 (unfilled) then this wall has divided the maze making some part of it unreachable, so set the wall back to unfilled.
- all remaining unfilled cells are part of the maze so set them to passages
def maze1(arr): unfilled = np.swapaxes(np.where(arr == 0), 0, 1) np.random.shuffle(unfilled) start = tuple(coord for coord in np.where(arr == 2)) arr = np.copy(arr) arr[arr == 2] = 0 for lc in unfilled: lc = tuple(lc) arr[lc] = 1 t = flood_fill(arr, start, 1) if np.any(t == 0): arr[lc] = 0 arr[arr == 0] = 2 return arr show(maze1(a))
So that’s something. It is a maze, but I wasn’t expecting the maze to allow moving diagonally. Also it’s very sparse (mostly walls) and easy to solve.
The first problem is easy to fix.
flood_fill has a
connectivity parameter that sets
the distance each cell can be from the next while allowing the fill to continue.
Here’s “maze2” like above but with
def maze2(arr): unfilled = np.swapaxes(np.where(arr == 0), 0, 1) np.random.shuffle(unfilled) start = tuple(coord for coord in np.where(arr == 2)) arr = np.copy(arr) arr[arr == 2] = 0 for lc in unfilled: lc = tuple(lc) arr[lc] = 1 t = flood_fill(arr, start, 1, connectivity=1) # no diagonals, please if np.any(t == 0): arr[lc] = 0 arr[arr == 0] = 2 return arr show(maze2(a))
Better, but this maze is still very easy to solve.
Our algorithm sets every unfilled cell to a wall as long as that wall doesn’t cause the maze to be divided. So our walls end up very thick because any time a dead-end (a cell with three walls surrounding it) is selected it will be turned into a wall as well.
Let’s protect our dead-ends to generate more complex mazes with “maze3”:
# mask for cells above, below, left and right neighbors = np.array([ [0, 1, 0], [1, 0, 1], [0, 1, 0]], dtype=np.uint8) def maze3(arr): unfilled = np.swapaxes(np.where(arr == 0), 0, 1) np.random.shuffle(unfilled) start = tuple(coord for coord in np.where(arr == 2)) arr = np.copy(arr) arr[arr == 2] = 0 for lc in unfilled: lc = tuple(lc) y, x = lc # protect dead-ends from becoming walls if np.sum(neighbors * arr[y-1:y+2, x-1:x+2]) > 2: continue arr[lc] = 1 t = flood_fill(arr, start, 1, connectivity=1) if np.any(t == 0): arr[lc] = 0 arr[arr == 0] = 2 return arr m = maze3(a) show(m)
That’s more like it.
This maze has start and end positions on the edge so we can discover the path from start to end by flood-filling the walls one side and tracing the border between the two different colors:
# spoiler t = flood_fill(m, (0, 0), 0) show(t)
A “normal” maze
To generate mazes that look more like standard grid mazes we can start with a pattern of alternating passages and walls:
c = box(31, 31) c[::2, ::2] = 1 # walls on even (y, x) values c[1::2, 1::2] = 2 # passages on odd (y, x) values show(c)
sm = maze3(c) show(sm)
The same algorithm now produces a common grid maze, but we don’t have to stop there.
Big brain solution
Let’s take inspiration from nature and generate a maze from a brain coral image:
We load the image with
imread then crop a small part and convert it to
brain = imread('brain-coral.jpg') crop_brain = rgb2gray(brain[-500:,200:1000]) plt.figure(figsize=(15, 9)) im = plt.imshow(crop_brain, plt.cm.gray) cb = plt.colorbar()
Next reduce the resolution with
resize and use
threshold_local to convert
grayscale to 1’s and 0’s:
small_brain = resize(crop_brain, (50, 80)) binary_brain = small_brain > threshold_local(small_brain, 15, 'mean') plt.figure(figsize=(9, 9)) im = plt.imshow(binary_brain, plt.cm.gray)
Then wrap the image with a box and turn the 0s into passages and the 1s into unfilled using modular arithmetic:
d = box(52, 82) insert_brain = (binary_brain + 2) % 3 d[1:-1, 1:-1] = insert_brain show(d)
When we generate a maze with this pattern the walls can only be placed in the unfilled areas so our maze will follow the shape of the brain coral:
bm = maze2(d) # maze2 is better: don't need lots of extra dead-ends show(bm)
Here’s the solution:
# spoiler t = flood_fill(bm, (0,0), 0) show(t)
Why don’t we have both?
Drawing patterns for the algorithm to fill lets us create all sorts of mazes.
If we save the grid and brain patterns with
imsave we can use an image editor
to combine them any way we like:
imsave('grid_pattern.png', palette[c]) imsave('brain_pattern.png', palette[d]) # use these to create combined_pattern.png with an image editing program
We can stitch patterns together and draw walls or passages through the image to shape the generated maze solution to any style and difficulty.
n = imread('combined_pattern.png') # use red component to convert RGB to 0:unfilled, 1: wall, 2: passage n = np.array((n[...,0] == 188) + (n[...,0] == 252) * 2, dtype=np.uint8) show(n)
mn = maze3(n) show(mn)
The solution follows our wandering path up and down through the different maze styles:
# spoiler t = flood_fill(mn, (0,0), 0) show(t)
This article showed how to generate mazes using jupyter notebooks, numpy, matplotlib,
and the scikit-image
The mazes started off very simple so we covered ways to increase the complexity and design custom patterns to shape the style and general path of the maze solution.
Thank you for reading!