Rapidly-exploring Random Tree

This applet demonstrates an search algorithm for path finding. Starting at a certain point the search tree will rapidly expand through parameter space. In this example the 2 dimensional field is used as the parameter space in which the red obstacles mark prohibited parameter combinations.

How does it works?

The algorithm itself is pretty simple:

  1. Initialize the tree with the starting point as root vertex
  2. Pick a random point within the valid parameter space
  3. Search the one vertex in the tree which is nearest to the random point chosen in 2.
  4. Move a certain distance from this vertex in the direction of the chosen point and create there a new leaf
  5. Loop over step 2. to 4. while the break condition is not satisfied

Java/rrt (last edited 2008-04-01 15:46:01 by StefanEngelke)