Skip to content

C++ Implementation of Path Planning Algorithms based on the Python Implementation by Huiming Zhou (https://github.com/zhm-real)

License

Notifications You must be signed in to change notification settings

ahmedadamji/PathPlanning

Repository files navigation

Path Planning Algorithms and Visualization in C++


Overview

This repository contains the C++ Implementation of Path Planning Algorithms of some common path planning algorithms used in robotics, including Search-based algorithms and Sampling-based algorithms based on the Python Implementation by Huiming Zhou. The algorithms can be visualized using the custom plotting class, which includes the generation of a new environment during each run for the grid-based planners, and an interactive dynamic environment developed to showcase dynamic algorithms. The related papers are listed in ZHM-REAL's original Python repository Papers.


Dependencies

The following dependencies are required to build and run the programs:

  • OpenCV 2.4 or later: Install OpenCV from https://opencv.org/releases/ or use your package manager.
  • ImageMagick++ (Magick++): Install ImageMagick++ from the official ImageMagick website or use your package manager. On many systems, installing libmagick++-dev (for Debian/Ubuntu) using sudo apt-get install libmagick++-dev or ImageMagick-c++-devel (for Red Hat/Fedora) using sudo dnf install ImageMagick-c++-devel should suffice.

Please make sure you have installed the required dependencies before compiling and running the programs.


Compilation and Build

Clone the repository:

git clone https://github.com/ahmedadamji/PathPlanning.git
cd PathPlanning

Make sure you have CMake installed. If not, install it from https://cmake.org/download/.

Create a build directory and navigate into it:

mkdir build
cd build

Run CMake to configure the build:

cmake ..

Build the project:


Running the Programs

Search_2D

To run the search-based algorithms (A*, Dijkstra, Best-First, etc.):

Open the terminal and navigate to the build directory.

Run the executable for the search_2D program:

./PathPlanning

The program will visualize the path planning algorithms on a 2D grid environment.

RRT_2D

To run the sampling-based algorithm (RRT-Connect):

Open the terminal and navigate to the build directory.

Run the executable for the rrt_2D program:

./SamplingBasedPlanning2D

The program will visualize the RRT-Connect algorithm on a 2D grid environment.

Note: In each main file, you can comment/uncomment the specific algorithm instantiation to choose which algorithm to run.


Animations - Search Based Planning

BFS

BFS

DFS

DFS

Dijkstra

Dijkstra

Best-First Search

Best-First

A* Search

A*

Repeated A* Search

Repeated A*

Bidirectional A* Search

Bidirectional A*

ARA* Search

ARA*

LRTA* Search

LRTA*

RTAA* Search

RTAA*

Animations - Sampling-Based

RRT 2D

RRT 2D

Goal Biased RRT

Goal Biased RRT

RRT Connect

RRT Connect


Acknowledgments

Thanks to Huiming Zhou for providing the original Python implementation and related papers for the path planning algorithms.