Navigation mesh
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
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
Navigation meshes were invented in the early 2000's 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
- 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
- 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
- Brand, Sandy (2009). "Efficient obstacle avoidance using autonomously generated navigation meshes". Master thesis. Delft University of Technology.
{{cite journal}}:|access-date=requires|url=(help) - "UDK: Navigation Mesh Reference". Retrieved 2014-10-31.
- "Unity: Navigation Meshes". Retrieved 2014-11-09.
- "Steam: Navigation Meshes". Retrieved 2014-11-09.
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |
- ^ Eberhart, Russell; Yuhui, Shi (10 August 2007). Computational Intelligence: Concepts to Implementations. Morgan Kaufmann Publishers Inc. p. 118. ISBN 1558607595.
{{cite book}}:|access-date=requires|url=(help) - ^ a b Bourg, David M; Seemann, Glenn (23 July 2004). AI for Game Developers. O'Reilly Media, Inc. ISBN 978-0-596-00555-9.
{{cite book}}:|access-date=requires|url=(help) - ^ [1]van Toll, Wouter G.; Cook IV, Atlas F.; Geraerts, Roland. "A navigation mesh for dynamic environments" (PDF). Utrecht University. Retrieved 2014-10-26.