This project is an interactive tool designed to visualize, compare, and analyze pathfinding and motion planning algorithms in real-time. It provides an intuitive graphical interface to understand how different algorithms behave under dynamic conditions.
| Algorithm | Type | Strategy |
|---|---|---|
| BFS | Grid | Unweighted FIFO queue -- explores layer by layer |
| Dijkstra | Grid | Priority queue on g-cost -- optimal shortest path |
| A* | Grid | Priority queue on g + Manhattan heuristic -- optimal, fewer nodes than Dijkstra |
| Greedy Best-First | Grid | Priority queue on h-cost only -- fast but non-optimal |
| RRT | Sampling | Random tree expansion in continuous space with collision detection |
| RRT* | Sampling | RRT with tree rewiring -- converges toward shorter paths |
- BFS vs Dijkstra -- identical on an unweighted grid, but Dijkstra generalizes to weighted graphs
- A vs Greedy* -- A* guarantees optimal paths (uses g + h); Greedy visits far fewer nodes but may find longer paths (uses h only)
- RRT vs RRT* -- RRT finds any feasible path quickly; RRT* rewires the tree to progressively shorten it
- Python 3.10+
- pygame-ce (community edition, supports Python 3.12+)
pip install -r requirements.txtpython main.py| Action | Input |
|---|---|
| Place start point | First left-click on grid (green) |
| Place end point | Second left-click on grid (red) |
| Draw obstacles | Left-click or drag on grid (gray walls) |
| Select algorithm | Click toggle buttons (top-right panel) |
| Run algorithm | Click Start |
| Switch algorithm | After completion, pick another algorithm and click Start again |
| Reset everything | Click Clear |
| Scale charts | Click - / + next to "Chart Size" |
| Scroll analytics | Mouse wheel or drag the scrollbar |
| Quit | Press Esc or close the window |
Three red circles bounce around the grid continuously. When you click Start, the algorithm plans a path that avoids the obstacles based on their current positions. If an obstacle later crosses the found path:
- The path flashes red/orange
- The status shows "PATH BLOCKED!"
- Click Start again to re-plan around the obstacles' new positions
The algorithm runs exactly once per click -- no automatic re-runs.
The right sidebar tracks metrics across all algorithm runs on the same grid:
- Comparison table -- Time (ms), Nodes Visited, and Path Length for each algorithm
- Bar charts -- three chart groups (Time, Nodes, Path Length) with horizontal bars scaled relative to the max value
- Chart Size +/- -- increase or decrease bar thickness, text size, and spacing
- Scrollbar -- drag the thumb or use mouse wheel when content overflows
Results accumulate across runs, so you can run all six algorithms on the same grid and compare them side by side.
Algorithm Simulation/
|-- main.py Entry point and game loop
|-- constants.py Colors, dimensions, algorithm parameters
|-- grid.py 50x50 grid with obstacle storage and neighbor queries
|-- state.py App state machine (SETUP -> RUNNING -> DONE)
|-- renderer.py Draws grid, visited cells, paths, obstacles
|-- ui.py Button, AlgorithmToggle, AnalyticsPanel with scrollbar
|-- obstacles.py Dynamic obstacle circles with bounce and collision
|-- algorithms/
| |-- base.py StepResult and RRTNode dataclasses
| |-- collision.py Shared segment-rect/circle collision utilities
| |-- bfs.py BFS generator
| |-- dijkstra.py Dijkstra generator
| |-- astar.py A* generator
| |-- greedy.py Greedy Best-First generator
| |-- rrt.py RRT generator
| |-- rrt_star.py RRT* generator
| |-- __init__.py Re-exports all algorithm functions
|-- requirements.txt pygame-ce dependency
|-- README.md
Each algorithm is a Python generator that yields a state snapshot after every node expansion (grid algorithms) or tree-edge attempt (RRT/RRT*). The main loop calls next(generator) several times per frame to animate exploration at a visible pace. This avoids threading entirely -- the generator preserves its local state (priority queue, visited set, tree) between yields.
- BFS, Dijkstra, A*, Greedy operate on
(row, col)grid coordinates.Grid.get_neighbors()returns 4-connected neighbors (up, down, left, right). - RRT, RRT* operate in continuous pixel space
(0-800, 0-800). Steering uses vector math:q_new = q_near + normalize(q_rand - q_near) * step_size. RRT uses 5% goal-bias in random sampling.
The renderer dispatches to cell-drawing or line-drawing methods based on the active algorithm type.
Static obstacles are grid cells. Dynamic obstacles are circles. The collision module (algorithms/collision.py) provides:
- Circle-rect intersection -- for grid cell vs dynamic obstacle overlap
- Segment-rect intersection -- for RRT edge vs static obstacle
- Segment-circle intersection -- for RRT edge vs dynamic obstacle (quadratic formula on parametric ray)
SETUP --> RUNNING --> DONE
^ |
| (Clear) | (Start again)
+------------------------+
- SETUP -- place start, end, obstacles; select algorithm
- RUNNING -- generator stepping, obstacles moving, toggle disabled
- DONE -- path found, toggle re-enabled, obstacles still moving, path-blocked detection active
+===========================================+=========================+
| | [BFS|Dijkstra|A* ] |
| Grid Visualization | [Greedy|RRT |RRT* ] |
| 800 x 800 pixels | [Start] [Clear] |
| 50x50 cells, 16px each | |
| | State: DONE |
| [start] .............. [end] | Algorithm: A* |
| ..obstacles... | |
| ..(walls)..... | Chart Size [- ][+]|
| | --- Comparison --- |
| ( ) <-- dynamic obstacles | Algo Time Nodes Path |
| bouncing around | BFS 0.3 70 18 |
| | Dijk 0.4 70 18 |
| | A* 0.3 60 18 |
| | Grdy 0.1 19 18 |
| | |
| | [Bar Charts] |
| | Time / Nodes / Path |
+===========================================+=========================+
800px 400px
- A* heuristic: Manhattan distance
h(n) = |x1 - x2| + |y1 - y2| - RRT steering:
q_new = q_near + ((q_rand - q_near) / |q_rand - q_near|) * step_size - RRT* rewire radius:
r = gamma * sqrt(log(n) / n)where gamma = 50 and n = tree size