This project has been created as part of the 42 curriculum by alalimov, brogaar.

A-Maze-ing

Description

A-Maze-ing is a maze generator and visualizer. It reads a configuration file, generates a maze, writes it to disk in a hex wall encoding (with the BFS-shortest path appended), and renders it graphically via the MiniLibX (MLX) library.

The generator supports both perfect mazes (exactly one path between any two cells) and imperfect mazes (extra openings, with a hard cap on corridor width). Every maze contains a hidden "42" pattern formed by fully-walled cells, with a small-maze guard that prints a warning when the pattern would not fit.

The maze generation logic ships as a standalone, pip-installable Python library (mazegen) backed by a compiled CFFI extension. The application (a_maze_ing.py) is a thin Python wrapper that drives libamazing.so for both generation and MLX rendering.

---

Instructions

Requirements

• Python 3.10 or later
• gcc / make
• X11 development headers (libxcb, libX11, libXext) for MLX

Installation

make install

This provisions a local .venv, installs cffi, mypy, flake8, build, and pytest, builds libamazing.so, builds the mazegen wheel, and copies the wheel + sdist to the repo root.

Running the program

python3 a_maze_ing.py config.txt

Or via the Makefile:

make run

Debug mode

make debug

Linting

make lint           # flake8 + mypy (project-relaxed flags)
make lint-strict    # flake8 + mypy --strict

Clean

make clean

---

Configuration File Format

The configuration file uses KEY=VALUE pairs, one per line. Lines starting with # are comments; trailing # comments are also stripped. Whitespace around keys and values is trimmed.

Key	Required	Description	Example
WIDTH	yes	Maze width in cells	WIDTH=30
HEIGHT	yes	Maze height in cells	HEIGHT=30
ENTRY	yes	Entry coordinates (x,y)	ENTRY=1,28
EXIT	yes	Exit coordinates (x,y)	EXIT=26,29
OUTPUT_FILE	yes	Output filename	OUTPUT_FILE=maze.txt
PERFECT	yes	Single-path maze (True) or imperfect (False)	PERFECT=True
SEED	no	RNG seed for reproducibility (32-bit unsigned)	SEED=42
IMPRATE	no	Imperfection rate, 0-100 (default 50)	IMPRATE=70

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

The output file is hex-encoded, one digit per cell, where each bit represents a closed wall: bit 0 = N, 1 = E, 2 = S, 3 = W (closed = 1). Cells are written row by row, one row per line. After a blank line, the file appends three lines: entry coordinates, exit coordinates, and the BFS shortest path as a sequence of N/E/S/W letters.

---

Maze Generation Algorithm

The generator carves a spanning tree using a depth-first walk with random history rewind:

1. Mark the entry cell as visited; push it onto an "active history" list.
2. From the current cell, pick a random direction. If the neighbour exists, is unvisited, and is not blocked by the "42" pattern, carve the wall between them, mark visited, set the new cell as the parent of the neighbour in the generation tree, and continue from there.
3. If the random direction does not yield a new cell, rewind to a uniformly random cell in the active history. From that cell, retry. If a cell has no remaining options, drop it from the history.
4. Stop when every non-pattern cell is visited.

When PERFECT=False, a second pass (imperfect_punch) walks the grid and probabilistically opens additional walls (per IMPRATE). Each candidate punch is rolled back if it would create a 3x3 fully-open square (the corridor-width cap from the project subject).

Why this algorithm?

The random-rewind variant is between pure DFS (long winding corridors) and Prim-like uniform expansion (lots of short dead ends). It produces well-balanced mazes without needing two separate code paths, and it carves around the pre-walled "42" pattern naturally — patterned cells are simply skipped during the carve.

The "shortest path" emitted to the output file is computed by a BFS over the carved graph (parent pointers reset and rebuilt during the BFS), so the path is correct in both perfect and imperfect modes.

---

Visual Representation

A graphical window is rendered via MiniLibX (MLX). Walls are drawn in the primary colour, the "42" pattern in the secondary colour, the entry cell in red, and the exit cell in green. The shortest path overlay is white when toggled on.

User interactions

Key	Effect
1	Re-generate a new maze
2	Show / hide the shortest path
3	Cycle wall colours
4	Quit

The on-screen panel under the maze shows the same legend.

---

Reusable Module

The maze generation logic is packaged as a standalone, pip-installable library (mazegen). It exposes a Python MazeGenerator class that wraps a compiled CFFI extension (mazegen._mazegen_c).

Installation

After running make install, the wheel and source distribution are placed at the repo root. Install into any environment with:

pip install ./mazegen-1.0.0-*.whl

Basic usage

from mazegen import MazeGenerator

mg = MazeGenerator({
    "WIDTH": 20,
    "HEIGHT": 15,
    "ENTRY": (0, 0),
    "EXIT": (19, 14),
    "PERFECT": True,
    "SEED": 42,
})
mg.generate()
mg.solve()
mg.write("maze.txt")              # or pass OUTPUT_FILE in config
print(mg.cells[0][0].walls)       # {'N': True, 'E': False, 'S': False, 'W': True}

Accessing the maze structure

mg.cells is a 2D list cells[y][x] of Cell objects. Each Cell exposes:

cell.x, cell.y          # 0-indexed coordinates
cell.walls              # dict: {'N': bool, 'E': bool, 'S': bool, 'W': bool} (True = closed)
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 on the shortest path (after solve())

mg.solve() returns the path as a list of (x, y) tuples from entry to exit.

Custom parameters

Parameter	Type	Default	Description
WIDTH, HEIGHT	int	required	Maze dimensions
ENTRY, EXIT	tuple/str	required	(x, y) or "x,y"
PERFECT	bool	required	Perfect maze if True
OUTPUT_FILE	str	None	Default for mg.write()
SEED	int	time-derived	32-bit RNG seed
IMPRATE	int	50	Imperfection rate, 0-100

Building the package from source

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

This produces mazegen/dist/mazegen-1.0.0-*.whl and mazegen/dist/mazegen-1.0.0.tar.gz.

---

Team & Project Management

Roles

alalimov — configuration file parsing, README.md file, python gluing, lint compliance.

brogaar — all maze generation algorithms (DFS with random rewind), maze solver, MLX graphical output, Makefile, general file system structure.

Planning

First, we have implemented the project in C and later on glued it to Python.

What worked well

Splitting generation, parsing and display cleanly between team members meant we rarely blocked each other. Keeping a single carve algorithm with a configurable post-pass for imperfect mazes 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
• cffi for the C/Python bridge
• build for packaging the mazegen wheel
• mypy and flake8 for static analysis and style
• Git for version control

---

Resources

• Maze generation algorithms — Wikipedia
• Buckblog: Maze algorithms by Jamis Buck
• MiniLibX documentation
• mypy documentation

AI usage

No AI and vibecoding were used in the project. Everything is human-coded.