This project has been created as part of the 42 curriculum by gomar, smoustaj.

A-Maze-ing 🧩

A Python maze generator and solver with animated visualization.

Description

This project generates random mazes and finds the shortest path from entry to exit. It features:

• Maze Generation: Creates perfect mazes using Recursive Backtracker or Prim's algorithm
• Pathfinding: BFS algorithm finds the shortest solution path
• Visualization: Colorful terminal rendering with Unicode box-drawing characters
• Animation: Watch the maze being generated step by step
• 42 Easter Egg: A hidden "42" pattern embedded in larger mazes

┏━━━┳━━━┳━━━┳━━━┓
┃ E     ┃   ┃   ┃     E = Entry
┣━━━╋   ╋   ╋   ┫     X = Exit
┃       ┃       ┃     . = Solution path
┣   ╋━━━╋━━━╋   ┫
┃   ┃         X ┃
┗━━━┻━━━┻━━━┻━━━┛

Instructions

Requirements

• Python 3.8+
• flake8 and mypy (for linting)

Installation

make install

Running the Maze Generator

make run

Or directly:

python3 a_maze_ing.py config.txt

Debug Mode

make debug

Linting

make lint          # Standard checks
make lint-strict   # Strict mode

Clean Up

make clean

Config File Format

The configuration file uses a simple KEY=VALUE format:

Key	Description	Example
WIDTH	Maze width (columns)	20
HEIGHT	Maze height (rows)	15
ENTRY	Entry coordinates (x,y)	0,0
EXIT	Exit coordinates (x,y)	19,14
OUTPUT_FILE	Output filename	maze_output.txt
PERFECT	Perfect maze (single path)	True
SEED	Random seed (optional)	42
ALGORITHM	Generation algorithm	recursive_backtracker or prims

Example config.txt:

# Maze Configuration
WIDTH=20
HEIGHT=15
ENTRY=0,0
EXIT=19,14
OUTPUT_FILE=maze_output.txt
PERFECT=True
SEED=42
ALGORITHM=recursive_backtracker

Maze Generation Algorithm

Chosen Algorithm: Recursive Backtracker (DFS)

We use the Recursive Backtracker algorithm as the default.

How it works:

1. Start at entry cell, mark as visited
2. While stack is not empty:
   a. Look at current cell
   b. If unvisited neighbors exist:
      - Pick random neighbor
      - Remove wall between them
      - Move to neighbor, push to stack
   c. Else:
      - Backtrack (pop from stack)

Why this algorithm?

Advantage	Description
Long passages	Creates winding corridors, making mazes feel more challenging
Perfect mazes	Guarantees exactly one path between any two cells
Simple implementation	Uses basic stack/recursion, easy to debug
Good for animation	Step-by-step generation looks visually appealing

Alternative: Prim's Algorithm

Also available via ALGORITHM=prims. Creates mazes with shorter dead-ends and a more "bushy" appearance.

Project Structure

a_maze_ing/
├── a_maze_ing.py       # Main entry point
├── config.txt          # Configuration file
├── Makefile            # Build commands
├── pyproject.toml      # Package build config
├── README.md           # This file
├── mazegen/            # Reusable package
│   ├── __init__.py
│   ├── generator.py
│   └── README.md
└── src/
    ├── config_parser.py   # Config file parsing
    ├── maze_generator.py  # Maze generation algorithms
    ├── pathfinder.py      # BFS pathfinding
    ├── renderer.py        # Terminal visualization
    └── animator.py        # Animation controller

Reusable Maze Generator Module (mazegen)

The mazegen package is a standalone, pip-installable module.

Building the Package

make build

This creates dist/mazegen-1.0.0-py3-none-any.whl and dist/mazegen-1.0.0.tar.gz.

Installing the Package

pip install dist/mazegen-1.0.0-py3-none-any.whl

Quick Start

from mazegen import MazeGenerator

# Create and generate a maze
maze = MazeGenerator(width=20, height=15)
maze.generate()

# Solve the maze
solution = maze.solve()
print(f"Path: {solution.directions}")  # e.g., "SSEENNWW"
print(f"Length: {solution.length} steps")

Custom Parameters

maze = MazeGenerator(
    width=30,                        # Maze width (columns)
    height=20,                       # Maze height (rows)
    entry=(0, 0),                    # Entry point (x, y)
    exit=(29, 19),                   # Exit point (x, y)
    seed=42,                         # Random seed for reproducibility
    algorithm="recursive_backtracker"  # or "prims"
)
maze.generate()

Accessing the Maze Structure

# Get all cells as 2D list
cells = maze.get_cells()

# Get specific cell
cell = maze.get_cell(5, 3)
print(f"Cell walls: {cell.walls}")

# Check walls using Wall flags
from mazegen import Wall
if cell.walls & Wall.NORTH:
    print("Has north wall")

# Export as hex string
hex_output = maze.to_hex_string()

Getting a Solution

solution = maze.solve()

if solution.found:
    print(solution.directions)  # "SSEEENWW"
    print(solution.path)        # [(0,0), (0,1), (1,1), ...]
    print(solution.length)      # Number of steps

Team & Project Management

Team Members

Role	Member	Responsibilities
Developer	gomar	Maze generation, main script, reusable package, documentation
Developer	smoustaj	Renderer, animator, config parser, pathfinder

Planning Evolution

The project was developed in phases: config parsing first, then maze generation, pathfinding, and finally rendering with animation. The initial plan was followed closely, with minor adjustments as features were implemented.

What Worked Well

• Modular design made testing individual components easy
• Using dataclasses for clean data structures
• BFS for guaranteed shortest path

What Could Be Improved

• Add GUI visualization option
• Support for non-rectangular mazes
• More generation algorithms (Kruskal, Eller)

Tools Used

Tool	Purpose
Python 3	Main language
VS Code	Development
flake8	Code style
mypy	Type checking
Git	Version control

Resources

• Maze Generation Algorithms - Wikipedia overview
• Recursive Backtracker - Jamis Buck's tutorial
• BFS Pathfinding - Red Blob Games