Insomniac Games
The information on this blog comes from the talk on
Navigation in Insomniac Engine at GDC 2011, found here. Reddy Sambavaram
speaks about the evolution of the AI Navigation from the ps2 to ps3, and in
several of Insomniac's games including Resistance: Fall of Man and Resistance
2, Ratchet and Clank Future series, etc. This blog will mainly go over the
sections leading to the end of Resistance 2’s AI development and methods of
navigation within their games.
A.I. in General
Well-designed/created A.I. is needed for the player to
properly have a challenge from non-controlled opponents. They must be created
in a way navigate similar to the player, to give them a worthy opponent. At the
same time these opponents must not be abuse able, where they'll be found in a strange situation. Remember A.I. stands for artificial intelligence, so as much as try to replicate our though processes, the AI probably won't be perfect.
Old AI- used in R&C deadlocked
In Ratchet and Clank Deadlocked, the last Insomniac game on
the PS2, had A.I. reminiscent of the PS2 era. First off all their paths were
hand made, and used way volume paths. Simply referring to the picture above, it
meant traveling from point A to B using these paths and volumes. Finally this
was all navigated using A-star, a common algorithm for AI used even today.
Nav Meshing
A Nav Mesh is simply a mesh which what the AI will use to
navigate the level. The mesh will be what the AI looks at when try to get from
one point to another. The mesh is either hand
created by designers, or created from a special tool. Also the designer can use this to predetermine where the AI can navigate to and where it can’t. The good part
about this, is that the mesh can be having fewer triangles than the actual
level, allowing for checking, and in the end faster path finding.
Resistance:Fall Of Man
When they moved to the PS3, Insomniac used navigation
meshes to help with AI for their flagship PS3 game, Resistance: Fall of man. Their work
began with a designer who would lay the nav-mesh out in Maya, after which tools
would convert them into convex poly meshes for runtime. The polygons were
treated as nodes in A* if they shared an edge. However despite the new method,
they still ran into an issue, only 8 enemies could navigate the mesh at once.
This was due to the “funneling of data”, also known as bottle necking on the PPU
(Physics Processing Unit).
Resistance 2 changes
There were many wanted Change with Resistance 2, however
with AI there was 3 major changes. First was the bottle necking issue, which
the team looked to PPUs and SPUs to fix. Second was the change of nav mesh,
where they wanted to have meshes 9x times the size of the ones in RFOM. Finally there
was the challenge of creating AI which would be appropriate for the 8 player
coop. The coop was a fun and frantic mode
which I have spent many hours on because of the AI’s successfully implemented.
Mesh changes
With the development of
Resistance 2 came a good amount of changes in nav meshes and their creation. There
were different sizes Nav Meshes in the level now, to deal with the different sizes of enemies, which ranged from the dog sized leapers, to human sized hybrids, and the
massive Titans. There were parameterizations for navigation of the mesh so
enemies can jump up and down ledges. Polygon shapes created for the nav mesh were
not acceptable anymore, so just good old triangles could be laid down. However meshes
were clustered together, separated by colors, to allow for the creation of
these polygon shapes.
A* or Hierarchical path finding
With the change in meshes, the
team debated whether to use the A* algorithm, or a hierarchical path finding. Hierarchical
path finding is an organized method which went through all the mesh, first at
a high level and then at a lower level. Unfortunately this method had issues
when creating a path, as the lower level path wasn’t always created. However at
the same time, path caching was introduced, which allowed for efficient checks whether
the path can successfully make it to its end point. This method allowed for A* to
have a better computation time when finding a path. Also AI would generally
just move from one end of room to another, so Hierarchical path finding wasn’t
as useful. In the end A* was used, and Hierarchical path finding was scraped
for Resistance 2.
Path Corners
When turning around corners with AI, there is always an issue with
the proper path and synchronization. This issue was especially prominent with
the new zombie enemies, the Grims, since they ran fast! Fast as in 8 Meters per
second, and the IG wanted to keep this speed, despite the problems in syncing
the animation and orientation of Grims. To solve this issue, a Bezier curve was
implemented to tune the path. The path helped the enemies properly find their way
around corner with a nice curve.
Grims
As mentioned earlier Grims were on of the
tricky enemies to create, because they would come in huge swarm. With Grims, there
were times where up to 50 of them would run through a narrow corridor and about
100 of them in the coop. This would be dangerous to performance since each grim
had to see every other grim as an obstacle, while checking for the local
environment obstacles.
The team came up with a special method of
doing this, called the “Grim cache”. The spark of this idea was that all the
Grims shared the same threshold tolerance they had to maintain from the
boundaries. The cache would allow every Grim obstacle would look around the
boundary edges and cache the closest distance to the boundary for each
one. This was similar to their obstacle avoidance method which was used
for other AI. In the end seeing dozens of Grims swarming you from every
direction became of my highlights of playing Resistance 2.
In
fact because of this I was so impressed with the Grims, the Grim skin became my most
favourite Chimera skin to use in competitive multiplayer. :P
Eliminating the Bottle neck: Using the SPU and PPU
To fix the bottle neck, they moved the
processing of the nav-meshes to the PS3’s SPU (Special processing Unit). To push all the processing on to the SPU, Insomniac
batched all the nav queries and ran it full-frame deferred on the PS3’s PPU.
All data access was isolated to be pushed to the SPU. A nav SPU job had to be
created, which included finding a point on a mesh query, with some restrictions
and finding a path between the start and the destination. This is in addition
to computing the obstacle processing data for steering behavior.
The SPU processing was split into 3 passes:
accumulation, finding nearest boundaries, and flagging tangents. The first
accumulated all obstacles in all paths, and the second gathered the nearest
boundaries for obstacles. The last pass ran through all the paths, once more
looking at all the obstacles and their boundary edge threshold tolerance. This
was computed in the previous pass, and it would be used to effectively flag the
tangents appropriately. This tangent is used for AI to properly make a path
around a corner, and other situations.
Conclusion
In the end, with all the extreme changes in the AI help
Insomniac game achieve their ambitious goal of making Resistance 2. With only a
year of full development I was very surprised to see overall quality of the
game come out. Despite the overall lack of quality, the MASSIVE scope more than
made up for it. In fact Resistance 2 stands as one of my most favourite
shooters for being respectable in compromising quality for a scope unseen in
most games. Hopefully this analysis of
all their processes put into the AI will inspire someone (or me) to make a game
of similar scope one day :D.
