Navigating Jumping Agents Through Virtual Environments

Abstract

In many computer games and crowd simulations, a navigation mesh is used as the underlying data structure for navigating agents through the virtual environment. A navigation mesh defines the areas where the agents are allowed to walk, and it enables agents to compute walkable paths through the environment. However, a navigation mesh does not provide information about where the agents are allowed to jump, so it does not support the discovery of paths that include jumps over gaps and obstacles. As a result, the agents will often take long detours to move to their designated positions. They will always walk around the obstacles in the environment, and will never take shortcuts by jumping over them.

In this MSc thesis, we present algorithms for extending navigation meshes with jump links, which are objects that represent valid jumps in the environment. Our approach can generate these links fully automatically, and works on any environment that is defined by a triangle soup. In addition, we present algorithms for planning paths on navigation meshes that are extended with jump links. These algorithms enable the agents to find new paths through the environment, which include jumps over gaps and obstacles. We have implemented our methods as an extension to Recast Navigation, which is a commonly-used software package for generating navigation meshes. Our experiments show that this implementation is capable of producing commodious sets of jump links for large and complex environments in a matter of seconds. This makes our implementation a useful extension to the Recast Navigation pipeline, enabling it to produce navigation meshes for applications that involve jumping agents.