Maze Quest — Interactive AI Search (Maze Solver)

Project Overview

Maze Quest is an educational project that implements classical AI search algorithms to solve 2D grid mazes and provides an interactive Tkinter GUI for visualization and experimentation.

Key features:

• Compare BFS, DFS, IDS, and A* on the same maze
• Step-by-step visualization of explored nodes and final paths
• Editable maze grid and configurable start/goal positions (up to 20x20)
• Limited player hints and AI preview mode

Files

• gui.py — Tkinter-based interactive GUI and visualization.
• maze_solver.py — Core MazeSolver class and CLI runner (BFS, DFS, IDS, A*).
• lab_report.md — Lab report describing design, results, and analysis.
• MazeQuest_Presentation (2).pptx — Presentation slides.

Requirements

• Python 3.8+
• tkinter (standard with most Python installations; no external packages required)

Installation

1. Ensure Python 3.8+ is installed.
2. Create a virtual environment (optional):

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

3. No pip packages are required — tkinter comes with Python. If your platform lacks tkinter, install your system package (e.g. sudo apt install python3-tk).

Usage

Run the GUI (recommended):

python gui.py

Run the CLI solver (prints results for the default maze):

python maze_solver.py

GUI Quick Guide

• On launch you may choose a default randomized maze or a custom empty grid.
• Controls (left panel): change rows/columns, set start/goal cells, clear/reset maze.
• Algorithm selection: pick BFS, DFS, IDS, A*, or All Algorithms to compare.
• Speed (ms): set animation delay per explored node (0 = instant).
• Enable Artificial Intelligence to toggle a live preview path from the player's current cell to the goal.
• Use arrow keys to move the Player (P) marker on the grid; limited hints are available via the Hint button.
• Results panel: nodes explored, path costs, execution time, and textual paths are shown.

Algorithms Implemented

• Breadth-First Search (BFS): level-order expansion — complete and optimal for unit-cost moves.
• Depth-First Search (DFS): LIFO exploration — low memory, not optimal.
• Iterative Deepening Search (IDS): repeated depth-limited DFS with increasing depth — complete and memory efficient.
• A* Search: priority queue with f(n)=g(n)+h(n), using Manhattan distance heuristic.

Heuristic (A*)

The heuristic used is Manhattan Distance:

$$ h(n) = |r_{current} - r_{goal}| + |c_{current} - c_{goal}| $$

This heuristic is admissible for 4-directional grid movement with unit costs.

Reproducing Results

• The AI Lab Mid Project Report.docx includes an example comparison table and notes about performance on the default maze. To reproduce:

1. Run python maze_solver.py to see console output for the default maze.
2. Use the GUI to generate random mazes at different densities and compare algorithms via the All Algorithms option.

Example CLI output includes algorithm names, nodes explored, path cost, and elapsed time.

Implementation Notes

• MazeSolver exposes both batch-run methods (run_bfs, run_dfs, run_ids, run_a_star) and step generators (run_*_steps) used by the GUI to animate exploration.
• get_solution_path_from and get_next_hint_step provide path/hint utilities used by the GUI.
• The GUI limits grid size to 20x20 for usability and rendering reasons.

Known Limitations & Tips

• Maze sizes larger than 20x20 are blocked by the GUI; the solver itself can handle larger grids but visualization and controls assume the 20x20 cap.
• tkinter behavior and fonts may vary across platforms; for best appearance use a modern OS font environment.
• IDS can be slow on large open grids because it repeats searches with growing depth limits.

Credits

Authors:

• Muhammad Ayan Sajid
• Muhammad Husnain
• Muhammad Sultan
• Noor-ul-ain Fatima

Project developed for CSC-202L · Artificial Intelligence Lab | UET Lahore, New Campus

License

This project is open-source and available under the MIT License.