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
gamedev:navigation [2012/12/01 17:54] – dragonlordgamedev:navigation [2019/05/24 23:43] (current) – ↷ Links adapted because of a move operation dragonlord
Line 1: Line 1:
 +{{tag>ai navigation pathfinding}}
 <WRAP youarehere> <WRAP youarehere>
-[[:start|Start Page]] >> [[gamedev:main|Game Development with the Drag[en]gine]] >> **Navigation System**+[[:start|Start Page]] >> [[:gamedev|Game Development with the Drag[en]gine]] >> **Navigation System**
 </WRAP> </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:navigation_sample_world.jpg?200 |Example world to navigate}}<WRAP centeralign>Example world to navigate</WRAP></WRAP>
 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 28:
  
 ===== 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: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 34: Line 38:
  
 ===== 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: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 103: Line 110:
  
 ====== Navigators ====== ====== Navigators ======
-<WRAP box 250px right :en>{{ :gamedev:images:navigation_sample_path.jpg?200 |Multi-Level Sample Path}}<WRAP centeralign>Multi-Level Sample Path</WRAP></WRAP>+<WRAP box 250px right :en> 
 +{{ :gamedev:navigation_sample_path.jpg?200 |Multi-Level Sample Path}} 
 +<WRAP centeralign>Multi-Level Sample Path</WRAP> 
 +</WRAP>
 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 133:
 <WRAP boxheader>Example</WRAP> <WRAP boxheader>Example</WRAP>
 <WRAP boxcontent> <WRAP boxcontent>
-<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: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.
 <WRAP clear></WRAP> <WRAP clear></WRAP>
  
-<WRAP box 250px right :en>{{ :gamedev:images:navigation_good_path.jpg?200 |Good Path Example}}<WRAP centeralign>Good Path Example</WRAP></WRAP>+<WRAP box 250px right :en> 
 +{{ :gamedev:navigation_good_path.jpg?200 |Good Path Example}} 
 +<WRAP centeralign>Good Path Example</WRAP> 
 +</WRAP>
 The first solution using doors requires us to create a "Navigation Type" in the navigator for the number 1. To avoid strolling through the office we can give the door a fix cost penalty. This can be done by setting "Fix Cost" to 5 for example leaving "Cost Per Meter" at 1. You can imagine this as if costs are real money costs. Hence for every walked meter you have to pay 1 credit. Now to cross the door you have to pay 5 credits no matter how far you move across the door. This extra cost is enough to make the path through the office to be way more expensive than walking around it in the hallway. The image on the right shows this behavior. This solution does not impact us if we want to end up in the office since for this we have to use the door no matter what direction we arrive. The path into the office is then still the cheapest although we have to cross a door. The first solution using doors requires us to create a "Navigation Type" in the navigator for the number 1. To avoid strolling through the office we can give the door a fix cost penalty. This can be done by setting "Fix Cost" to 5 for example leaving "Cost Per Meter" at 1. You can imagine this as if costs are real money costs. Hence for every walked meter you have to pay 1 credit. Now to cross the door you have to pay 5 credits no matter how far you move across the door. This extra cost is enough to make the path through the office to be way more expensive than walking around it in the hallway. The image on the right shows this behavior. This solution does not impact us if we want to end up in the office since for this we have to use the door no matter what direction we arrive. The path into the office is then still the cheapest although we have to cross a door.
  
Line 159: Line 175:
 </WRAP> </WRAP>
 <WRAP clear></WRAP> <WRAP clear></WRAP>
 +
 +====== Exporting ======
 +<WRAP box 250px right :en>{{ :gamedev:blender3d:object_navspacetype.png?200 |Navigation Space Type property}}<WRAP centeralign>Navigation Space Type property</WRAP></WRAP>
 +The Blender export scripts provide support to export Mesh objects as Drag[en]gine Navigation Spaces. To mark an object as a navigation space for exporting use the Nav-Space Type property in the Object panel. Only objects with a value other than None are exported in the appropriate format.
 +<WRAP clear></WRAP>
 +
 +<WRAP box 250px right :en>{{ :gamedev:blender3d:material_navtype.png?200 |Material Navigation Type property}}<WRAP centeralign>Material Navigation Type property</WRAP></WRAP>
 +For Mesh and Volume type navigation spaces the Cost type can be defined using the Material each face belongs to. For this use the Navigation Type property in the Material panel. The control provides a soft range from 0 to 10 for quick editing but you can enter any positive integer value including 0.
 +<WRAP clear></WRAP>
 +
 +For Edges and points as used for Grid navigation spaces it is a bit more complicated due to the nature of how Blender handles custom properties. You have to use Vertex Groups for this to work. Create for each navigation type a single vertex group in the object.
 +<WRAP center round important 80%>Since vertex groups are half-model half-object data the custom data is attached to the object. Reusing a mesh hence does not take over these values as they stick to individual objects. If you want to copy the data duplicate the object.</WRAP>
 +<WRAP box 250px right :en>{{ :gamedev:blender3d:vertexgroup_navtype1.png?200 |Vertex Group Nav-Type}}<WRAP centeralign>Vertex Group Nav-Type</WRAP></WRAP>
 +Once created you can now set the navigation type to use for edges and vertices belonging to a certain vertex group. For this use the Drag[en]gine Vertex Group sub panel in the Mesh Data panel. This shows the navigation data for the active vertex group. If no data has been set yet a button is shown to create the data. Once set the sub panel switches allowing you to set the navigation type the the same way as with materials. Once set you can assign edges and vertices to vertex groups. For a an edge the first vertex group is picked both end point vertices belong to. Hence make sure only one such vertex group fulfills this requirement or the result is undefined.
 +<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.
gamedev/navigation.1354384469.txt.gz · Last modified: 2012/12/01 17:54 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