A-Maze-ing

This project has been created as part of the 42 curriculum by jsmidt, sbonevel.

A-Maze-ing

Description

A-Maze-ing is a maze generator and visualizer written in Python. It generates mazes from a configuration file, writes them to an output file using a hexadecimal wall encoding, and displays them either in the terminal via ASCII rendering or graphically via the MiniLibX (MLX) library.

The generator supports both perfect mazes (exactly one path between any two cells) and imperfect mazes with multiple paths. Every generated maze contains a hidden "42" pattern formed by fully closed cells, and includes a computed shortest path from entry to exit.

The maze generation logic is packaged as a standalone reusable Python library (mazegen) that can be installed via pip.

Instructions

Requirements

Python 3.10 or later
MiniLibX (42's MLX-2.2py3.whl, for graphical display)

Installation

make install

Running the program

python3 a_maze_ing.py config.txt

Or via the Makefile:

make run

Debug mode

make debug

Lint

make lint

Clean

make clean

Configuration File Format

The configuration file uses KEY=VALUE pairs, one per line. Lines starting with # are treated as comments and ignored.

Key	Description	Example
`WIDTH`	Maze width in cells	`WIDTH=20`
`HEIGHT`	Maze height in cells	`HEIGHT=15`
`ENTRY`	Entry coordinates (x,y)	`ENTRY=0,0`
`EXIT`	Exit coordinates (x,y)	`EXIT=19,14`
`OUTPUT_FILE`	Output filename	`OUTPUT_FILE=maze.txt`
`PERFECT`	Generate a perfect maze	`PERFECT=True`
`SEED`	Random seed for reproducibility	`SEED=42`
`BIAS`	Algorithm bias (0.0–1.0)	`BIAS=0.5`
`IMPRATE`	Imperfection rate (0–100)	`IMPRATE=65`
`PATTERN`	Pattern to embed in maze	`PATTERN=42`
`RENDER`	Display mode (`2D` or `MLX`)	`RENDER=2D`

A default config.txt is provided at the root of the repository.

Maze Generation Algorithms

Growing Tree (covers DFS and Prim's)

The growing_sigma_tree function implements the Growing Tree algorithm, controlled by a bias parameter:

bias = 1.0 → always picks the most recently added cell → behaves as Recursive Backtracker (DFS), producing long winding corridors
bias = 0.0 → always picks a random cell → behaves as Prim's algorithm, producing mazes with many short dead ends
0.0 < bias < 1.0 → hybrid behaviour between the two

This means a single function covers two classic algorithms depending on configuration.

Wilson's + Hunt-and-Kill

The wilson_sometimes_hunts function combines Wilson's algorithm (loop-erased random walks) with a Hunt-and-Kill fallback. The bias parameter controls how often each branch is used. An imprate (imperfection rate) parameter randomly removes extra walls to create imperfect mazes with multiple paths.

Generation Algorithms

Two generation strategies are available, selected via PERFECT in config.

`PERFECT: true` — Growing Tree (Sigma)

Carves a perfect maze (single solution, no loops) using an active cell list. Behavior is controlled by bias: 1.0 = recursive backtracker, 0.0 = Prim's.

Step 1: start        Step 2: carve        Step 3: done
┌─┬─┬─┬─┐           ┌─┬─┬─┬─┐           ┌─┬─┬─┬─┐
│ │ │ │ │           │ · · · │           │ ╶─╴ │ │
├─┼─┼─┼─┤     →     ├─┼─┼─┼─┤     →     ├─╴ ├─┤ │
│S│ │ │ │           │S· │ · │           │S│ ╶─╴ │
├─┼─┼─┼─┤           ├─┼─┼─┼─┤           ├─┴─╴ ├─┤
│ │ │ │ │           │ │ · · │           │ ╶───╴ │
└─┴─┴─┴─┘           └─┴─┴─┴─┘           └─┴─┴─┴─┘
 all walls            active (·)          finished
                      being carved        maze

`PERFECT: false` — Wilson's + Hunt-and-Kill (hybrid)

Each iteration, a random roll against bias selects the algorithm for that step. Both can inject imperfections via imprate, punching extra passages to create loops.

random() < bias  →  Wilson's (loop-erasing random walk)
random() >= bias →  Hunt-and-Kill (scan for unvisited cell adj. to maze)
                         ↓ (both)
                 _maybe_add_imperfection()

Wilson's — random walk with loop erasure, carves when walk hits visited cell:

 start walk      loop detected     loop erased      path carved
 ┌─┬─┬─┐         ┌─┬─┬─┐         ┌─┬─┬─┐         ┌─┬─┬─┐
 │ →→↓ │         │ →→↓ │         │    │ │         │ ╶─╴ │
 ├─┼─┼─┤    →    ├─┼─┼─┤    →    ├─┼─┼─┤    →    ├─┼─┼─┤
 │ │ ↓ │         │ ↑←← │         │    │ │         │   ╶─┤
 ├─┼─┼─┤         ├─┼─┼─┤         ├─┼─┼─┤         ├─┼─┼─┤
 │ │■│ │         │ │■│ │         │ │■│ │         │ │■│ │
 └─┴─┴─┘         └─┴─┴─┘         └─┴─┴─┘         └─┴─┴─┘
                  ■ = visited      walk reset       ■ = visited

Hunt-and-Kill — scans for unvisited cell adjacent to existing maze:

 ┌─┬─┬─┬─┐
 │■│■│ │ │   scan order: → → → ↓
 ├─┼─┼─┼─┤                       found: (2,1) has visited neighbor
 │■│ →?│ │   ──────────────────► connect & mark visited
 ├─┼─┼─┼─┤
 │ │ │ │ │
 └─┴─┴─┴─┘
  ■ = visited maze so far

Imperfection injection — after each carve, rolls against imprate:

  before          after (imprate hit)
 ┌─┬─┬─┐         ┌─┬─┬─┐
 │■│■│ │         │■ ■│ │   ← extra wall removed,
 ├─┼─┼─┤    →    ├─┼─┼─┤     loop created
 │■│ │ │         │■│ │ │
 └─┴─┴─┘         └─┴─┴─┘

Config reference

Parameter	Effect
`PERFECT`	`true` = Growing Tree only. `false` = hybrid + imperfections
`BIAS`	`0.0–1.0`. Controls cell selection (Growing Tree) or algorithm split (hybrid)
`IMPRATE`	`0–100`. % chance of punching an extra wall per carve step
`SEED`	Optional int for reproducible output

Why these algorithms?

Wilson's algorithm guarantees a uniform spanning tree, meaning every possible perfect maze is equally likely to be generated. The Growing Tree algorithm was chosen for its flexibility — one implementation covers the full spectrum from DFS to Prim's by adjusting a single parameter. The Hunt-and-Kill fallback ensures progress when Wilson's random walks get stuck in sparse unvisited regions.

Visual Representation

Two display modes are available:

Terminal ASCII — renders the maze directly in the terminal using box-drawing characters. Entry, exit, and the solution path are clearly marked.

MiniLibX (MLX) — graphical window rendering. Set RENDER=MLX in your config file to use this mode.

User interactions

Key / Action	Effect
`R`	Re-generate a new maze
`P`	Show / hide the shortest path
`C`	Cycle wall colours
`ESC` or close window	Exit

Reusable Module

The maze generation logic is packaged as a standalone pip-installable library.

Installation

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

Basic usage

from maze import MazeGenerator

config = {
    'WIDTH': 20,
    'HEIGHT': 15,
    'ENTRY': (0, 0),
    'EXIT': (19, 14),
    'PERFECT': True,
    'SEED': 42,
    'BIAS': 0.7,
}

mg = MazeGenerator(config)
grid = mg.generate()

Accessing the maze structure

mg.generate() returns a 2D list of Cell objects (grid[y][x]).

Each Cell exposes:

cell.x, cell.y          # coordinates
cell.walls              # dict: {'N': bool, 'E': bool, 'S': bool, 'W': bool}
cell.is_start           # True if this is the entry cell
cell.is_goal            # True if this is the exit cell
cell.in_path            # True if this cell is part of the shortest path

Custom parameters

Parameter	Type	Default	Description
`WIDTH`	int	required	Maze width
`HEIGHT`	int	required	Maze height
`ENTRY`	tuple	required	Entry `(x, y)`
`EXIT`	tuple	required	Exit `(x, y)`
`PERFECT`	bool	required	Perfect maze or not
`SEED`	int/None	`None`	Random seed
`BIAS`	float	`0.5`	Growing Tree bias
`IMPRATE`	int	`65`	Imperfection rate (imperfect mazes only)

Building the package from source

python -m venv build_env
source build_env/bin/activate
pip install build
python -m build

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

Team & Project Management

Roles

jsmidt — configuration file parsing, MLX graphical output, Makefile, general file system structure, lint compliance.

sbonevel — all maze generation algorithms (Growing Tree / DFS / Prim's, Wilson's + Hunt-and-Kill), terminal ASCII output, maze solver.

Planning

We started by agreeing on the Cell data structure and the config format so both of us could work in parallel from day one. The initial plan was to finish generation first, then display, then packaging — this held up reasonably well. The main deviation was that the circular import between generator.py and pattern.py cost us time mid-project, which we resolved by moving Cell into its own cell.py module.

What worked well

Splitting generation, parsing and display cleanly between team members meant we rarely blocked each other. Using a bias parameter to cover both DFS and Prim's in one function kept the codebase lean.

What could be improved

We underestimated the time needed for flake8/mypy compliance, especially with type hints across the whole codebase. Starting lint early would have saved time at the end. Same goes for choosing algorithm. It took us a long time to figure out that we also had to generate imperfect mazes. At first we were only generating perfect mazes. It would've saved us time to research this beforehand.

Tools used

Python 3.13
MiniLibX for graphical rendering
build for packaging
mypy and flake8 for static analysis and style
Git for version control

Resources

AI usage

AI (Claude & ChatGPT) werte used for the following tasks:

Explaining the differences between maze generation algorithms and helping choose between them
Debugging the circular import issue between generator.py and pattern.py
Guiding the Python packaging process (pyproject.toml setup, python -m build, .whl structure)
Reviewing type hint syntax for mypy compliance
Drafting this README & Docstrings for functions

All AI-generated content was reviewed, tested, and validated by both team members before inclusion in the project.

Name		Name	Last commit message	Last commit date
Latest commit History 40 Commits
assets		assets
src		src
.gitignore		.gitignore
Makefile		Makefile
README.md		README.md
a_maze_ing.py		a_maze_ing.py
config.txt		config.txt
mlx-2.2-py3-none-any.whl		mlx-2.2-py3-none-any.whl
pyproject.toml		pyproject.toml
requirements.txt		requirements.txt

Folders and files

Latest commit

History

Repository files navigation

A-Maze-ing

Description

Instructions

Requirements

Installation

Running the program

Debug mode

Lint

Clean

Configuration File Format

Maze Generation Algorithms

Growing Tree (covers DFS and Prim's)

Wilson's + Hunt-and-Kill

Generation Algorithms

PERFECT: true — Growing Tree (Sigma)

PERFECT: false — Wilson's + Hunt-and-Kill (hybrid)

Config reference

Why these algorithms?

Visual Representation

User interactions

Reusable Module

Installation

Basic usage

Accessing the maze structure

Custom parameters

Building the package from source

Team & Project Management

Roles

Planning

What worked well

What could be improved

Tools used

Resources

AI usage

About

Resources

Uh oh!

Stars

Watchers

Forks

Releases

Packages 0

Uh oh!

Contributors

Uh oh!

Languages

`PERFECT: true` — Growing Tree (Sigma)

`PERFECT: false` — Wilson's + Hunt-and-Kill (hybrid)

Packages