Drag[en]gine Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
{{tag>ai navigation pathfinding}}
<WRAP youarehere>
[[:start|Start Page]] >> [[:gamedev|Game Development with the Drag[en]gine]] >> **Navigation System**
</WRAP>

====== Navigation System ======
<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.

===== Layering =====
All of these classes share a common property, the **layer number**. Often one navigation system is not enough as there could be actors of different sizes or movement abilities as well as the game wishing to use navigation spaces of differing granularity. An example for this would be an RTS game requiring a world scale reasoning as well as a local path finding with units of different sizes not all fitting through the same place. In this case multiple navigation systems are required each used for a different purpose. This can be simply done using different layer numbers for each member of a navigation system. The layer number can be chosen freely as an Integer number. A navigator with the layer number X thus is affected only by navigation meshes and blockers with the same layer number X. If navigation is not working as expected make sure all navigation system members use the same layer number.
<WRAP clear></WRAP>

===== Cost System =====
One particular strength of path finding algorithms is the ability to alter the path chosen through the game world using cost functions. This allows the AI to choose a path more intelligently. In the Drag[en]gine the cost system works using a **Type System**. Each type is an Integer value describing a particular cost function to be used whenever the AI wants to venture along a certain part of the game world. To allow simple usage of cost functions navigation spaces provide for individual space elements a **type number**. You are free to choose the type numbers the way it fits your game. You can also reuse the type number in different navigation systems. Inside a navigation system (same layer number) the meaning of a type number is the same for all members of the system. The navigators define then a mapping of cost functions to type numbers. This way cost functions can be easily modified on a per navigator basis. Cost functions are describe in detail under **Navigators**.

===== Module Support =====
The **AI Module** provides support to solve the navigation problems using this system.

====== 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.

The **layer number** defines which navigators are affected by this navigation space. The Drag[en]gine allows to use multiple navigation spaces with the same layer number. In this case the AI module is responsible to link the individual navigation spaces together to act as one huge navigation space. It is also valid to use different types of navigation spaces with the same layer number. In this case all navigation spaces of the same type and layer are grouped together by the AI module. Use the appropriate **space type** parameter in the navigators to select which space type to use for a given layer.

To define types just assign the matching **type number** to the individual elements of a navigation space. The AI module is responsible to match them to navigator cost functions.

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 =====
<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.

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>

===== Navigation Mesh =====
<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.

For a valid navigation mesh **vertices**, **corners** and **faces** have to be defined. All other elements are ignored. **Vertices** behave the same as in the case of navigation grids. **Corners** are the vertices used in the faces and are stored as a list of Integer indices together with a type number. The edges of the faces are not explicitly stored. They are implicitly defined using the corners. Hence the first edge of a face starts at the vertex defined in the first corner of the face and ends at the second corner of the face. This is cyclic hence the last edge starts at the last corner and ends at the first corner. Thus the first corner is not stored a second time (hence 3 corners for a triangle). The type number of a corner is used when the face is left along the edge belonging to the corner (hence the edge starting at this corner) to enter a different face. Edges therefore exist twice if they connect two faces but can have different type numbers. Here too this allows to have different cost functions for moving from face A to B or B to A across the same edge. **Faces** store the number of corners and a type number. Faces can have as many corners as you want as long as they are convex and the number of corners is at least 3. The first corner for each face is not stored explicitly as it is implicitly defined by the fact that the corners are stored in the same order as faces are. Hence the index of the first corner for face X is the sum of all corner counts of all faces 0 up to X-1. The orientation of faces does not matter. They are also not required to be oriented all the same way. The type number in the face is used to determine the cost while moving inside the face.
<WRAP clear></WRAP>

===== 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.

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 =====
<WRAP column 45%>
<WRAP boxheader>Navigation Space</WRAP>
<WRAP boxcontent>
^Name^Description^Value^
|Layer|Layer this navigation space affects|Integer|
|Type|Space type|Grid, Mesh or Volume|
</WRAP>

<WRAP boxheader>Vertex</WRAP>
<WRAP boxcontent>
^Name^Description^Value^Space Type^
|Position|Position of the vertex relative to the parent navigation space|3-Component Vector|Grid, Mesh, Volume|
</WRAP>

<WRAP boxheader>Edge</WRAP>
<WRAP boxcontent>
^Name^Description^Value^Space Type^
|Vertex 1|Index of the first vertex of this edge|Unsigned Short|Grid|
|Vertex 2|Index of the second vertex of this edge|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|
</WRAP>

<WRAP boxheader>Corner</WRAP>
<WRAP boxcontent>
^Name^Description^Value^Space Type^
|Vertex|Index of the vertex for this corner|Unsigned Short|Mesh, Volume|
|Type Number|Type to use crossing this edge|Unsigned Short|Mesh|
</WRAP>
</WRAP>

<WRAP column 45%>
<WRAP boxheader>Face</WRAP>
<WRAP boxcontent>
^Name^Description^Value^Space Type^
|Corner Count|Number of corners in this face|Unsigned Short|Mesh, Volume|
|Type Number|Type to use moving through this face|Unsigned Short|Mesh|
</WRAP>

<WRAP boxheader>Wall</WRAP>
<WRAP boxcontent>
^Name^Description^Value^Space Type^
|Face|Index of the face for this wall|Unsigned Short|Volume|
|Type Number|Type to use crossing this face|Unsigned Short|Volume|
</WRAP>

<WRAP boxheader>Room</WRAP>
<WRAP boxcontent>
^Name^Description^Value^Space Type^
|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|
|Type Number|Type to use moving through this room|Unsigned Short|Volume|
</WRAP>
</WRAP>
<WRAP clear></WRAP>

====== Navigators ======
<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.

===== Cost Functions =====
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.

For navigation grids the calculation is:
<code>cost = edge.fixCost + edge.costPerMeter * distance</code>

For navigation meshes the calculation is:
<code>cost = corner.fixCost + face.fixCost + face.costPerMeter * distance</code>

And for navigation volumes the calculation is:
<code>cost = wall.fixCost + room.fixCost + room.costPerMeter * distance</code>

By default **fix cost** is 0 and **cost per meter** is 1. In addition tho these values the **blocking cost** can be defined. If the cost for a potential path raises above this limit the path is considered blocked or unwalkable. By default this value is 1'000. This value is also useful in the case of impossible path. If a path can not be found the entire search space has to be exhausted first. Using a reasonably low blocking cost though you can avoid this time consuming search by defining a maximum cost. This way a path is considered impossible if no path is found which costs less than blocking cost which is usually only a fraction of the search space.
<WRAP clear></WRAP>

<WRAP boxheader>Example</WRAP>
<WRAP boxcontent>
<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.
<WRAP clear></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 same can be achieved also using a different method. Instead of penalizing the doors we can penalize the rooms. Hence we want strolling through the office to be expensive instead of strolling through the hallway. For this add a "Navigation Type" with the value 2 and assign it the "Cost Per Meter" 1.5 . What happens now is that if we want to move through the office we have to pay 1.5 times the cost than if we move through the hallway. 1.5 is actually enough for this to work out since the longest way we can take around the room is the same as the diagonal across the room. In the worst case this is a square hence the square-root of 2 which is 1.41... . 1.5 is thus enough to penalize this room no matter the shape. You can though also use a higher value if you want. The same image as above is the result using this solution. Here too we can end up in the room if we want to without a problem.

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>
</WRAP>

===== Parameter Summary =====
<WRAP column 45%>
<WRAP boxheader>Navigator</WRAP>
<WRAP boxcontent>
^Name^Description^Value^
|Layer|Layer this navigator uses to find a path|Integer|
|Space Type|Navigator uses only navigation spaces of this type to find a path|Grid, Mesh or Volume|
|Default Fix Cost|Fix cost 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|
</WRAP>
</WRAP>

<WRAP column 45%>
<WRAP boxheader>Navigation Type</WRAP>
<WRAP boxcontent>
^Name^Description^Value^
|Type Number|Type number matching this cost function|Unsigned Short|
|Fix Cost|Fix cost to use|Float|
|Cost Per Meter|Cost Per Meter to use|Float|
</WRAP>
</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 ======
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.
Drag[en]gine Wiki

User Tools

Site Tools

Page Tools
