Java
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:
- Initialize the tree with the starting point as root vertex
- Pick a random point within the valid parameter space
- Search the one vertex in the tree which is nearest to the random point chosen in 2.
- Move a certain distance from this vertex in the direction of the chosen point and create there a new leaf
- Loop over step 2. to 4. while the break condition is not satisfied