Robotaxi Zoox is a Python AI course project that puts five classical search algorithms head-to-head on a real pathfinding challenge: navigate a robotaxi across a grid-based city, collect every waiting passenger, and deliver them all to a shared destination. Each algorithm drives the same taxi through the same map, so you can measure — with hard numbers — exactly how BFS, DFS, UCS, Greedy Best-First, and A* differ in nodes expanded, path cost, and search time. The simulation runs inside an animated Pygame GUI with city-themed visuals and audio feedback, making abstract algorithmic concepts immediately tangible.Documentation Index
Fetch the complete documentation index at: https://mintlify.com/Juan-Carlos-Cruz/robotaxi-zoox/llms.txt
Use this file to discover all available pages before exploring further.
The Problem
The robotaxi starts at a fixed cell on a grid map and must visit every passenger cell before arriving at the single shared destination. The grid is composed of three cell types:- Free cells (roads) — traversable at standard cost.
- Wall cells (buildings) — impassable; the taxi must route around them.
- High-traffic cells (traffic lights) — traversable but carry a higher movement cost, penalising routes that cut through congested intersections.
Algorithms Included
Uninformed search (no heuristic guidance):| Algorithm | Description |
|---|---|
| BFS — Amplitud | Explores the search frontier level by level; guarantees the shortest path in terms of steps. |
| DFS — Profundidad | Dives deep along one branch before backtracking; uses cycle-avoidance to prevent infinite loops. |
| UCS — Costo uniforme | Expands nodes in order of accumulated path cost; optimal when edge costs vary. |
| Algorithm | Description |
|---|---|
| Greedy Best-First — Avara | Always expands the node that looks closest to the goal according to the heuristic; fast but not guaranteed optimal. |
| A* | Combines actual path cost with the heuristic estimate; optimal and complete when the heuristic is admissible. |
Key Design Decisions
Composite state — The search state is(position, frozenset_of_collected_passengers) rather than position alone. This lets the taxi revisit a cell after picking up a passenger without triggering a false cycle, because the state has genuinely changed.
Manhattan heuristic — Informed algorithms estimate remaining cost using Manhattan distance: if passengers are still outstanding, the distance to the nearest uncollected passenger is used; once all passengers are aboard, the distance to the destination is used. The heuristic is admissible and consistent, so A* is guaranteed optimal.
Audio feedback — The application plays looping ambient music, a road-loop sound during animation, a horn when a passenger is collected, and a jingle when the results modal opens. If pygame.mixer cannot initialise, the app continues silently.
Results modal — At the end of each run a modal overlays the map and reports nodes expanded, search depth, path steps, total cost, and search time in milliseconds (measured separately from animation time). Close the modal and run a different algorithm without restarting the application.
Explore Further
Quickstart
Run the simulation in one command and compare algorithm results in minutes.
Algorithms Overview
Deep-dive into how each of the five search algorithms is implemented.
Problem Model
Understand the grid structure, state representation, and cost model.
Grid API
Reference documentation for the Grid class and map file format.
Running in a headless environment with no graphical display? Use
make test to execute all algorithm tests without launching the GUI. This validates BFS, DFS, UCS, Greedy, and A* logic against the included maps entirely from the terminal.