Gabriel Ware asks “How do you apply RRT (Rapidlyexploring Random Trees) and its derivatives to games? Is there any middleware for such algorithms?
Also, do you think it can be used to create more believable paths for units evolving in ‘unknown environment’, for example when entering a forest?“
In light of all the animation algorithms I’ve reviewed here on AiGameDev.com, this is a particularly interesting question for nextgen games. But I also believe this kind of technology can help reduce costs of lowbudget productions also, although it may need a little more applied research.
Rapidlyexploring Random Trees and Motion Strategy Algorithms Steven M. LaValle (url) Lecture Slides, INRIA, 1999 (PS.GZ, 1.4Mb)
Taking illustration from these slides, I’ll first write a brief overview of RRT algorithms and datastructures, then discuss ways they can be applied to games and artificial intelligence.
Figure 1: A Rapidlyexploring Random Tree searching a 2D space.
A Quick Overview of RRT
Rapidlyexploring Random Trees provide a way to search highdimensional spaces efficiently. They consist of a tree datastructure of samples in the space, and an algorithm to create the tree in a way that provides good coverage. The treeconstruction algorithm basically a loop that repeats the following operations:
Pick a random sample in the search space.
Find the nearest neighbor of that sample.
Select an action from the neighbor that heads towards the random sample.
Create a new sample based on the outcome of the action applied to the neighbor.
Add the new sample to the tree, and connect it to the neighbor.
The basic idea of the algorithm is very simple, though it relies on some custom logic in step three which depends on your problem.
Figure 2: Illustrating the RRT algorithm.
What Problems do RRT Solve?
Generally speaking, applications of RRT fall into three academic disciplines, corresponding to three classes of problems in practice.
Holonomic Motion Planning — Also known as the piano moving problem. “Holonomic” means that the constraints on the system does not depend on the velocity or momentum.
Nonholonomic Motion Planning — This is the driving cars problem, because the constraints on the object don’t depend only on its coordinates (velocity and momentum comes into play).
Kinodynamic Motion Planning — It involves thrusting spacecrafts around. This is the most complex type of problem and is still underresearched.
The first category of problems is rather easy to solve these days, but the other two need more work.
Applying RRT to Games
Where can you use an algorithm that explores space? Most notably at in AI/animation, whether it’s about navigation or a precision control.
 Creating Physically Situated MotionGraphs

More games are using very advanced contextsensitive animations like climbing and jumping in Assassin’s Creed or Prince of Persia’s 3D remake. These animations need to be responsive, realistic, and physically accurate, so they are critical to the gameplay.
What RRT can offer is to create motion graphs that are situated in space. The idea is that you take a set of animations for climbing or jumping, and then let the algorithm build a graph of the possible movements in complex situations (like climbing a difficult building). In the end, you get a “situated motiongraph” that can take over control locally to provide responsive and realistic animations.
 Automatically Generating Navigation Graphs

The ideas behind rapidlyexploring random trees are generally very useful for covering complex spaces. They’re very similar to other techniques such as growing neural gas networks. These ideas can be adapted for generating waypoint networks automatically.
In my thesis (RAR, 1.5Mb), I developed an incremental algorithm that’s very similar to RRT. (If only I’d known!) The key differences are that it builds a network rather than a tree, it uses nonrandom samples from an ingame actor’s position, and collision information is used to help simplify the network.
Effectively, this kind of technology is really useful for generating various levels of detail in a pathnode network.
 Planning Detailed Animation at Runtime

Of course, animation is also a big application for this algorithm. As discussed in this paper on interactive object manipulation, you can use RRT to generate motion that respects the physical constraints of its environment.
If you want to adjust individual limbs, you have to base the algorithm off a motioncaptured animation. This paper in particular applies the planning to specific limbs only, such as hands and feet. After the algorithm, a significant amount of smoothing is necessary to maintain realism.
Of course, with a few modifications, you could apply Rapidlyexploring Random Trees to motion planning on a logical level, like motion graphs on steroids. See this paper (PDF, 679 Kb) entitled “Fast and Accurate Goaldirected Motion Synthesis for Crowds“.
In summary, you can apply RRT to games very successfully, but be sure to use them to enhance existing techniques (whether animation or navigation). It’ll be easier to work with, present fewer risks, and offer greater results in the end.
Figure 3: A nonholonomic navigation problem: driving a car.
Existing Libraries
The Rapidlyexploring Random Tree algorithm is extremely simple. The bulk of your code will be in the application domain itself, so animation or navigation as the case may be. You’ll need to be able to find nearest neighbors efficiently, generate random samples, and build new solutions biased towards a particular point.
For full motion planning, there’s a library available:
It’s C++ and seems to have many algorithms and collision strategies that you can experiment with!
Discussion 5 Comments
As always, neat stuff. I can't help but wonder, though: could something like this be modified for decision making in the same way that A* is a fairly general algorithm for searching? Without having looked too closely at the technique, it seems as though it might be a good strategy for an agent that needs to plan through very complex environments with many options, which might have applications in open world games along the veins of Oblivion.
Ian, That's a really interesting point. Come to think of it, they seem to complement each other quite well. A* is much more guided towards a target via the heuristic, whereas RRT is about general exploration... However, in some cases (e.g. dual RRT) two trees search towards each other... The big difference is that A* assumes the graph exists, and RRT builds the search structure on the fly (the graph is too complex). I think they both can be considered "search" and/or "decision making" algorithms, just targeting different kinds of search spaces (discrete vs. continuous). Interesting train of thought though :) Alex
Ian, You may want to take a look at RRTPlan which is a strips planning algorithm (i.e. you define a domain, actions, preconditions, effects, goal and start state and it creates a plan). The main issue one will probably face implementing such strategy comes from the sampling part of the algorithm. Before implementing such algorithm you will have to answer : "How do I sample the domain?". Plus, it uses a subplanner (in order to plan from the nearest point to the random point), meaning you may have to implement another planning algorithm. From what I can tell A* uses a graph built using workspace information, this is the main difference with RRT algorithm. This said, if you have workspace information, you may be able to direct the search in some way. Take a look at OBRRT (Obstacle based rrt) which uses obstacles information to direct the growing tree. I'd be glad to know if anyone has previously used these algorithms in their pipe or at runtime. Thanks Alex for giving us some examples of practical applications in the gaming industry !
[B]Gabriel[/B], I've not heard much about this algorithm generally, so I would be very surprised if it had been used in games. The only place you're likely to find it is for advanced animation systems at the moment... Alex
Another example of RRT in games is to apply them to special cases tha are particularly difficult, for example crash recovery in racing games. If a car ends up in a weird position and it needs to get back on the track, then often you'll need the strength of a planner to be able to do that without resetting the car. Alex