Applying Rapidly-exploring Random Trees to Games

Alex J. Champandard on October 19, 2007

Gabriel Ware asksHow do you apply RRT (Rapidly-exploring 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, this is a particularly interesting question for next-gen games. But I also believe this kind of technology can help reduce costs of low-budget productions also, although it may need a little more applied research.

Rapidly-exploring 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 data-structures, then discuss ways they can be applied to games and artificial intelligence.

Rapidly-exploring Random Tree

Figure 1: A Rapidly-exploring Random Tree searching a 2D space.

A Quick Overview of RRT

Rapidly-exploring Random Trees provide a way to search high-dimensional spaces efficiently. They consist of a tree data-structure of samples in the space, and an algorithm to create the tree in a way that provides good coverage. The tree-construction algorithm basically a loop that repeats the following operations:

  1. Pick a random sample in the search space.

  2. Find the nearest neighbor of that sample.

  3. Select an action from the neighbor that heads towards the random sample.

  4. Create a new sample based on the outcome of the action applied to the neighbor.

  5. 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.

RRT Algorithm

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 under-researched.

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 Motion-Graphs

More games are using very advanced context-sensitive 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 motion-graph” that can take over control locally to provide responsive and realistic animations.

Automatically Generating Navigation Graphs

The ideas behind rapidly-exploring 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 non-random samples from an in-game 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 path-node 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 motion-captured 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 Rapidly-exploring Random Trees to motion planning on a logical level, like motion graphs on steroids. See this paper (PDF, 679 Kb) entitled “Fast and Accurate Goal-directed 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.

Nonholonomic car driving.

Figure 3: A nonholonomic navigation problem: driving a car.

Existing Libraries

The Rapidly-exploring 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

Ian Morrison on October 19th, 2007

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.

alexjc on October 20th, 2007

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

gware on October 22nd, 2007

Ian, You may want to take a look at RRT-Plan 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 !

alexjc on October 28th, 2007

[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

alexjc on November 1st, 2007

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

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!