This project has been created as part of the 42 curriculum by jabuleje and mvasquez
A-Maze-ing is a maze generator and solver written in Python 3.10+. It reads a configuration file, generates a maze based on specific mathematical parameters, and displays it in the terminal utilizing ASCII rendering and ANSI escape codes.
The project also provides a reusable Python module (mazegen) that facilitates maze generation and solving for external applications.
Main features:
- Random maze generation utilizing an iterative Depth-First Search (DFS) algorithm.
- Support for generating perfect mazes (single solution) or imperfect mazes (multiple paths).
- Embedded "42" restricted pattern inside the maze bounds.
- Shortest path resolution utilizing Breadth-First Search (BFS).
- ASCII terminal visualization with customizable color palettes.
- Hexadecimal encoded file exportation.
- Python 3.10 or later
- pip
- virtualenv (recommended)
# Step 1: Create the virtual environment
make venv
# Step 2: Install dependencies
make install
# Step 3: Run the program
make runmake debug # Run in debug mode using pdb
make clean # Remove __pycache__ and .mypy_cache directories
make clean-venv # Remove the virtual environment
make lint # Execute flake8 and mypy checks
make lint-strict # Execute mypy with the --strict flag
make build-pkg # Compile the wheel packagespython3 a_maze_ing.py config.txtUpon execution, the program will present an interactive menu allowing the user to:
- Generate a new maze.
- Show or hide the solution path.
- Rotate the maze wall colors.
- Animate the maze generation.
- Exit the application.
The configuration file requires one KEY=VALUE per line. Lines starting with # are ignored.
Example(config.txt):
WIDTH=20
HEIGHT=15
ENTRY=0,0
EXIT=19,14
OUTPUT_FILE=maze.txt
PERFECT=True
SEED=42| Key | Description |
|---|---|
| WIDTH | Maze width |
| HEIGHT | Maze height |
| ENTRY | Entry point (x,y) |
| EXIT | Exit point (x,y) |
| OUTPUT_FILE | Output file name |
| PERFECT | True = one path only |
| SEED | Optional random seed |
The maze topology is generated utilizing a randomized, iterative Depth-First Search (DFS) algorithm:
- Initializes from the designated entry point.
- Randomly explores adjacent valid neighbors.
- Removes walls between connected cells via bitwise operations.
- Performs backtracking when a dead end is reached.
This approach inherently produces a spanning tree, representing a "perfect" maze where every cell is reachable via a single, unique path.
The shortest path from the entry to the exit is computed utilizing Breadth-First Search (BFS):
- Explores reachable nodes radially (level by level).
- Mathematically guarantees the discovery of the shortest possible path in an unweighted grid.
- Reconstructs the final route using a parent-tracking dictionary.
Output format:
The solution is represented as a sequence of cardinal directions: N, E, S, W.
Internally and during file exportation, each cell is encoded using a 4-bit hexadecimal value where each bit represents the presence of a wall.
| Bit | Direction |
|---|---|
| 0 | North |
| 1 | East |
| 2 | South |
| 3 | West |
Example:
- A (1010) -> East and West walls closed
- 3 (0011) -> Noth and East closed
- F (1111) -> All walls closed (unvisited cell).
The maze is dynamically rendered in the terminal output utilizing:
- ASCII walls (████, █)
- ANSI colors:
- Walls (customizable)
- Entry (E)
- Exit (X)
- Solution path (●)
- "42" pattern
This project is packaged to include a reusable module that can be imported into other Python applications.
Import Statement:
from mazegen.maze_generator import MazeGeneratorImplementation Example:
config = {
"WIDTH": 20,
"HEIGHT": 15,
"ENTRY": (0, 0),
"EXIT": (19, 14),
"PERFECT": "True",
"SEED": 42
}
maze = MazeGenerator(config)
maze.generate(animate=False)
maze.solve()
maze.print_maze(show_path=True)Available Methods:
generate(animate: bool): Computes the maze structure.solve(): Computes the shortest path using BFS and returns the direction string.print_maze(show_path: bool): Renders the ASCII representation to standard output.write_maze(filename: str): Exports the hexadecimal grid and solution to a specified file.
- Depth-First Search (DFS): Chosen for its efficiency in generating natural-looking, complex mazes with long corridors, while ensuring full connectivity without isolated sections.
- Breadth-First Search (BFS): Selected for the solver due to its absolute mathematical guarantee of finding the shortest path in an unweighted graph.
- Iterative Architecture: The DFS relies on a manual stack rather than recursion to prevent Python RecursionError exceptions when generating excessively large mazes.
Roles and Responsibilities:
-
jabuleje: Handled the retrieval and parsing of maze configurations, implemented the core DFS and BFS algorithms, and managed the maze.txt file generation protocol.
-
mvasquez: Managed user interactions and the terminal menu flow, implemented the imperfect maze generator (loops and multiple paths), and configured the project packaging structures (pyproject.toml).
As per curriculum requirements, a static pattern representing the number "42" is embedded in the center of the maze. These coordinates are strictly reserved, and the generation algorithm dynamically routes paths around them. If the specified maze dimensions are too small to accommodate this pattern safely, the program will halt execution and raise an error.
- Graph Theory Concepts: Depth-First Search and Breadth-First Search.
- Mathematics of Spanning Trees.
- Python Packaging Authority (PyPA) User Guide.
- ANSI Escape Codes Documentation.
Artificial Intelligence tools were utilized strictly as developmental aids for:
- Understanding standard Python packaging requirements and virtual environment deployments.
- Refining, proofreading, and structuring the markdown formatting of this documentation.