Since the beginning of the video game revolution, one aspect of games has almost always been necessary to create an enjoyable experience for the player. This game component that I speak of is of course Artificial Intelligence. Without this crucial element, current generation games would not be possible, as non-player characters would have no concept of what action to initiate, to attempt to counter the player. What I feel is at the core of video game AI, would have to be how NPCs navigate throughout the game space provided. In one of our lectures with Dr. Houge, we discovered how navigation is presented in the Insomniac Engine from Insomniac Games. The main focus of the presentation was how navigation of NPCs (mainly enemies) can influence the immersion presented to the character. It was a very informative talk that covered many aspects of why level navigation is becoming increasingly necessary, as well as improved as our knowledge of AI deepens.
The lecture presented to our class was designed by one of the employees from Insomniac Games. This employee went into great detail about the navigation systems used by the engine, and which games they applied to from Insomniacs AAA lineup. In this blog, I will attempt to give my understanding of the talk given by Reddy Sambavaram and discuss how I feel these systems work and what sort of impact they have on the players gaming experience. To analyse this, I will begin with the earlier works of Insomniac, Ratchet and Clank, and slowly progress through their timeline and navigation development with games such as Resistance Fall of Man, Resistance 2 and Resistance 3. Before any of this occurs however, I will first touch on why navigation is necessary in games and what players can take away from a system that performs well. So without further delay, lets begin!
We as gamer's are always looking for the next best game to be released. Whether it be a FPS, RTS, RPG, or even a simple puzzle game. We are always looking for games that will make us feel immersed in the world, games that will transform these character models into living breathing entities. For this realism to occur and attachments to be formed, the game must have a solid AI. For this AI to occur however, the NPCs must move and act in a way that brings their character to life. When this navigation functions well, the player will feel involved and will feel as though the NPCs belong in the world. However, when glitches and errors occur in the navigation systems, the players immersion can be broken, causing the game to lose its magic appeal. This is one of the main reasons that game developers, such as Insomniac, are investing a large portion of their time and energy into creating a navigation system that feels very natural to the player and can occur without them realizing what is taking place.
In some cases, AI is a large and cumbersome task for level designers and developers. Having to input commands for the NPC to move from point A to point B, all the while avoiding obstacles C,D,E is very expensive in time it takes to implement from a designers standpoint. Even when this is completed, the designers must rigorously test the system to ensure that the animations flow realistically, while also following the path laid out for the NPC to follow. Noticing this problem, many companies including Insomniac are trying to move in a more designer friendly direction, by making the movement of NPCs a more dynamic action, instead of being heavily scripted. Many variations have come and gone in the industry, including such methods as sphere and box based approach, point and connection placement by the level designer, a 2D grid approach, as well as the widely used A* path finding algorithm method. Now although these methods all have their pros and cons, Insomniac has moved towards a mesh based system, which allows a mesh to be placed over the current game mesh, to outline where many NPCs can inhabit and not move towards. It is not a perfect system, sadly no system has been discovered yet, but it does offer many benefits towards Insomniacs titles.
.jpg) |
| An Enemy that would need to navigate in Ratchet and Clank: Deadlocked |
Now before I get into the navigation mesh method of navigation that was touched upon above, I felt it fitting to include a short summary of how Insomniac was doing NPC navigation, before the introduction of these meshes. In Ratchet and Clank: Deadlock, the enemies did not use any of the navigation methods used currently by Insomniac. Instead they used a way-volume representation system with connection nodes in between. The way that this system works, while simplistic, did the job at the time for the game. NPCs would inhabit these way-volume spaces, doing basic animations such as idling, seeking the player, and when necessary moving. To move from area to area however, the enemy would need to choose one of several adjacent connections. These connections were all previously laid out and designed by the team to give the most realistic movements for the NPCs, while still restricting where they can move. The systems used volumes as nodes for A* graph to determine which connection would be used to move in a direction to face the player.
 |
| An outline of the way-volume connection system. |
.jpg)
RESISTANCE: FALL OF MAN
Since the release of Resistance FOM was release on the PS3, the opportunities for improvement pertaining to navigation had grown in size for the team at Insomniac. The decision to implement the nav-mesh system into this title, truly led them on a path towards more intelligent AI and a more immersive gaming experience. For the production of the this title designers certainly had a tough task ahead of them. For the level to be designed for NPC navigation, the level designers were tasked with taking each area where NPCs could inhabit and laying out a nav-mesh in maya. At runtime on the systems, tools in the engine would take these meshes and convert them to convex poly meshes. After much time in the designing stage of the levels, the system actually functioned pretty well. This was because the polys of the mesh were treated as though they were nodes in the A* path finding algorithm, allowing them to move between separate nodes based on their needs and behaviours. It was a great revolution for Insomniacs nav system, however, the team ran into issues occurring in the PPU when navigating 8 NPCs, as well as their distance based Ai lod restriction. This sent the team back to the drawing board to think of ways to fix this issue for their upcoming title Resistance 2.
 |
| Nav-Mesh being implemented in Maya |
RESISTANCE 2
Moving into their new Resistance title, Insomniac had few goals in which they hoped to achieve to alleviate the issues that plagued Fall of Man. The team hoped to fix the PPU bottleneck that occurred with multiple NPCs, as well as fix or remove the Ai lod restriciton, while simultaneously adding in support for a 9x nav-mesh poly load. To start, Insomniac decided that by moving the processing of the nav-mesh system to SPU, they would be able to cure many of the problems that were associated with the PPU hitting a bottleneck. With this issue solved, the team was able to come to the conclusion that the convex poly idea of their mesh system was not well suited to the A* path finding. To resolve this issue, the team implemented a triangulated system, giving the navigation system less paths to worry about when moving NPCs. It was also necessary to use tri-mesh and tri-edges as A* nodes, to ensure that the shortest path was always being discovered. The final change made to the mesh system was a jump up and down parameterization. This would allow enemies the ability to climb certain objects to access more advantageous cover against the player. To achieve this, the team added different coloring of meshes based on height and accessibility.
 |
| Nav-mesh with the height addition |
With all of these changes being done on the mesh system, the team at Insomniac need to develop a new pathing system for the NPCs. At first, the team attempted to introduce a hierarchical path finding system. This system however came with its issues, as at times a high-level path would be established, without a low-level path being present. To try and fight this issue, the team implemented a path caching system to try and determine if there was a start and end point within the "successful" path. Although the system did eventually function as the team had predicted, it just did not save the system enough time during path finding to justify being added into the system. For this reason the team scrapped the idea of hierarchical path-finding and instead stuck with the A* method, making slight changes such as parameterizing path-queries to allow the use of selective nav-meshes by NPCs.
Another key element fixed during the development of Resistance 2 was the pathing around corners or the "bend point" of the turn. The issue during the production was that NPCs generally had to be running around a corner for the animation to play in a semi-smooth looking manner. The enemies were not slowing down enough during their turns in a realistic manner, as the currently implemented string pull approach was not allowing it. To combat this aesthetically unappealing look in the animation, the designers decided to add in a Bezier curve in the bend point. What this allowed to occur, was the enemies could arrive into the turn, target the midpoint of the bezier curve (in comparison to the bend point in the old method) and slow their actions for the animation to appear realistic and smooth. To allow many NPCs to be completing these animations and turns at the same time, the team made sure to keep the steering system very lightweight, as to not bog down the engine.
The final change the team came to in Resistance 2 was the use of the mesh to avoid obstacles in the environment while traveling on their path. For the objects in the game, each NPC was given a set of escape tangents, which when used will modify the path traveled to avoid collision with the object in the worldspace. As shown in the image below, when a capsule and a box object are loaded into the world, each object is given two different tangents to follow so as not to collide. Based on the path of the NPC discovered using A*, the system will make a decision on which tangent path to use to avoid these obstacles. This system came with a couple flaws however, as enemies were still getting stuck in objects, and enemies were being perceived as objects in the queries of other enemies, causing 80% of the time being spent on object avoidance alone. To combat enemies becoming stuck in objects, the system performed a sweep check during the course of every collision check. If the enemy would still collide with an object, the system would add 90 degrees to the path to avoid collision. To help with the time burden of enemies seeing each other as obstacles, the designers introduced a special chache they called the "Grim Cache" (Grims being in game monsters). Since they all contained the same threshold tolerance they had to maintain for boundaries, the Grims would function as a unit instead of individual entities, sharing information between each other on obstacles and which paths to be taken. It was an ingenious system that ended up fixing their issue.
.jpg)
RESISTANCE 3
Since so much was changed during the course of Resistance 2, there was not a lot of work to be done to navigation system when it came to Resistance 3. However, the team at Insomniac were very adamant about releasing the caches developed at the end of Resistance 2 in a more formal fashion. To accomplish this task, the team split the SPU into three different passes. The first of these passes was responsible for accumulating a list of all of the objects that would be in the path of moving NPCs. Next up was for the SPU to gather all of the boundary information of the obstacles and ensure that no NPC would get stuck in the object, or avoid it in an unrealistic fashion. Finally, the last pass would review the second step of the process and ensure that all of the tangents for the NPCs are set correctly and avoiding all the objects.
One of the more exciting and visible features that the team included in Resistance 3 was using custom links to further include the vertical movement of enemies. To allow the designers to add these custom links for things like jumps, ladders, etc. The team implement a box system for links instead of points on the mesh. These boxes were more adaptable when it came to level changes and allowed the designers to place the link and not have to worry about them at a different point in time. This worked really well with the A* approach as these edges (or clue edges) allowed the NPCs a more dynamic movement style instead of on the ground linear movement. In Resistance 3, we can see enemies jump from one rooftop, across a clearing to another, all because of these custom links implemented by Insomniac. It helped to really enforce the personality of the NPCs, as it really gave the illusion that they were thinking and communicating, while trying to get to the best position to thwart the players efforts.
 |
| An NPC uses the custom link to climb the wall! |
CONCLUSION
Before learning about how Insomniac handles their navigation, I was unaware of the challenges that came along with moving an NPC from point A to point B. With the evolution of the AI and navigation we as players are starting to realize the potential for games and how NPCs can be given real emotion through there actions. I can not see this area of the industry slowing down and I can not wait to see what the big name companies will bring to the table in the coming years.
No comments:
Post a Comment