Way to go - A framework for multi-level planning in games

Path planning is one of the classical computational tasks in video games. Virtual characters need to autonomously find a path from their current position to a designated goal position. This is usually solved by running the A* algorithm on a grid or a navigation mesh. However, in many modern games, strictly following the resulting path is not sufficient. More levels of planning are necessary to efficiently simulate realistic and advanced behavior, and the underlying data structure should support those levels. In this paper, we discuss a five-level hierarchy of planning in games. Furthermore, we present a framework that provides solutions for the three center levels: global route planning, route following, and local planning. It uses an efficient and flexible navigation mesh based on the exact geometry of the environment. Our framework can be extended to solve advanced path planning problems in future games. When used as an interface for higher-level semantic planning systems, it provides a comprehensive set of techniques for game developers and path planning researchers.