Navigation mesh

Last updated

A navigation mesh, or navmesh, is an abstract data structure used in artificial intelligence applications to aid agents in pathfinding through complicated spaces. This approach has been known since at least the mid-1980s in robotics, where it has been called a meadow map [1] , and was popularized in video game AI in 2000.

Contents

Description

A navigation mesh is a collection of two-dimensional convex polygons (a polygon mesh) that define which areas of an environment are traversable by agents. In other words, a character in a game could freely walk around within these areas unobstructed by trees, lava, or other barriers that are part of the environment. Adjacent polygons are connected to each other in a graph.

Pathfinding within one of these polygons can be done trivially in a straight line because the polygon is convex and traversable. Pathfinding between polygons in the mesh can be done with one of the large number of graph search algorithms, such as A*. [2] Agents on a navmesh can thus avoid computationally expensive collision detection checks with obstacles that are part of the environment.

Representing traversable areas in a 2D-like form simplifies calculations that would otherwise need to be done in the "true" 3D environment, yet unlike a 2D grid it allows traversable areas that overlap above and below at different heights. [3] The polygons of various sizes and shapes in navigation meshes can represent arbitrary environments with greater accuracy than regular grids can. [4]

Creation

Navigation meshes can be created manually, automatically, or by some combination of the two. In video games, a level designer might manually define the polygons of the navmesh in a level editor. This approach can be quite labor intensive. [5] Alternatively, an application could be created that takes the level geometry as input and automatically outputs a navmesh.

It is commonly assumed that the environment represented by a navmesh is static – it does not change over time – and thus the navmesh can be created offline and be immutable. However, there has been some investigation of online updating of navmeshes for dynamic environments. [6]

History

In robotics, using linked convex polygons in this manner has been called "meadow mapping" [1] , coined in a 1986 technical report by Ronald C. Arkin. [7]

Navigation meshes in video game artificial intelligence are usually credited to Greg Snook's 2000 article "Simplified 3D Movement and Pathfinding Using Navigation Meshes" in Game Programming Gems. [8] In 2001, J.M.P. van Waveren described a similar structure with convex and connected 3D polygons, dubbed the "Area Awareness System", used for bots in Quake III Arena . [9]

Notes

  1. 1 2 Tozour 2002, p. 171.
  2. ↑ Snook 2000, p. 294–295.
  3. ↑ Snook 2000, p. 289.
  4. ↑ Brand 2009, p. 4.
  5. ↑ Brand 2009, p. 10.
  6. ↑ van Toll, Cook IV & Geraerts 2012.
  7. ↑ Arkin 1986.
  8. ↑ Golodetz 2013.
  9. ↑ van Waveren 2001, p. 24–46.

Related Research Articles

Autodesk 3ds Max, formerly 3D Studio and 3D Studio Max, is a professional 3D computer graphics program for making 3D animations, models, games and images. It is developed and produced by Autodesk Media and Entertainment. It has modeling capabilities and a flexible plugin architecture and must be used on the Microsoft Windows platform. It is frequently used by video game developers, many TV commercial studios, and architectural visualization studios. It is also used for movie effects and movie pre-visualization. For its modeling and animation tools, the latest version of 3ds Max also features shaders, dynamic simulation, particle systems, radiosity, normal map creation and rendering, global illumination, a customizable user interface, new icons, and its own scripting language.

Constructive solid geometry Creating a complex 3D surface or object by combining primitive objects

Constructive solid geometry is a technique used in solid modeling. Constructive solid geometry allows a modeler to create a complex surface or object by using Boolean operators to combine simpler objects, potentially generating visually complex objects by combining a few primitive ones.

Distance transform

A distance transform, also known as distance map or distance field, is a derived representation of a digital image. The choice of the term depends on the point of view on the object in question: whether the initial image is transformed into another representation, or it is simply endowed with an additional map or field.

Havok (software) Video game middleware

Havok is a middleware software suite developed by the Irish company Havok. Havok provides a physics engine component and related functions to video games.

Polygon mesh Set of polygons to define a 3D model

In 3D computer graphics and solid modeling, a polygon mesh is a collection of vertices, edges and faces that defines the shape of a polyhedral object. The faces usually consist of triangles, quadrilaterals (quads), or other simple convex polygons (n-gons), since this simplifies rendering, but may also be more generally composed of concave polygons, or even polygons with holes.

A first-person shooter engine is a video game engine specialized for simulating 3D environments for use in a first-person shooter video game. First-person refers to the view where the players see the world from the eyes of their characters. Shooter refers to games which revolve primarily around wielding firearms and killing other entities in the game world, either non-player characters or other players.

In video games, artificial intelligence (AI) is used to generate responsive, adaptive or intelligent behaviors primarily in non-player characters (NPCs) similar to human-like intelligence. Artificial intelligence has been an integral part of video games since their inception in the 1950s. AI in video games is a distinct subfield and differs from academic AI. It serves to improve the game-player experience rather than machine learning or decision making. During the golden age of arcade video games the idea of AI opponents was largely popularized in the form of graduated difficulty levels, distinct movement patterns, and in-game events dependent on the player's input. Modern games often implement existing techniques such as pathfinding and decision trees to guide the actions of NPCs. AI is often used in mechanisms which are not immediately visible to the user, such as data mining and procedural-content generation.

In video games, a bot is a type of artificial intelligence (AI)–based expert system software that plays a video game in the place of a human. Bots are used in a variety of video game genres for a variety of tasks: a bot written for a first-person shooter (FPS) works very differently from one written for a massively multiplayer online role-playing game (MMORPG). The former may include analysis of the map and even basic strategy; the latter may be used to automate a repetitive and tedious task like farming.

In 3D computer graphics, polygonal modeling is an approach for modeling objects by representing or approximating their surfaces using polygon meshes. Polygonal modeling is well suited to scanline rendering and is therefore the method of choice for real-time computer graphics. Alternate methods of representing 3D objects include NURBS surfaces, subdivision surfaces, and equation-based representations used in ray tracers.

3D GameStudio

3D GameStudio or 3DGS is a pan 3D computer game development system which allows the users to create 3D games and other virtual reality applications, and publish them royalty-free. It includes a model/terrain editor, a level editor, a script editor/debugger and comes with a big collection of textures, models and artwork, as well as a game template system that allows the creation of basic shooter games or RPGs without programming. For complex games or other applications, either the integrated programming language named Lite-C or an external development language such as Visual C++ or Borland Delphi can be used.

Blender Game Engine

The Blender Game Engine is a free and open-source 3D production suite used for making real-time interactive content. The game engine was written from scratch in C++ as a mostly independent component, and includes support for features such as Python scripting and OpenAL 3D sound.

Lloyds algorithm

In electrical engineering and computer science, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is an algorithm named after Stuart P. Lloyd for finding evenly spaced sets of points in subsets of Euclidean spaces and partitions of these subsets into well-shaped and uniformly sized convex cells. Like the closely related k-means clustering algorithm, it repeatedly finds the centroid of each set in the partition and then re-partitions the input according to which of these centroids is closest. In this setting, the mean operation is an integral over a region of space, and the nearest centroid operation results in Voronoi diagrams.

Procedural animation Type of computer animation

A procedural animation is a type of computer animation, used to automatically generate animation in real-time to allow for a more diverse series of actions than could otherwise be created using predefined animations.

Action selection is a way of characterizing the most basic problem of intelligent systems: what to do next. In artificial intelligence and computational cognitive science, "the action selection problem" is typically associated with intelligent agents and animats—artificial systems that exhibit complex behaviour in an agent environment. The term is also sometimes used in ethology or animal behavior.

Any-angle path planning

Any-angle path planning algorithms are a subset of pathfinding algorithms that search for a path between two points in space and allow the turns in the path to have any angle. The result is a path that goes directly toward the goal and has relatively few turns. Other pathfinding algorithms such as A* constrain the paths to a grid, which produces jagged, indirect paths.

In artificial intelligence research, the situated approach builds agents that are designed to behave effectively successfully in their environment. This requires designing AI "from the bottom-up" by focussing on the basic perceptual and motor skills required to survive. The situated approach gives a much lower priority to abstract reasoning or problem-solving skills.

xaitment is a German-based company that develops and sells artificial intelligence (AI) software to video game developers and simulation developers. The company was founded in 2004 by Dr. Andreas Gerber, and is a spin-off of the German Research Centre for Artificial Intelligence, or DFKI. xaitment has its main office in Quierschied, Germany, and field offices in San Francisco and China.

Autodesk Gameware is a discontinued middleware software suite developed by Autodesk. The suite contained tools that enable designers to create game lighting, character animation, low level path finding, high-level AI and advanced user interfaces. On July 12, 2017, Autodesk removed Scaleform, Beast, HumanIK and Navigation from their online store, and announced the ending of support for the products.

Real-Time Path Planning is a term used in robotics that consists of motion planning methods that can adapt to real time changes in the environment. This includes everything from primitive algorithms that stop a robot when it approaches an obstacle to more complex algorithms that continuously takes in information from the surroundings and creates a plan to avoid obstacles.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.