This activity has been created as part of the 42 curriculum by nsadoune, hdavid.

A-Maze-ing 🌀

📝 Description

A-Maze-ing is a Python maze generator that reads a configuration file, generates a maze (perfect or imperfect), and writes it to an output file using a hexadecimal wall representation. The program also provides a visual representation of the maze with interactive controls.

A perfect maze has exactly one path between any two cells (no loops, no isolated areas). An imperfect maze introduces a small number of extra openings (~5% of cells) to create loops and alternative paths.

The maze also embeds a visible "42" pattern made of fully closed cells as a visual signature.

---

Instructions

Requirements

• Python 3.10 or later
• Dependencies listed in requirements.txt

Installation

make install

Run

make run

Debug

make debug

Lint

make lint

Clean

make clean

---

Usage

python3 a_maze_ing.py config.txt

config.txt is the only argument. It defines all maze generation options (see Configuration below).

---

Configuration File Format

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

Mandatory keys

Key	Description	Example
WIDTH	Maze width (number of column)	WIDTH=20
HEIGHT	Maze height (number of line)	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

Example config.txt

# A-Maze-ing configuration
WIDTH=20
HEIGHT=15
ENTRY=0,0
EXIT=19,14
OUTPUT_FILE=maze.txt
PERFECT=True

---

🧠 Maze Generation Algorithm

🧩 Algorithm used: Randomized Kruskal's / Union-Find

The perfect maze is generated using a zone-merging (Union-Find) approach:

• Each cell starts in its own unique zone.
• At each step, a random cell and a random direction are picked.
• If the neighboring cell belongs to a different zone, the wall between them is removed and both zones are merged into one.
• This repeats until all non-locked cells belong to a single zone, guaranteeing a spanning tree — i.e., exactly one path between any two cells.

Why this algorithm?

• It naturally guarantees a perfect maze (no loops, full connectivity) by construction — once all cells share the same zone, the maze is complete.
• It is straightforward to extend to imperfect mazes: after generating the perfect maze, a second pass (create_imperfect_maze) randomly breaks ~5% of remaining walls to introduce loops.
• It is easy to implement with reproducible randomness via a seed.
• Wall coherence (symmetric walls between neighbors) is enforced by always updating both sides of a wall simultaneously.

---

🔀 Path resolution algorithm

Solving uses a three-step approach:

1. Graph construction (create_dict) — builds an adjacency dict from the maze grid. For each cell, it checks all 4 directions; if a wall is open (orientation[d] is False), the neighbor's position is added as a reachable node.

2. BFS (bfs) — runs a standard breadth-first search from the entry, assigning a distance level to each visited node. Returns a dict of {position: level} in reverse order (from exit back toward entry).

3. Path reconstruction (resolver) — starting from the exit, greedily follows neighbors whose BFS level is exactly current_level - 1, walking back to the entry. The result is reversed to give the final path from entry to exit.

This approach correctly finds the shortest path for both perfect and imperfect mazes.

Output File Format

One hexadecimal digit per cell encodes which walls are closed (bit = 1) or open (bit = 0):

Bit	Direction
0 (LSB)	North
1	East
2	South
3	West

Cells are written row by row, one row per line. After an empty line, the file contains:

• Entry coordinates
• Exit coordinates
• Shortest path from entry to exit (using N, E, S, W)

---

Visual Representation

The program supports the following display modes:

• Terminal ASCII rendering — colored block-based display in the terminal using curses or ANSI colors.

Interactive controls

• Using simple_term_menu for interactive menu

The "42" pattern is rendered as a group of fully closed (walled) cells visible in the maze.

---

Reusable Module (mazegen)

The maze generation logic is packaged as a standalone, importable Python module.

Installation

Copy the directory dist in your new project to have access to the exposed tools in mazegen package that can be seen in the __init__.py.

Basic usage

from mazegen import *

interface()

Custom parameters

You can change parameter of the config.txt from the program that reinitialise automaticaly gracefully this line:

os.execl(sys.executable, sys.executable, *sys.argv)

Understand the structure

• maze.grid → 2D list of Cell objects
• Each Cell has an orientation dict: {"N": bool, "S": bool, "E": bool, "W": bool} where True means wall is present
• metadata is a dictionnary that contain all the main informations that is needed to solve and display the maze:

metadata = {
    "maze"= conatain the grid of the maze
    "entry"= start of the maze
    "exit"= end of the maze
    "path"= shortest way to solve the maze
    "output_file" = name of the output file
    "logo" = information if the logo need to be displayed
}

Note: the internal structure uses Cell objects and boolean wall flags — this is not the same format as the hexadecimal output file.

---

📚 Resources

References

• Maze generation algorithms - johan.sgura.fr
• Breadth-First Search - datacamp.com
• Git usage
• Library python

AI usage

AI (Claude) was used for the following tasks during this project:

• Drafting this README

---

Team & Project Management

Team members

Login	Role
nsadoune	Maze generation logic, path solving, Makefile
hdavid	Visual rendering, reusable module,

Planning

Initial plan:

1. generate the perfect maze
2. display
3. perfect maze solver
4. generate imperfect maze
5. imperfect maze solver

How it evolved:

• We both started by implementing the maze generation separately: nsadoune with Kruskal's algorithm, hdavid with a recursive backtracker. After a while, the recursive approach hit Python's recursion limit on larger mazes, so we switched to Kruskal's.
• For path solving, we initially used backtracking recursion on the perfect maze, but hit the same recursion depth issue with imperfect mazes. nsadoune then implemented BFS, which we kept for both perfect and imperfect mazes.

What worked well

• The Union-Find approach made it easy to guarantee maze validity by construction.
• Splitting generation logic into a separate module from the start made packaging straightforward.

What could be improved

• add music
• 3D
• display path without animation
• add possibility to the menue (choosing algorithm)

Tools used

• VS Code — main editor
• mypy + flake8 — static analysis and linting