Welcome to the Maze Solver project! This repository contains implementations of two fundamental graph traversal algorithms, Breadth-First Search (BFS) and Depth-First Search (DFS), to solve maze problems. These algorithms are used to find paths from a start point to an end point within a maze, demonstrating their practical applications in pathfinding and AI.
This project provides a simple and clear implementation of BFS and DFS algorithms to solve mazes. It is designed for educational purposes, demonstrating how these algorithms can be used to navigate through a maze from a specified start point to an end point.
- BFS Implementation: Ensures the shortest path is found (if one exists).
- DFS Implementation: Explores as far as possible along each branch before backtracking.
- Customizable Input: Supports custom maze definitions via text files.
- Visual Representation: Outputs the path found in a visual format.
To run this project, you need Python installed on your machine. Follow the steps below to set up the project:
-
Clone the repository:
git clone https://github.com/yourusername/maze-solver.git cd maze-solver
-
(Optional) Create a virtual environment and activate it:
python -m venv venv source venv/bin/activate # On Windows, use `venv\Scripts\activate`
-
Install the required packages:
pip install -r requirements.txt
To run the maze solver, use the following command:
python maze.py maze1.txt
The maze input should be provided in a text file with the following format:
A
denotes the start point.B
denotes the end point.#
denotes walls.
Example maze.txt
:
#######
#A# #
# # # #
# # #B#
# #
#######
The output will display the maze with the path from start to end marked with *
if a path is found.
Example output:
#######
#S#***#
#.#*#*#
#.#*#E#
#*****#
#######
BFS explores the maze level by level, ensuring the shortest path is found. It uses a queue to manage the nodes to be explored next.
DFS explores as far as possible along each branch before backtracking. It uses a stack (or recursion) to manage the nodes.
Run BFS on a sample maze:
python maze.py maze1.txt
Run DFS on a sample maze:
Simply go to the maze.py file and uncomment out the commented code and it will run the DFS code.
python maze.py maze1.txt
Contributions are welcome! Please fork this repository and submit pull requests with your changes. For major changes, please open an issue first to discuss what you would like to change.
This project is licensed under the MIT License. See the LICENSE file for details.
Feel free to explore, modify, and use the code to better understand BFS and DFS algorithms. If you have any questions or suggestions, please open an issue or reach out directly.
Happy coding!