Using Navigation Meshes in FatLoot

Posted by | November 01, 2013 | Programming | No Comments
Our Artificial Intelligence Engineers Nick Abreunedina and Ravi Sanampudi worked on the Navigation Mesh in Fat Loot. Here is their process in implementing this feature in the game. 
Fat Loot is a 3rd person stealth game. The goal of the player is to steal treasure from a palace while evading the guards.
Nick A and I stepped into the shoes of AI Engineers and started working on implementing behavior of the guards. One of the basic needs of a guard is the ability to traverse the game level fluidly. We did the initial implementation using Path Nodes. These are markers placed at different locations in the level. A guard is made aware of a set of Path Nodes and thus can move in between them. After a few weeks of development, our Engineer Lead Lu told us of a more advanced and natural way to traverse levels, which is through using Navigation Meshes.
I had never heard of the term before, so it was time for some good old research. My first choice (as it is for any information) was Wikipedia. Unfortunately it did not have much of a description on Navigation Meshes. Luckily, (and quite surprisingly) the Unreal website has good articles on how Navigation Meshes are constructed and used. So then I started reading pages and pages of Unreal articles (it was only about 5 pages really, but felt like a lot more, as I had to read them multiple times because they were so complex.)
There were good amount of diagrams to help understand and keep the monotony of huge blocks of text away.
Long story short, Path Nodes define paths from point to point, whereas NavMesh defines paths from an area to another area.

Image1

Once I read the whole thing and understood the concepts fairly well, I sat down to implement it in our game.
First we needed to create nav meshes in the level. This was done via UDK Editor. It’s as simple as adding a Pylon and clicking “Build Paths.”  However, to actually see the paths, we needed to press “P”. It actually took me half a day to figure that out, as it was not mentioned in any tutorial. I kept wondering why the paths were not generated and it ended up being a simple fix. Anyways, this needed to be done just once per level. Once a nav mesh is built, it is saved in the level information. It is now up to us to use the nav mesh in code. That is fairly easy too.
Here’s all the code you’d need to make a guard navigate around the level using nav mesh:

Image2

Notice that there’s potentially a While(true) loop in there. The code will loop until the destination is reached. NavMesh, if used well, is pretty robust in that all accessible areas of a level can be calculated. But just for that one off occasion when it fails, we need a backup. So I set a limit to the number of searches we make per destination.

Image3

Another tweak we had to do to the basic code is to get it working not just for an Actor destination (an object in the level), but for a Vector destination (any location coordinates). For some weird reason, the library/reference code only works for Actors, which we may not always have available. The code gets a little messy when we need to check using vector3 destinations, but it had to be done. (we have an investigate state for the guard where he doesn’t move to a particular PathNode, but to any given location in the level.)

As an ending note, I’d say NavMesh is working pretty well now. But we haven’t used it’s real power, which is to set goals and constraints. That allows the guard to traverse the same area in different ways based on different conditions. That is something that cannot be achieved using PathNodes.

So here’s hoping we get to implement more cool behaviors for the guards and unleash the power of NavMesh! :)

 Image4

Image5

 

About Lawrence Jung

Lawrence Jung is a USC MFA Interactive Media and Games student and Lead Producer of Fat Loot. He enjoys painting, watching anime and getting lost in the forest. Some of his favorite games include Teenage Mutant Ninja Turtles: Turtles in Time and Mario Kart.

Leave a Reply