NPC Navigation: The Insomniac Way

Navigation is an extremely important aspect of creating engaging and interesting game AI. Anyone who's witnessed an NPC walk tirelessly into walls and obstacles knows it can break the immersion very quickly. In order to create visually pleasing NPC navigation, a delicate balance between goal based path-finding, obstacle avoidance, and animation must be established. This is demonstrated in excellent fashion by Insomniac studios (creators of Spyro The Dragon, Ratchet and Clank and Resistance) in their recent titles released on the PS3 console. I recently had the privilege of watching Reddy Sambavaram's GDC talk (http://www.insomniacgames.com/navigation-gdc11/) detailing the navigation systems of their recent games and some techniques from their upcoming titles. With this new-found knowledge, I will provide a brief rundown of how Insomniac achieved such fluid character navigation in their recent titles (Particularly the Resistance series).

Navigation can be seen as a step by step process, so I will try to explain it as such.

Step 1: Path-finding

Finding the shortest, or most cost effective path between a series of checkpoints (called nodes) is a fairly simple process. First, a cost value is assigned to each node. This cost is usually representative of the distance or time it takes to travel to the node, however this may not always be the case. If desired, the cost could literally be a monetary value required to travel from node A to node B.

Once the cost of traveling from node to node has been assessed, the A* algorithm can be applied to determine the most cost effective path. This is without a doubt the easiest part of the path finding process. The hard part is selecting our nodes.

When you hear the word node, you may be tempted to think of a single coordinate in space. Most of the time this is not an incorrect assumption, however in a comprehensive 3D game engine, path nodes are usually represented as geometry. These bits of geometry are more commonly referred to as Navigation Meshes (Nav Meshes for short).

Image captured from Reddy Sambavaram's GDC presentation

Nav Meshes are convex 3D polygons which are used to represent the space that NPCs can traverse. In the path-finding algorithm, these are our nodes. Nav meshes can be (and have historically been) generated in different ways. In Resistance 1 and 2, the nav meshes were laid out by level designers in Maya. Eventually this system was overhauled in favor of an automated nav mesh generator in the team's world editor. Insomniac's process of automated nav mesh generation uses voxels (3D volumetric pixels) to approximate the traversable area of the game world. This is done in a step by step process as follows:

Image captured from Reddy Sambavaram's GDC presentation

Once the nav mesh has been generated, and the A* algorithm applied we can move on to:

Step 2: Steering

Steering NPCs in a realistic way is mostly a combination of obstacle avoidance, and spline interpolation. These techniques ensure that enemies do not walk into objects, or move in boring linear paths. For simple navigation around corners, Insomniac uses the "string pull" method to smooth the AI's turning.

Image captured from Reddy Sambavaram's GDC presentation

For more complex sets of obstacles however, this technique is not enough

In scenarios with multiple small obstacles, "escape tangents" are computed for each obstacle. These are simply possible vectors which allow the NPC to avoid contact with the obstacle.

Image captured from Reddy Sambavaram's GDC presentation

Simply having NPCs move in straight lines while avoiding obstacles is not enough. These escape tangents are used as the basis of bezier curves which will produce a fluid, more realistc path of motion.

Ok, now we have NPC's that can avoid obstacles, and move along a spline. What else is left?

Step 3: Animation

In order for the AI to traverse a dynamic environment in a believable fashion, each NPC must animate differently according to obstacles/interactables in the game world. The most notable example is when the AI must traverse some sort of height difference, whether it be by climbing, jumping up, or jumping down. Insomniac solves this issue by using a system called "custom links". Custom links are like nodes, except they allow the designer to specify what animation the NPC will play upon traversal, and even allow the NPCs to modify the cost of individual nodes (for example if one NPC climbs through a window, the link's cost will increase while he does so). This technology allows for highly dynamic AI that can traverse the level in interesting ways.

These 3 main components when done right, come together to create very believable AI navigation in games. Insomniac does an exemplary job tying these components together, and with very impressive performance to boot. If you'd like to learn more about Insomniac's navigation ingenuity, check out Reddy Sambavaram's original GDC Talk (http://www.insomniacgames.com/navigation-gdc11/).

Blog Quest 1: Emotional Contagion (Round 2)

Similarly to my previous entry (http://jamesmakesgames.blogspot.ca/2013/10/blog-quest-1-emotional-contagion.html), this post is about a game that has impacted me emotionally and inspired me to become a game developer. This time, that game is the Metal Gear series. The franchise's genre-defining stealth gameplay, deep plot, and Hollywood cinematic production have made it into a household name and one of my favorite games of all time.

First of all, let's talk gameplay.

Metal Gear Solid was the first game I played (and know of) with a cover system. Unlike this mechanic's use in most modern third person shooters, the cover system was only useful for stealth (as Snake was unable to attack from cover). This feature was later improved in Metal Gear Solid 2: Sons of Liberty, allowing Snake to peek around corners and fire weapons from cover. This cover system undoubtedly served as inspiration for the cover system in Gears of War, which would eventually be imitated by the majority of subsequent third person shooter titles.

Before Marcus Fenix, there was Solid Snake.

As one of the earliest pioneers in the stealth genre, Metal Gear Solid was the innovator of many mechanics which have become standard stealth game staples.

One such mechanic was the radar system used in MGS1 and MGS2. This game (along with Eidos' Commandos: Behind Enemy Lines) was one of the first to use this type of GUI to display the field of view of enemy NPCs. This would later become very popular in other stealth titles.

My personal favorite mechanic to be popularized by the series is stealth take-downs. These close quarters surprise attacks have evolved with each game, giving Snake more options to dispose of his foes lethally or non-lethally.

That's enough talk about mechanics, time to talk about the feels.

The series has featured a number of different protagonists, the primary one being Solid Snake. Over the years Snake has matured into a complex character with a deep inner conflict. In Metal Gear Solid 4, Snake is told he has less than a year to live due to an accelerated aging condition related to his mysterious origin. The theme of certain death is explored throughout the game as Snake embarks on a suicide mission to destroy yet another military super weapon.

Aside from MGS4's particularly morbid tone, each game explores themes of patriotism, loyalty, compassion, and humanity. While the games do at times feel like movies, this is not a bad thing as the production quality of the in engine cut-scenes have always been top notch for the time. Below is one of MGS4's exceptionally choreographed fight sequences.

Fortunately these cut-scenes are not just about flashy combat and explosions. They are often filled with emotion and presented in experimental/interactive ways. MGS4 in particular has scenarios where gameplay and cut-scenes happen simultaneously via split screen. This seems confusing at first, but the tension created by seeing multiple characters' points of view is truly exhilarating

. 

This type of scene exemplifies the innovation and high quality presentation the Metal Gear Solid Series has become known for. 

Final Thought: If you haven't played this series before, I'm sorry for possibly spoiling it for you. That being said, you should still play it. If you're a long time fan of the series like me, I'm sure you can't wait to get your hands on Metal Gear Solid 5: Phantom Pain. So far the title looks to be even more innovative and well presented than the previous games.

Blog Quest 2: Design your game item

Have you ever found yourself wishing for non-existent items in your favorite games?

I recently played and beat Outlast, a horror game that pits you in an asylum gone awry with nothing but a camcorder. There were many times when the scared little girl in me was practically praying for a weapon (hell even like, a shovel would have been okay). But this isn't about Outlast, maybe I'll do that one next blog.

Allow me to introduce, Ryu's Bandana! The latest addition to Mario's arsenal. 

Art by Michael Musco

What exactly does it do? (Besides turning mario into a total badass). Mario learns the power of Shotokan Karate, mastering 3 powerful moves:

Art by Cory Goodwin http://coreygoodwin.deviantart.com/

Shoryuken (Forward, Down, Down + Forward + Sprint): This rising dragon punch stays true to it's name, giving Mario the ability to soar upward with a fiery uppercut. The move does 3 points of damage (a classic headstomp does 1 point), and makes Mario invulnerable to attacks during it's 3 frames of animation startup. Any blocks Mario's fist makes contact with will explode, releasing any coins or power ups contained within.

The only downside to this attack is it's recovery period. As Mario descends from his Shoryuken, he is left completely vulnerable to physical attacks and projectiles. That's right kids, just like in Street Fighter.

This attack is particularly useful against bosses as the move's invincibility can be used to avoid their attacks, and normal enemies tend to die in one hit anyway.

Art by Leandro Nerd http://www.2nerds.com.br/humor/a-verdade-sobre-mario/

Hadouken (Quarter Circle Forward + Sprint): Using the power of the "wave motion fist" Mario channels his inner ki into a ball of red hot fire. Sure he can already eat a fire flower and toss puny little tennis balls of fire at unsuspecting goombas, but believe me when I say this attack is far more powerful. The fireball does not disappear when it makes contact with enemies. It also does not bounce on the ground like the fire flower shot, moving in a straight line until it reaches the end of the screen. The projectile does 1 point of damage.

The major disadvantage to this attack is it's long start up time of 25 frames. Mario needs to be relatively safe in order to fire a Hadouken, or he risks being hit out of the move entirely.

Just pretend it's Mario. I do not own this art.

Tatsumaki Senpuu Kyaku (Quarter Circle Back + Sprint): Mario unleashes a furious tornado kick, traveling forward about 1/4 screen distance. If this move is executed mid air, Mario's gravity value is decreased by half causing him to float. This means the move can be used to reach high places (executed before apex of jump) or to glide for long distances (executed after apex of jump). This is not to say the move has no merit as a physical attack...

The Tatsu (Street Fighter shorthand) allows Mario to travel through projectiles while advancing with an attack. The kick hits 3 times, each dealing 1 point of damage.

Unfortunately this move is not completely fail safe, Mario's raised leg becomes the attack hitbox, but his head and upper torso remain vulnerable to physical attacks. That being said, the move is great for enhancing Mario's mobility and gaining the upper hand on pesky ranged enemies.

Final Thought:

Due to it's indisputable power, Ryu's bandana would have to be a relatively rare drop. A strong player may likely be able to hold onto it for the entire game.