Tag Archives: insomniac

Navigation mesh as used in insomniac games

A navigation mesh, or navmesh, is an abstract data structure utilized in AI applications to aid agents in path-finding through vast spaces. Meshes that don’t map to static obstacles in the environment they model offer the additional advantage that agents with access to the mesh will not consider these obstacles in path-finding, reducing computational effort and making collision detection between agents and static obstacles moot. Meshes are typically implemented as graphs, opening their use to a large number of algorithms defined on these structures.

One of the most common uses of a navigation mesh is in video games, to describe the paths that a computer-controlled character can follow. It is usually represented as a volume or brush that is processed and computed during level compilation.

Games are striving for a more immersive and fun experience and Non-Playable-Characters in game play a huge role in it as it gives NPCs the ability to perceive the world around them, react according to situation is a fundamental element of the game.

How AIs navigate is often how design gives personality to the NPC in the game. Designers are not burdened with movement implementation and let him/her worry about higher level aspects of game as it should be. The industry is moving away from heavily scripted AI to more dynamic and innate movement solution as usually AI usage comes in as few commands into the system.

NPC also uses system to scan for targets to feed it back to AI logic to monitor threat perception by AI & player. Also used to determine ‘spawn’ locations in the level. Resistance single player levels reused by multiplayer designers, various world representations have been used as a result

Navigation-mesh has gained considerable current reception. A* algorithm and its mods are typically used for path-finding on the navigation world following covers our experience, implementation and progress path-finding (A*) had volumes as nodes.


Designer laid out the entire level navigation mesh in maya, polygons are represented as nodes and edges as connections for A*. Navigation was one of the big bottle necks on PPU; maximum soft limit of 8 navigating NPCs at a given time. The lod system was put in place so NPCs at a distance did not use nav and went to great lengths to stagger the nav queries across frames even with above limits.

It was different production cycle for PS3 launch. If you look at RFOM levels . 3 RFOM levels shared a theme and wanted that to make one Resistance 2 level. Level streaming took care of rendering but nav was monolithic for whole level design planned to increase nav poly density by 3x. we were making 8 player co-op mode which implied enough NPCs to keep 8 players engaged in some encounters.


Tri-edges are A* graph nodes and polys are connections/links in the search graph which provide customization abilities like jump-up and jump-down distance A* parametrization now possible. It introduced Hierarchical path-finding and used A* among poly-clusters to calculate coarse path in order to refine NPC’s immediate path with in poly cluster as needed

They ran into inherent disadvantages of the scheme where in it doesn’t give shortest path which designer expects as a result path caching was added. NPC’s new request for path was checked against its last successful-path (high hit ratio) and made cost estimates in A* do more work which removed edge-mid point to edge-mid point for cost estimate that computed point on edge which minimizes cost (greedily) to be outputted path hardly needed smoothing.

A* at the time was so low that we took out hierarchical path finding. Hardly spent 10% of navigation shader budget on A* even in co-op mode with ~100 NPCs using navigation on screen. Path-finding was changed to consider more parameters ability to jump up/down various distances where we use one navigation-mesh for varied size NPCs.

A* considered NPC’s threshold clearance when searching the design used above feature to selective path among AI. They preferred corner radius (maintains radius away from boundary) and full-frame deferred navigation queries. The game-play code was changed to  use navigation data as queries while AI synced previous frame results and set the query for next frame’s needs. Code was streamlined to batch all navigation queries. Navigation query data access was also isolated for concurrency needs. Readied for shader offloading of navigation processing to find point on mesh query given a volume and parameters, outputs closest point on mesh maintain NPC’s tolerance radius away from boundary. Navigation-mesh cluster’s AABBs are kept in LS for broad-phase.

Read navigation query results from previous frame, steering the setup navigation queries for next frame’s animations and physics setup update. Animation shader jobs are added, physics shader jobs are added and navigation shader jobs are added. Could have run anywhere after pre-update to next-frame’s pre-update.

All the navigation queries were full frame deferred (gameplay issues reads results from previous frame’s issued query, steers and setup up for next frame if it has to)


One mesh is used for all sized AI so string pull doesn’t maintain NPC’s tolerance away at corners. The issue, especially for big NPCs like Titan in Resistance (where they would try to cut across the edge).

NPC has to not only get to first bend point but also need to orient towards the next bend point in the path. Navigation shader job computed the bezier approach curve for the bend point.




Curve tangent is computed by doing a swept sphere check for the specified distance in the current NPC facing direction. The end curve tangents is computed by doing back projection swept sphere check from first bend point in the opposite direction of second bend point. The bezier curve is computed using above tangents. NPC always aim for the mid-point of the curve for smoother approach.

To support higher volume of NPCs, especially for 8 player coop steering used a simple dynamic avoidance for the shader to compute escape tangents for each obstacle it came across.


Steering span all escape tangents in a circle around the NPC and are picked the resulting direction is the valid vacant hole closer to the desired direction towards the path bend point. Simplicity trade-off above in order to support huge number of NPCs running and it held up just fine. NPCs could still get stuck as picking the closest escape tangent would make it run into wall.

The game engine I am destined to create

Every aspiring game developer has hopes of making the next great game, or for those who are more realistic, make a game that can be enjoyed by people while paying your light bill. Strangely enough, it’s usually those starting out in their game development school who think the former while people with more education in the field along with more experience tend to sway towards the latter.

Does it necessarily have to do with the fact that our youthful energy is being syphoned out of us as we progress?


Considering it is university yes, however the main reason is as we mature we develop a more realistic outlook on things which makes us set realistic goals. How you set the scope for your projects may make or break it with carefully consideration of your resources, talents and limitations.

Hence why we’re studying Game Engine Design and Implementation, to culminate all our coding knowledge so far to be able to put together a workable engine that can support graphics, animation, gaming mechanics and all our gaming knowledge. So for this blog, I will talk about how I would design the engine of a standard platform game.

The term game engine was coined in the nineties in which it was referring to first-person shooters such as Id’s prolific title Doom due to how intricately its architecture was defined. With separation between core software components, art assets and gameplay mechanics, this is when developers started licencing games and re-tooling them into newer games which opened a whole new world for independent studios and other small organizations.


The game in question will be based on Uncharted’s engine along with the player mechanics of the Spiderman games and the recent Ninja Gaiden games. Given that the engine in question contains many of the ideal mechanics required to put out a solid platformer on the level of Crash Bandicoot which was also created and published by Naughty Dog.

I intend to use this engine as a template for other types of games such as adventure and fighting games since those are the types of games I intend to make and both games require the following:

–       A third-person view camera that follows your characters and stays focused on the players general area in order to focus on its location and the surrounding radius to alert the player of incoming hazards.

–       A camera collision system to ensure that view points never go into places it’s not supposed such as into the background or into a mountain.

–       A rich set of animations rendered for all sorts of commands from climbing to fighting.

–       User inputs that allow players to execute all sorts of tasks.

I mentioned earlier that I aim to include the player mechanics of Spiderman from the Spiderman games and Ryu Hayabusa from the Ninja Gaiden games. Why you ask? Because both characters both characters can do virtually anything; from jumping to climbing to fighting. More than most characters, they do the best job of making the player feel like their capabilities are limitless.


Spiderman for the Playstation, the game the developers of Superman 64 wish they’d made.

There has never been a concrete measurement or assessment of how a game can be good as games can be good for several different reasons, in my opinion, I think the ultimate way to determine a game’s quality is to identity how deeply you can immerse players into the experience and what better way to do so that with a character who can do just about everything.

This is why user inputs is very important, the possibilities of the game’s world is placed in their hand and the transition from one action to the next should be seamless and effortless on the part of the player.

In order to ensure an acceptable framerate it’s important to design the engine so that it can manage all the objects on screen without slowing down the action. In this regard we can take a page out of Insomniac’s hit title Spyro which managed to create massive worlds with distances that expanded to the horizon without relying on fog effects, this was done writing code that would decrease and increase the polygon count of far away objects relative to your character’s distance. This way objects can be slowly loaded over time so as not to overload the console.


Platformers tended to be drawn and designed in cartoon like manners with little emphasis on realism. I grew up with cartoons and platformers such as Mario, Crash Bandicoot and Sonic, so I intend to use such a style. Many of these games relied on principles of animation such as anticipation, squash and stretch, pose to pose, timing and exaggeration in order to achieve the cartoon-like style they were aiming for.

Most of these games were made before Smilebit’s Jet Set Radio spearheaded the use of toon shading in games. I like the toon shading effect because it gives games the comic book feel that I like, however since most of these games were animated and rendered the way they were prior to cel-shading, it’s important to realize that just combing them would be overkill, so it’s important not to just throw them together but to create a balance.

Motion capture generally results in the smoothest and most realistic movement animations so I appoint to utilize it with motion capture artists who can capture the exaggerated movements of cartoon characters in conjunction with the model rendering to capture the less feasible principles such as exaggeration when it comes to characters changing size for the sake of humor.

That’s all for now, it’s still pretty early in the course with much to learn on game engines hence my immature knowledge of the subject, so I just gave you may basic understanding based on previous education and a lifetime passion for gaming. Stay tuned to my blog and see how far I come with my understanding of the topic.