Lecture
A navigation mesh, or navmesh (navigation mesh), is an abstract data structure used in artificial intelligence programs to help agents find paths through complex spaces. This approach has been known at least since the mid-1980s in robotics, where it was called a "meadow map," and was popularized in game AI in the year 2000.
A navigation mesh is a collection of two-dimensional convex polygons (a polygonal mesh) that define which areas of the environment agents can traverse. In other words, a character in a game can freely walk across these areas without being obstructed by a tree, a bench, or other obstacles that are part of the environment. Adjacent polygons are connected to one another in a graph.
Determining contours within one of these polygons can be done trivially in a straight line, since the polygon is convex and traversable.
Representing traversable areas in a 2D-like form simplifies calculations that would otherwise have to be done in a "true" 3D environment; however, unlike a 2D grid, it allows for traversable areas that overlap above and below at different heights. Polygons of different sizes and shapes in navigation meshes can represent arbitrary environments with greater accuracy than regular grids.
A navigation mesh in a game (often called a navigation mesh or navmesh) is a simplified geometric structure that indicates where characters can move. It looks like a network of polygons (usually triangles or quadrilaterals) stretched across the surface of the levels. Here is how it can be represented:
Flat or contoured polygons covering traversable areas;
Bright boundaries separating zones where movement is possible from obstacles;
Sometimes — arrows or directions of movement, if the navmesh uses flow field data;
Gaps or "holes" in places where one cannot walk (for example, water, walls, cliffs).
Visually this resembles a simplified map of the level, ruled into pieces, where each piece is a potential point for NPC movement. In editors or debug modes, it is usually displayed as a semi-transparent mesh overlaid on the scene.
Compared to navigation points, navigation meshes have the following advantages:
Navigation meshes can be created manually, automatically, or through a certain combination of both. In video games, a level designer can manually define the navmesh polygons in a level editor.
It is generally accepted that the environment represented in a navmesh is static — it does not change over time — and, consequently, a navmesh can be created offline and left unchanged. However, some research has been conducted on online updating of navigation meshes for dynamic environments.
A navigation map is created based on the level geometry (manually or automatically).
Navigation agents (NPCs, enemies, allies) use the NavMesh for pathfinding.
In conjunction with an algorithm (most often A*), the agent calculates the shortest route to the target.
In robotics, the use of linked convex polygons in this way was called "meadow mapping," coined in a 1986 technical report by Ronald C. Arkin.
Navigation meshes in video game AI are generally attributed to Greg Snook's 2000 article "Simplified 3D Movement and Pathfinding Using Navigation Meshes" in "Game Programming Gems." The "Area Awareness System" was used for bots in Quake III Arena.
Implementing a navigation mesh actually involves three algorithms:
A* is most often used to find the optimal path
| Game genre | NavMesh application |
|---|---|
| 3D Action/RPG | Enemies search for a path to the player |
| 2D platformers | Jumping across platforms and avoiding cliffs |
| Strategy games | Groups of units navigate around buildings and objects |
| Crowd simulators | People avoid colliding with one another |
Comments