Simulacrum: Building Believable Behaviors in Video Game AI
If you were to think of an example Artificial Intelligence, what would it sound like? How would it act? If you thought that it would sound robotic, cold, and inhuman I would not blame you. If you were to look at most depictions of AI in popular media, Data from Star Trek, any of The Terminators, Hal from 2001, etc. it would seem that there is always a way to tell the difference from a series of ones and zeroes from an actual human being. They sound different, think differently, behave differently. Or would they? For decades now programmers, computer scientists, artists, and designers have been working on games. Many of these games pit the player against computerized enemies. These representations of both fantastical and actual foes started simple and unbelievable. But with time and advancements in technology and AI research, these virtual simulacrums have advanced to the point of seeming almost as real as you or me, just on a computer screen. How did this happen, how did we get here? Advancements in natural language processing, pathfinding, and many other fields. What I’ll be focusing on though, is behavior. Namely, the historical advancements of NPC behavior in the landmark games that introduced them. Starting from the Nimatron, the first computerized game, to the first F.E.A.R. game I cover will the games that advanced NPC behavior in games, cover the aspirations that required new advancements, the advancements themselves, and how they changed the gaming landscape.
Early History: The Nimatron
It was in 1940 that the first computer game, by the name of the Nimatron, would challenge people to a game of Nim. The goal of the Nimatron was to portray new, military-developed, technology in a nicer light since World War II was still happening and computers and other military technologies were still seen as imposing and dangerous war machines. Using an array of lights to simulate the matchsticks, as television sets were not common at the time, it does not fit the typical definition of a video game but a computer game, but it is the grandfather of the modern video game. Using electromechanical relays, the Nimatron would execute an algorithm that would allow it to win the game, if played against someone not familiar with the algorithms used to win Nim. This is the first example of a computer opponent making decisions against a human player; so it will be our starting point. Unfortunately, there will not be another advancement for another 30 years.
AI Enters Video Games as Simple Patterns
It was during 1971 that Nolan Bushnell and Ted Dabney release Computer Space, the first commercial video game and the first arcade game. Based off of the first video game Spacewar!, a 2D two-player space themed shooting game, Bushnell and Dabney wanted to provide a commercial version of Spacewar! but couldn’t afford the equipment necessary to do so. Instead, they decided to make a cheaper version. This led to the inclusion of the first computer enemy in video games; two tiny spaceships that would travel around and shoot in the general direction of the player’s ship. Although the enemy ship relied on hard-coded movement patterns and timing, the ability to locate the general direction of the player and fire in the player’s direction shows a small bit of intelligent behavior. So not only did Computer Space introduce the general public to video games it also showed the public that computers could be actors in games. After Computer Space NPCs would show a similar level of enemy intelligence until 1980.
Pac-Man: Ghosts with Attitudes
Released in 1980, Namco’s Pac-man included one of the most complex AIs in the industry at the time. Wanting to create a video game that everyone could enjoy the designers of Pac-man had to make certain changes to the enemy design formula. They included four ghost enemies of different colors, as well give them different navigation behaviors to vary up their method of attack (since four ghosts just trailing Pac-man would be boring to play and look at). Furthermore, the game used changing universal states for the ghosts to further vary their behaviors. The states of Scatter, Attack, and Flee would change about every seven seconds unless a super pellet was eaten, and would eventually default to Attack as time went on. Pac-man was the first use of the finite state machine model being used in video games. Thanks to the introductions of basic NPC behaviors, and changing finite states Pac-man was a major success and is still beloved ‘till this day.
The GPU: The True Hero
Unfortunately, it wasn’t until the late 90s that AI dealing with NPC Behavior would be revisited. This was mostly due to technological limitations since until 1996 graphics were handled by the CPU, leaving very little processing power for NPC behavioral AI, or most AI in general. With the advent of 3D GPUs, the strenuous load of rendering 3D graphics that was crushing many a CPU was greatly lessened, leaving more processing power for calculating more complex game mechanics and, more importantly for us, more complex AIs.
Get Sean Carpenter’s stories in your inbox
Join Medium for free to get updates from this writer.
Making Sense and Acting Together
Once CPUs had finally had the albatross of 3D graphics removed from their neck the world begins to see new AI behaviors because in 1998 Valve released Half-Life blowing everyone’s mind with their revolutionary NPC behavior. When starting Half-Life Valve wanted to make a game with a story where the player is in control of the protagonist for its entirety. This meant getting rid of cutscenes and replacing them with actual interactions with NPCs. this was something that was never done before and requiring a new approach to both game writing and NPC behavior programming. Valve used player-triggered, scripted AI scenes while players were still controlling Freeman created a greater sense of immersion. To better accommodate the scripted cutscenes and produce greater immersion, Valve added sensing technology to NPC behavior to allow NPCs seem more real. This was the first time that NPCs reacted to the player because they could “see” him, not just because he existed. This sensing of the player made interactions more believable because you, the player, were in control of them. If the player was tired of an NPC going on and on, the player could just leave or press buttons and that would annoy the NPC. Enemy NPCs would react as well. The Vortigaunts would run away if they had low health. Half-Life also introduced squad tactics to NPC behavior. Once the player started encountering soldiers the player would find that the soldiers stupid. They were capable of flanking, covering, and rushing the player to always keep the player on the defensive. Which compared to the enemy NPCs of contemporary games, Half-Life’s soldiers are tactical geniuses. All of this while yelling threats and insults at Gordon Freeman. It also seems that Half-Life was the spark that started the fire of NPC behavioral design because, after Half-Life, advancements would happen back to back.
Stealing the Senses
Just a few months after the release of Half-Life, a game named Thief: The Dark Project pushes NPC senses even further. With the intention of making the first 3D stealth game Looking Glass Studios had to take the basic concepts introduced in Half-Life crank them to 11. For there to be strong stealth mechanics, the senses of NPCs needed to be as close as human as possible. As opposed to in Half-Life, where the NPCs either knew where the player was or they didn’t, the NPCs in Thief had a suspicion mechanic that worked off of environmental factors and was a spectrum scale. Furthermore, since the player was supposed to be sneaking around groups of guards, the guards needed a way of communicating with each other when one of them spotted something suspicious or saw the player. This meant improving the squad-based systems not for combat like in Half-Life but for information sharing. This means that not just individual NPCs had to act believable, but now entire groups of NPCs had to seem natural as well.
Behavior Evolved
It was in 2004 that modern AI practices began to be more standardized after the massive success of Halo 2. Bungie wanted to make the extremely diverse enemies of the Covenant feel like a real, thinking grouping of different species working together, rather than the same enemy in a different skin. With the practices of the time, that would be difficult to make the diverse grouping of creatures be believable Bungie had to make the AI design of Behavior trees, in junction with context, priorities, stimulus behaviors. The behavior tree is a type of tree, or a directed acyclic graph, in which based on the state of the world (NPC, Player Character, etc.) certain branches or paths of the tree are chosen by a certain NPC over others and at the end of a path a an action or group of actions that the NPC carries out. Context is the world state in which the certain NPC finds itself in (its health, its type, what the player is doing, etc.). These contexts either disable or enable certain branches in the behavior tree so the NPC can only choose the options that are actually available to it. If the player is not next to the NPC the NPC won’t even consider a melee attack. While context tells the NPC what it can do, priorities tell the NPC what it should do. Based on what is happening around an NPC, the NPC may have several branches open to it on the behavior tree, giving certain priorities, or weights, to specific branches, allows the NPCs to act quickly and in different ways to their dynamic environment. For instance, a Jackal would try to snipe the player if it sees the player out in the open. Finally, the stimulus behaviors are ways of shifting the priorities of NPCs so that they can better address certain changes in their environment. An example of which is when all of the grunts run from the player character when the player character kills their commander. All of these pieces come together to make a complex system when compared to the earlier NPC behavior systems dictated by Finite State Machines. It is through the complexities of these interwoven systems that the player can see the differences between the cowardly grunts, sneaky jackals, and brave elites. While this method of AI behavior programming is highly variable and common, Monolith created a more powerful, although less common AI behavioral archetype.
Planning for the Future
In just under a year, there is another revolution in NPC behavior, letting NPCs plan. Monolith wanted to create a squad shooter in which the squads can act dynamically, quickly, and uniquely in each encounter. In order to make the squad tactics believable, the AI in that controls the enemies has two sections: a Squad section, where the NPCs can share certain knowledge that each individual has and use it to create a plan of action for the group of NPCs, and an individual section, where the individuals gather knowledge and enact plans of their own when alone. This would allow the individual NPCs act and coordinate attacks as a single unit but also allow individuals to act effectively without others. Furthermore, the AI uses a planning model and a simple finite state machine to allow NPCs to accomplish their goals (ultimately, killing the player character). The NPCs actually think ahead of time what it is they want to accomplish, how to accomplish it, act out the plan, and create new plans as the situation changes. In contrast to the more common and complex behavior trees used in most modern games and in Halo 2, as mentioned above, the use of a planning system can work well with just several goals and actions. Finally, the lack of tons of coded sequences allowed gameplay experience to be virtually unrepeatable.
As we look back at the history of advancements in NPC behavior in video games we can see how far we have come: from the humble algorithms of Nimatron, the simple patterns of Computer Space, the finite state machines of Pac-man, the senses and tactics in Half-Life and Theif: The Dark Project, to the behavior trees in Halo 2, and the planning in F.E.A.R. While F.E.A.R. was the last major advancement in NPC behavioral technology to date, there are still some advancements that mostly rely on behavioral trees and layering levels of control AIs on top of them. So, when I look back at how quickly behavioral AI has evolved and know that other AI aspects like learning, vision, and natural language processing are advancing just as quickly, I can’t believe that people still think that an AI would act any differently than a human.
This article was published as a requirement for the History of Digital Games course at UC Santa Cruz with A.M. Darke. Please be kind.
