Maze Solver - BFS & DFS Implementation

A C++ project that implements Breadth-First Search (BFS) and Depth-First Search (DFS) algorithms to solve mazes efficiently using object-oriented design principles and the Standard Template Library (STL).

🎯 Features

• Two Pathfinding Algorithms:

  • BFS (Breadth-First Search): Guarantees the shortest path
  • DFS (Depth-First Search): Explores paths deeply, may not find shortest path

• Interactive Maze Input:

  • Load mazes from text files
  • Create custom mazes with user-defined dimensions
  • Specify custom start and end positions

• Visual Step-by-Step Solving:

  • Watch the algorithm explore the maze in real-time
  • Clear visualization with legend
  • Path marking and current position tracking

• Object-Oriented Design:

  • Clean separation of concerns
  • Extensible architecture for adding new algorithms
  • Modular code structure

📁 Project Structure

maze-solver/ ├── Maze.h # Maze class declaration ├── Maze.cpp # Maze class implementation ├── Solver.h # Abstract solver base class ├── BFSolver.h # BFS solver declaration ├── BFSolver.cpp # BFS solver implementation ├── DFSolver.h # DFS solver declaration ├── DFSolver.cpp # DFS solver implementation ├── main.cpp # Main program entry point ├── maze.txt # Sample maze file └── README.md # This file

🛠️ Technologies Used

• Language: C++11/C++17
• Data Structures:
  • Vectors (2D grid representation)
  • Queue (for BFS)
  • Stack (for DFS)
  • Map (for parent tracking and visited nodes)
  • Pair (for coordinates)
• Algorithms: BFS, DFS
• Design Patterns: Strategy Pattern (Solver interface)

📋 Prerequisites

• C++ compiler with C++11 support or higher (g++, clang++, MSVC)
• Windows/Linux/macOS operating system

🚀 Getting Started

Compilation

'''bash g++ -std=c++11 main.cpp Maze.cpp BFSolver.cpp DFSolver.cpp -o MazeSolver

Running A program

./MazeSolver # Linux/macOS MazeSolver.exe # Windows

📝 Maze File Format Create a text file (e.g., maze.txt) with the following format:

5 5 ..... .#.#. .#... ..##. #.... 0 0 4 4 Format Explanation:

-> Line 1: rows columns (dimensions of the maze) -> Next rows lines: Maze layout ~ . = Open path ~ # = Wall/Obstacle -> Last 2 lines: Start position (row col) and End position (row col)

🎮 Usage Main Menu Options

1. Use default maze: Load and solve the maze from maze.txt
2. Enter custom maze: Create your own maze interactively
3. Exit: Close the program

Solver Options

1. Solve with DFS: Use Depth-First Search algorithm
2. Solve with BFS: Use Breadth-First Search algorithm
3. Back to main menu: Return to main menu

Legend During visualization, the following symbols are used:

Symbol Meaning S Start Position E End/Goal Position

•         Current Position (being explored)
  

o Path Taken

Wall/Obstacle

. Empty/Open Space

📊 Algorithm Comparison Feature BFS DFS Path Quality Shortest path guaranteed May not find shortest path

Memory Usage Higher (stores all nodes Lower (stores only at current level) current path)

Exploration Pattern Level-by-level (breadth-first) Deep exploration (depth-first)

Best For Finding shortest path Memory-constrained scenarios

Time Complexity O(V + E) O(V + E)

Space Complexity O(V) O(h) where h is max depth

💡 Example Sample Maze S . . . . . # . # . . # . . . . . # # .

. . . E

BFS Solution (Shortest Path - 8 steps) S . . . . o # . # . o # . . . o o # # .

o o o E

DFS Solution (May vary - explores deeply) S o o o o . # . # o . # . . o . . # # o

. . . E

🧪 Key Concepts Demonstrated Data Structures: Vectors, Queues, Stacks, Maps, Pairs Algorithms: Graph traversal (BFS, DFS) OOP Principles: Inheritance, Polymorphism, Encapsulation Design Patterns: Strategy Pattern File I/O: Reading maze configurations Error Handling: Exception handling for invalid inputs STL Usage: Standard Template Library containers and algorithms 🎯 Learning Outcomes Understanding of graph traversal algorithms Implementation of BFS and DFS from scratch Object-oriented design in C++ STL container usage (vector, queue, stack, map) File I/O operations Algorithm visualization techniques Problem-solving and algorithmic thinking Real-world pathfinding challenges

Creating Custom Mazes You can create your own maze files following the format:

<maze_layout> <start_row> <start_col> <end_row> <end_col>

🐛 Troubleshooting Issue: Compilation errors

Solution: Ensure you're using C++11 or higher: g++ -std=c++11 ... Issue: "Cannot open file" error

Solution: Make sure maze.txt is in the same directory as the executable Issue: "No path found"

Solution: Verify that your maze has a valid path from start to end Issue: Visualization too fast/slow

Solution: Adjust the Sleep() value in Maze.cpp (default is 200ms)

🚀 Future Enhancements ~ Add A* algorithm implementation ~ Add Dijkstra's algorithm ~ Implement maze generation algorithms ~ Add GUI using graphics library ~ Performance metrics and comparison ~ Save solution to file ~ Multiple maze file support ~ Animated path visualization

👨‍💻 Author Sparsh Chaudhary

🙏 Acknowledgments Inspired by classic pathfinding problems in computer science Built as a demonstration of Data Structures and Algorithms concepts in C++Thanks to the open-source community for C++ resources and best practices Special thanks to professors and mentors for guidance

📚 References Introduction to Algorithms (CLRS) C++ STL Documentation Graph Theory and Pathfinding Algorithms Object-Oriented Design Principles

📞 Contact For questions, suggestions, or feedback:

GitHub: [https://github.com/Sparsh17092004] Email: [3214sparshchaudhary@gmail.com] ⭐ If you found this project helpful, please consider giving it a star! ⭐

Note: This project was developed as part of coursework to demonstrate proficiency in C++, Data Structures, Algorithms, and Object-Oriented Design principles.