Making a maze

(27 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.7

Comments

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

eypros 4 years ago

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

Link | Reply
Current rating: 3.7

Philip Thompson 3 years, 9 months ago

"North, East, South and East"

no west then?

Link | Reply
Current rating: 4.1

christian 3 years, 9 months ago

Ha! Good catch – fixed.

Link | Reply
Current rating: 3.6

dcox 3 years, 9 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.1

christian 3 years, 9 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: 4.4

Tony Dahbura 3 years, 9 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 3 years, 9 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: 3

Zul 3 years, 4 months ago

how/where would you insert the code for this?

Link | Reply
Current rating: 3.7

Jeff 2 years, 6 months ago

Wtf??

Link | Reply
Current rating: 1

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

christian 3 years, 5 months 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: 3.7

Ahmet Celebi 2 years, 2 months ago

I would like to add a treasure, starting and ending point, can you help me please ?

I don't know how to modifie your write_svg functions to make this ?

Link | Reply
Currently unrated

christian 2 years, 2 months ago

Every cell is accessible from every other cell, so you're free to designate any cell you want as the start, end and treasure cells. you could start by drawing a coloured square at your chosen coordinates: look up the SVG documentation for the <rect> element, for example (and use the same scaling factor as for the walls of course!)

Link | Reply
Currently unrated

Tabitha 3 years, 2 months 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 3 years, 2 months 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 3 years, 2 months ago

Thank you!! 😊

Link | Reply
Currently unrated

maze runner 2 years, 8 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

Ahmet Celebi 2 years, 2 months ago

Hello when i run the function write_svg it load me a file in my directory but it's not the maze but instead i get a file with those line : <?xml version="1.0" encoding="utf-8"?>
<svg xmlns="http://www.w3.org/2000/svg"
xmlns:xlink="http://www.w3.org/1999/xlink"
width="520" height="520" viewBox="-10 -10 520 520">
<defs>
<style type="text/css"><![CDATA[
...
</svg>

Link | Reply
Currently unrated

christian 2 years, 2 months ago

Dear Ahmet,
This is a Scalable Vector Graphics (SVG) file: you can view the image in e.g. a browser like Chrome or Firefox.
Hope that helps,
Christian

Link | Reply
Current rating: 3

Ahmet Celebi 2 years, 2 months ago

Yes it helped me,

I'm building an AI that learn to build maze, your structure of maze helped me a lot.

BIg thanks

Link | Reply
Currently unrated

Irv Kalb 2 years ago

Outstanding! I've adapted your code to a game that I'm developing. Your approach works perfectly.

Thank you!

Irv

Link | Reply
Currently unrated

NEED Help 1 year, 12 months ago

Is it possible for kruskal algorithm to make a path finding for maze just like a maze solver?

Link | Reply
Currently unrated

Joseph 1 year, 11 months ago

How do we set a fixed starting and ending position.? I am a bit confused on how to do that ? I would appreciate the help .

Link | Reply
Currently unrated

christian 1 year, 11 months ago

As noted above, the maze generated is "perfect": every cell can be accessed from every other cell, so you are free to set the start and end points to be wherever you want.

Link | Reply
Currently unrated

Rowan Gallagher 1 year, 4 months ago

How would i go about knocking out the wall above the top left and the wall below the bottom right?

Link | Reply
Currently unrated

christian 1 year, 4 months ago

I pushed a change to the code on GitHub to allow this: see https://github.com/scipython/scipython-maths/tree/master/maze

Link | Reply
Currently unrated

Sarah 1 year ago

Would it be possible in the SVG that instead of creating a line, we create a black background surrounding the path?

Link | Reply
Currently unrated

New Comment

required

required (not published)

optional

required