Game AI

Two different meanings of "AI" in games

The term "artificial intelligence" shows up in games in two different senses, and it's worth separating them. According to Wikipedia's article "Artificial intelligence in video games," "academic AI—aimed at developing autonomous reasoning or learning—is distinct from game AI," whose aim is "engaging, believable, and efficient behavior for players," and which, according to the same article, often consists of "a half-dozen rules of thumb, or heuristics, that are just enough to give a good gameplay experience." That is the game AI most entries in this category are about: the Pac-Man ghosts, the characters in Left 4 Dead, the opponent in a racing game. The second sense is what this site calls "a computer that plays against a person or learns to play" — for example Deep Blue, which beat the world chess champion, and AlphaGo, which learned to play Go. These are systems built to win at a game, and they sometimes involve real machine learning. Both senses share the words "artificial intelligence," but not the method and not the goal.

The finite-state machine: the basic building block

One of the simplest and most common techniques for game AI is the finite-state machine (FSM). According to Wikipedia, an FSM "models an NPC as one state at a time, such as attacking or patrolling." A guard in a stealth game, for example, can be in a "patrol" state, switch to an "investigate" state when it hears a noise, and to an "attack" state once it sees the player. Every transition between states is decided in advance by the programmer: if X happens, switch to state Y. The method is easy to build and understand, but according to the same source, "these FSMs are simple to build but become difficult to extend as the number of behaviors grow": every new behavior a programmer adds adds more transitions that have to be defined between the existing states.

Behavior trees: when an FSM isn't enough

To deal with that limitation, behavior trees were developed, which also belong to robotics and are explained in their own separate entry on this site. The key difference from an FSM: the building block of a behavior tree is a task, not a state, and tasks are arranged in a hierarchical tree that decides, at every moment, what to try first. According to Wikipedia, behavior trees "have been extensively used in high-profile video games such as Halo, Bioshock, and Spore," and the article cites a 2005 conference talk on the AI of Halo 2, Bungie's 2004 game. Instead of writing out every possible transition between "patrol" and "attack" in advance, the programmer defines a list of tasks ranked by priority, and the tree checks them again and again in order of importance, running the first one it can currently perform — which makes it easier to add new behavior without rewriting everything that came before it.

Finding a way across the map: navigation and pathfinding

Another problem every moving game character has to solve is navigation: how to get from point A to point B without getting stuck on a wall. One of the most common algorithms for this, A* ("A-star"), was first published in 1968 by Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International), as part of the Shakey project — an attempt to build a mobile robot that could plan its own actions. According to Wikipedia, "A* is often used for the common pathfinding problem in applications such as video games." Many commercial games divide the map into a grid of tiles, and A* efficiently computes the shortest path between them without checking every possible route — so a character can "know" how to walk around a table without a programmer having hand-coded that specific detour in advance.

The four personalities of the Pac-Man ghosts

Pac-Man, released by the Japanese company Namco in 1980, is an early and especially well-known example of game AI. According to Wikipedia, each of the four ghosts has its own "unique artificial intelligence (A.I.), or 'personality.'" According to a detailed analysis of the game's code (The Pac-Man Dossier, by Jamey Pittman), each ghost follows a fixed targeting rule: red Blinky aims straight for Pac-Man's current tile. Pink Pinky targets a point four tiles ahead of Pac-Man in his direction of travel, effectively ambushing him. Cyan Inky calculates a point two tiles ahead of Pac-Man, then doubles the length of the line from Blinky to that point — a rule that makes it hard to predict. And orange Clyde behaves like Blinky when more than eight tiles away from Pac-Man, but heads for his own corner once he gets closer than that. The ghosts also alternate, on a fixed schedule, between a "chase" mode, in which each one follows its own targeting rule, and a "scatter" mode, in which each retreats to its own corner of the maze. There is no learning here: four fixed arithmetic rules are what make the ghosts look like they each have a character.

AI that runs the whole game: Left 4 Dead's Director

Not all game AI controls a single character. Left 4 Dead (2008), developed by Turtle Rock Studios (by then renamed Valve South) and published by Valve, introduced a system called the "Director" that manages the entire game: according to Wikipedia, it is "a dynamic system for game dramatics, pacing and difficulty," with no fixed spawn points — instead, it decides in real time how many enemies and items to place, and where, based on each player's situation, location and skill, in order to keep tension high and make every playthrough feel different. It also uses visual effects, dynamic music and character dialogue as emotional cues. Valve's Gabe Newell, writing in Edge magazine, described it this way: "This is what makes procedural narrative more of a story-telling device than, say, a simple difficulty mechanism." This is a different level of game AI: not a character deciding for itself, but a conductor shaping the experience of the entire game.