Yesterday, the sequel for the The Last of Us sequel was released, a game that has been one of the most recognizable PlayStation exclusives for seven years. This is a cinematic story about human lives in the inhuman reality of a world destroyed by modern plague. At a time when players take control of the cynical and embittered protagonist Joel, artificial intelligence plays out other characters, be it an ally, an enemy, or an infected one.

Against the background of the second part of the game, we talk about why the players liked the original so much. In this translated article, we’ll talk about The Last of Us design philosophy that addresses all aspects of artificial intelligence.

ITKarma picture

Warning: this article is only about the original game of 2013.


About the game


The Last of Us is a third-person action-adventure game with a focus on stealth mechanics and a dynamic shelter system. In the world of post-apocalyptic America, players are forced to confront two types of opponents: hunters - people who control and patrol certain territories throughout the country, and infected - creatures that turn people who become sick with fungal plague.
“When we were just starting to prototype AI in the case where the enemy is a human being, the first question we asked was the following: how to make a player believe in the reality of his opponents so that he doesn’t want to kill them? The answer to this question became the basis of the design of the enemy AI. Answering it required more than just hiring the best voice actors, the best 3D artists and animators, although all this was also important. First of all, we needed to solve the problem of artificial intelligence itself. Because if we can’t make the player believe that these squads of survivors think and interact like real people, no advanced mockups can keep the player in the stream. ”

Travis Mackintosh, "Enemy AI in The Last of Us ", Game AI Pro , Volume 2 Chapter 34, 2015

It follows that not only hunters need to act smartly, harmoniously and ruthlessly. Infected persons should also create a feeling of a serious threat due to their chaotic and aggressive behavior.

And do not forget about Ellie - a teenage girl that Joel has to lead through the whole country so that she gets into a group of revolutionaries who call themselves Cicadas. Ellie is in many ways the avatar of the player in this story. Unlike Joel, who is too aware of the horrors of the outside world, Ellie has no idea what awaits her outside the walls of the Boston quarantine zone. She constantly asks questions about a former reality that she never knew, and reacts violently to the horrors that she and her companion have to endure. It was very important that the players develop a relationship with her in much the same way that Joel did.


AI Architecture


Let's start by explaining the basics of the artificial intelligence architecture of the various characters in the game — and why Naughty Dog built it that way.

AI in The Last of Us is based on the use of finite state machines (KA) - a long-established approach to the creation of artificial intelligence. Popularized him Half-Life back in 1998. Its essence is that the character can have several successive states: for example, he will attack the target or search for its location until a trigger event occurs that transfers it from one state to another.

ITKarma picture
A simple two-state spacecraft

The AI ​​in The Last of Us is built on the idea of ​​behaviors and skills. Skills are what a character can do. For example, a hunter may begin to find out what kind of rustling he hears or what kind of movement he sees, hide behind cover or bypass the player.In case of infected, this list will be different: for example, it will include chaotic wandering around the map and pursuing the enemy. In any of the options, smaller specific actions are used, such as moving around locations, interacting with objects in the world, or reacting to them. This is where the behavior comes into effect.

Behavior is a specific action that can be performed by any characters, but each of them will do it in their own way. A hunter or an infected nutcracker will attack the player hand-to-hand in different ways, using each of his own animations. The idea is that these behaviors are performed multiple times per game, but when they are performed by various characters, their dissimilarity becomes truly noticeable.

Each skill, which is a state inside a finite state machine, and itself, in turn, is a finite state machine consisting of behaviors. Such a hierarchical spacecraft is a well-established method for controlling the behavior of AI. But the most important thing here is that skills and behaviors in themselves are also modular.

ITKarma picture

A more extensive and independent AI system allows designers to perform many iterations without overloading programmers with feature requests or the need to individually configure certain parts of the code. This made it possible to concentrate much more time and effort on testing each type of character, ensure its compliance with the originally conceived design, improve functions, quickly prototype new ideas or abandon those that did not work without special problems.
“The best way to achieve your goals is to make our characters intelligent before making them smart. Characters create the illusion of intelligence when placed in a well-designed environment; They respond to the player, play convincing animations and sounds, and generally behave quite interesting. All this can easily come to naught if they thoughtlessly crash into the walls or make any other mistakes characteristic of poor AI. Removing these issues is not only an extremely rewarding experience, but it also makes it clear how different characters look who just don't do stupid things. ”

“Typically, characters do not need complex decision logic to look convincing, believable, and create the illusion of intelligence. All they need is to adequately respond to the world around them and interact with it. ”

Mark Bott, “Infected AI in The Last of Us," Game AI Pro , Volume 2, Chapter 33, 2015

But even having a good set of tools already available does not mean that there will be no need for further experiments. In order to achieve their goal, Naughty Dog radically changed and revised many of the elements of a friendly and enemy AI. Some enemy archetypes and even Ellie’s behavior system took their final form only in the last five months before the release of the game.

Now that we know how the basic architecture of gaming AI works, let’s take a look at the behavior of each character individually.

ITKarma picture


Hunters


First, consider the human enemies called hunters in the game. They are spelled out so that each of them in itself poses a real threat. Without delay and remorse, they will kill you, they will fight for their lives in the event of a retaliatory attack, and in no case will they become just cannon fodder. The purpose of the hunters is to act in a coherent, systematic way to track down and destroy the player, while taking care of their own safety, as well as unambiguously show their behavior, allowing the player to react accordingly.

First of all, let's talk about how hunters and other human AIs can detect a player.

They have both visual and sound sensors for detecting external stimuli at a level that can be described as standard. As we will see later, the sensitivity of these sensors changes quite sharply in the case of each of the four “infected” archetypes.

First of all, it's worth talking about vision. NPCs use different field of view to detect a player in space.

Initially, in The Last of Us they were the same as in another series of games Naughty Dog - Uncharted . But they coped poorly with their function: the player was noticed too quickly both at close and long distances. They did not correspond to the pace of the game, and therefore were modified and had no longer conical shape. Now the field of view of the NPC began to resemble the contour of a keyhole, thereby providing wider peripheral vision and a narrower view at a distance.

ITKarma picture
NPC Field of View at Uncharted

ITKarma picture
The NPC's Field of View in The Last of Us

In addition to this, the player cannot be detected instantly: he needs to remain in full view of the enemy for at least a couple of seconds to be noticed. This happens faster in battle mode, when the enemy is on the alert and has an increased concentration on finding the enemy. In addition, any NPC that the player is in the field of vision performs an additional test and launches reykast - a beam from the camera - from its point to the position of Joel in order to understand whether something is blocking its visibility. Initially, every joint in the Joel model was tested in this way, but this option was not very working. As a result, we stopped at a test of two conditions: whether the rakecast falls into his chest or the upper part of his head. This turned out to be quite simple, but at the same time effective.

In addition to this, hunters can still hear noises of different volume levels, but we will talk about this in more detail when it comes to infected people, for whom it is more important to hear the player than to see.

ITKarma picture

Hunters have many skills. As we can see, most of them are built around the battle: close, distant, with a direct attack or approach from the flank. Most of the sequences of hostilities in The Last of Us begin with the fact that a player who was in invisible mode is detected. Therefore, now we will focus on two skills, the most critical in stealth mode: investigation and search.

Investigation - a model of behavior used by a hunter to check suspicious noises and movements, whether it is a specially thrown brick or bottle, or light seen in the distance from the lamp. The search mode, in turn, is used by the hunter when he already knows for sure that the player is somewhere nearby, and then the NPC begins his systematic search. Both of these modes are based on the following key elements:

  • Combat coordination system , defining the role and appropriate behavior for each character;
  • Navigation map , showing the fastest way to move in space in the immediate vicinity of the character;
  • Exposure map , showing what the NPC can see from the current position;
  • And finally, the shelter points system , which defines not only good shelters for battle, but also the starting points of certain animations and behaviors.

Let's look at how these systems put the search and investigation modes into operation.

When the Hunter needs to start the investigation mode, a request is sent to the battle coordinator for the role of investigator. The system limits the number of characters in this role, so it will not happen that all five opponents who hear it will go to check the brick throw. While one character is testing an external stimulus, others may simply stand or act normally. Then the NPC, in investigative mode, turns to the shelter system to check the so-called open post - a place near the point of interest that meets certain criteria.In this case, this is a good place to run investigation animations.

The difference between the investigation and search modes is that in the second case, the NPCs already know that the player is somewhere nearby, they just do not know where. A coordination system is used here, allowing the NPCs to move around the map and explore it, while their trajectory must be systematic. If the enemies just roam the terrain, this will not be a challenge for the player and will look simply unrealistic.

Consequently, in this mode, NPCs rely on a navigation and exposure map. Together, they represent a grid that allows the AI ​​to calculate paths in space.

The navigation map allows you to quickly and inexpensively calculate whether there is a path to the desired location in the immediate vicinity of the NPC, and the exposure map shows what it will see. Using this data, the system creates a search map that shows areas of the exposure map that are not visible from this point, but they can be seen from another within walking distance from it. So the NPC calculates which areas to check from those that it does not see at the moment. At this stage, the coordinating system sends an NPC to search for the player in the designated places, whether it is territory around the corner or behind cover. Consequently, if a player stays where he was, the hunters will track him down.

ITKarma picture
Part of the territory is not visible, but it can be checked

As soon as a player is discovered, hunters change their behavior to one of the possible combat ones. If they want to attack the player from the flank, engage in a shootout or move to a tactically more advantageous position, they need to clearly understand where the player is, what areas provide the best cover and where the player is aiming at the moment. And the systems listed above help the characters in this.

First of all, enemies may need shelter. How do they know where to hide? In this case, the shelter point system is again used, but with different criteria. We no longer need open posts, now we need protection for the unit. The game calculates the 20 closest points for shelter on the map within the radius of the NPC, and then launches 4 rakast for each fragment of the shelter to assess whether the player can kill the enemy in a shootout from this position. If the system decides that the place is safe, it is judged by the degree of ease of achievement and whether the AI ​​needs to move in front of the player. Shelters are ranked by these criteria, after which the character selects the post with the most points. It should be borne in mind that the most preferred position at the moment can lose its relevance after 5 seconds, if only the player moves to another point, and then subsequent calculations of other best places can affect the pace of the battle.

ITKarma picture
Choosing the best cover for your position

Now that a suitable shelter has been chosen, how is it better for hunters to coordinate their attack?

First things first, at this moment, the game creates a link to the player’s location. A data packet is generated with its coordinates and the corresponding time stamp. It is useful to know it in order to detect how much time has passed since the last time a player was seen. If Joela notices another NPC, a new data packet will be generated. Whenever this happens, the generated data is shared by other NPCs nearby. The hunters will advance to the player’s location: some will use cover to catch him by surprise, others will go ahead. The roles between the NPCs are allocated by the combat coordinator. Among them: flanker , advanced , accompanying shooter , waiting gunner .

Each character will be judged by its relevance to a particular role. In the case of a flanker, the game calculates the so-called combat vector of the player - the direction in which the player conducts the attack.Using this vector and navigation tools, the system will assign flankers if it detects a path that does not intersect with this combat vector and allows you to sneak up on the player unnoticed.

Usually this system works well, but it depends a lot on the environment configuration. If the combat zone is sufficiently dense and closed, the player is forced to constantly fight off enemies, which makes the battle feel more intense and dynamic. And in a completely different way, it will be perceived in larger combat spaces and areas with greater verticality, where it is easier for the player to lose sight of enemies and force them to move around the level, changing their location many times. This is especially noticeable in the example of the battle in the courtyard in Pittsburgh, where Ellie shoots Hunters from a height with a rifle.

ITKarma picture

Infected


When we figured out how the AI ​​works with hunters, we switch to infected ones.

There are several types of infections whose skills and even sensory systems can vary greatly. Runners are fast and evil creatures, often attacking in groups. Stalkers move quickly and often ambush a player in dark places. The Nutcrackers are completely blind and rely on hearing only to track the player. And, finally, the tolka are also blind and at the same time quite slow monsters, but at the same time having powerful armor, which is not easy to penetrate at all.

In addition to the appearance and more fierce melee attacks, the infected AIs differ from hunters in that they rely more on hearing.

As mentioned earlier, the tolka and nutcrackers are blind, therefore they can only respond to sound stimuli. Runners and stalkers retain their vision, but it is much worse than people, so they need more time to notice the player. In order to compensate for this, the audio sensors of the infected were made six times more sensitive than those of hunters, which means that the player needs to be as secretive as possible and keep a distance so as not to attract attention.

Let's look at how the sound in the game works.

The ringing of broken glass from a bottle or even the player’s steps generate logical events in the game world. Such an event is broadcast in a radius specified by designers. In the case of infected, this radius is multiplied by a custom value for each NPC archetype. A striking example of this is the player’s steps, since infected people are much more sensitive to the sounds of movement, and the faster you move, the greater the radius of the sound event. An NPC that crosses the range of the propagated sound performs a quick rake test on the local environment to determine if walls or any other surfaces could block the sound. This would mean that in fact the noise was not loud enough to be heard.

ITKarma picture
Sound propagation radius

These logical sound events are generated for the vast majority of in-game events, especially for movement and combat, or for the operation of items such as generators or vehicles. However, there are still such “invisible” events that generate sounds, but the player does not hear them. For example, they include the sound of Joel's breath. We don’t hear him, but he helps the NPC find the player if he is hiding somewhere nearby.

To avoid this, you can throw bricks and bottles that distract the infected. Or a Molotov cocktail, which not only lures the enemy into a sound, but also easily kills him. Or even smoke bombs. As the name implies, they create a cloud that prevents the hunters and the player from viewing something with them. In theory, they should be useless against nutcrackers and fireflies, since they respond solely to sound. However, as practice has shown, if you throw a smoke bomb, it not only dazzles the characters caught in the cloud, but also makes them deaf.

ITKarma picture

Now take a look at the list of infected skills. It differs depending on the archetype of the character, but in the same way as in the case of hunters, it has a priority order. This makes sense - after all, let's say, the bogeyman is more focused on ranged attacks, while stalkers are the only type of infected that can hide from the player and thereby catch him by surprise. At the same time, they all have a lot in common: they sleep until no one bothers them, or wander around the location, or they can search the player - and, of course, attack against him, which is their highest priority.

By default, the infected state is just wandering around . This is the lowest priority behavior. Next, the designer can decide for each NPC whether he will patrol the location, walk from one given point to another, or simply move randomly. In the latter case, the history of visited polygons is saved in the navigation grid to minimize the chance of a return to these positions. It is important to note that if you distract the infected person from patrolling, he will not return to him and will wander along a random trajectory. This makes the NPC more unpredictable, and also prevents the unrealistic behavior of the blind nutcracker, who would hardly have gone astray again along the same trajectory as two minutes ago.

ITKarma picture

Given that the confrontation with the infected is largely based on secrecy, how will the nutcracker and runner look for a player if they hear something suspicious?

They definitely will not do this in the same way as hunters. They are less methodical in their approach and not so thorough, and therefore after a while they simply return to their wandering behavior. The search skill of infected people is focused on visiting the place where the sound was heard from or where the player was seen. It launches the unique behavior of the infected, known as " combing the territory ". This is a special search mode in which the infected one quickly and unpredictably turns to observe the environment. This behavior, like any other in the game, is associated with an accessible set of animations for each character, but uses these animations to determine how he will look around him.

While scouring the territory, the infected one generates a grid on top of the navigation map that shows which parts of the local environment he has not examined yet. This process is similar to hunter search mode. Then the infected one goes through the “search” animations, such as turning the head or the whole body. For each animation, he calculates how much “invisible” space he will “see” if he starts this animation at a given time, and selects the one that provides the best coverage. This process will be repeated for some time, after which the character will sometimes return to him in the wandering or idle mode. This behavior is alarming, it prevents the predictability of those infected, and gives suspense to the situation.

The infected give a completely different combat experience than the hunters, but, like the latter, they also previously experienced many playtests during development.

The ability of stalkers to ambush a player - the only infected behavior using shelters - appeared only in the last months of development. Sleeping skill reduces the sensitivity of infected sensors, but is used to create sentries around collision points. Infected people have no way to communicate with each other, but you may have noticed that sometimes they follow each other in search or attack mode. Thanks for this, it is worth saying the following skill: if one infected person moves to a certain place, the other may decide to follow him. You can think of it as a kind of “train”, where one is just ahead in the know where everyone is heading.

In addition to this, there are some behavioral changes to balance complexity. For example, when an infected person chases a player, he may sometimes stop and begin to look around.This not only allows the infected person to change the direction of movement, but also gives the player a slight respite. You can also see here that the nutcrackers are much less aggressive at lower difficulty levels.

image

Ally


Now that we’ve explored the adversary’s artificial intelligence philosophy, there’s yet another unreached topic: AI ally and, in particular, Ellie.

One of the first game demos in January 2013 showed how players left the Boston quarantine zone. Tess and Ellie, led by Joel, made their way through a skyscraper crowded with runners and nutcrackers. In this demo, the companion characters had to stay away from the place of cleaning up the infected ones, but at that time their AI was still raw and did not correspond to the plan of Naughty Dog.

So, let's talk about AI priorities in the case of Ellie:

  • Make sure she never lags behind Joel, and find points in space that allow her to adhere;
  • Give her a chance to prove useful, be it an indication of the proximity of an enemy or an attack on him;
  • Make Ellie an interesting character with special animations and audio dialogs;
  • And finally - to ensure the authenticity of her experience, preventing cheating on her part, but within reasonable limits.

The most important thing was to correctly register where Ellie should be. If she stands too close, it will interfere with the freedom of movement of the player. If too far away, this will interfere with the need to protect it and the development of relationships between characters. Thus, outside the fight, Ellie usually keeps up with or behind Joel, while in stealth mode, she tries to stay with him in the same shelter.

So that Ellie can follow Joel, the game creates an area around the player that Tess, Bill, Henry and Sam also try to adhere to — although they usually stay farther from Joel than Ally. As soon as this area is built, the game sends rakcasts parallel to the navigation grid in order to find suitable positions for companions. As in the case of the shelter point system, each position is evaluated by such parameters as the distance to enemies and allies, the angle relative to the player’s position, does the geometry block the look at Joel or forward movement. Solving this problem correctly is incredibly difficult - and yet, even if the system is imperfect, it is much more likely that it manages to place the character correctly than it does not.

ITKarma picture
Determining acceptable positions for Ellie based on Joel’s position when they hide behind cover

When a player hides behind cover, this is a completely different problem.

There is a system in the game that generates packages with the most preferred sheltering actions for Ellie. These packages are usually used by the player to interact with environmental objects such as the stairs to climb. In this case, they are created in the immediate vicinity of the player by launching 80 rakastas from his position and are designed to tell Ellie which nearby places are good points for her. The closest shelter points detected take precedence over the distance to Joel, to the nearest threats, and depending on whether these points are in front or behind the player.

The system worked well until it became clear that in this case, Ellie would always be next to Joel. Then a modification was added, which allowed to create action packages at the point of shelter where the player stands. In combination with the new animation, this allows Joel to protect Ellie's body from threats while he is in hiding, and thereby helps strengthen the relationship between the characters.

ITKarma picture
Shelter Follow Mode

ITKarma picture
Shelter Defense Mode

As you progress through the game, characters are increasingly finding themselves in situations where they are both participating in battle. At the same time, Ellie is gradually gaining more freedom of action and a wider variety of weapons in order to protect both herself and Joel. One of her first abilities is the ability to throw bricks and bottles at enemies. In fact, this ability is a bit of cheating, because at the time of the action, Ellie connects to the enemy's perceptual systems to check if he is going to detect Joel. If the answer is yes, she rolls. Please note that for this she does not need to take a bottle or brick.

When Ellie acquires real weapons, she uses it only when the player is the first to attack the enemy or is in danger. Once you kill a couple of opponents and hide again behind cover, Ellie will also stop attacking and follow you. In rare cases, she can also share a first-aid kit or ammunition with Joel if she is nearby. This is due to the features of the inventory system and will only work when the player himself does not have the necessary supplies.

Outside of battle and stealth, Ellie still needs to be an independent realistic character, which is achieved using contextual animation and dialogs. There are hundreds, if not thousands, of lines of dialogue that Ellie can launch throughout the game, be it her reaction to objects in the world, to Joel’s murder of people or those infected, her help in finding enemies, aversion to the dead, and much more. The reason that there are so many of them is because over time, the character's change, its growing self-confidence and acceptance of the situation are so shown. This is really a subtle part of the game, enriching the character of the girl even more.

And one more important priority remains.

AI Ellie cheats in favor of the player in very specific situations, but - as often happens in games - does this in order to minimize the player’s frustration and improve the overall gameplay experience. So, Ellie is “teleported” to Joel, if he is being held by an adversary to help him get rid of the threat. In combat, the accuracy of the girl’s shooting will vary depending on whether her opponent is in the player’s field of vision or outside of it. Behind the screen, Ellie does no harm to the enemy, but often turns to shoot someone whom Joel can see. This is partly done to support the player, but also to show that she is not just an NPC attached to the player, but is really involved in the conflict.

And besides, as many players have noticed, outside the battle, Ellie is invisible to hunters and infected. This was done in order to minimize the player’s failure to try to hide from the enemy due to the fact that he noticed Ellie.

Conclusion


Naughty Dog sought to create a game with an emotionally resonant story, built on a series of intense and fierce battles. In many ways, it really succeeds and represents the focus of the creative efforts and energy of the development team of one of the key AAA industry studios at the moment.

Source