top of page

Generate a Maze

The earliest known maze patterns date back to ancient times, with examples found in ancient Egyptian tomb paintings and Greek mythology. The labyrinth at Knossos on the island of Crete, associated with the myth of the Minotaur, is one of the most famous examples of a maze.


There's something captivating about the challenge of finding a way through. I've always enjoyed solving mazes, but when I learned Python, I decided to challenge myself solve mazes programatically.


In this part one of two series blog, I will dive into generating a maze.


I decided to use recursive backtracking to create a maze, as it seemed like a natural choice. We basically mark cells as we visit them and move through the grid, randomly selecting unvisited neighbors until we reach a dead end. Then, we backtrack to find an unvisited path, continuing until all cells are visited.


Here is the explanation in detail:


Maze Configuration:

  • width = 20: Set the width of each cell in the maze.

  • cols = int(size[0] / width): Calculate the number of columns in the maze based on the window size and cell width.

  • rows = int(size[1] / width): Calculate the number of rows in the maze based on the window size and cell width.

  • stack = []: Initialize an empty stack to track visited cells during maze generation

  • traversed_path = []: Initialize an empty list to track the path the player has taken

import random, math
import pygame, os, sys, gc
import time
pygame.init()

WHITE, BLACK, GREY = (255,255,255), (0,0,0), (128,128,128)
PURPLE, RED, BLUE = (100,0,100), (255,0,0), (0,0,255)
GREEN, YELLOW = (0,255,0), (255,255,0)

size = (801,801)
screen = pygame.display.set_mode(size)

pygame.display.set_caption("Maze")
clock = pygame.time.Clock()

width = 20 # 25
cols = int(size[0] / width)
rows = int(size[1] / width)
stack = []
traversed_path=[]
solved=False

Cell Class:

  • Define a Cell class to represent each cell in the maze.

  • Each cell has attributes for its position (x and y), visited status, current status, walls (top, right, bottom, left), neighbors, and the next cell to visit.

  • get_rect: Returns a Rect object representing the cell's position and size.

  • draw: Draws the cell on the screen, including its walls and whether it has been visited

  • checkNeighbors: Checks the neighboring cells of the current cell and returns a random unvisited neighbor

class Cell():
    def __init__(self,x,y):
        global width
        self.x, self.y = x * width, y * width
        # We keep a track of which squares we've visited and which we have not.
        self.visited, self.current = False, False        
        self.walls = [True,True,True,True] # top , right , bottom , left
        # neighbors
        self.neighbors = []
        self.top, self.right, self.bottom, self.left = 0, 0, 0, 0        
        self.next_cell = 0
    
    def get_rect(self):
        return pygame.rect.Rect((self.x,self.y),(width,width))
    
    def draw(self, bg=WHITE, fill=True, small=False):
        if self.visited:
            if not fill:
                pygame.draw.rect(screen,bg,(self.x,self.y,width,width), width//4)
            else:
                if small:
                    pygame.draw.rect(screen,bg, (self.x+width//4, self.y+width//4, width-width//2, width-width//2))
                else:
                    pygame.draw.rect(screen,bg,(self.x, self.y, width,width))    
            if self.walls[0]:
                # top
                pygame.draw.line(screen,GREY,(self.x, self.y),((self.x + width),self.y),1) 
            if self.walls[1]:
                # right
                pygame.draw.line(screen,GREY,((self.x + width),self.y),((self.x + width),(self.y + width)),1) 
            if self.walls[2]:
                # bottom
                pygame.draw.line(screen,GREY,((self.x + width),(self.y + width)),(self.x,(self.y + width)),1) 
            if self.walls[3]:
                # left
                pygame.draw.line(screen,GREY,(self.x,(self.y + width)),(self.x, self.y),1)
    
    def checkNeighbors(self):
        if int(self.y / width) - 1 >= 0:
            self.top = grid[int(self.y / width) - 1][int(self.x / width)]
        if int(self.x / width) + 1 <= cols - 1:
            self.right = grid[int(self.y / width)][int(self.x / width) + 1]
        if int(self.y / width) + 1 <= rows - 1:
            self.bottom = grid[int(self.y / width) + 1][int(self.x / width)]
        if int(self.x / width) - 1 >= 0:
            self.left = grid[int(self.y / width)][int(self.x / width) - 1]
        if self.top != 0:
            if self.top.visited == False:
                self.neighbors.append(self.top)
        if self.right != 0:
            if self.right.visited == False:
                self.neighbors.append(self.right)
        if self.bottom != 0:
            if self.bottom.visited == False:
                self.neighbors.append(self.bottom)
        if self.left != 0:
            if self.left.visited == False:
                self.neighbors.append(self.left)
        if len(self.neighbors) > 0:
            self.next_cell = self.neighbors[random.randrange(0,len(self.neighbors))]
            return self.next_cell
        else:
            return False

When traveling to this new square we remove the wall to the new square and this is what carves out the maze!

def removeWalls(current_cell, next_cell):
    x = int(current_cell.x / width) - int(next_cell.x / width)
    y = int(current_cell.y / width) - int(next_cell.y / width)
    if x == -1: # right of current
        current_cell.walls[1] = False
        next_cell.walls[3] = False
    elif x == 1: # left of current
        current_cell.walls[3] = False
        next_cell.walls[1] = False
    elif y == -1: # bottom of current
        current_cell.walls[2] = False
        next_cell.walls[0] = False
    elif y == 1: # top of current
        current_cell.walls[0] = False
        next_cell.walls[2] = False
        
def draw_maze(flip=True):
    screen.fill(GREY)
    for y in range(rows):
        for x in range(cols):
            grid[y][x].draw()
    if flip:
        pygame.display.flip()
        clock.tick(60)

Maze Generation:

  • We are using Recursive backtracking algorithm to generate the maze

  • We remove walls between cells as we move through the maze.


def generate_maze():
    global current_cell, next_cell, player, exit_cell, traversed_path
    maze_generated = False
    while not maze_generated:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                done = True
        current_cell.visited = True
        current_cell.current = True
        
        # Examining all the neigbours of the current square and 
        # selecting (at random) any of the unvisited squares, moving 
        # into it, then mark this new location as also visited.
        next_cell = current_cell.checkNeighbors()
        
        if next_cell != False:
            current_cell.neighbors = []
            stack.append(current_cell)
            removeWalls(current_cell,next_cell)
            current_cell.current = False
            current_cell = next_cell
        elif len(stack) > 0:
            # No next_cell, dead end! Take a step backwards to see if there  
            # are any unvisted neigbours from the last visited square
            current_cell.current = False
            current_cell = stack.pop()
        elif len(stack) == 0:
            draw_maze()
            maze_generated=True

    # Define Entry and Exit Cells
    player = grid[0][random.randrange(0,cols)]
    exit_cell = grid[rows-1][random.randrange(0,cols)]
    traversed_path.append(player) # First path cell
    traversed_path[0].draw(GREEN, False)
    exit_cell.draw(YELLOW, False)
    pygame.image.save(screen,"maze.png")

Initializes an empty grid of cells based on the number of rows and columns and generate the maze

   # Initialize empty grid
grid = []
for y in range(rows):
    grid.append([])
    for x in range(cols):
        grid[y].append(Cell(x,y))

current_cell = grid[0][0]
next_cell = 0

# Generate the Maze 
generate_maze()

The program saves the generated maze as an image. Here are some samples of generated mazes:



100 views1 comment

Recent Posts

See All

1 Comment


Guest
Feb 22

aMAZEing!

Like

Subscribe

Subscribe to our mailing list for regular updates on news, events, insightful blogs, and free code!

Thanks for subscribing!

bottom of page