AUTOMATIC CONSTRUCTION OF ROADMAPS FOR PATH PLANNING IN GAMES

Abstract

Path planning plays an important role in many computer games. Currently the motion of entities is often planned using a combination of scripting, grid-search methods, and reactive approaches. In this paper we describe a new approach, based on a technique from robotics, that computes a roadmap of smooth, collision-free, high-quality paths. This roadmap can be used to obtain instantly good paths for entities. We also describe applications of the technique for planning the motion of groups of entities and for creating smooth camera movements through an environment.