Thursday 12 December 2013

Game Engine Design and Implementation: A Semester Post Mordem

It's been a long, hard semester but it's finally coming to an end. The past month has been overwhelmingly busy between programming Gamma Gears and wrestling with course work and the like. In this blog, I'll talk about a few of the lessons I've learned this semester and a bit about what I've been up to.

Lesson 1: Gamedevs Don't Do Documentation.


At the start of the semester we were required to use a pre-made engine, despite my requests to use our Dungeon Boy engine from GTFO: The Double Dungeon Debacle. My professor felt that by using a third party engine (in our case Sony's Phyre) we could get straight to the making the most important part, gameplay.

Yeah I mad.


I didn't believe him for a second. We had a pretty good workflow with our existing engine with working combat, and all necessary game engine components working in acceptable capacity. Getting set up with a new engine would take time. There would be so much troubleshooting and failure ahead, with no merit to what we had previously accomplished.

A wise prof once said: "Gamedevs don't do documentation". I thought he was kidding before I met Sony's Phyre Engine.



When using a tool as extensive as a game engine for the first time, there is a lot of uncharted territory. In some cases it's like being given a bag of futuristic Alien tools with little to no instructions on their intended use.

Samples like these were our primary means of deconstructing Phyre.


To clarify, the engine does come with some documentation that will get you started, but there are many common tasks that are not detailed or covered. The instructions are often incomplete and downright negligent. In order to get started making a game with this tool, I had to deconstruct the few sample projects I was provided with. Unfortunately none of these sample projects contained any form of combat, so this left me with very little reference for that aspect of the game. Chances are if you didn't help make Phyre engine, you're going to run in to some issues.

Thankfully for some of the more technical issues (like how to create a phyre base project) we were able to get help from one of our fellow classmates. His blog can be found here: http://mikedaprogramma.blogspot.ca/

Lesson 2: Choosing an engine should be about the right tool for the right job.

To make a long story short, development on Gamma Gears was slow and often confusing. Due to the intense learning curve in working with Phyre and minimal of availability of assets early on, getting the basics up and running took much longer than expected. Once we managed to get our skeletal animation system working, we had decent animation and locomotion with environment collision detection. All of these features were implemented in script as recommended in Phyre's documentation and demonstrated in the samples. We took this approach so that we could build our game scenes using the Phyre level Editor which we thought would make things easier. Not to mention the samples were implemented in this way. Once the game is constructed in the level editor, the assets are exported and the scene can be loaded in code.

We ran into problems when trying to access data between our script (lua) and code (c++) platforms. This was most likely due to our own inexperience with the tools, but as a result we were unable to implement certain "code only" features such as GUI and audio.



To make matters worse, despite my best efforts at implementing combat in script, things just weren't coming together.

I knew I had to present some form of gameplay to my Game Design professor today, so last night I coded a combat prototype using our Dungeon Boy engine in about 12 hours. Many new systems had to be added (multiplayer input, chain combos, multiplayer camera), as well as countless adjustments to movement, collision, animation states, and assets. This was only possible because I was working with tools that I had created.

Working Title Screen: Check

It may not look like much, but this is gameplay. There was very little time for visual adjustments.
I can't wait to sleep after this blog is over. 

In 12 hours we achieved fully functional 1 on 1 multiplayer combat (I wouldn't say it's super fun yet but you can beat eachother up pretty good), with GUI, sounds, and a basic restart event. This build is sadly, more playable than our Phyre build, which I've spent at least 10 times the hours working on.

If there's a point I'm trying to make here, it's the one about getting right to the gameplay. Sometimes the right tool for the right job is the one you made yourself.

Lesson 3: The Shawarma effect

Mmmmm Shawarma.


The shawarma effect is a term that refers to the continuous stripping down of an idea or project.

Often when designing games, the initial scope is set too high. The process of refining the idea is usually very much about simplifying it into it's most important parts. Over the course of the semester, Gamma Gears has been many different things. The Gamma Gears (both prototypes) you see in this blog is nowhere near as complex as planned in the design document. It's meaty bits have been trimmed down until only the base is present. This is a natural reality when creating early prototypes of games, especially when running on a tight schedule.

To deal with the shawarma effect, it's important to strip your game down early rather than later when it's time to actually implement your design.

Thursday 5 December 2013

Camera Systems: The Good, The Bad and The Ugly

I don't know who this guy is, but I hope you agree that his face is awesome.

Camera systems in games play an extremely important role in delivering an enjoyable experience. Not only does the camera represent the viewpoint of the player, it is also responsible for delivering a visually pleasing and functional scene. In this blog I'll be discussing some camera systems from older games and eventually, some much better ones from a few newer titles. Over the years developers have learned from each other's mistakes, and gamers' standards have risen. Back in the day, bad cameras were almost an acceptable part of 3D games. Now as games continue to grow in complexity, so do the cameras that power them.

Ok let's get started shall we.


Old Games, Bad Cameras:

Early Resident Evil Games

I remember this game being so scary in 1996..

Despite being one of my favorite game series' (with the exception of RE6), the Resident Evil franchise has had a history of awkward fixed camera systems. This was largely due to the levels being made up of 2D sprites (pre RE: Code Veronica). Often the player would be engaged by enemies located off screen, or occluded by objects in the level. To make matters worse the movement controls were not relative to the camera, giving the characters a tank like feel. Some would argue that the early RE games owe their scariness to the fumbly controls and awkward camera angles.

Skip to 6:24 to see what I mean.


Capcom eventually learned their lesson with Resident Evil 4, popularizing the now standard "over the shoulder" camera perspective. We'll talk about this one in the "good cameras" section.


Early Tomb Raider Games

Again don't get me wrong, I love these games. But boy did the camera make me rage.

The Tomb Raider series was one of the original innovators of the traditional 3rd person camera. The camera is offset a certain distance from Lara in the Y and Z axes, and follows her constantly. The camera interpolates to Lara's orientation as she runs forward (but not when turning on the spot). This is all well and good for the most part.

The real problems arise when the game's camera collides with the environment. This can make it very difficult to make precise jumps, or avoid the game's lethal obstacles. Combine this with the camera being unaffected by enemies (on screen or off) and you're in for some pretty frustrating scenarios.

Dishonorable mention: Prince of Persia Warrior Within

SPOILER: Sands of Time was better.

As you probably guessed, I am a fan of the Prince of Persia series. The camera system in the Sands of Time trilogy was very good for the most part. However in Warrior Within, whenever the Prince encounters "the Dahaka" the camera takes a turn for the worst (no pun intended).



The transitions from third person camera to fixed camera can be quite jarring, especially since the camera is moving in such a way that the player cannot see the platforms ahead.

Thankfully they did not continue to use this system in subsequent Prince of Persia titles.

Games with good cameras:

God of War


There are many cases where a camera system is so natural that we as players don't notice it all. Chances are if nobody is complaining about it, the developers have gotten it right. God of War is known for it's brutal cinematic gameplay that makes you feel like a total badass. The game gives no camera control to the player as the right analog stick is used for dodging, yet somehow it works nearly flawlessly.

The series is partially responsible for popularizing the node based, cinematic action camera. This camera system involves interpolating between set camera nodes (positions in 3D space) based on the position of the main character. Each camera node has it's own properties (orientation, field of view) that are also interpolated accordingly. The main character's movement may also have a weighted influence on the camera's movement depending on the scene.

In combat the enemies and player become weighted nodes, each with their own varying amounts of influence on the camera's target position. The larger and more threatening enemies have a greater influence than the smaller pawns. This ensures that the scene is always well represented, and the player rarely dies to off-screen threats.


The game makes heavy use of quick time events (QTEs) which trigger a separate camera, synced to the animation of the event. As the animation progresses (Kratos decapitating a poor foe), the camera shakes and interpolates along a curve. These camera curves are specified in the QTE animations themselves.


Resident Evil 4


Resident Evil 4 was a major departure from Capcom's previous RE titles. For starters, the worlds were rendered in full 3D. While Code Veronica and Resident Evil Zero had already used 3D environments, this was the first Resident Evil game to adopt (and perfect) the "over the shoulder" camera. 

This camera is fully controlled by the player, giving them precise aim during combat and a close up view of the game's many puzzles and objectives. These were two firsts for the series which lead to a change of direction to more action based gameplay, especially in subsequent titles.

Metal Gear Solid 4

I can't write a blog about cameras and not mention the Metal Gear Solid series. Notorious for being more movie than game, the MGS titles have always had a cinematic quality about them. Metal Gear Solid 4 is no exception.




As demonstrated in the video above, the game makes use of a variety of different cameras depending on the gameplay situation. The primary camera is a third person orbiting camera centered on Snake. It can be manipulated completely via the right analog stick. During combat, snake must aim in either first person view, or and over the shoulder view reminiscent of RE4. Gameplay aside, the MGS series has some of the best cutscenes in video games and much of this is thanks to the camera work. A typical MGS cutscene features many spline paths for cameras to interpolate along, as well as realistic camera shake and spring functions to make things feel lifelike.

If there's any one game that's demonstrated pretty much every camera technique I've mentioned (and more) to a tee it's this one.

So what have we learned?

A good camera system doesn't just need to make a game look pretty, it also has to work! This may seem self explanatory, but it can be easy for a camera to ignore information that is vital to gameplay.

Tuesday 3 December 2013

Game Dev PvP Fight: A Portal 2 level Peer Review


Today I will be taking a critical look at a Portal 2 level made by a good friend of mine, Cole Bonvarlez (http://colebonvarlezgd.blogspot.ca/). I've made two of these myself which can be found on my Steam Workshop page (http://tinyurl.com/le8hdwb). You can find Cole's level to try it for yourself at this link (http://tinyurl.com/nx7teoj). Now without further ado, let's talk about my impressions of this puzzle.



The first room serves as a hub to the level's two other small chambers. I found it to be somewhat confusing in the beginning, since my initial path lead me to a dead end with a large gap.

This is where I ended up for following the most natural path (according to the player's starting trajectory. 

It's clear that I need to launch myself across the gap with the help of the angled platform which you'll need a cube to trigger.

After seeing that a cube was necessary to progress, I began to backtrack and found another room beside the initial entrance. Although there is nothing "wrong" about this placement, I personally would have opted to switch these two rooms' locations. I say this because there seems to be a slight disconnect between where the player should be looking, and where they should be going. However, one could argue that this simply increases the puzzle's complexity and Cole may have done this intentionally.

The cube chamber has multiple buttons that are supposed to be pressed, however only the one that drops the cube is necessary thanks to a poorly placed grating that allows for early access.

So I've grabbed my cube through this grating, shimmied it over the wall and am ready to go back to the previous dead end.

Ok, the cube is in place and I see an angled platform with a very high, portal able ceiling. This is clearly a momentum based, falling launch type maneuver. Unfortunately, despite fully knowing what to do, the tile placement was a bit tricky for me to fall with the correct orientation to shoot the exit portal at the angled platform. The solution requires the players to orient themselves to face the away from the gap, such that when they fall through the portal they are facing the angled platform.


Once I crossed the gap I was met with a companion cube, a switch, and a laser shooting at a blank, portalable wall.

The necessity of the cube was questionable to me, as it was placed directly beside the switch it was designed to trigger. This cube is not useful for any other task so in my opinion a simple button switch would have been a better, less confusing choice. I do however like the use of a "bounce" here, as the switch enables a light bridge that brings you back across the gap. Cole sees that you've already earned your way across once, and allows players to forgo the deadly goo on the return trip.

Before heading back to the main room, you'll want to leave a portal for the laser to shoot into. I'm telling you this because I didn't realize until going all the way back to the hub room. To be honest, this laser is placed a bit too far from it's trigger for my liking. Again this may have been a conscious choice on Cole's part. 

 After using the laser to trigger it's receiver, this button becomes accessible, initiating a somewhat time consuming sequence of a ball being launched across several bounce pads, until it finally lands inside a tractor beam in the hub room. When the ball reaches the top it triggers a switch that allows access to the final room.

The final room is a series of two momentum based jumps. The first uses an angled platform and is similar to the first large gap, the second is simpler and requires little to no finesse to cross. The entire floor is portalable and there is a significant drop. A portal is placed on either side of the floor and simply jumped into, giving the player more than enough height to clear the edge. 


Unfortunately if you do manage to fail in crossing these gaps, the only way to get back is these elevator platforms. These would not be so bad if the trigger switches were placed in a more friendly manner. In order to trigger the switch and still ride the elevator, you must be standing right on the edge of the platform.

All in all I had fun with Cole's level despite a few moments of confusion. To be honest it took me a little longer than expected to beat, clocking in at at around 10 minutes. If I had to give any particular criticism it would be regarding Cole's switch selection and placement throughout the level. I feel some of the triggers could have been placed to be slightly more player friendly and less confusing. Also, I would recommend that next time, Cole evaluate where players tend to look and tailor the flow of the level with regards to this.

Thanks for a fun level Cole, and I hope my feedback has been of use. Feel free to review one of my levels some time!


Benefits of Scripting and it's use in modern Game Engines

A few popular examples of General purpose scripting languages

Scripting is a powerful tool that allows a game engine to become dynamic and highly modifiable. This tool can drastically improve iteration time, and serves to empower content creationists among other benefits. In this blog I hope to explain what makes scripting so beneficial and give a brief rundown of how we'll be implementing scripts in my team's upcoming game.

Naughty Dog's take on scripting at GDC '09

Having a scripting system in place means that core game-play features can be implemented in a much simpler environment (Editor tools such as UDK, Unity or Phyre) without touching any of the C++ code. This gives content creators the ability to script complex scenarios, and most importantly manipulate component based game objects. 

That was a bit of a mouthful. 

What exactly does component based mean?


Examples of components in Unity


Using a component based model means that game objects are composed of an assortment of components, each with their own properties and scripts. This makes it possible to create highly complex objects with a variety of functionality, all within a simplified scripting interface.

In example 1, the AIComponent is pre-built before being added to the entity. The content creator can only select an AIComponent based on what was specified by the programmer. In example 2, the AI states are created as separate components and are modifiable by a designer without interference from a programmer.

From Damien Isla's GDC '11 presentation on scripting

Script can be seen as the glue that binds an object's components together. It tells each component what to do and how to communicate with other components and other objects. 

Component based, script heavy models have the benefits of being easy to use and very agile. They also help to easily separate the re-usable engine code from the game logic specific to any one project. This is extremely convenient for fast iteration and prototyping.

Working with scripting and component models in Phyre Engine:

Sony's Phyre engine includes a level editor tool that uses lua script to provide a powerful environment for content creation. In Phyre it is possible to instantiate and manipulate components in both C++ and script. The scripting component to Phyre is heavily emphasized and has been the main basis of everything we've implemented in our game thus far.



Here is an example of our main character's game object. You can see he contains a small collection of components which handle various tasks.

- Physics Character controller: Contains a script that handles physics based movement and collision detection.
- Character controller: Contains a script that handles animation according to user input and the movement output from the physics character controller. Interfaces with all other components.
- Animatable component: Contains the animation sets for the character exported from maya. Manipulated by the character controller component.

How scenes are constructed in Phyre:

Assets and Components are stored in the palette view where they can be customized.

Instances are created in the objects box, and are populated with components and assets by dragging them from the palette.

Here is a simple scene in our current work of progress game build. It's objects are displayed in the object hierarchy above.

Why not make everything in script?!


So far I've only said good things about the use of scripting. That's because it can be extremely useful and versatile as previously stated. However it does come at a cost to performance. Due to the nature of run-time scripting languages it may not be optimal to implement performance heavy tasks using script. Of course this is very dependent on the specific game engine/implementation and the strength of it's code/script relationship. Phyre engine in particular contains script access to complex code systems such as animation and collision detection. In fact, all of our animation, physics and locomotion code is currently being done in script.

That about wraps up my discussion of the power scripting languages add to game engines. If you have any questions or are looking for any specific information regarding Phyre engine feel free to leave a comment, it seems the documentation is sparse and the forums are non-existent.






Sunday 1 December 2013

Dekonstruer #1: Game atoms of Street Fighter 4


Chances are if you know me personally, you're aware that I'm pretty obsessed with Street Fighter. I've been playing the series since before I can remember (Street Fighter 1) and ever since, fighting games have had a special place in my heart. Over the years I've played more fighters than I can keep track of, each with their own unique mechanics and nuances. Although every fighting game plays differently, every one of these games share common design elements which can be traced back to Street Fighter 2. Although this post will be talking specifically about Street Fighter 4, many of the design aspects I'll be covering are present in other fighting games and date back to the SF2 days.

Yes, this is Zangief's actual ending from Street Fighter 2

To be clear, I won't be talking about any elements that are non-essential to game-play. That means the plot (terrible), music (fantastic), and AI (useless) will have to be discussed elsewhere. As a competitive player, I'll be focusing on the topics relevant to high level play. Many of these topics will not be encountered by novice players, but rest assured they are very real and very important to the game and how it was designed to be played. Alright enough chit chat, let's get started.

For the purposes of this blog (and my grades), I will organize these topics into "Game Design Atoms".


Objectives/Goals:


The primary objective in Street Fighter is extremely simple. Deplete your opponent's life bar by landing as many blows as possible. Try to prevent the opponent from depleting your life bar by defending against or avoiding their attacks. When one player's life bar reaches 0 they are knocked out, and the other wins the round. If both players are knocked out simultaneously, they are both awarded a round. If this is the final round, a draw game occurs.

There is a secondary objective in Street Fighter, and that is to control space. What this means, is using physical attacks and projectiles to dominate the space surrounding your character, forcing the opponent either move away or challenge you for this space. The importance of space control in high level play is extremely vital, as being walked into the corner can lead to nearly certain death against a strong player. Although it may not be immediately apparent to new players, good space control is directly related to how much control you have over your opponent.

Sequencing: 

Street Fighter is a game that unfolds in real-time with both players making decisions simultaneously. It is regarded by some as a "double-blind guessing game", because when a player makes any given decision, they are unaware of the opponent's current decision. This is not to say that the game is all about guessing, there are certainly situations where one player reacts to the move of another, but when it comes to neutral situations the game does rely heavily on educated guessing.

Accomplished game designer David Sirlin explains it best.

Players/Interaction: 


In Street Fighter or any other 1 on 1 fighting game, your experience and enjoyment of the game is heavily dependent on the opponent you're playing against. If both players are evenly matched, chances are the experience will be enjoyable for both as the win/loss ratio will be relatively even. If there is a significant skill gap between players, it will likely not be enjoyable for anyone involved. The weak player will be losing consistently to tactics they may not understand or know how to counter, and the strong player will receive no stimulation from such empty victories.

Super Street Fighter 4: Arcade Edition currently features 39 playable characters, each with their own unique move-sets, mobility options, health/stun ratings, and throw ranges. These characters are all widely varied to cater to as many different playstyles as possible. I make no exaggeration in saying that players are allowed to express their individuality through these characters. Although these characters were created with certain tools in mind, thanks to the emergent nature of Street Fighter's gameplay (and fighting games in general) players are free to invent their own strategies, combos and advanced techniques within the game's set of rules.

Player interaction is arguably the deepest aspect of Street Fighter. Two competent opponents who have full knowledge of their (and each other's) characters will play an intricate mental game of high speed chess. Both players know each other's options and the risk/reward associated with any given choice. Each player must attempt to read the mind of the opponent to achieve the upper hand.

Rules/Mechanics:

The rules of Street Fighter mostly pertain to what actions a player can or cannot perform when in a particular state. There are 4 main states a player can be in at any given time. They are as follows:

Neutral: The player has not committed to an attack, and is not being attacked. He is free to move, attack, or defend.

Hitstun: When a player gets hit with an attack, they enter a state where they can do nothing. The hitstun state's length is completely dependent on the move that inflicted it. If the attacker recovers before the hitstun period ends they may be able to follow up with a successive attack, resulting in a combo. Players are not susceptible to throws while in this state.

Blockstun: This is a state similar to hitstun in that the player is not allowed to act and cannot be thrown. The major difference is that blockstun happens when a player blocks an attack. If the attacker recovers from their attack before the defender recovers from blockstun, the attack is said to have frame advantage. Moves that grant frame advantage are said to be safe, whereas moves that cause the opposite (frame disadvantage) are unsafe. Unsafe moves that leave the attacker open long after the defender has finished blocking are said to be punishable.

Attacking: When a player commits to an attack, they can do nothing but cancel it into another attack or action. The subsequent attack must be specifically allowed to cancel the previous attack, this is not a universal property. Although cancelability varies on a per attack basis, most attacks must connect with an opponent (hit or blocked) in order to be canceled. There are exceptions to this rule however. Some moves can be cancelled on whiff (not connecting with the opponent). Cancelability is only one of the many properties by which a moves' effectiveness can be measured. Here are the others.

Range: How far the move reaches.

Start-up Speed: How quickly the move becomes active.

Recovery: How quickly or slowly the move recovers. Subtract this from the hitstun/blockstun time a move inflicts, and you will know if it is safe, punishable, or can  be combo'd from.

Priority: How likely the move is to beat or trade with other moves when performed at the same (or similar) time. This is not a numerical value and is very situational as priority is dictated by hitbox interactions on a per move basis.

Invincibility: Some moves cause the character to become invulnerable to certain attacks for a short period of time. These are usually very unsafe on block, and are designed to be punishable if the defender knows they're coming. Think of this as forgoing future safety in favor of invincibility right now.

Damage: Self explanatory

Information:

The majority of the information relevant to a match of Street Fighter is clearly displayed. The health and meter indicators are a good indicator of who is winning the match. One important piece of information that is not clearly displayed to the player is the stun meter. When a character falls dizzy, it is because they have taken too many successive attacks and their stun value has reached it's limit.

The most important information that is not clearly given to the player is the properties of each move. It is impossible for a player to make educated decisions without knowing the properties of each of their moves and those of their opponent. Traditionally these properties are discovered through play and experimented with over time. Lately Capcom has become more generous in providing detailed changelists with move properties for each balance update to the game.

Game States:

Some may say, in Street Fighter all you do is fight. That means there's one game state, right?
Wrong. Over the course of the match, there are a few states that occur which are heavily responsible for the outcome.

Neutral Game
Succeeding in the neutral game means gaining some sort of advantage over one's opponent. This could be in the form of knocking the opponent down, scoring damage, or even having the opponent block an attack that leaves you at a frame advantage (remember that word?).
Two of the world's greatest getting ready to face off

The neutral game is the fundamental core of Street Fighter. When the match begins, both players start considerably far away from one-another. Once they are allowed to move, they shuffle back and forth, jockeying for position in an attempt to gain the upper hand. Each player understands which moves they can throw out safely, what moves their opponent will threaten with, and what tools (if applicable) they can use to counter their opponent's most likely offensive options. 


Getting In


When the aggressor lands an attack, the real fun begins. It is up to the attacker to recognize the hit has connected, and follow it up with an optimal combo if possible. This is known as hit-confirmation. A strong player knows how to convert as much damage as possible off of a single opening.

As a combo increases in length, each successive hit does a decreasing amount of damage. This makes it unwise to keep a combo going for too long, especially if it requires the use of super meter. If a player knows extending his combo will not result in significant damage, they may attempt a reset. A reset is a simple mix-up in which the aggressor forgoes the guaranteed damage of the current combo, in favor of a new unscaled combo or throw.

Knockdown/Okizeme


When a player scores a knockdown, they have a distinct advantage over the opponent. The downed player can not move, and can only act once they have risen completely. Since the timing of each characters rising animation is very predictable, the aggressor can exploit this with a well timed offense that is hard to block and safe to wake-up attacks. The word Okizeme is japanese term for "Rousing Attack", meaning attacking a downed opponent.

Resources:

The resources in Street Fighter are displayed in the form of the game's meters. The super meter allows your character to access EX versions of their special moves, as well as their unique super move. EX moves cost 1/4 of your super meter and have increased utility (or damage). The super meter refills gradually as the player does damage, takes damage, blocks attacks, or has their attacks blocked.

The ultra meter gives your character access to their unique Ultra attack. Ultras usually do large amounts of damage and serve as a comeback mechanic. The ultra meter (also known as the revenge meter) refills as your character takes damage.

Finally, the health bar can be seen as a resource. Your character's health is directly related to how many mistakes you are allowed to make in a match, and ultimately how much damage you are allowed to take. Sometimes it is beneficial to take a risk that merits high reward, at the expense of a little health. This is demonstrated to a tee in the Guile vs Zangief matchup. Guile is a pure zoning character who dominates from a distance, while Zangief is a grappler who must get in to do his damage. Observe Zangief's careful approach, and the calculated risks he must take to win.


Well, that about wraps up my rundown of the basic design atoms present in Street Fighter 4. Hopefully this was relatively clear and I did not use too many complicated terms. If you were unaware of all this before, now when you watch a game of Street Fighter you should be able to appreciate at least some of what's going on.

Wednesday 27 November 2013

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/).