A-Maze-ing

ProjectM2

Pair project in Python: a seeded maze generator from a config file with hex output, a 42 pattern, shortest path and a pip package.

Requires

Exam Rank 02

Unlocks

Exam Rank 03

Guide

A-Maze-ing is the first Python project of milestone M2, done in pairs. You write a maze generator driven by a configuration file: it builds a maze of the requested size, carves the "42" pattern in its centre, writes the result to a file in a compact hexadecimal format with the shortest path from entry to exit, and shows it visually. The generator itself must be packaged as a reusable module (mazegen) shipped as a wheel, because a later project, Pac-Man, uses another team's package. Details below come from student repositories (Reported by students); check them against your subject.

What you will learn

Maze generation as graph theory: spanning trees, depth-first backtracking, Prim's and Kruskal's algorithms
Breadth-first search for the shortest path on a grid
Representing walls as bit masks and serialising them to hexadecimal
Parsing and validating a KEY=VALUE configuration file with clear errors
Reproducibility with random seeds
Packaging a Python library with pyproject.toml and python -m build
Working in a pair with git branches and reviews

Before you start

Previous nodes: Python Modules (at least 00 to 06; packaging from module 08 helps a lot). push_swap trained the algorithmic thinking.
Tools: Python 3.10+, flake8, mypy, build, a virtual environment, and either MiniLibX bindings or a terminal UI for the display (both are reported).
Agree with your partner on the split before coding: one owns generation and the package, the other parsing, output and display.

Plan of attack

Day 1: write the config parser. Mandatory keys reported by students: WIDTH, HEIGHT, ENTRY, EXIT, OUTPUT_FILE, PERFECT, with SEED optional and # comments allowed. Reject missing keys, bad coordinates and entry or exit outside the grid with a clear message and a non-zero exit code.
Day 1: define the cell model: four walls per cell as a 4-bit mask (north, east, south, west), a set bit meaning a closed wall.
Day 2: implement a perfect maze with an iterative depth-first backtracker seeded from SEED. Same seed, same maze.
Day 2: reserve the cells of the "42" pattern before carving so they stay fully closed. If the maze is too small, skip the pattern with a warning on stderr.
Day 3: imperfect mode (PERFECT=False): remove extra walls to add loops, without opening large empty areas.
Day 3: shortest path with BFS, written as a string of N, E, S, W.
Day 4: output file (one hex digit per cell, then entry, exit and path) and the visual display with regenerate, show or hide path, and colour change.
Day 5: package mazegen with a small public class, build the wheel, install it in a fresh venv and import it from outside the repository.
Day 5: Makefile with install, run, debug, clean, lint and lint-strict; README with usage, algorithm choice and the AI usage section.

An example of the kind of interface to aim for (names are yours to choose):

from mazegen import MazeGenerator

maze = MazeGenerator(width=20, height=15, seed=42, perfect=True)
maze.generate()
print(maze.solve())

Common pitfalls

Recursive DFS hitting Python's recursion limit on large mazes: use an explicit stack.
Walls that disagree between neighbours (east of one cell open, west of the next closed).
Entry or exit landing inside the "42" pattern.
A wheel that only works because your repository is on PYTHONPATH. Test it in a clean environment.
Confusing your package with the unrelated mazegen on PyPI.
flake8 or mypy strict errors in the display code, which teams often leave for last.

How it is evaluated

Peer evaluation of the pair; both students must be able to explain all the code.
The evaluator runs make lint, then several configs: valid, invalid, tiny, large, seeded twice.
The output file is checked for format and consistency, and the path for correctness.
The wheel is installed and imported as a library.
Extra algorithms or animation are reported as bonus.

Resources