A robust, interactive visualization tool built with Pygame that demonstrates and compares various graph searching and pathfinding algorithms. Users can interactively define a grid, place obstacles (barriers), set start and end points, and watch the algorithms search for the shortest path in real-time.
- Interactive Grid Interface: Create a dynamic 2D grid where each cell (Spot) can be manipulated.
- Node States: Visually distinguish between Start, End, Barrier (Wall), Open Set (Unvisited), Closed Set (Visited), and the final Path using distinct colors.
- Multiple Algorithm Support: Choose from a wide selection of informed and uninformed searching methods.
- Real-time Visualization: Watch the search process step-by-step as nodes are explored, offering deep insight into how each algorithm operates.
- User Controls: Intuitive mouse and keyboard controls for setting up and running the simulation.
The project includes sophisticated implementations of both uninformed (blind) and informed (heuristic-based) search algorithms:
- Breadth-First Search (BFS)
- Depth-First Search (DFS)
- Uniform Cost Search (UCS)
- Depth-Limited Search (DLS)
- Iterative Deepening Search (IDS)
- A* Search (A-Star)
- Greedy Best-First Search
- Iterative Deepening A* (IDA*)
| Action | Control | Description |
|---|---|---|
| Set Start Node | Left Click (First Time) | Place the blue starting node. |
| Set End Node | Left Click (Second Time) | Place the yellow destination node. |
| Set Barrier (Wall) | Left Click (Any Time After Start/End) | Draw black obstacles to block paths. |
| Remove Node/Barrier | Right Click | Clear the clicked spot. |
| Start Algorithm | SPACEBAR | Starts the visualization of the currently selected algorithm. |
| Reset Grid | 'C' Key | Clears the path and the search history, but keeps the Start, End, and Barriers. |
| Full Reset | 'R' Key | Clears the entire grid, removing Start, End, Barriers, and the search path. |
| Select Algorithm | Click UI Button | Switch between the available algorithms (e.g., BFS, A*). |
| File | Role |
|---|---|
main.py |
Main Entry Point. Handles Pygame initialization, the main game loop, user input (mouse/keyboard), and algorithm selection and display management. |
grid.py |
Manages the 2D grid structure. Responsible for creating the Spot objects, drawing the grid lines, and determining the position of a mouse click within the grid. |
spot.py |
Defines the Spot class. Represents a single cell in the grid and holds its state (color, position, neighbors). Includes methods to change its type (e.g., make_barrier, is_closed). |
searching_algorithms.py |
Core Logic. Contains the complete implementations of all the pathfinding algorithms (BFS, A*, DFS, etc.). |
utils.py |
Stores global constants, including window dimensions (WIDTH, HEIGHT) and the color mapping (COLORS) used across the application. |