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 mazeWe 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!