Making a maze


The Depth-first search algorithm is a simple approach to generating a maze. It is well described and illustrated in lots of places on the internet, so only an outline is given here.

The maze is considered to consist of a grid of cells; each cell initially has four walls (North, East, South and West). Starting from a given cell, we will aim to produce a path visiting each cell according to the following procedure:

  • Inspect the neighbouring cells. If any of them have yet to be visited, pick one and move at random into it by removing the wall between them.

  • If no neighbouring cell is unvisited (a dead end), then backtrack to the last cell with an unvisited neighbour.

In the implemention of this algorithm in the Python program below, we define classes for the cell and for the entire maze. We wind our way through the grid of cells at random, keeping track of the path we take on a stack implemented as a Python list. If we end up in a dead end, we simply pop visited cells off the stack until we find one with unvisited neighbours.

The code below produces an SVG image of a maze with given dimensions. For example (40 x 40):

Depth-first maze

and (15 x 15):

enter image description here

This code is also available on my Github page.

import random

# Create a maze using the depth-first algorithm described at                    
# Christian Hill, April 2017.

class Cell:
    """A cell in the maze.

    A maze "Cell" is a point in the grid which may be surrounded by walls to
    the north, east, south or west.


    # A wall separates a pair of cells in the N-S or W-E directions.
    wall_pairs = {'N': 'S', 'S': 'N', 'E': 'W', 'W': 'E'}

    def __init__(self, x, y):
        """Initialize the cell at (x,y). At first it is surrounded by walls."""

        self.x, self.y = x, y
        self.walls = {'N': True, 'S': True, 'E': True, 'W': True}

    def has_all_walls(self):
        """Does this cell still have all its walls?"""

        return all(self.walls.values())

    def knock_down_wall(self, other, wall):
        """Knock down the wall between cells self and other."""

        self.walls[wall] = False
        other.walls[Cell.wall_pairs[wall]] = False

class Maze:
    """A Maze, represented as a grid of cells."""

    def __init__(self, nx, ny, ix=0, iy=0):
        """Initialize the maze grid.
        The maze consists of nx x ny cells and will be constructed starting
        at the cell indexed at (ix, iy).


        self.nx, self.ny = nx, ny
        self.ix, self.iy = ix, iy
        self.maze_map = [[Cell(x, y) for y in range(ny)] for x in range(nx)]

    def cell_at(self, x, y):
        """Return the Cell object at (x,y)."""

        return self.maze_map[x][y]

    def __str__(self):
        """Return a (crude) string representation of the maze."""

        maze_rows = ['-' * nx*2]
        for y in range(ny):
            maze_row = ['|']
            for x in range(nx):
                if self.maze_map[x][y].walls['E']:
                    maze_row.append(' |')
                    maze_row.append('  ')
            maze_row = ['|']
            for x in range(nx):
                if self.maze_map[x][y].walls['S']:
                    maze_row.append(' +')
        return '\n'.join(maze_rows)

    def write_svg(self, filename):
        """Write an SVG image of the maze to filename."""

        aspect_ratio = self.nx / self.ny
        # Pad the maze all around by this amount.
        padding = 10
        # Height and width of the maze image (excluding padding), in pixels
        height = 500
        width = int(height * aspect_ratio)
        # Scaling factors mapping maze coordinates to image coordinates
        scy, scx = height / ny, width / nx

        def write_wall(f, x1, y1, x2, y2):
            """Write a single wall to the SVG image file handle f."""

            print('<line x1="{}" y1="{}" x2="{}" y2="{}"/>'
                                .format(x1, y1, x2, y2), file=f)

        # Write the SVG image file for maze
        with open(filename, 'w') as f:
            # SVG preamble and styles.
            print('<?xml version="1.0" encoding="utf-8"?>', file=f)
            print('<svg xmlns=""', file=f)
            print('    xmlns:xlink=""', file=f)
            print('    width="{:d}" height="{:d}" viewBox="{} {} {} {}">'
                    .format(width+2*padding, height+2*padding,
                        -padding, -padding, width+2*padding, height+2*padding),
            print('<defs>\n<style type="text/css"><![CDATA[', file=f)
            print('line {', file=f)
            print('    stroke: #000000;\n    stroke-linecap: square;', file=f)
            print('    stroke-width: 5;\n}', file=f)
            print(']]></style>\n</defs>', file=f)
            # Draw the "South" and "East" walls of each cell, if present (these
            # are the "North" and "West" walls of a neighbouring cell in
            # general, of course).
            for x in range(nx):
                for y in range(ny):
                    if maze.cell_at(x,y).walls['S']:
                        x1, y1, x2, y2 = x*scx, (y+1)*scy, (x+1)*scx, (y+1)*scy
                        write_wall(f, x1, y1, x2, y2)
                    if maze.cell_at(x,y).walls['E']:
                        x1, y1, x2, y2 = (x+1)*scx, y*scy, (x+1)*scx, (y+1)*scy
                        write_wall(f, x1, y1, x2, y2)
            # Draw the North and West maze border, which won't have been drawn
            # by the procedure above. 
            print('<line x1="0" y1="0" x2="{}" y2="0"/>'.format(width), file=f)
            print('<line x1="0" y1="0" x2="0" y2="{}"/>'.format(height),file=f)
            print('</svg>', file=f)

    def find_valid_neighbours(self, cell):
        """Return a list of unvisited neighbours to cell."""

        delta = [('W', (-1,0)),
                 ('E', (1,0)),
                 ('S', (0,1)),
                 ('N', (0,-1))]
        neighbours = []
        for direction, (dx,dy) in delta:
            x2, y2 = cell.x + dx, cell.y + dy
            if (0 <= x2 < nx) and (0 <= y2 < ny):
                neighbour = maze.cell_at(x2, y2)
                if neighbour.has_all_walls():
                    neighbours.append((direction, neighbour))
        return neighbours

    def make_maze(self):
        # Total number of cells.
        n = self.nx * self.ny
        cell_stack = []
        current_cell = self.cell_at(ix, iy)
        # Total number of visited cells during maze construction.
        nv = 1

        while nv < n:
            neighbours = self.find_valid_neighbours(current_cell)

            if not neighbours:
                # We've reached a dead end: backtrack.
                current_cell = cell_stack.pop()

            # Choose a random neighbouring cell and move to it.
            direction, next_cell = random.choice(neighbours)
            current_cell.knock_down_wall(next_cell, direction)
            current_cell = next_cell
            nv += 1

# Maze dimensions (ncols, nrows)
nx, ny = 40, 40
# Maze entry position
ix, iy = 0, 0

maze = Maze(nx, ny, ix, iy)

Current rating: 3.8


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

eypros 5 months, 2 weeks ago

Really good work. I would like to have some control over the wall width though.
Anyway, appreciated.

Link | Reply
Current rating: 3

Philip Thompson 2 months ago

"North, East, South and East"

no west then?

Link | Reply
Current rating: 5

christian 2 months ago

Ha! Good catch – fixed.

Link | Reply
Current rating: 5

dcox 2 months ago

When I run this, how do I see the SVG image? It outputs the maze onto the console as characters. I'm sure it's something obvious I'm missing , I'm new to this...

Link | Reply
Currently unrated

christian 2 months ago

It should also save a file, maze.svg, to the same directory you run the program from (last line of the code).

Link | Reply
Current rating: 5

Tony Dahbura 1 month, 2 weeks ago

Really cool! Couple of questions:
Does this generate a perfect maze?
Where is the entrance and exit?

Link | Reply
Currently unrated

christian 1 month, 2 weeks ago

I'm glad you like it. It should generate a perfect maze (all cells can be visited by some path from the initial cell, which is at (0,0): the top left corner); the end cell isn't specified: you can choose where it should be after the maze has been created or alter the code to mark it when the algorithm visits a pre-defined cell.

Link | Reply
Currently unrated

New Comment


required (not published)