Loading the image

We load the image by creating a utils.py file that reads the image, resizes it and stores it as a numpy array in a variables called image

# MODULES
import cv2
import random 

# DD
image = cv2.imread("ref2.png", 0)
newW = int(image.shape[1] * 0.1)
newH = int(image.shape[0] * 0.1)
print(newW,newH)
image = cv2.resize(image,(newW,newH))
_,image = cv2.threshold(image, 127, 255, cv2.THRESH_BINARY)
image = image/255

Generating the maze

The parameters of the Algorithm

• RES: (int) - The pixel size of each tile/cell in the maze grid
• DIMS: (int,int) - Total number of columns and rows derived from the input image dimensions (image.shape[1], image.shape[0])
• SCREEN: (int,int) - The width and height of the display window in pixels, calculated as (DIMS[0]*RES, DIMS[1]*RES)
• TILE: Tile() - Basic unit representing each cell in the maze with properties for walls [R,D,L,U], visited status, position, and color
• GRID: [[TILE, ..., n=DIMS[0]], ..., n=DIMS[1]] - A 2D array of Tile objects representing the complete maze structure
• VISITOR: Tile() - The current tile being processed during maze generation using depth-first search
• STACK: [TILE, ...] - Collection of tiles used for backtracking when the algorithm reaches dead ends in the depth-first traversal

# MODULES
import pygame
import random
from utils import image

# DD
RES = 12
DIMS = (image.shape[1], image.shape[0])
SCREEN = (DIMS[0]*RES, DIMS[1]*RES)
display = pygame.display.set_mode(SCREEN)

# DD. TILE
# tile = Tile()
# interp. a square in the screen
class Tile:
  def __init__(self,c,r):
    self.c = c
    self.r = r 
    self.x = self.c *RES
    self.y = self.r * RES
    self.rect = pygame.Rect(self.x, self.y, RES, RES)
    # attr. related to maze generator
    self.walls = [True, True, True, True]
                #  R,    D,    L,    U
    self.visited = False
    self.nullcolor = False
    self.color = "blue"

  def drawTile(self):
    self.getColor()
    pygame.draw.rect(display, self.color, self.rect)
    

  def drawWalls(self):
    if not self.nullcolor:
      # R
      if self.walls[0]:
        pygame.draw.line(display,"white",(self.x + RES, self.y),(self.x + RES, self.y + RES),1)
      # self.x + RES, self.y ---> self.x + RES, self.y + RES
      # D
      if self.walls[1]:
        pygame.draw.line(display,"white",(self.x, self.y + RES),(self.x + RES, self.y + RES),1)
      # L
      if self.walls[2]:
        pygame.draw.line(display,"white",(self.x, self.y),(self.x, self.y + RES),1)
      # U
      if self.walls[3]:
        pygame.draw.line(display,"white",(self.x, self.y),(self.x + RES, self.y),1)


  def getColor(self):
    if self.visited:
      self.color = "black"
    
    if visitor == self:
      self.color = "black"
                    
    if self.nullcolor:
      self.color = "black"
    
  
  
  
# DD. ROW
# row = [TILE, ..., n=DIMS[0]]
# interp. a collection of tiles that goes from left to right
row = []
for c in range(DIMS[0]):
  tile = Tile(c, 0)
  row.append(tile)

# TEMPLATE FOR ROW
# for tile in row:
#   ... tile


# DD. GRID
# grid = [ROW, ..., n=DIMS[1]]
# interp. a 2D array of TILE
grid = []
for r in range(image.shape[0]):
  row = []
  for c in range(image.shape[1]):
    tile = Tile(c, r)
    if image[r][c] == 0.0:
      tile.visited = True
      tile.nullcolor = True
    row.append(tile)
  grid.append(row)

# TEMPLATE FOR GRID
# for row in grid:
#   for tile in row:
#     ... tile

# DD. VISITOR
# visitor = grid[int][int]
# interp. the current tile that is being visited
visitor = grid[0][0]
visitor.visited = True

# DD. STACK
# stack = [TILE, ...]
# interp. a collection of tiles in the order in which we visit them
stack=[visitor]


# CODE

def draw():
  display.fill("#1e1e1e")
  for row in grid:
    for tile in row:
      tile.drawTile()

  for row in grid:
    for tile in row:
      tile.drawWalls()

  pygame.display.flip()

def getNeigh(visitor):
  r = visitor.r
  c = visitor.c
  candidates = []
  # R
  if c < DIMS[0]-1 and not grid[r][c+1].visited:
    neigh = grid[r][c+1]
    candidates.append(neigh)
  # D
  if r < DIMS[1]-1 and not grid[r+1][c].visited:
    neigh = grid[r+1][c]
    candidates.append(neigh)
  # L
  if c > 0 and not grid[r][c-1].visited:
    neigh = grid[r][c-1]
    candidates.append(neigh)
  # U
  if r > 0 and not grid[r-1][c].visited:
    neigh = grid[r-1][c]
    candidates.append(neigh)

  return candidates

def teardownWalls(vs, ch):
  # R
  if vs.c - ch.c < 0:
    vs.walls[0] = False 
    ch.walls[2] = False
  
  # D
  if vs.r - ch.r < 0:
    vs.walls[1] = False
    ch.walls[3] = False

  # L
  if vs.c - ch.c > 0:
    vs.walls[2] = False
    ch.walls[0] = False

  # U
  if vs.r - ch.r > 0:
    vs.walls[3] = False
    ch.walls[1] = False

  

def update():
  global visitor
  # get a list with the valid neighbors
  potentialNeighbor = getNeigh(visitor)
  # if the total number of neigh is > 0:
  if len(potentialNeighbor) > 0:
    #   pick one of the neighbors at random
    chosen = random.choice(potentialNeighbor)
    #   tear down the walls between the new chosen neigh and visitor
    teardownWalls(visitor, chosen)
    #   set visited from neigh to True
    chosen.visited = True
    stack.append(chosen)
    #   make visitor = chosen
    visitor = chosen
  else:
    # if the length of the stack is bigger than 0
    if len(stack) > 0:
      visitor = stack[-1]
      stack.pop(-1)
    else:
      pass
      
  for event in pygame.event.get():
    if event.type == pygame.QUIT:
      pygame.quit()
    if event.type == pygame.MOUSEBUTTONDOWN:
      if event.button == 1:
        for row in grid:
          for tile in row:
            if tile.rect.collidepoint(pygame.mouse.get_pos()):
              visitor = tile
              visitor.visited = True
              stack.append(visitor)



while True:
  draw()
  update()

The Algorithm

• Initialize GRID based on input image mask (black pixels become obstacles, white pixels become walkable areas)
• Set starting VISITOR at grid[0][0] and mark it as visited
• Add VISITOR to STACK for backtracking
• WHILE STACK is not empty:
• • Get all unvisited neighbors of current VISITOR (Right, Down, Left, Up)
  • IF valid neighbors exist:
    • Pick one neighbor at random from candidates
    • Tear down walls between VISITOR and chosen neighbor
    • Mark chosen neighbor as visited
    • Add chosen neighbor to STACK
    • Move VISITOR to chosen neighbor
  • ELSE (no unvisited neighbors):
    • Backtrack by removing last TILE from STACK
    • Set VISITOR to previous position in STACK
• Continue until all reachable tiles have been visited, creating a perfect maze with no loops