Navigation mesh

From Wikipedia, the free encyclopedia

A navigation mesh is an abstract data structure used in artificial intelligence applications to aid agents in path-finding through large spaces. Meshes that do not map to static obstacles in the environment they model offer the additional advantage that agents with access to the mesh will not consider these obstacles in path-finding, reducing computational effort and making collision detection between agents and static obstacles moot. Meshes are typically implemented as graphs, opening their use to a large number of algorithms defined on these structures.