High quality navigation in computer games

Navigation plays an important role in many modern computer games. Currently the motion of entities is often planned using a combination of scripting, grid-search methods, local reactive methods and flocking. In this paper we describe a novel approach, based on a technique originating from robotics, that computes a roadmap of smooth, collision-free navigation paths. Because the vast amount of computation time is spent in the pre-processing phase, navigation during the execution of an application is almost instantaneous. The created roadmap can be queried to obtain high quality paths. Furthermore, the applications of the roadmap are not limited to navigating an entity. Therefore, besides navigation for an entity, two other applications are presented; one for planning the motion of groups of entities and one for creating smooth camera movements through an environment. All applications are based on the same underlying techniques.