Home/Precomputed Search Trees: Planning for Interactive Goal-Driven Animation

Precomputed Search Trees: Planning for Interactive Goal-Driven Animation

Manfred Lau and James Kuffner
Conference Paper, Proceedings of ACM SIGGRAPH / Eurographics Symposium on Computer Animation, January, 2006

View Publication

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.


We present a novel approach for interactively synthesizing motions for characters navigating in complex environ- ments. We focus on the runtime efficiency for motion generation, thereby enabling the interactive animation of a large number of characters simultaneously. The key idea is to precompute search trees of motion clips that can be applied to arbitrary environments. Given a navigation goal relative to a current body position, the best avail- able solution paths and motion sequences can be efficiently extracted during runtime through a series of table lookups. For distant start and goal positions, we first use a fast coarse-level planner to generate a rough path of intermediate sub-goals to guide each iteration of the runtime lookup phase. We demonstrate the efficiency of our technique across a range of examples in an interactive application with multiple autonomous characters navigating in dynamic environments. Each character responds in real-time to ar- bitrary user changes to the environment obstacles or navigation goals. The runtime phase is more than two orders of magnitude faster than existing planning methods or traditional motion synthesis techniques. Our technique is not only useful for autonomous motion generation in games, virtual reality, and interactive simulations, but also for animating massive crowds of characters offline for special effects in movies.

author = {Manfred Lau and James Kuffner},
title = {Precomputed Search Trees: Planning for Interactive Goal-Driven Animation},
booktitle = {Proceedings of ACM SIGGRAPH / Eurographics Symposium on Computer Animation},
year = {2006},
month = {January},
} 2017-09-13T10:42:59-04:00