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 FalseWhen 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:
aMAZEing!