A dual-purpose project: an interactive educational tool for visualizing AI search algorithms, and a robust, generic Java framework for solving state-space search problems.
Developed at INSAT (Institut National des Sciences Appliquées et de Technologie), this project bridges the gap between abstract algorithmic theory and practical implementation. By applying search strategies to a delivery route simulation, users can visually grasp how different agents "think," explore, and optimize paths in complex environments.
Understanding the difference between Breadth-First Search (BFS), Depth-First Search (DFS), and A (A-Star)* can be difficult with code alone. This application is designed for students and researchers to:
- 👁️ Visualize the "Frontier": Watch exactly how an algorithm expands its search space in real-time. See the difference between the "ripple" of BFS and the "focused beam" of A*.
- ⚖️ Compare Strategies: Run two algorithms side-by-side on the same map. Does A* really find the path faster than UCS? Does DFS get stuck in infinite loops?
- 📉 Analyze Heuristics: Switch between Manhattan and Euclidean distances to see how the choice of heuristic function drastically impacts performance and path optimality.
- ⚡ Understand Trade-offs: Visualize the classic trade-off between Completeness (finding a solution), Optimality (finding the best solution), and Time Complexity (memory/speed).
Under the hood, this project is powered by a completely generic search engine.
- Decoupled Architecture: The search logic (
search.framework) is isolated from the problem logic (grid.model). - Extensible: Developers can use this codebase to solve any state-space search problem (e.g., 8-Puzzle, Water Jugs, Rubik's Cube) simply by implementing the
SearchProbleminterface.
- Interactive Map Editor: Draw walls, place Stores (Sources), Destinations (Goals), and Tunnels (teleporters) to create complex non-linear graphs.
- Real-Time Animation: Control the speed of the search visualization (Play/Pause/Step).
- Batch Comparison: Run multiple algorithms on the same map instantly to generate comparative statistical charts.
The engine supports a wide range of strategies to solve the defined problem:
| Category | Algorithm | Description |
|---|---|---|
| Uninformed | BFS (Breadth-First) | Guarantees shortest path; explores level-by-level. |
| DFS (Depth-First) | Memory efficient; not optimal; can get lost in deep branches. | |
| UCS (Uniform Cost) | Explores lowest path cost g(n) first. |
|
| IDS (Iterative Deepening) | Combines BFS completeness with DFS memory efficiency. | |
| Informed | Greedy Best-First | Fast but not optimal; follows heuristic h(n) only. |
| A Search* | Optimal and efficient; uses f(n) = g(n) + h(n). |
Available Heuristics: Manhattan Distance, Euclidean Distance, and Non-Admissible variants.
The application is split into three intuitive modules:
Create custom problems to test specific algorithmic behaviors.
- Draw Walls: Click and drag to create mazes or open fields.
- Place Entities: Add the Agent and Destinations.
- Tunnels: Place teleporters to create complex graphs.
Once your map is ready, configure the solver:
- Select Algorithm: Choose from BFS, DFS, UCS, IDS, Greedy, or A*.
- Select Heuristic: (For informed searches) Choose Manhattan, Euclidean, etc.
- Animation Control: Speed up, slow down, or pause to inspect the state.
Select multiple algorithms and run them in batch mode to generate a statistical dashboard:
- Nodes Expanded: Memory usage.
- Path Cost: Solution optimality.
- Execution Time: Computation speed.
- Java JDK 17+
- Maven
-
Clone the repository:
git clone https://github.com/medtaher123/AI-Pathfinding-engine.git cd your-repo -
Build the project:
mvn clean install
-
Run the Application:
mvn exec:java -Dexec.mainClass="app.Main"
For a deep academic dive into the generic architecture design, and performance benchmarks of these algorithms, please refer to the full project report:
👉 Read the Full Academic Report (PDF)
This project is licensed for educational use.