Gabriel Ware asks “How 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 AiGameDev.com, 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.

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.

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.

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:

• Motion Strategy Library

It’s C++ and seems to have many algorithms and collision strategies that you can experiment with!