Rapidly-exploring random tree

Speed/Memory Tradeoff


An example where it might be very useful in a video game is if you have a character that can freely move around a 3D world *and rotate*. This is called the "Piano Mover's Problem." If you tried to run A* naively in this space you will quickly run out of memory. You could make A* work in this space only by doing clever and very complicated techniques involving lazy evaluation and anytime, heirarchical planning. These techniques are often very difficult to understand and end up being fairly slow anyway. This is because A* is necessarily an *optimization* procedure. It is trying to find the "best" path.

In contrast, an RRT will often give you a "good enough" path much much faster than A*, and in expectation will use far less memory than A* for high dimensional problems.

Code Example

PCG Wiki References

External Links

The Rapidly-Exploring Random Tree (RRT) Page
Rapidly Exploring Random Trees - Blog post on using RRTs to generate river basins.
