Maze Solver - AI Search Algorithms

A comprehensive Python implementation of various artificial intelligence search algorithms for solving mazes. This project demonstrates the practical application of different search strategies, from basic uninformed search to advanced heuristic-based algorithms.

Overview

This maze solver supports multiple search algorithms and provides visual representation of both the maze and the solution path. The implementation includes performance metrics to compare the efficiency of different algorithms.

Features

• Multiple Search Algorithms: Implements five different search strategies
• Visual Output: ASCII representation of mazes with solution paths
• Performance Metrics: Tracks steps explored and solution path length
• Flexible Input: Supports custom maze files with simple text format
• Command-line Interface: Easy-to-use CLI with algorithm selection

Supported Algorithms

1. Depth-First Search (DFS)

• Strategy: Explores as far as possible along each branch before backtracking
• Implementation: Uses a stack (LIFO) frontier
• Characteristics: Memory efficient, not guaranteed to find optimal solution

2. Breadth-First Search (BFS)

• Strategy: Explores all neighbors at current depth before moving to next level
• Implementation: Uses a queue (FIFO) frontier
• Characteristics: Guaranteed to find shortest path, higher memory usage

3. Greedy Best-First Search

• Strategy: Always moves toward the goal using heuristic function
• Heuristic: Manhattan distance to goal
• Characteristics: Fast but not guaranteed to find optimal solution

4. Smart Greedy Best-First Search

• Strategy: Considers both distance from start and distance to goal
• Heuristic: Combines start distance and goal distance
• Characteristics: Better balance between exploration and exploitation

5. A* Search

• Strategy: Optimal pathfinding using f(n) = g(n) + h(n)
• Heuristic: Actual cost from start + Manhattan distance to goal
• Characteristics: Guaranteed optimal solution, admissible heuristic

Installation

No external dependencies required. The script uses only Python standard library modules.

git clone <repository-url>
cd maze

Usage

Basic Usage

python maze.py maze1.txt

With Algorithm Selection

python maze.py maze1.txt --search-type breadth-first-search

Available Algorithms

• depth-first-search (default)
• breadth-first-search
• greedy-best-first-search
• smart-greedy-best-first-search
• a-star-search

Command-line Options

python maze.py [-h] [--search-type {depth-first-search,breadth-first-search,greedy-best-first-search,smart-greedy-best-first-search,a-star-search}] filename

Maze Format

Mazes are defined in simple text files using the following symbols:

• A - Start position (exactly one required)
• B - Goal position (exactly one required)
• # - Wall (impassable)
• - Empty space (passable)

Example Maze

#####B#
##### #
####  #
#### ##
     ##
A######

Output Format

The program displays:

1. Original Maze: Shows the initial maze layout
2. Solution: Maze with solution path marked
3. Performance Metrics: Number of explored steps and solution path length

Output Symbols

• █ - Wall
• A - Start position
• B - Goal position
• * - Solution path
• - - Explored but not part of solution
• - Empty space

Sample Mazes

The repository includes five sample mazes of varying complexity:

• maze1.txt: Simple 6x7 maze - good for testing basic functionality
• maze2.txt: Complex 16x29 maze - tests algorithm efficiency
• maze3.txt: Small 6x7 maze with different layout
• maze4.txt: Medium 7x12 maze with moderate complexity
• maze5.txt: Linear 7x12 maze - tests algorithm behavior on simple paths

Performance Comparison

Different algorithms will show varying performance on the same maze:

• BFS: Finds shortest path but explores many nodes
• DFS: May find longer paths but uses less memory
• Greedy: Fast execution but may not find optimal solution
• A*: Optimal solution with efficient exploration

Implementation Details

Core Classes

• Node: Represents a state in the search space with parent tracking
• Maze: Handles maze loading, validation, and solution visualization
• Frontier Classes: Implement different search strategies
  • StackFrontier: DFS implementation
  • QueueFrontier: BFS implementation
  • ClosestToGoalFrontier: Greedy best-first search
  • ClosestToStartAndGoalFrontier: Smart greedy and A* search

Key Features

• Heuristic Function: Uses Manhattan distance for informed search
• Path Reconstruction: Traces back from goal to start using parent pointers
• Validation: Ensures exactly one start and one goal position
• Error Handling: Handles unsolvable mazes gracefully

Educational Value

This project demonstrates:

• Search Algorithm Theory: Practical implementation of classical AI algorithms
• Heuristic Design: How different heuristics affect search performance
• Space-Time Tradeoffs: Comparison between different algorithmic approaches
• Problem Representation: Converting real-world problems to search spaces

Contributing

Feel free to contribute by:

• Adding new search algorithms
• Improving maze generation
• Enhancing visualization
• Adding performance benchmarks
• Creating more test cases

License

This project is part of the CS50AI curriculum and is intended for educational purposes.

---

Originally developed as part of Harvard's CS50 Introduction to Artificial Intelligence with Python course.