🧩 a-maze-ing

This project has been created as part of the 42 curriculum by catencio and jbarreir.

🧩 a-maze-ing

Description

a-maze-ing is a procedural maze generation and visualization application that combines graph theory algorithms with a graphical interface to create and display organic-looking mazes in real-time. The project uses Python for the core logic, including the Prim's algorithm implementation for maze generation, and integrates with the MiniLibX graphics library for interactive 2D visualization.

The primary goal is to generate perfect mazes (mazes with exactly one path between any two points) using a depth-first, randomized approach, then visualize them with a responsive GUI that supports multiple visual themes and customizable maze parameters.

Instructions

Prerequisites

Python 3.8+
Linux environment (X11 support required)
Git (for cloning the repository)

Installation

Clone the repository:

git clone <repository-url>
cd a-maze-ing

Install dependencies using the Makefile:
```
make install
```
This command will:
- Create a Python virtual environment (venv/)
- Upgrade pip
- Install all project dependencies from requirements.txt, including the MiniLibX library (provided as mlx-2.2-py3-none-any.whl)

Execution

Basic usage with default configuration:

make run

Custom configuration: Edit config.txt before running. The GUI will launch and display the generated maze with your specified configuration.

Running tests with pytest:

make debug

This executes the test suite using pytest with verbose output.

Code quality checks:

make lint          # Standard linting (flake8 + mypy)
make lint-strict   # Strict linting with enhanced type checking

Clean temporary files:

make clean         # Remove __pycache__, .mypy_cache, build artifacts, etc.

Available Make commands:

Command	Purpose
`make install`	Set up virtual environment and install dependencies
`make run`	Execute the maze application with default config
`make debug`	Run tests with pytest
`make lint`	Run code quality checks (flake8 + mypy)
`make lint-strict`	Run strict type checking and linting
`make build`	Build distribution package
`make clean`	Remove temporary files and caches

Configuration File Format

The config.txt file controls all maze generation and display parameters. The format is key-value pairs, one per line:

Parameter	Type	Description	Example
`WIDTH`	Integer	Maze width in cells	`WIDTH=30`
`HEIGHT`	Integer	Maze height in cells	`HEIGHT=30`
`ENTRY`	Coordinates	Entry point (x,y)	`ENTRY=1,0`
`EXIT`	Coordinates	Exit point (x,y)	`EXIT=14,14`
`OUTPUT_FILE`	String	File to save maze data	`OUTPUT_FILE=output_file.txt`
`PERFECT`	Boolean	Generate perfect maze (no loops)	`PERFECT=False`
`SEED`	String/Integer	Random seed for reproducibility	`SEED=Javi`

Example configuration:

WIDTH=30
HEIGHT=30
ENTRY=1,0
EXIT=14,14
OUTPUT_FILE=output_file.txt
PERFECT=False
SEED=Javi

Maze Generation Algorithm

Algorithm: Prim's Algorithm (Randomized)

a-maze-ing uses a randomized variant of Prim's algorithm to generate mazes. This is a probabilistic approach that builds the maze by randomly selecting walls to carve passages through, creating organic-looking mazes with characteristic properties.

Why Prim's Algorithm?

We chose Prim's algorithm for several key reasons:

Organic Structure: Generates mazes with more natural, winding paths that create visually appealing results with numerous short, narrow corridors
Graph Theory Foundation: Provides an excellent educational opportunity to understand minimum spanning trees and graph connectivity theory
Balanced Characteristics: Produces mazes with uniform distribution of solution paths and multiple dead-ends, creating challenging navigation
Visual Appeal: The algorithm's nature results in compact clusters of passages rather than long straight corridors, leading to more interesting visual patterns

Algorithm Characteristics

Time Complexity: O(V²) where V is the number of cells
Space Complexity: O(V) for the visited set and frontier
Guaranteed Properties: Produces a perfect maze (exactly one path between any two points)
Randomness: Uses Python's random module for non-deterministic generation (controlled via SEED parameter)

Understanding Perfect Mazes

A perfect maze has these properties:

Exactly one path exists between any two cells
No cycles (loops) are created
All cells are accessible from any starting point

Wall Representation with Bit Flags

The implementation uses bitwise operations for memory-efficient wall tracking. Each cell stores its wall state using 4 bits:

NORTH = 1  (binary: 0001) - wall on north side
EAST  = 2  (binary: 0010) - wall on east side
SOUTH = 4  (binary: 0100) - wall on south side
WEST  = 8  (binary: 1000) - wall on west side

A cell with value 15 (1111 binary) = CLOSED (all walls present)
A cell with value 0 (0000 binary) = OPEN (all walls removed)
Mixed values represent partial wall configurations

Removing a wall is accomplished via bitwise subtraction: grid[y][x] -= NORTH

Detailed Algorithm Steps

Step 1: Initialization

1. Create grid of size (col × row) with all cells CLOSED (value = 15)
2. Create reserved pattern (the "42" emblem in maze center)
3. Initialize in_maze set with the entry point
4. Add all neighbors of entry point to the frontier
5. Create a random number generator (seeded for reproducibility)

Step 2: Main Loop - Maze Construction

The algorithm continues while the frontier list is not empty:

2.1 Select random cell from frontier:

curr_x, curr_y = frontier.pop(random_index)

Random selection ensures non-deterministic maze variations.

2.2 Check if already in maze:

if (curr_x, curr_y) in in_maze:
    continue  # Skip, move to next frontier cell

Prevents processing the same cell twice.

2.3 Find connected neighbors in maze:

neighbors_in = _get_neighbors((curr_x, curr_y), in_maze, is_in=True)

Identifies adjacent cells that are already part of the generated maze.

2.4 Break walls between cells:

if valid_neighbors:
    nx, ny = random.choice(valid_neighbors)
    _break_walls(curr_x, curr_y, nx, ny)

Removes the wall between the current cell and a randomly chosen neighbor already in the maze. This creates the connection.

Breaking walls logic:

If y1 > y2 (current cell is south): remove NORTH from current, SOUTH from neighbor
If x1 > x2 (current cell is east): remove WEST from current, EAST from neighbor
Same principle applies for other directions

2.5 Add to maze:

in_maze.add((curr_x, curr_y))

2.6 Expand frontier:

new_neighbors = _get_neighbors((curr_x, curr_y), in_maze, is_in=False)
for nn in new_neighbors:
    if nn not in frontier:
        frontier.append(nn)

Adds all neighbors of the newly-added cell to the frontier for future processing.

Step 3: Finalization

1. Seal walls around reserved pattern (the "42" emblem)
2. If imperfect maze requested: randomly remove additional walls to create loops
3. Return completed grid

Visualization Example

The algorithm expands the maze outward from the entry point, gradually connecting cells:

Phase 1 - Initialization:

All cells start with all walls closed
Entry point marked as part of the maze
Frontier contains only the neighbors of the entry

Phase 2 - Growth:

Randomly select a cell from frontier
Connect it to an already-connected cell by removing the wall between them
Add its neighbors to frontier
Process repeats until all cells are connected

Phase 3 - Completion:

Every cell is now reachable from the entry point
Exactly one path exists between any two points
All cells form a single connected component (spanning tree)

Optional: Imperfect Mazes

When is_perfect=False, the algorithm adds extra loops:

def make_imperfect(self, extra_paths: int = 5):
    """Remove additional walls to create multiple solution paths"""
    # Randomly selects walls and removes them while maintaining integrity
    # Each removal creates alternative routes
    # Safety check: ensures cells retain at least 2 walls before breaking

This creates mazes with multiple valid paths from entry to exit, increasing difficulty.

Maze Solving: BFS Algorithm

After generation, the maze can be solved using Breadth-First Search (BFS), an optimal pathfinding algorithm:

How BFS Works

BFS explores the maze layer by layer, visiting all cells at distance d before exploring cells at distance d+1:

Step 1: Initialize

queue = deque([entry])           # Start from entry point
visited = {entry}                # Mark as visited
parent_map = {}                  # Track where we came from

Step 2: Main Loop - Level-by-Level Exploration

while queue is not empty:
    current = queue.popleft()    # Process next cell (FIFO)
    
    if current == exit:
        path_found = True        # Stop if exit found
        break
    
    # Check all 4 directions (N, E, S, W)
    for each neighbor of current:
        if neighbor is passable and not visited:
            visited.add(neighbor)           # Mark visited
            parent_map[neighbor] = current  # Remember where we came from
            queue.append(neighbor)          # Add to queue for exploration

Step 3: Path Reconstruction

# Walk backwards from exit to entry using parent_map
path = []
current = exit
while current != entry:
    path.append(current)
    current = parent_map[current]  # Follow parent pointers
path.append(entry)
path.reverse()  # Reverse to get entry → exit order

Technical Stack & Architecture

Core Components

mazegen/generator.py: Implements the Prim's algorithm maze generation engine
- MazeGenerator class: Handles grid representation, wall carving, and maze solving
- Uses bitwise operations for efficient wall tracking (NORTH=1, EAST=2, SOUTH=4, WEST=8)
gui_engine.py: Graphics rendering layer wrapping MiniLibX
- GuiEngine class: Manages window creation, image buffering, and pixel rendering
- Handles event loops and user interactions
- Supports multiple visual themes with customizable color palettes
maze_app.py: Application orchestration
- MazeApp class: Coordinates maze generation and visualization
- Theme management (dreamy, forest, sunset)
- Configuration loading and parameter validation
parse_config.py: Configuration file parsing
- Validates parameter types and bounds
- Provides error handling for malformed configurations

Design Decisions

Graphics Integration Challenge: Integrating MiniLibX (an X11-based C wrapper) with Python required careful abstraction of low-level pixel manipulation. The GuiEngine class encapsulates all graphics operations, translating Python-level maze data into pixel coordinates and color values that MiniLibX can render.

Pixel-Level Control: Working with graphical interfaces required meticulous calculation of element sizing, positioning, and rendering. Each pixel must be precisely placed to create the maze visualization, requiring attention to coordinate systems and color space encoding (ARGB hexadecimal format).

Reusable Components

1. MazeGenerator Class

Location: mazegen/generator.py

Reusability: Complete independence from UI layer

Can generate mazes without graphics context
Outputs maze data to files for external processing
Algorithm can be extended for different maze types (perfect/imperfect, different start/end points)
Suitable for use in other projects requiring maze generation

Building as a Reusable Package

The MazeGenerator class is packaged as a standalone Python module that can be installed in other projects:

Step 1: Build the package

make build

This command:

Creates a distribution package in the dist/ directory
Generates mazegen-<version>-py3-none-any.whl (wheel file)
Creates mazegen-<version>.tar.gz (source archive)
Uses pyproject.toml configuration for package metadata

Step 2: Install in another project

# From the other project's environment
pip install /path/to/project/dist/mazegen-*.whl

# Or install from PyPI
pip install mazegen

Package Structure

The built package includes:

Core Algorithm: MazeGenerator class for standalone maze generation
No UI Dependencies: Works without MiniLibX or GUI components
Type Hints: Full Python type annotations for IDE support and type checking
Documentation: Docstrings and this README for reference

Benefits for External Projects

Standalone Usage: Use maze generation without needing graphics
Reproducible Results: Seed-based generation for testing and demos
Flexible Output: Export to files, arrays, or custom formats
Educational Value: Learn graph algorithms and maze generation
No External Dependencies: Only requires Python standard library

Usage Example

from mazegen.generator import MazeGenerator

generator = MazeGenerator(col=50, row=50, 
                         entry=(0, 0), exit=(49, 49),
                         seed="reproducible_seed")
generator.generate()
maze_data = generator.get_grid()

2. GuiEngine Class

Location: gui_engine.py

MiniLibX Graphics Pipeline - Complete Flow

The GuiEngine class wraps MiniLibX (a C X11 graphics library) and implements a complete graphics rendering pipeline:

Phase 1: Initialization

When GuiEngine.__init__() is called:

def __init__(self, col: int, row: int, title: str):
    # 1. Initialize MiniLibX connection
    self.mlx = Mlx()
    self.ptr = self.mlx.mlx_init()  # Create MLX instance
    
    # 2. Calculate optimal tile size based on maze dimensions
    self.tile_size = self._calculate_dynamic_tile_size()
    
    # 3. Create window
    self.win = self.mlx.mlx_new_window(
        self.ptr, 
        self.win_w,    # Window width in pixels
        self.win_h,    # Window height in pixels
        title          # Window title
    )
    
    # 4. Create image buffer (off-screen rendering)
    self.img_ptr = self.mlx.mlx_new_image(self.ptr, self.win_w, self.win_h)
    self.img_data, self.bpp, self.line_len, self.endian = (
        self.mlx.mlx_get_data_addr(self.img_ptr)
    )
    
    # 5. Setup event hooks for interaction
    self._setup_hooks()

Key Components Created:

self.ptr: MLX connection handle (needed for all MLX calls)
self.win: Window handle (target for rendering)
self.img_ptr: Image buffer handle (off-screen drawing surface)
self.img_data: Raw pixel data (bytes array for direct pixel access)
self.bpp: Bits per pixel (32-bit ARGB)
self.line_len: Bytes per row (for offset calculations)

Phase 2: Event Handling Setup

def _setup_hooks(self):
    # Listen for window close (X button click)
    self.mlx.mlx_hook(self.win, 17, 0, self.close_window, None)
    
    # Listen for keyboard input
    self.mlx.mlx_key_hook(self.win, self._handle_keys, None)

Event Flow:

User presses key → MiniLibX captures event
MiniLibX calls _handle_keys(keycode, param)
_handle_keys invokes registered on_key_press callback
Application logic processes the input (e.g., regenerate maze, change theme)

Phase 3: Rendering Cycle (Per Frame)

The main loop runs every frame (typically 60+ FPS):

User Action/Timer Event
         ↓
mlx_loop_hook() → calls registered callback function
         ↓
set_loop_callback(func) → Your application's render function
         ↓
[Function executes]
         ↓
Put pixels in image buffer → put_pixel_to_image()
         ↓
Flush buffer to screen → flush_image()
         ↓
Display updated frame

Pixel Rendering: From Maze to Screen

The core of the graphics pipeline is pixel-level rendering:

Step 1: Buffer-to-Pixel Mapping

def put_pixel_to_image(self, x: int, y: int, color: int):
    """
    Calculate memory offset for pixel and write color data
    
    Memory Layout:
    [0] [1] [2] ... [win_w-1]           ← Row 0
    [win_w] [win_w+1] ... [2*win_w-1]  ← Row 1
    ...
    """
    # Calculate offset in bytes from image buffer start
    offset = (y * self.line_len) + (x * (self.bpp // 8))
    
    # Convert hex color to ARGB format if needed
    if color <= 0xFFFFFF:
        color |= 0xFF000000  # Add full alpha channel
    
    # Write 4 bytes (ARGB) to buffer
    self.img_data[offset:offset+4] = color.to_bytes(4, byteorder="little")

Memory Access:

Each pixel requires 4 bytes (ARGB: Alpha, Red, Green, Blue)
Offset calculation: (row * bytes_per_row) + (col * 4)
Little-endian byte order for Linux X11

Step 2: Wall Rendering from Bit Flags

def render_cell(self, x: int, y: int, value: int, color: int):
    """
    Render walls based on bit flags in maze cell
    
    Bit masks:
    1 = NORTH (top)    → Draw horizontal line at top
    2 = EAST (right)   → Draw vertical line at right
    4 = SOUTH (bottom) → Draw horizontal line at bottom
    8 = WEST (left)    → Draw vertical line at left
    """
    start_x, start_y = self._to_screen(x * self.tile_size, y * self.tile_size)
    
    # Check NORTH wall (bit 0)
    if value & 1:
        for i in range(self.tile_size):
            for t in range(self.line):  # line thickness
                put_pixel_to_image(start_x + i, start_y + t, color)
    
    # Check EAST wall (bit 1)
    if value & 2:
        for i in range(self.tile_size):
            for t in range(self.line):
                put_pixel_to_image(start_x + self.tile_size - 1 - t, 
                                 start_y + i, color)
    
    # Check SOUTH wall (bit 2)
    if value & 4:
        for i in range(self.tile_size):
            for t in range(self.line):
                put_pixel_to_image(start_x + i, 
                                 start_y + self.tile_size - 1 - t, color)
    
    # Check WEST wall (bit 3)
    if value & 8:
        for i in range(self.tile_size):
            for t in range(self.line):
                put_pixel_to_image(start_x + t, start_y + i, color)

Example: Cell with value 5 (binary: 0101)

Bit 0 (NORTH) = 1 → Draw top wall
Bit 1 (EAST) = 0 → No right wall
Bit 2 (SOUTH) = 1 → Draw bottom wall
Bit 3 (WEST) = 0 → No left wall
Result: Top and bottom walls visible, left and right open

Step 3: Complete Maze Rendering

def draw_maze(self, maze: list[list[int]], color: int):
    """Render entire maze grid cell by cell"""
    for y, row in enumerate(maze):
        for x, cell_value in enumerate(row):
            # Each cell's walls rendered according to bit flags
            self.render_cell(x, y, cell_value, color)

Complete Frame Rendering Process

1. draw_bg(background_color)
   └─ Fill all pixels with background color (clearing the screen)

2. draw_maze(maze_data, wall_color)
   └─ For each cell: render_cell(x, y, value, color)
      └─ For each wall present: put_pixel_to_image() × N pixels

3. (Optional) draw_block(path_x, path_y, path_color)
   └─ Highlight solution path cells

4. flush_image()
   ├─ mlx_put_image_to_window() → Copy buffer to screen
   └─ mlx_do_sync() → Force display refresh

5. draw_menu()
   └─ mlx_string_put() → Text overlay (drawn directly to window)

Result: Complete frame displayed on screen

Dynamic Tile Sizing

The engine automatically calculates optimal tile size:

def _calculate_dynamic_tile_size(self) -> int:
    """Scale maze to fit different window sizes"""
    safe_w = MAX_SCREEN_W - (padding * 2)
    safe_h = MAX_SCREEN_H - menu_height - (padding * 2)
    
    ideal_tile_w = safe_w // col          # Width per tile
    ideal_tile_h = safe_h // row          # Height per tile
    
    tile_size = min(ideal_tile_w, ideal_tile_h)
    return max(10, min(tile_size, 45))    # Clamp to 10-45 pixels

Examples:

30×30 maze on 1200×800 screen → ~23px tiles
100×100 maze on 1200×800 screen → ~10px tiles (minimum)
10×10 maze on 1200×800 screen → 45px tiles (maximum)

Event Loop Integration

def set_loop_callback(self, func):
    """Register function to run every frame"""
    self._loop_callback = func
    
    def _internal_wrapper(engine_instance):
        # Wrapped with error handling
        try:
            return self._loop_callback(self)  # Call your function
        except Exception as e:
            print(f"Critical error: {e}")
            exit(1)
    
    # Register with MiniLibX
    self.mlx.mlx_loop_hook(self.ptr, _internal_wrapper, self)

def run(self):
    """Start the event loop (blocks indefinitely)"""
    self.mlx.mlx_loop(self.ptr)
    # mlx_loop keeps running, calling loop hooks repeatedly

Loop Flow:

mlx_loop()
├─ Process events (keyboard, window close)
├─ Call registered mlx_loop_hook() callbacks
├─ Display frame
└─ Repeat ~60+ times per second

Complete MiniLibX Method Reference

Method	Purpose	Parameters	Returns
`mlx_init()`	Initialize MLX	None	MLX handle (`ptr`)
`mlx_new_window()`	Create window	ptr, width, height, title	Window handle
`mlx_new_image()`	Create buffer	ptr, width, height	Image handle
`mlx_get_data_addr()`	Get pixel data	image_ptr	(data, bpp, line_len, endian)
`mlx_put_image_to_window()`	Display buffer	ptr, win, img, x, y	0 (success)
`mlx_do_sync()`	Refresh display	ptr	0 (success)
`mlx_hook()`	Register event	win, event_type, mask, func, param	0 (success)
`mlx_key_hook()`	Register keyboard	win, func, param	0 (success)
`mlx_loop_hook()`	Register loop callback	ptr, func, param	0 (success)
`mlx_loop()`	Start event loop	ptr	(never returns)
`mlx_string_put()`	Draw text	ptr, win, x, y, color, string	0 (success)

Performance Considerations

Off-Screen Rendering: All pixels drawn to buffer first (put_pixel_to_image)
Single Flush: Buffer displayed once per frame (flush_image)
Efficient: Only pixels that change need updating
Pixel-Perfect: Direct control at pixel level

This architecture provides smooth, responsive graphics while maintaining clean separation between game logic and rendering.

Team & Project Management

Team Members & Roles

Member	Responsibilities
jbarreir	• MiniLibX graphics engine implementation and X11 integration • Core maze generation algorithm (Prim's randomized variant) • Pixel-level rendering system and visual theme architecture • BFS pathfinding and maze solving algorithms • Performance optimization and bitwise operations
catencio	• Configuration file parsing and validation framework • Maze generation logic refinement and edge case handling • Algorithm optimization and perfect maze guarantees • Testing strategy and test case design • Documentation and code quality standards

Resources & References

Documentation & Official References

Python Official Documentation: python.org/3/library - Standard library reference
PEP Standards: PEP 257 - Docstring conventions, PEP 8 - Style guide
42 Intra: Project subject PDF and evaluation criteria
MiniLibX Documentation: harm-smits.github.io/42docs/libs/minilibx

Algorithm & Theory Resources

Maze Generation Algorithms: Professor L's Comprehensive Guide - Algorithm explanations and visualizations
Breadth-First Search: GeeksforGeeks BFS Tutorial - BFS algorithm and applications

Video Tutorials & Visualizations

Prim's Algorithm Visualization: YouTube - Algorithm Visualization
Randomized Prim's Algorithm: YouTube - Implementation Tutorial
MiniLibX Graphics Programming: Understanding X Window Programming

Testing & Quality Assurance

pytest: pytest documentation - Python testing framework
flake8: flake8 linting - Code quality checker
mypy: mypy documentation - Static type checker for Python

AI Usage Disclosure

In compliance with 42's evaluation standards:

Concept Clarification: AI was used to understand graph theory (Prim's algorithm, spanning trees), bitwise operations, BFS optimality, and MiniLibX graphics programming.
Architecture & Design: AI assisted in identifying separation of concerns between generation and visualization layers, design patterns, and package structure.
Documentation & Explanation: AI helped translate algorithmic concepts into clear explanations, generate docstrings (PEP 257), and structure this README.
Strict Policy:
- No Copy-Paste: All code was written manually after understanding concepts
- Ownership: Every line is understood and replicable by the authors
- Verification: Cross-referenced with official documentation, algorithm textbooks, and manual testing

Name		Name	Last commit message	Last commit date
dist		dist
mazegen		mazegen
Makefile		Makefile
README.md		README.md
a_maze_ing.py		a_maze_ing.py
config.txt		config.txt
gui_engine.py		gui_engine.py
maze_app.py		maze_app.py
mlx-2.2-py3-none-any.whl		mlx-2.2-py3-none-any.whl
mypy.ini		mypy.ini
parse_config.py		parse_config.py
pyproject.toml		pyproject.toml
requirements.txt		requirements.txt
test_a_maze_ing.py		test_a_maze_ing.py

Latest commit

History

Folders and files

Repository files navigation

🧩 a-maze-ing

Description

Instructions

Prerequisites

Installation

Execution

Configuration File Format

Maze Generation Algorithm

Algorithm: Prim's Algorithm (Randomized)

Why Prim's Algorithm?

Algorithm Characteristics

Understanding Perfect Mazes

Wall Representation with Bit Flags

Detailed Algorithm Steps

Step 1: Initialization

Step 2: Main Loop - Maze Construction

Step 3: Finalization

Visualization Example

Optional: Imperfect Mazes

Maze Solving: BFS Algorithm

How BFS Works

Technical Stack & Architecture

Core Components

Design Decisions

Reusable Components

1. MazeGenerator Class

Building as a Reusable Package

Package Structure

Benefits for External Projects

Usage Example

2. GuiEngine Class

MiniLibX Graphics Pipeline - Complete Flow

Phase 1: Initialization

Phase 2: Event Handling Setup

Phase 3: Rendering Cycle (Per Frame)

Pixel Rendering: From Maze to Screen

Complete Frame Rendering Process

Dynamic Tile Sizing

Event Loop Integration

Complete MiniLibX Method Reference

Performance Considerations

Team & Project Management

Team Members & Roles

Resources & References

Documentation & Official References

Algorithm & Theory Resources

Video Tutorials & Visualizations

Testing & Quality Assurance

AI Usage Disclosure

About

Resources

Stars

Watchers

Forks

Contributors

Languages