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.
Navigation and Path Finding
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.
Navigation Meshes
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.
Navigators
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.
Pack it all together
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.
Outlook
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).
![Drag[en]gine](https://media.indiedb.com/cache/images/engines/1/1/9/crop_120x90/banner_large.png)
I've not really been a fan of nav mesh movement mainly because it looks a bit too machine like, notice how the characters tend to hug the corners when they move.. a human wouldn't do this (because of fear of bumping into a person), understandably constraints could help make it a bit more believable to stop the AI doing that but yeah unfortunately Nav Mesh is designed to find the quickest path, not necessarily the safest. I just think if we're going to destroy this idea of machine intelligence in games we have to start making the characters movements less predictable and more random, and more believable that they are human.
I think you've done great work so far- really impressive stuff.
This is actually not the problem of the nav-mesh. Navigation consists of 4 main steps: Path Finding, String-Pulling, Steering-Control and Collision-Avoidance. In a poor implementation one stops after the second step and then it looks robotic. In contrary to common nav-meshes my implementation includes proper cost-functions. This takes care of choosing "safe" routes as you call it. Steering-Control takes care of not hugging corners and making actors move natural. There exist various ways this can be done. This test here uses a quick and basic approach already existing in the code but anything up to spline curves can be used. Since this is in script-land the developer has full controll over this. Eventually you have collision-avoidance which takes care of providing a realistic response to dynamic obstacles. This is though not implemented here yet (basic code in place though but not used).
So no, nav-meshes provide good results if used correctly. Just many don't use them correctly, that's the problem.
Thankyou for explaining that, thing is that I'm worried about path finding with my own projects and I've been concerned about the whole thing looking a bit too machine, its good to know that its not the technique then rather the developer's willingness to develop systems for it to work- so maybe I need to look at Nav mesh a bit further.
Look at it like with responsibilities (the way my entire engine functions). When you look at the individual steps in the process ask yourself what question you would ask the service. In case of the nav-mesh the question is "what path is the best from target to goal?". Therefore you get as a result a point-list. The question for the Steering-Control then is "how can I follow this path smoothly?". And thus you get there as result a new point-list which you can then follow with your AI. Hence in my implementation the AI module provides you with the solution for the first question as this is a generic question. The solution for the second one is up to you and your game scripts as this solution depends a lot on the game actor in question.
Nice article. I only recently started learning about AI and pathfinding etc so i find this intresting. I only just been learning about nav meshs and i think they work pretty well, 90% of time it works great it's just when turning cornors etc looks abit weird.