Pathfinding Algorithms
DESCRIPTION
Four pathfinding agents implemented on a grid-based environment, each using a different search strategy. From optimal cost-based exploration to heuristic-driven shortcuts and a custom hybrid approach, the project compares how each algorithm navigates from start to goal across different map types.
SCREENSHOTS
MY ROLE & CONTRIBUTION
I implemented all four agents on top of the provided pathfinding SDK. The A* Manhattan agent combines accumulated path cost with a Manhattan distance heuristic for efficient optimal pathfinding. The Dijkstra agent performs uniform-cost search without any heuristic, guaranteeing optimality at the cost of broader exploration. The Greedy agent uses only the Manhattan heuristic to reach the goal as fast as possible, trading optimality for speed. The DFS/BFS Hybrid is a custom agent I designed that starts in BFS mode for broad shallow exploration and switches to DFS once a configurable depth threshold is reached, adapting its strategy mid-search.
CORE CONCEPTS
This project explores the fundamental trade-offs in search algorithm design: optimality vs. speed, and informed vs. uninformed search. It applies classical AI pathfinding theory to a practical grid environment, making the differences between algorithms directly visible through path quality and node exploration patterns.
TECHNICAL ASPECTS
Developed in Python using a provided pathfinding SDK. All agents share the same grid interface, ensuring a fair comparison. Evaluated across multiple map types including random mazes and weighted grids. Each agent is fully deterministic and path cost is computed by summing the entry cost of each cell along the reconstructed path.
