Making a maze

(15 comments)

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.

# df_maze.py
import random


# Create a maze using the depth-first algorithm described at
# https://scipython.com/blog/making-a-maze/
# 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 = ['-' * self.nx * 2]
        for y in range(self.ny):
            maze_row = ['|']
            for x in range(self.nx):
                if self.maze_map[x][y].walls['E']:
                    maze_row.append(' |')
                else:
                    maze_row.append('  ')
            maze_rows.append(''.join(maze_row))
            maze_row = ['|']
            for x in range(self.nx):
                if self.maze_map[x][y].walls['S']:
                    maze_row.append('-+')
                else:
                    maze_row.append(' +')
            maze_rows.append(''.join(maze_row))
        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 / self.ny, width / self.nx

        def write_wall(ww_f, ww_x1, ww_y1, ww_x2, ww_y2):
            """Write a single wall to the SVG image file handle f."""

            print('<line x1="{}" y1="{}" x2="{}" y2="{}"/>'
                  .format(ww_x1, ww_y1, ww_x2, ww_y2), file=ww_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="http://www.w3.org/2000/svg"', file=f)
            print('    xmlns:xlink="http://www.w3.org/1999/xlink"', file=f)
            print('    width="{:d}" height="{:d}" viewBox="{} {} {} {}">'
                  .format(width + 2 * padding, height + 2 * padding,
                          -padding, -padding, width + 2 * padding, height + 2 * padding),
                  file=f)
            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(self.nx):
                for y in range(self.ny):
                    if self.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 self.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 < self.nx) and (0 <= y2 < self.ny):
                neighbour = self.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(self.ix, self.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()
                continue

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

To use this class, run a script such as the following:

from df_maze import Maze

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

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

print(maze)
maze.write_svg('maze.svg')
Current rating: 3.8

Comments

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

eypros 1 year, 7 months ago

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

Link | Reply
Current rating: 3.8

Philip Thompson 1 year, 4 months ago

"North, East, South and East"

no west then?

Link | Reply
Current rating: 4.2

christian 1 year, 4 months ago

Ha! Good catch – fixed.

Link | Reply
Current rating: 4

dcox 1 year, 4 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
Current rating: 4

christian 1 year, 4 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 year, 4 months ago

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

Link | Reply
Current rating: 5

christian 1 year, 3 months 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
Current rating: 5

Zul 11 months, 1 week ago

how/where would you insert the code for this?

Link | Reply
Current rating: 3.4

Jeff 1 month ago

Wtf??

Link | Reply
Currently unrated

Xario 1 year ago

Very nice work.
One thought: If you want to make it importable, add the line
if __name__ == "__main__":

before
# Maze dimensions (ncols, nrows)

and indent the ten lines below.
Also: You use the variable name "maze" at three positions inside class functions, those should be substituted with "self". So change these:
if maze.cell_at(x,y).walls['S']:
if maze.cell_at(x,y).walls['E']:
neighbour = maze.cell_at(x2, y2)

to:
if self.cell_at(x,y).walls['S']:
if self.cell_at(x,y).walls['E']:
neighbour = self.cell_at(x2, y2)

Because the name "maze" doesn't really exist inside the maze class. You use it in script part at the bottom, which should be extra, for example like I suggested. Because there a user should be free to call it "mymaze" for example and then your code breaks.
All the best! X.

Link | Reply
Currently unrated

christian 1 year ago

Thanks – I didn't update the code on this page properly when I updated it on GitHub. I've replaced it with the GitHub scripts df_maze.py and make_df_maze.py which I hope addresses your concerns.

Link | Reply
Current rating: 5

Tabitha 9 months, 1 week ago

i tried to run this code but receied the error no module named 'df maze' what did i do wrong?

Link | Reply
Currently unrated

christian 9 months, 1 week ago

You need to save the first block of code as "df_maze.py" – it is imported by the second script, which should be saved to the same directory.

Link | Reply
Currently unrated

Tabitha 9 months, 1 week ago

Thank you!! 😊

Link | Reply
Currently unrated

maze runner 3 months ago

Good work .
I will try to analyze and inspire myself to do the code myself on my own. thanks a lot

Link | Reply
Current rating: 5

New Comment

required

required (not published)

optional

required