The Drag[en]gine is a fully customizable game engine and game development environment designed with modularity and extensibility in mind not requiring expensive licenses.
Infos about the navigation system in the Drag[en]gine.
Posted by Dragonlord on Jul 10th, 2011
The last couple of weeks has been spent in the name of navigation. Many know this as Path Finding but correctly path finding is just one (albeit important) ingredient of the navigation problem. As always the Drag[en]gine takes a general approach in dealing with the navigation problem to allow all kinds of games to use it efficiently and painlessly.
I try to keep the technical details as short as possible here. Due to demand from watchers I'll try to add a more in depth documentation to the Wiki of the Drag[en]gine over time (maybe this summer if I get the time). This way you can see better how awesome this engine is (which is not so visible from summary type news posts).
As with other technical parts of the engine for anything related to AI an own module exists, the AI module. This module provides services required typically by AI routines like navigation support. Thus the player can choose the AI module on his own allowing to improve for example navigation easily. At the base the navigation system composes of two main components, the navigation mesh and the navigator.
To implement path finding various way exist but the typical ones are the navigation grid and the navigation mesh. Navigation Grids are often also used way-point systems but covers many other scenarios like hexagonal fields on an RTS type game map and so forth. This can be imagined as a collection of Nodes connected with edges. Each node is a field or location an actor can be located at and each edge defies a valid transition from one location to another. Giving cost functions to edges the choice of path can is improved a lot. Cost functions define how costly it is to move along an edge. This way AI can be kept on fast traveling routes unless it is more favorable to treat through rough terrain. Combined with A* (the most common path finding algorithm) this yields a solid base but gets in troubles with complex scenarios or large open plains. For this reason Navigation Meshes have been invented. A navigation mesh augments the navigation grid in that they add a new dimension to it. The nodes are now faces while the valid transitions still are edges but this time between neighboring faces. This allows to cover the walkable space more precisely with less faces/nodes than using navigation grids. In contrary to navigation grids though the notion of cost functions for the edge is more difficult now. The Drag[en]gine solves though all of this for you.
In the Drag[en]gine all these navigation spaces are folded into one single object, the Navigation Mesh, as they are all similar to each other just with differing properties. Thus the navigation mesh object can hold at your wish navigation grids, navigation meshes or even navigation volumes. Navigation volumes are an extension on the navigation mesh in that they take it another dimension higher so now you have rooms as nodes which are connected by faces. Navigation volumes are currently not yet implemented. Cost functions are provided using a type value for node connections (for example faces). This can then be linked later on. Navigation meshes can be created any number and added/removed to the game world at any time. The AI module takes care of the rest for you. This allows to have for example navigation meshes for individual buildings and/or terrain segments which you can edit individually. This improves work flow and allows for reusable content (for example modular assets). Furthermore every navigation mesh has a layer value. All navigation meshes with the same layer value belong to the same search space. Hence you can have various navigation meshes for different types of AI in your game each using its own layer value.
While Navigation Meshes define the search space the Navigator objects define the search function. Every AI in the world typically maintains a personal navigator. As with navigation meshes the navigator has a layer value and thus only takes navigation meshes with the same layer value into account. You simply define the start and goal position and you get your path out as a list of path points. The neat trick on using navigators is that you can define cost functions per navigator (thus per AI if required). Remember the type numbers of navigation meshes? In a navigator you define a table of cost functions which is a mapping of type value to cost function. AIs can thus have individual navigation behavior (also dynamic at run-time). Cost functions consist of two values: fix cost and cost-per-meter. Simply put the final costs are:
Thus costs are a simple MAD and generic. For navigation grids fixCost would be non-0 while in navigation meshes costPerMeter is non-0. Distance is the length of the path segment traveled inside a face. This yields a good cost function for navigation meshes which usually lack a useful cost function in other engines.
The current AI module uses for path finding the A* algorithm using the outlined cost functions. While A* is works well the resulting path would not be very good as it runs along the center of the faces. To deal with this the String-Pulling is used. String-pulling is the name for a technique where the A* path is pulled at the ends to make it fit tightly around scene geometry. Various solutions exist for this too but a well known one is the Funnel Algorithm. This presentation contains an explanation of the algorithm (look for the next corner point slide). This results in a tight path as shown here. Unfortunately the funnel algorithm fails in various situations as it is lacking as you can see here (left image base funnel algorithm, right image how it should be). Some projects like Recast tip-toe around the problem by introducing ray-casting (can be slow) and thus is not suitable for a generic solution. I've done now some modifications to the algorithm to catch the problems while retaining the speed advantages of the funnel algorithm. The result is now a properly working and fast calculated path.
On the game side a bunch of additional classes have been implemented namely the ActorAI class. This works similar to the PlayerActions class but for AI purpose. Implemented there a basic Move-To type AI to show how the navigation works. Hence you can just say where you want to go and the code does the rest for you. To finish this news post here a test-run where I send the actor down to the back entrance and from there back up again.
More details hopefully in the Wiki later on.
More work on the game script side of AI handling especially adding real collision avoidance as well as improving on objects dynamically blocking things (blocker memory and so forth).