AAAI Publications, Twenty-Fifth International FLAIRS Conference

Font Size: 
Generating Texture Aware Spatial Decompositions
D. Hunter Hale, G. Michael Youngblood

Last modified: 2012-05-16


This work presents an algorithm to provide a better represen- tation of space to artificially intelligent characters (i.e., agents or bots) in game and simulation environments by providing a more accurate breakdown of the traversable space present in the game environment. Such representations are generally constructed by decomposing the walkable space present in a game environment into a series of convex regions to form a data structure called a navigation mesh. We extend the basic concept of a navigation mesh by the introduction of an understanding of the textures that are attached to the underlying geometry creating what we refer to as a texture-aware navigation mesh. This does result in a more complex navigation mesh (more regions and a larger search space). However, since the textures of walkable geometry can be used to determine the appropriate traversal method for that terrain, a game character can determine valid paths for their traversal methods using just the navigation mesh (e.g., characters in cars can generate paths containing just roads or walking characters can create paths containing just sidewalks). We also present a use case that shows how such a system of texture aware naviga- tion meshes might benefit character path planning and search in virtual environments. In this use case, we examine a Real Time Strategy game style game environment, which shows it is possible to generate a navigation mesh such that each region is composed of a single terrain type.


navigation meshes, spatial decomposition, spatial data structures

Full Text: PDF