Rapidly-Exploring Random Tree
overview
I created a simple 2-D RRT algorithm in Python that is able to avoid obstacles while exploring a map for a goal position. The obstacles are black circles of varying sizes, and both the number of circles and their sizes are randomly generated each time a new map is created. The start position (green dot) and goal position (red "X") are also randomly generated each time a new map is created.
For generating the random tree, a new point is randomly placed on the map. I then check which point on the tree this new point is nearest to, and then I add a new point on the tree that is a unit distance away and in the direction of the randomly generated point. To avoid obstacles, I check if the coordinates of the new point that I am trying to add to the tree is within the radius of a circle. If so, the new point is not added, and a new random point is placed on the map. To find the goal, I check if there is a clear path between the generated goal position and the newly added point on the tree. If so, a path is connected between those two points and the entire path is highlighted in red. If not, a new random point is placed on the map.