README.md

Pathfinding Visualizer

A tool for visualizing numerous pathfinding algorithms in two dimensions.

This project involves minimal implementations of the popular planning algorithms, including both graph-based and sampling-based planners. We provide an easy-to-use GUI to control the animation process and explore different planner configurations. Current implementation of the project involves four search-based planning algorithms: BFS, DFS, DIJKSTRA and A-Star and two sampling-based planners: RRT and RRT*. The project extensively uses SFML, ImGui and Modern C++ features such as smart pointers, lamda expressions along with multi-threading concepts.

Dependencies

• cmake >= 3.14
  • All OSes: click here for installation instructions
• make >= 4.1 (Linux, Mac), 3.81 (Windows)
  • Linux: make is installed by default on most Linux distros
  • Mac: install Xcode command line tools to get make
  • Windows: Click here for installation instructions
• gcc/g++ >= 5.4
  • Linux: gcc / g++ is installed by default on most Linux distros
  • Mac: same deal as make - install Xcode command line tools
  • Windows: recommend using MinGW

Basic Build Instructions

The project depends on SFML, Dear ImGui and ImGui-SFML. However, you are not required to install external dependencies by yourself. The following build instructions will manage all the necessary external dependencies for you.

1. Clone this repo.
2. Make a build directory in the top level project directory: mkdir build && cd build
3. Compile: cmake .. && make
4. Run it: ./main.

TODO

Graph-based planners

• BFS
• DFS
• DIJKSTRA
• A*
• Bidirectional-A*
• D*
• LPA*

Sampling-based planners

• RRT
• RRT-Connect
• RRT*
• Informed-RRT*
• FMT*
• BIT*
• ABIT*
• AIT*

Related Publications

• DIJKSTRA: A Note on Two Problems in Connexion with Graphs
• A*: A Formal Basis for the Heuristic Determination of Minimum Cost Paths
• LPA*: Lifelong Planning A*
• RRT: Randomized kinodynamic planning
• RRT*: Sampling-based algorithms for optimal motion planning