Navigation mesh

From Wikipedia, the free encyclopedia
Jump to: navigation, search

A navigation mesh, or navmesh, is a data structure which is used to model the traversable areas of a virtual map. It is primarily used by pathfinding algorithms in video games.[1]

Description[edit]

A navigation mesh is a collection of two-dimensional convex polygons that define which areas of a virtual map are traversable by agents. Each polygon acts as a single node that links to other nodes it is adjacent to.[2] Due to the convex nature of these nodes, an agent can assume that any point in a node is reachable by travelling in a straight line from any other point in that node. Thus, because a straight line represents the shortest distance between any two points, a pathfinding algorithm will determine shorter and more natural paths when using a navigation mesh than it will with traditional waypoint-based systems.

History[edit]

Navigation meshes were invented in the early 2000s as a tool for producing shorter, more natural paths for intelligent agents in video games. At the time, most pathfinding implementations were based on either grids or waypoints due to their efficiency and ease of use. The navigation mesh became popular when the A* algorithm was adapted to it, allowing navigation mesh pathfinding to be calculated efficiently. This led to the widespread inclusion of navigation meshes in game engines.[2]

Advantages[edit]

  • Creates shorter and more natural paths than traditional grid and waypoint-based pathfinding systems.
  • Allows pathfinding algorithms to ignore static obstacles. Some implementations also ignore dynamic obstacles by regularly updating the navigation mesh to exclude them.[3]
  • A wide variety of pathfinding algorithms can be modified and optimized for using navigation meshes.

Disadvantages[edit]

  • Not as efficient as traditional grid and waypoint-based pathfinding systems.
  • Procedural generation of a navigation mesh can yield sub-optimal solutions.
  • Manual creation of navigation meshes can be time-consuming and yield flawed solutions (existence of a concave polygon, unconnected nodes, etc.).

References[edit]


  1. ^ Eberhart, Russell; Yuhui, Shi (10 August 2007). Computational Intelligence: Concepts to Implementations. Morgan Kaufmann Publishers Inc. p. 118. ISBN 1558607595. 
  2. ^ a b Bourg, David M; Seemann, Glenn (23 July 2004). AI for Game Developers. O'Reilly Media, Inc. ISBN 978-0-596-00555-9. 
  3. ^ [1]van Toll, Wouter G.; Cook IV, Atlas F.; Geraerts, Roland. "A navigation mesh for dynamic environments". Utrecht University. Retrieved 2014-10-26.