This is an old project showing how a simple rapidly exploring random tree (RRT) can work. This was mainly used to see how a RRT works and to learn a bit of C++.
A rapidly exploring random tree is a search algorithm which we can employ in an n-dimensional space (not just 2d or 3d). We explore the space by picking random points / configurations and try to connect them to the tree. The tree grows this way until the end point is found. We can then traverse the tree from the root to the end point. I came first upon this topic when reading this blog post. by Casey Muratori for the witness.
You need the sdl2 graphics library and cmake to build it.
On an arch based OS you can get the sdl2 library with:
sudo pacman -Sy sdl2.
On ubuntu it would probably be the library libsdl2 or libsdl2-dev.
sudo apt-get install libsdl2
sudo apt-get install libsdl2-dev
- clone or download the repo
git clone git@github.com:Laeri/rer_tree.git
- enter the folder and build it with cmake and make
cmake .
make
- run the binary in the bin folder
bin/rer_tree
- First left mouse click sets the starting point of the tree.
- Second click sets the endpoint.
- Then hold ctrl down and draw some obstacles with the mouse.
- Start the expansion by clicking s.
- Reset with r
s - starts or stops the tree expansion
d - set unset rect drawing (main purpose was to create images from the tree without having the rectangles there).
f - toggle fill rectangles or draw outlines
r - reset everything
left mouse - click twice for setting start and end point while the tree is expanding you can manually "help" it a bit if you want to which creates new tree points.
ctrl - while pressing the control key you can start drawing new rectangles. These rectangles represent obstacles
Escape or q - quit
You can freeze the expansion with s and raw some new obstacles if the tree makes too much progress or help it along by clicking with the mouse which instantly adds new points to the tree.
This project is licensed under the MIT License - see the LICENSE.md file for details.