Technology Stack
Python, Graph Search, Heuristic Design, Dynamic Programming, Visualisation
Overview
Duration: 1/2023
A pathfinding engine that solves maze navigation with four different search strategies and renders the result, so the practical differences between them are visible rather than theoretical. An agent starts at a marked position and must reach the single exit, moving in four directions at uniform cost.
The point of implementing all four rather than only the best one is that "best" depends on the map. A* dominates on paper, but the comparison shows exactly where each strategy's guarantees hold and where they break — which is the knowledge that actually transfers to real routing and planning problems.
Search Strategies
Uninformed search — no knowledge of where the goal is:
- Depth-First Search — memory-efficient and fast to find a path, with no guarantee that path is short. On large open maps it commits early to a bad direction and explores a long way before backtracking
- Breadth-First Search — complete and optimal for uniform cost, at the price of holding the entire frontier in memory, which grows quickly on wide maps
Informed search — using a heuristic estimate of remaining distance:
- Greedy Best-First Search — always expands the node that looks closest to the goal. Very fast, and neither complete nor optimal: a wall between the agent and the goal is exactly the case that defeats it
- A* — combines cost-so-far with the heuristic estimate. Optimal when the heuristic is admissible, and in practice expands a fraction of the nodes BFS does
Heuristic Design
The heuristic is where informed search is won or lost, and several were implemented and compared. Manhattan distance is the natural fit for four-directional movement: it never overestimates the true remaining cost, which makes it admissible, so A* keeps its optimality guarantee while pruning aggressively. Euclidean distance was also tested — admissible, but a weaker bound in this movement model, so it expands more nodes for the same result.
The comparison is run across five maps chosen specifically because the strategies diverge on them, including at least one large map, with the explored path rendered for each so the behavioural difference is directly observable.
Reward Collection Variant
The second half of the problem changes its nature entirely. Reward points scattered through the maze reduce total path cost when collected, and the agent is not required to collect them — which turns a shortest-path problem into constrained optimisation over which subset to collect and in what order.
This is combinatorially harder: it is a routing problem over a chosen subset, closely related to travelling-salesman-with-optional-stops. The implementation handles maps with 2, 5, and 10 reward points of differing values, and where an exact optimum is not tractable it applies a documented heuristic strategy — evaluating rewards by value against detour cost rather than collecting greedily by proximity, since a high-value reward slightly further away frequently beats a nearby low-value one.
Input Format
Maps are defined in a plain text format: a reward count, then one line per reward giving coordinates and value, then the grid itself with markers for the start position, walls, rewards, and the single exit on the boundary.
Output for every run is a rendered path with its total cost, so results are comparable across strategies at a glance.
This project is applied algorithms: implementing the classical search family correctly, designing admissible heuristics for a specific movement model, and recognising when a small change to the problem statement moves it into a different complexity class entirely.