This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revision | Next revisionBoth sides next revision | ||
gamedev:navigation [2012/12/01 17:54] – dragonlord | gamedev:navigation [2012/12/03 23:40] – dragonlord | ||
---|---|---|---|
Line 4: | Line 4: | ||
====== Navigation System ====== | ====== Navigation System ====== | ||
- | <WRAP box 250px right :en>{{ :gamedev:images: | + | <WRAP box 250px right :en>{{ : |
The navigation system provides the game with the necessary tools to choose a path through the game world. Often this is simply called **Path Finding**. Path finding by itself though is just one part of a navigation system albeit an important one. In the Drag[en]gine the navigation problem is represented using 3 main classes. These are the **Navigation Space**, **Navigator** and **Navigation Blocker** classes. In the rest of this text **Navigation System** is used as the grouping name for a set of spaces, navigators and blockers working together. | The navigation system provides the game with the necessary tools to choose a path through the game world. Often this is simply called **Path Finding**. Path finding by itself though is just one part of a navigation system albeit an important one. In the Drag[en]gine the navigation problem is represented using 3 main classes. These are the **Navigation Space**, **Navigator** and **Navigation Blocker** classes. In the rest of this text **Navigation System** is used as the grouping name for a set of spaces, navigators and blockers working together. | ||
Line 27: | Line 27: | ||
===== Navigation Grid ===== | ===== Navigation Grid ===== | ||
- | <WRAP box 250px right :en>{{ :gamedev:images: | + | <WRAP box 250px right :en> |
+ | {{ : | ||
+ | <WRAP centeralign> | ||
+ | </ | ||
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 34: | Line 37: | ||
===== Navigation Mesh ===== | ===== Navigation Mesh ===== | ||
- | <WRAP box 250px right :en>{{ :gamedev:images: | + | <WRAP box 250px right :en> |
+ | {{ : | ||
+ | <WRAP centeralign> | ||
+ | </ | ||
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 103: | Line 109: | ||
====== Navigators ====== | ====== Navigators ====== | ||
- | <WRAP box 250px right :en>{{ :gamedev:images: | + | <WRAP box 250px right :en> |
+ | {{ : | ||
+ | <WRAP centeralign> | ||
+ | </ | ||
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. | ||
Line 123: | Line 132: | ||
<WRAP boxheader> | <WRAP boxheader> | ||
<WRAP boxcontent> | <WRAP boxcontent> | ||
- | <WRAP box 250px right :en>{{ :gamedev:images: | + | <WRAP box 250px right :en> |
+ | {{ : | ||
+ | <WRAP centeralign> | ||
+ | </ | ||
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" | 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" | ||
<WRAP clear></ | <WRAP clear></ | ||
- | <WRAP box 250px right :en>{{ :gamedev:images: | + | <WRAP box 250px right :en> |
+ | {{ : | ||
+ | <WRAP centeralign> | ||
+ | </ | ||
The first solution using doors requires us to create a " | The first solution using doors requires us to create a " | ||