Grab Bag Release: Rapidly-Exploring Random Trees

Almost there! I’ve finished the implementation of Rapidly-Exploring Random Trees, and added the Random Number Generator implemented by Denis Vaz Alves to the Grab Bag.

Next up are algorithms for the computation of Shortest Paths, and I’m done!

Rapidly-Exploring Random Trees

Rapidly-Exploring Random Trees are a randomized data structure designed by Steven M. LaValle for a broad class of path planning problems.

Rapidly-Exploring Random TreeEach tree lives in a configuration space that allows making motions from one configuration towards another, and has a distance function imposed on. Given a configuration space and an initial configuration, the tree can grow around that configuration until it is unable to make any further motions.

Author: npruehs

Nick Pruehs is a Co-Founder of Slash Games, Hamburg. In 2009, he graduated as “Best Bachelor” in computer science at Kiel University. Two years later Nick finished his master’s degree in “Sound, Vision, Games” at Hamburg University of Applied Sciences, becoming the Lead Programmer of Daedalic Entertainment shortly after.

2 thoughts on “Grab Bag Release: Rapidly-Exploring Random Trees”

    1. The short answer is: I already did.

      The long answer is: All of the stuff has been used before, some of them in different languages or on different platforms, though. Priority queues are great at speeding up pathfinding by a huge deal. Minimum spanning trees and Union-Find are used by the Shortest Paths-Algorithm by Thorup. Random Number Generators have been used by Denis and me in the ByChance Framework. And Graphs and Math are used by the other ones 🙂

Questions? Comments? Suggestions? Your turn! :)