AI in the Insomniac Engine

It makes sense that AI is plays a big part of game. Gameplay heavily relies on enemies and the AI that controls them. With a pool of behaviors to draw from and a handler to choose the correct behavior to use can create the illusion of an enemy with intelligence. Some games forget the intelligence part of AI. With enemies that are blind, to friendly NPC running into a horde of enemies guns blazing and drawing all of the fire. Sometimes they die and sometimes they are curtail for the story to progress and become a damage soak and never die.

In a lecture we watched a talk presented by Insomniac's Reddy Sambavaram (at GDC11) about the AI in the Insomniac engine and I have to say that it peaked my interest. What caught my attention the most was the way that they looked at navigation and interesting ways to improve it. If you are interested there is a link that will take you to the slides that were used in the presentation.

The term navigation is used when you are describing how a given NPC moves through terrain on a movement path. The NPC is at its current position A, and has set a destination that is has to reach B. Now it has to compute the short path to reach its destination. The shortest path to its destination is straight but there are not many times where that is possible as there will be something in the way. This is where a bunch of different path finding algorithms is used to compute the shortest and safest path to its destination. One of the more famous algorithm is called A Star (A*). This algorithm is one of the more widely used and is a great way to determine a path.

There are others methods of finding paths such as Insomniac’s approach that they took with Ratchet and Clank: Deadlocked. For the navigation system in that game they used way-volume representation. These way-volume were hand made by the designers using volumes and nodes to help with an A* path. There were connections made between the volumes to help guide NPC between them. In the presentation slides this is illustrated in slide six. Once Insomniac moved on to the Playstation3 they started to change their workflow and started to introduce Navigation Meshes to the process.

Resistance: Fall of Man was one of the first games that used nav-meshes. The designers built the mesh in Maya. The polys were used as nodes in the A* algorithm. There was a problem with the early implementation of the mesh as it took too much for the PPU (physics processing unit) to handle. This is why that they could only use eight navigating NPC with the system. They know that they had a lot of tweaking to do. For Resistance 2 they set some goals to improve the navigation system and make sure that it was more usable. To fix some of their issue they tried a number of different solutions such as portioning the meshed and triangulating the mesh’s polys. They added Bezier curves to help make the paths smooth and help with corners. They also added more advanced obstacle avoidance. We have been talking about navigation meshes but what are they?

A navigation mesh or nav-mesh is an abstract mesh used in AI to aid path finding in large spaces. How does a nav-mesh work? The A* algorithm uses waypoints or nodes to compute its path. With the nav mesh each poly is a node that the NPC can use to navigate to. Insomniac decided to only dedicate 10% of its navigation bugged for the A* algorithm so they spent a lot of time on optimization. They accomplished this by cashing paths for reusability, flagging walls of tangents of the path, and gathering nearest boundaries for obstacles.

Insomniac also created an automatic tool to generate navigation meshes instead of making them by hand. This freed up also of time in the development stage as designers did not have to go through the terrain and create the nav-mesh by hand. The tool is not perfect but it is easier to fix one or two errors then to make the entire mesh by hand. Insomniac also added functionality to jump up, down, or over objects with jump nodes. If there was a ledge there would be hard for path finding to jump over terrain.

I find solutions to problems interesting as they are usually innovative and inspiring. Finding creative solutions to the problems that games face is how the industry has grown so rapidly in the sort time span. Trying to squeeze everything you can get from the hardware that you are given is interesting to say the least. Creating a mesh that you can use to make A* more efficient is a cool solution to a tough problem.