Graph traversal & sampling-based planning explorer
Draw walls or mud on the grid, drag the start (S) and goal (G), then watch each method work.
Graph traversal searches the grid cells directly
Sampling-based planners build a random roadmap or tree in continuous space
Paint tool:
click or drag on the grid
StartGoalFrontierExpanded / treePathMud
Expanded0Path length –Path cost –
| Method | Data structure | Optimal? | Uses weights? | Uses heuristic? |
|---|---|---|---|---|
| BFS | Queue (FIFO) | Fewest steps only | No | No |
| DFS | Stack (LIFO) | No | No | No |
| Dijkstra | Priority queue on g | Yes | Yes | No |
| A* | Priority queue on g + h | Yes (admissible h) | Yes | Yes |
| PRM | Roadmap (fixed k), then any graph search | Optimal on the roadmap only | Edge lengths (mud 5×) | Depends on search |
| PRM* | Roadmap (shrinking radius), then any graph search | Optimal as samples → ∞ | Edge lengths (mud 5×) | Depends on search |
| RRT | Random tree | No (probabilistic) | Path cost reported | Goal bias |
| RRT* | Random tree with parent choice and rewiring | Optimal as samples → ∞ | Yes (mud 5×) | Goal bias |