Path Planning Visualizer

An interactive visualization tool for comparing different pathfinding algorithms. This project demonstrates three fundamental graph search algorithms used in robotics and game development: Dijkstra's Algorithm, A Search*, and Breadth-First Search (BFS).

Features

• Interactive GUI: Click to set start point, goal point, and draw/erase obstacles
• Real-time Visualization: Watch the algorithms explore the world in real-time
• Three Algorithms:
  • Dijkstra's Algorithm: Guarantees shortest path; explores nodes uniformly in all directions
  • Astar Search: Uses heuristics for faster pathfinding while maintaining optimality
  • Breadth-First Search (BFS): Simple but complete search algorithm; works well on uniform grids
• Obstacle Handling: Dynamically add and remove obstacles to see how algorithms adapt
• Performance Comparison: Visualize the difference in exploration patterns between algorithms

Demo

Requirements

• Docker

Installation & Usage

1. Clone the repository

   git clone https://github.com/yourusername/path-planning-visualizer.git
   cd path-planning-visualizer

2. Build the Docker image

   docker build -t path-planning-visualizer .

3. Enable X11 forwarding for GUI display (Ubuntu only)

   xhost +

4. Run the visualizer

   docker run -it --rm -e DISPLAY=$DISPLAY \
     -v /tmp/.X11-unix:/tmp/.X11-unix \
     -v ~/.Xauthority:/root/.Xauthority:ro \
     path-planning-visualizer

How to Use

Once the application starts, you can:

• Select any algorithm from the dropdown menu at the top
• Compare algorithms by switching between them with the same obstacle layout
• Visualize in real-time as you modify obstacles

GUI Controls

• Algorithm Dropdown: Select which algorithm to use (Dijkstra, A*, or BFS)
• Left Click & Drag: Draw obstacles
• Right Click & Drag: Erase obstacles
• Shift + Left Click: Set the start point (yellow)
• Ctrl + Right/Middle Click: Set the goal point (magenta)
• Clear Button: Reset all obstacles
• Quit Button: Exit the application

Visualization

The visualization shows:

• Yellow circle: Start point
• Magenta circle: Goal point
• Red areas: Obstacles
• Green gradient: Explored/visited nodes (intensity represents distance)
• White path: The computed optimal solution

The algorithm will automatically compute and display the path whenever you:

• Modify obstacles
• Change start/goal positions
• Switch to a different algorithm

Architecture

The project uses a clean, modular structure:

• main.py: Single entry point that initializes and runs the unified UI
• app/ package: UI shell and thin bindings (no Python algorithm implementations)
  • algorithms.py: Provides AlgorithmBase plus C++ wrappers (Dijkstra, A*, BFS)
  • gui.py: Enhanced Tkinter GUI with algorithm selection dropdown
  • common.py: Shared utility functions for visualization
• algorithms/ folder: High-performance C++ implementations only
  • dijkstra.cpp: Dijkstra's shortest path algorithm
  • astar.cpp: A* heuristic search algorithm
  • bfs.cpp: Breadth-First Search algorithm
• Documentation: Complete guides for setup, GitHub, and GIF recording

Contributing

Contributions are welcome! Feel free to:

• Add more algorithms (Jump Point Search, Theta*, RRT, etc.)
• Improve the visualization
• Add performance metrics
• Optimize existing implementations
• Add unit tests

License

This project is based on educational materials by Claus Brenner (original GUI and framework). Extensions and modifications are available for educational and research purposes.

References

• Dijkstra's Algorithm - Wikipedia
• A* Search Algorithm - Wikipedia
• Breadth-First Search - Wikipedia
• Path Planning in Robotics

Author

Visualization and comparison framework created with educational purposes in mind. Based on foundational work by Claus Brenner.