Maze Solver with Genetic Algorithms

This project implements a high-performance maze generator and solver using Genetic Algorithms (GA) and Dijkstra's algorithm. It features custom Numba-optimized kernels for efficient pathfinding and evolution simulation, along with visualization tools for analyzing population convergence.

Requirements

• Python: 3.13.7 or higher
• Operating System: Linux, macOS, or Windows

Dependencies

• numpy = 2.3.5
• matplotlib = 3.10.5
• scipy = 1.16.3
• numba = 0.63.1
• tqdm = 4.67.1

Development Dependencies:

• pytest = 6.2.1
• pytest-cov = 6.2.1
• ruff (optional, for linting)

Installation

Option 1: Using Nix

This project includes a flake.nix file for a reproducible development environment.

1. Ensure Nix is installed with flakes enabled.
2. Enter the development shell:

   nix develop

Option 2: Using Pip

1. Create a virtual environment:

   python -m venv .venv
   source .venv/bin/activate  # On Windows: .venv\Scripts\activate

2. Install dependencies:

   pip install numpy matplotlib scipy numba tqdm

3. Install testing tools:

   pip install pytest pytest-cov

Usage

Here is the detailed "Configuration" section to include in your README.md.

Configuration

The application is controlled via config.conf. Below is a detailed description of each parameter organized by section.

[main]

• maze_width / maze_height: Dimensions of the maze grid (integer).
• genetic_population_size: Number of individuals in the population. If set to None, it is automatically calculated based on maze dimensions.
• genetic_runs: Maximum number of generations to simulate. If set to None, it is automatically calculated.

[genetic]

• random_goal_start: If True, start and goal positions are randomized for each run.
• max_position_trials: Maximum attempts to place start/goal positions if randomization is enabled.
• goal_distance_weight: Fitness coefficient penalizing distance from the goal.
• invalid_move_penalty_weight: Fitness coefficient penalizing hitting walls or boundaries.
• backtrack_penalty_weight: Fitness coefficient penalizing revisiting the same cell (cycles).
• following_pheromone_weight: Weight influencing the probability of following existing pheromone trails during mutation.
• selection_rate: Fraction of the population selected as parents for the next generation (0.0 to 1.0).
• mutation_rate_pop: Base probability that an individual is selected for mutation.
• max_mutation_rate_pop: Maximum cap for the adaptive population mutation rate.
• mutation_rate_path: Probability of mutating a specific step (gene) within an individual's path.
• max_mutation_rate_path: Maximum cap for the adaptive path mutation rate.
• mutation_window_ratio_max / min: Defines the dynamic range for the mutation window size (percentage of path length affected around a mutation point).
• stagnation_window: Number of generations without improvement required to trigger adaptive hyperparameter adjustments.
• run_until_solution: If True, the simulation continues indefinitely until the goal is reached, ignoring genetic_runs.
• desired_invalid_moves / desired_backtrack_moves: Minimum counts of invalid/backtrack moves required before considering the maze solved (if the goal is reached).

[display]

• verbose: Logging verbosity level (0: None, 1: Warning, 2: Info, 3: Debug).
• maze: Enable visualization of the maze structure.
• dijkstra_map: Enable visualization of the Dijkstra heatmap (distance to goal).
• direction_map: Enable visualization of the optimal flow field.
• solution: Enable visualization of the solution path found by Dijkstra.
• genetic_population: Enable a heatmap visualization of the final population's exploration.
• genetic_console_progress: Show a progress bar (tqdm) in the console during evolution.
• genetic_console_update_iterations: Update frequency for the console progress bar and displayed plots (in generations).
• genetic_best_individual: Enable a plot showing the best path found after the run.
• cell_size: Size of each maze cell in the visualization (pixels / 100).
• path_width: Width of the path lines in the visualization (will be passed to the linewidths parameter of matplotlib.LineCollection).
• marker_size: Size of the start/goal markers in the visualization (pixels).
• animated: Enable real-time matplotlib animation of the evolution process.
• animation_step_ms: Delay between animation frames in milliseconds. Must be sufficiently high to allow rendering.
• show_pheromone_markers: Visual toggle for pheromone indicators in the animation.

[benchmark]

• enabled: Master switch to run in benchmark mode instead of normal simulation.
• maze, dijkstra, direction, solution_length, genetic: Toggles to enable specific benchmark suites.
• samples: Number of repetitions per test case for statistical accuracy (excluding genetic algorithm).
• maze_min_size, maze_max_size: Range of maze sizes (N x N) to test (excluding genetic algorithm, maze size are always defined under the [main] section).
• step_size: Increment step for the maze size range.

Running the Application

To start the solver or benchmarks, run the entry point:

python main.py

By default, this will load the configuration, generate a maze, and attempt to solve it using the genetic algorithm.

Benchmarks

To enable benchmarking, edit config.conf:

[benchmark]
enabled = True

And specify which benchmarks to run by setting the corresponding flags to True. Multiple benchmarks can be enabled simultaneously.

Then run python main.py. The results will include execution times and convergence analysis.

Testing

This project uses pytest for unit and integration testing.

Running Tests

Execute the test suite from the project root:

pytest

Running Tests with Coverage

To generate a coverage report:

pytest --cov=. --cov-branch

Project Structure

• Core Application:

  • main.py: Application entry point and orchestration logic.
  • genetic.py: Class implementation of the Genetic Algorithm solver.
  • maze.py: Class implementation for Maze generation, state management, and Dijkstra solver.
  • init.py: Numba JIT warmup routines to minimize runtime latency.
  • config.py: Configuration loader and schema validation logic.
  • printing.py: Utility module for controlled console verbosity.

• Optimization Kernels:

  • genetic_n_fn.py: Numba-optimized static functions for high-performance genetic operations.
  • maze_n_fn.py: Numba-optimized static functions for maze generation and pathfinding.

• Testing & Benchmarking:

  • *_test.py: Unit and integration test suites using pytest.
  • benchmark_utils.py: Utilities for performance measurement, statistical analysis, and plotting.

• Configuration & Environment:

  • config.ini: Default configuration file for runtime parameters.
  • flake.nix / flake.lock: Nix flake definitions for reproducible development environment.

• Documentation:

  • README.md: Project overview, setup instructions, and usage guide.
  • Rapport_Maze_Runner.md: Detailed project report (in French).
  • Projet Maze 2025.pdf: Project topic provided by ENSIBS for this assignment (in French).