Drag[en]gine Wiki

User Tools

Site Tools

Trace:
gamedev:navigation

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
Next revisionBoth sides next revision
gamedev:navigation [2011/07/22 11:44] – dragonlordgamedev:navigation [2012/12/01 17:45] – dragonlord
Line 1: Line 1:
 +<WRAP youarehere>
 +[[:start|Start Page]] >> [[gamedev:main|Game Development with the Drag[en]gine]] >> **Navigation System**
 +</WRAP>
 +
 ====== Navigation System ====== ====== Navigation System ======
 <WRAP box 250px right :en>{{ :gamedev:images:navigation_sample_world.jpg?200 |Example world to navigate}}<WRAP centeralign>Example world to navigate</WRAP></WRAP> <WRAP box 250px right :en>{{ :gamedev:images:navigation_sample_world.jpg?200 |Example world to navigate}}<WRAP centeralign>Example world to navigate</WRAP></WRAP>
Line 13: Line 17:
 The **AI Module** provides support to solve the navigation problems using this system. The **AI Module** provides support to solve the navigation problems using this system.
  
-===== Navigation Spaces =====+====== Navigation Spaces ======
 Navigation problems alway take place in one or more navigation spaces depending on the need of the game. There exist different kinds of navigation spaces that can be used each of them having different properties. These are **navigation grids**, **navigation meshes** and **navigation volumes**. The **Navigation Space** class is an all-round class able to describe all supported navigation spaces in one place. The type of space described with a Navigation Space object is set using the **type** parameter. If the navigation does not work properly make sure each navigation space has the matching **type** parameter set. Navigation problems alway take place in one or more navigation spaces depending on the need of the game. There exist different kinds of navigation spaces that can be used each of them having different properties. These are **navigation grids**, **navigation meshes** and **navigation volumes**. The **Navigation Space** class is an all-round class able to describe all supported navigation spaces in one place. The type of space described with a Navigation Space object is set using the **type** parameter. If the navigation does not work properly make sure each navigation space has the matching **type** parameter set.
  
Line 22: Line 26:
 Navigation spaces are considered to be static in respect to their content. It is allowed to change the layout of a navigation space at runtime but the performance could suffer. The position and orientation of a navigation space though is allowed to change. This allows to simulate dynamic navigation spaces like for example a connected set of moving platforms. There the layout of the platforms itself does not alter but the location of the entire group of platforms does. Due to the static nature the elements in a navigation space are defined as continuous arrays. Hence you do not add elements to the navigation space but you set first the total number of elements you want to use and then you set each element in turn. If you have to change the layout of a navigation space you have to call the **Notify Layout Changed** to tell the AI Module that you finished changing the layout of the navigation space. Navigation spaces are considered to be static in respect to their content. It is allowed to change the layout of a navigation space at runtime but the performance could suffer. The position and orientation of a navigation space though is allowed to change. This allows to simulate dynamic navigation spaces like for example a connected set of moving platforms. There the layout of the platforms itself does not alter but the location of the entire group of platforms does. Due to the static nature the elements in a navigation space are defined as continuous arrays. Hence you do not add elements to the navigation space but you set first the total number of elements you want to use and then you set each element in turn. If you have to change the layout of a navigation space you have to call the **Notify Layout Changed** to tell the AI Module that you finished changing the layout of the navigation space.
  
-==== Navigation Grid ====+===== Navigation Grid =====
 <WRAP box 250px right :en>{{ :gamedev:images:navigation_grid.jpg?200 |Sample Navigation Grid}}<WRAP centeralign>Sample Navigation Grid</WRAP></WRAP> <WRAP box 250px right :en>{{ :gamedev:images:navigation_grid.jpg?200 |Sample Navigation Grid}}<WRAP centeralign>Sample Navigation Grid</WRAP></WRAP>
 Navigation grids are useful for navigation problems where an exact and smooth path is not required. This is usually used for coarse grained navigation typically not directly linked to a visible world or checker board type navigation. In this navigation space vertices are the nodes and edges are the connections between nodes. Navigation grids are useful for navigation problems where an exact and smooth path is not required. This is usually used for coarse grained navigation typically not directly linked to a visible world or checker board type navigation. In this navigation space vertices are the nodes and edges are the connections between nodes.
Line 29: Line 33:
 <WRAP clear></WRAP> <WRAP clear></WRAP>
  
-==== Navigation Mesh ====+===== Navigation Mesh =====
 <WRAP box 250px right :en>{{ :gamedev:images:navigation_mesh.jpg?200 |Sample Navigation Mesh}}<WRAP centeralign>Sample Navigation Mesh</WRAP></WRAP> <WRAP box 250px right :en>{{ :gamedev:images:navigation_mesh.jpg?200 |Sample Navigation Mesh}}<WRAP centeralign>Sample Navigation Mesh</WRAP></WRAP>
 Navigation meshes are useful for all kinds of navigation problems in detailed scene geometry where a smooth path around the world is desired. This is the typical space used for AI navigation of visible game actors. Most of the time you want to use this type of navigation space. In this navigation space faces are the nodes and edges the connections between them. In contrary to the navigation grid the connection is located at the edges of the face hence you do not travel along them but simply cross them. Navigation meshes are useful for all kinds of navigation problems in detailed scene geometry where a smooth path around the world is desired. This is the typical space used for AI navigation of visible game actors. Most of the time you want to use this type of navigation space. In this navigation space faces are the nodes and edges the connections between them. In contrary to the navigation grid the connection is located at the edges of the face hence you do not travel along them but simply cross them.
Line 36: Line 40:
 <WRAP clear></WRAP> <WRAP clear></WRAP>
  
-==== Navigation Volume ====+===== Navigation Volume =====
 Navigation volumes are useful for all navigation problems that navigation meshes can not accurately represent anymore. These are typically situations where the movement of actors is not limited to moving on the ground with jumping or hovering but where they can roam around three dimensions freely. A good example for this is Descent where the AI roams around in 0-gravity inside a large cavern complex. Here navigation volumes provide the same smooth path finding around the game world as does the navigation mesh just in three dimensions. In this navigation space rooms are the nodes and faces are the connections between them. Here too the rooms are directly connected to each other using faces similar to navigation meshes. Navigation volumes are useful for all navigation problems that navigation meshes can not accurately represent anymore. These are typically situations where the movement of actors is not limited to moving on the ground with jumping or hovering but where they can roam around three dimensions freely. A good example for this is Descent where the AI roams around in 0-gravity inside a large cavern complex. Here navigation volumes provide the same smooth path finding around the game world as does the navigation mesh just in three dimensions. In this navigation space rooms are the nodes and faces are the connections between them. Here too the rooms are directly connected to each other using faces similar to navigation meshes.
  
 For a valid navigation volume **vertices**, **corners**, **faces**, **walls** and **rooms** have to be defined. **Vertices**, **corners** and **faces** work the same as with navigation meshes except that the type numbers of corners and faces have no meaning. **Walls** are the indices of faces used in the rooms and are stored as a list of face indices including a type number. The system works the same as with corners hence the type number is used of the room is left along the matching face. Here too different cost functions can be defined depending in which direction the face is crossed. **Rooms** store the number of front and back facing walls and a type number. In general the rooms work here the same way as faces in the navigation mesh hence the walls are stored in the same order as the rooms are. In contrary though different counts for front and back facing walls are stored. The index of the first wall for a room X is thus the sum of all wall counts of the rooms 0 up to X-1. For each room first the front facing walls are stored then the back facing walls. Rooms can have any number of walls as long as they stay convex and the number of walls is at least 4 (a pyramid). The orientation of the faces inside the room does not matter as well as the order in which the are stored as long as front faces are stored before back faces. The term front and back facing walls refers to the face normal. If the normal of a face points inside the room the face is considered front facing otherwise back facing. For a valid navigation volume **vertices**, **corners**, **faces**, **walls** and **rooms** have to be defined. **Vertices**, **corners** and **faces** work the same as with navigation meshes except that the type numbers of corners and faces have no meaning. **Walls** are the indices of faces used in the rooms and are stored as a list of face indices including a type number. The system works the same as with corners hence the type number is used of the room is left along the matching face. Here too different cost functions can be defined depending in which direction the face is crossed. **Rooms** store the number of front and back facing walls and a type number. In general the rooms work here the same way as faces in the navigation mesh hence the walls are stored in the same order as the rooms are. In contrary though different counts for front and back facing walls are stored. The index of the first wall for a room X is thus the sum of all wall counts of the rooms 0 up to X-1. For each room first the front facing walls are stored then the back facing walls. Rooms can have any number of walls as long as they stay convex and the number of walls is at least 4 (a pyramid). The orientation of the faces inside the room does not matter as well as the order in which the are stored as long as front faces are stored before back faces. The term front and back facing walls refers to the face normal. If the normal of a face points inside the room the face is considered front facing otherwise back facing.
  
-==== Parameter Summary ==== +===== Parameter Summary ===== 
-Navigation Space+<WRAP column 45%> 
 +<WRAP boxheader>Navigation Space</WRAP> 
 +<WRAP boxcontent>
 ^Name^Description^Value^ ^Name^Description^Value^
 |Layer|Layer this navigation space affects|Integer| |Layer|Layer this navigation space affects|Integer|
 |Type|Space type|Grid, Mesh or Volume| |Type|Space type|Grid, Mesh or Volume|
 +</WRAP>
  
-Vertex+<WRAP boxheader>Vertex</WRAP> 
 +<WRAP boxcontent>
 ^Name^Description^Value^Space Type^ ^Name^Description^Value^Space Type^
 |Position|Position of the vertex relative to the parent navigation space|3-Component Vector|Grid, Mesh, Volume| |Position|Position of the vertex relative to the parent navigation space|3-Component Vector|Grid, Mesh, Volume|
 +</WRAP>
  
-Edge+<WRAP boxheader>Edge</WRAP> 
 +<WRAP boxcontent>
 ^Name^Description^Value^Space Type^ ^Name^Description^Value^Space Type^
 |Vertex 1|Index of the first vertex of this edge|Unsigned Short|Grid| |Vertex 1|Index of the first vertex of this edge|Unsigned Short|Grid|
Line 57: Line 67:
 |Type Number 1|Type to use to cross the edge from the first to the second vertex|Unsigned Short|Grid| |Type Number 1|Type to use to cross the edge from the first to the second vertex|Unsigned Short|Grid|
 |Type Number 2|Type to use to cross the edge from the second to the first vertex|Unsigned Short|Grid| |Type Number 2|Type to use to cross the edge from the second to the first vertex|Unsigned Short|Grid|
 +</WRAP>
  
-Corner+<WRAP boxheader>Corner</WRAP> 
 +<WRAP boxcontent>
 ^Name^Description^Value^Space Type^ ^Name^Description^Value^Space Type^
 |Vertex|Index of the vertex for this corner|Unsigned Short|Mesh, Volume| |Vertex|Index of the vertex for this corner|Unsigned Short|Mesh, Volume|
 |Type Number|Type to use crossing this edge|Unsigned Short|Mesh| |Type Number|Type to use crossing this edge|Unsigned Short|Mesh|
 +</WRAP>
 +</WRAP>
  
-Face+<WRAP column 45%> 
 +<WRAP boxheader>Face</WRAP> 
 +<WRAP boxcontent>
 ^Name^Description^Value^Space Type^ ^Name^Description^Value^Space Type^
 |Corner Count|Number of corners in this face|Unsigned Short|Mesh, Volume| |Corner Count|Number of corners in this face|Unsigned Short|Mesh, Volume|
 |Type Number|Type to use moving through this face|Unsigned Short|Mesh| |Type Number|Type to use moving through this face|Unsigned Short|Mesh|
 +</WRAP>
  
-Wall+<WRAP boxheader>Wall</WRAP> 
 +<WRAP boxcontent>
 ^Name^Description^Value^Space Type^ ^Name^Description^Value^Space Type^
 |Face|Index of the face for this wall|Unsigned Short|Volume| |Face|Index of the face for this wall|Unsigned Short|Volume|
 |Type Number|Type to use crossing this face|Unsigned Short|Volume| |Type Number|Type to use crossing this face|Unsigned Short|Volume|
 +</WRAP>
  
-Room+<WRAP boxheader>Room</WRAP> 
 +<WRAP boxcontent>
 ^Name^Description^Value^Space Type^ ^Name^Description^Value^Space Type^
 |Front Wall Count|Number of front facing walls in this room|Unsigned Short|Volume| |Front Wall Count|Number of front facing walls in this room|Unsigned Short|Volume|
 |Back Wall Count|Number of back facing walls in this room|Unsigned Short|Volume| |Back Wall Count|Number of back facing walls in this room|Unsigned Short|Volume|
 |Type Number|Type to use moving through this room|Unsigned Short|Volume| |Type Number|Type to use moving through this room|Unsigned Short|Volume|
 +</WRAP>
 +</WRAP>
 +<WRAP clear></WRAP>
  
 ===== Navigators ===== ===== Navigators =====
Line 98: Line 121:
 <WRAP clear></WRAP> <WRAP clear></WRAP>
  
-=== Example ===+**Example**\\
 <WRAP box 250px right :en>{{ :gamedev:images:navigation_bad_path.jpg?200 |Bad Path Example}}<WRAP centeralign>Bad Path Example</WRAP></WRAP> <WRAP box 250px right :en>{{ :gamedev:images:navigation_bad_path.jpg?200 |Bad Path Example}}<WRAP centeralign>Bad Path Example</WRAP></WRAP>
 An example for the use of cost functions is given in the images on the right. The first image shows a sample path through the world. In this case the path leads through the office of a coworker. This is indeed the shortest possible path if we assume doors are automatically opening not hampering your progress. Yet in reality this path is not a realistic one as strolling through an office like that is not considered to be polite. We need thus a way to penalize this route without preventing the path to end up in the office should this be our destination. For this costs functions can be used. In the example the "Type Numbers" 0, 1 and 2 are used. 0 is used for "default" hence anything like the hallway where we can walk without a problem. 1 stands for "door" and 2 stands for "room". This allows us to use two different ways to get a more realistic path. The first is to penalize doors and the second to penalize rooms. An example for the use of cost functions is given in the images on the right. The first image shows a sample path through the world. In this case the path leads through the office of a coworker. This is indeed the shortest possible path if we assume doors are automatically opening not hampering your progress. Yet in reality this path is not a realistic one as strolling through an office like that is not considered to be polite. We need thus a way to penalize this route without preventing the path to end up in the office should this be our destination. For this costs functions can be used. In the example the "Type Numbers" 0, 1 and 2 are used. 0 is used for "default" hence anything like the hallway where we can walk without a problem. 1 stands for "door" and 2 stands for "room". This allows us to use two different ways to get a more realistic path. The first is to penalize doors and the second to penalize rooms.
Line 112: Line 135:
  
 ==== Parameter Summary ==== ==== Parameter Summary ====
-Navigator+<WRAP column 45%> 
 +**Navigator**
 ^Name^Description^Value^ ^Name^Description^Value^
 |Layer|Layer this navigator uses to find a path|Integer| |Layer|Layer this navigator uses to find a path|Integer|
Line 119: Line 143:
 |Default Cost Per Meter|Cost Per Meter to use if no matching type is found|Float| |Default Cost Per Meter|Cost Per Meter to use if no matching type is found|Float|
 |Blocking Cost|Path with costs larger than this value are considered unwalkable|Float| |Blocking Cost|Path with costs larger than this value are considered unwalkable|Float|
- +</WRAP> 
-Navigation Type+<WRAP column 45%> 
 +**Navigation Type**
 ^Name^Description^Value^ ^Name^Description^Value^
 |Type Number|Type number matching this cost function|Unsigned Short| |Type Number|Type number matching this cost function|Unsigned Short|
 |Fix Cost|Fix cost to use|Float| |Fix Cost|Fix cost to use|Float|
 |Cost Per Meter|Cost Per Meter to use|Float| |Cost Per Meter|Cost Per Meter to use|Float|
 +</WRAP>
 +<WRAP clear></WRAP>
  
 ===== Steering and Collision Avoidance ===== ===== Steering and Collision Avoidance =====
 The navigation system provides you only with the path to take along the world. After this task navigation typically consists also of the process of **steering** and **collision avoidance**. These tasks though depend heavily on the game in question and are thus not provided by the AI Module. This is though not a problem since the Physics Module provides you already with collision detection to implement your steering and collision avoidance of choice. The navigation system provides you only with the path to take along the world. After this task navigation typically consists also of the process of **steering** and **collision avoidance**. These tasks though depend heavily on the game in question and are thus not provided by the AI Module. This is though not a problem since the Physics Module provides you already with collision detection to implement your steering and collision avoidance of choice.
- 
-====== Links ====== 
-  * [[gamedev:main|Game Development Informations]] 
-  * [[:start|Main page]] 
gamedev/navigation.txt · Last modified: 2019/05/24 23:43 by dragonlord

Page Tools

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 4.0 International
CC Attribution-Noncommercial-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki