This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revision | Next revisionBoth sides next revision | ||
gamedev:navigation [2012/11/30 15:51] – dragonlord | gamedev:navigation [2012/12/01 17:41] – dragonlord | ||
---|---|---|---|
Line 17: | 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 26: | 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. | ||
- | <WRAP boxheader> | + | ===== Navigation Grid ===== |
- | ==== Navigation Grid ==== | + | |
- | </ | + | |
- | <WRAP boxcontent> | + | |
<WRAP box 250px right :en>{{ : | <WRAP box 250px right :en>{{ : | ||
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 35: | Line 32: | ||
For a valid navigation grid **vertices** and **edges** have to be defined. All other elements are ignored. A **vertex** has only a position. An **edge** has Integer indices of the two vertices it connects as well as two type numbers. The first type number is used if the edge is crossed from the first vertex towards the second. The second type number is used if the edge is crossed in the other direction. This allows for different costs depending in what direction an edge is crossed. | For a valid navigation grid **vertices** and **edges** have to be defined. All other elements are ignored. A **vertex** has only a position. An **edge** has Integer indices of the two vertices it connects as well as two type numbers. The first type number is used if the edge is crossed from the first vertex towards the second. The second type number is used if the edge is crossed in the other direction. This allows for different costs depending in what direction an edge is crossed. | ||
<WRAP clear></ | <WRAP clear></ | ||
- | </ | ||
- | <WRAP boxheader> | + | ===== Navigation Mesh ===== |
- | ==== Navigation Mesh ==== | + | |
- | </ | + | |
- | <WRAP boxcontent> | + | |
<WRAP box 250px right :en>{{ : | <WRAP box 250px right :en>{{ : | ||
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 46: | Line 39: | ||
For a valid navigation mesh **vertices**, | For a valid navigation mesh **vertices**, | ||
<WRAP clear></ | <WRAP clear></ | ||
- | </ | ||
- | <WRAP boxheader> | + | ===== Navigation Volume ===== |
- | ==== Navigation Volume ==== | + | |
- | </ | + | |
- | <WRAP boxcontent> | + | |
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**, | For a valid navigation volume **vertices**, | ||
- | </ | ||
- | <WRAP boxheader> | + | ===== Parameter Summary ===== |
- | ==== Parameter Summary ==== | + | |
- | </ | + | |
- | <WRAP boxcontent> | + | |
<WRAP column 45%> | <WRAP column 45%> | ||
**Navigation Space** | **Navigation Space** | ||
Line 67: | Line 52: | ||
|Type|Space type|Grid, Mesh or Volume| | |Type|Space type|Grid, Mesh or Volume| | ||
- | **Vertex** | + | <WRAP boxheader> |
+ | <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, | |Position|Position of the vertex relative to the parent navigation space|3-Component Vector|Grid, | ||
+ | </ | ||
**Edge** | **Edge** | ||
Line 101: | Line 88: | ||
</ | </ | ||
<WRAP clear></ | <WRAP clear></ | ||
- | </ | ||
===== Navigators ===== | ===== Navigators ===== | ||
Line 107: | Line 93: | ||
While the navigation spaces define the space in which navigation takes pace it is the navigators that determine which path to choose across such a space. Navigators are also also all-round class and can thus be used on all kinds of navigation spaces. To use a navigator you have to first set the **layer number** and the **space type**. The navigator is going to determine a path only using navigation spaces having the same layer and space type. If navigation does not work properly check first if these two parameters are set correctly. Once this is done you can set a **start position** and a **goal position**. Call then **update path**“ and the AI module calculates a path for you. The path is stored as a list of points (DVector) in world space. If no path is found the list of points is 0. Otherwise the list of points defines the path starting with the first path point to head towards. The list does not start with the **start position** but with the first path point. The last point in the list is the **goal position**. The list stays intact until the next time **update path** is called. | While the navigation spaces define the space in which navigation takes pace it is the navigators that determine which path to choose across such a space. Navigators are also also all-round class and can thus be used on all kinds of navigation spaces. To use a navigator you have to first set the **layer number** and the **space type**. The navigator is going to determine a path only using navigation spaces having the same layer and space type. If navigation does not work properly check first if these two parameters are set correctly. Once this is done you can set a **start position** and a **goal position**. Call then **update path**“ and the AI module calculates a path for you. The path is stored as a list of points (DVector) in world space. If no path is found the list of points is 0. Otherwise the list of points defines the path starting with the first path point to head towards. The list does not start with the **start position** but with the first path point. The last point in the list is the **goal position**. The list stays intact until the next time **update path** is called. | ||
- | <WRAP boxheader> | ||
==== Cost Functions ==== | ==== Cost Functions ==== | ||
- | </ | ||
- | <WRAP boxcontent> | ||
Cost functions allow you to influence the path the AI module calculates for you. As mentioned at the beginning navigation spaces define a **type number** for individual space elements. The navigator stores a list of **Navigation Type** objects. A navigation type stores a **type number**, a **fix cost** and a **cost per meter** parameter. The type number is used to match the navigation type with the navigation space elements. If no match can be found the default parameters for fix cost and cost per meter are used as stored in the navigator. Depending on the navigation space in use the costs are calculated differently using these parameters. **distance** is the distance in meters traveled along a navigation space element. | Cost functions allow you to influence the path the AI module calculates for you. As mentioned at the beginning navigation spaces define a **type number** for individual space elements. The navigator stores a list of **Navigation Type** objects. A navigation type stores a **type number**, a **fix cost** and a **cost per meter** parameter. The type number is used to match the navigation type with the navigation space elements. If no match can be found the default parameters for fix cost and cost per meter are used as stored in the navigator. Depending on the navigation space in use the costs are calculated differently using these parameters. **distance** is the distance in meters traveled along a navigation space element. | ||
Line 137: | Line 120: | ||
Which method is the better depends on the situation. The solution with the added fix cost is usually better though as it does not increase the costs too much while still delivering the desired result. | Which method is the better depends on the situation. The solution with the added fix cost is usually better though as it does not increase the costs too much while still delivering the desired result. | ||
<WRAP clear></ | <WRAP clear></ | ||
- | </ | ||
- | <WRAP boxheader> | ||
==== Parameter Summary ==== | ==== Parameter Summary ==== | ||
- | </ | ||
- | <WRAP boxcontent> | ||
<WRAP column 45%> | <WRAP column 45%> | ||
**Navigator** | **Navigator** | ||
Line 160: | Line 139: | ||
</ | </ | ||
<WRAP clear></ | <WRAP clear></ | ||
- | </ | ||
===== 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. |