In the broadest sense, most games incorporate some form of artificial intelligence (AI). For instance, developers have used AI for years to give seemingly intelligent life to countless game characters, from the ghosts in the classic arcade game Pac Man to the bots in the first-person shooter Unreal, and many others in between. The huge variety of game genres and game characters necessitates a rather broad interpretation as to what is considered game AI. Indeed, this is true of AI in more traditional scientific applications as well.
Some developers consider tasks such as pathfinding as part of game AI. Steven Woodcock reported in his "2003 Game Developer's Conference AI Roundtable Moderator's Report' that some developers even consider collision detection to be part of game AI.Clearly, some wide-ranging interpretations of game AI exist.
We're going to stick with a broad interpretation of game AI, which includes everything from simple chasing and evading, to pattern movement, to neural networks and genetic algorithms. Game AI probably best fits within the scope of weak AI (see the sidebar "Defining AI"). However, in a sense you can think of game AI in even broader terms.
In games, we aren't always interested in giving nonplayer characters human-level intellect. Perhaps we are
writing code to control nonhuman creatures such as dragons, robots, or even rodents. Further, who says we always have to make nonplayer characters smart? Making some nonplayer characters dumb adds to the variety and richness of game content. Although it is true that game AI is often called upon to solve fairly complex problems, we can employ AI in attempts to give nonplayer characters the appearance of having different personalities, or of portraying emotions or various dispositionsfor example, scared, agitated, and so on.

Defining AI
The question "what is artificial intelligence?" is not easy to answer. If you look up artificial intelligence in a dictionary, you'll probably find a definition that reads something like this: "The ability of a computer or other machine to perform those activities that are normally thought to require intelligence." This definition comes from The American Heritage Dictionary of the English Language, Fourth Edition (Houghton Mifflin Company). Still other sources define artificial intelligence as the process or science of creating intelligent machines.
From another perspective it's appropriate to think of AI as the intelligent behavior exhibited by the machine that has been created, or perhaps the artificial brains behind that intelligent behavior. But even this interpretation is not complete. To some folks, the study of AI is not necessarily for the purpose of creating intelligent machines, but for the purpose of gaining better insight into the nature of human intelligence. Still others study AI methods to create machines that exhibit some limited form of intelligence.
This begs the question: "what is intelligence?" To some, the litmus test for AI is how close it is to human intelligence. Others argue that additional requirements must be met for a machine to be considered intelligent. Some people say intelligence requires a conscience and that emotions are integrally tied to intelligence, while others say the ability to solve a problem requiring intelligence if it were to be solved by a human is not enough; AI must also learn and adapt to be considered intelligent.
AI that satisfies all these requirements is considered strong AI. Unlike strong AI, weak AI involves a broader range of purposes and technologies to give machines specialized intelligent qualities.

Game AI falls into the category of weak AI.
The bottom line is that the definition of game AI is rather broad and flexible. Anything that gives the illusion of intelligence to an appropriate level, thus making the game more immersive, challenging, and, most importantly,
fun, can be considered game AI. Just like the use of real physics in games, good AI adds to the immersiveness of the game, drawing players in and suspending their reality for a time.

Deterministic Versus Nondeterministic AI
Game AI techniques generally come in two flavors: deterministic and nondeterministic.

Deterministic
Deterministic behavior or performance is specified and predictable. There's no uncertainty. An example of deterministic behavior is a simple chasing algorithm. You can explicitly code a nonplayer character to
move toward some target point by advancing along the x and y coordinate axes until the character's x and y coordinates coincide with the target location.

Nondeterministic
Nondeterministic behavior is the opposite of deterministic behavior. Behavior has a degree of uncertainty and is somewhat unpredictable (the degree of uncertainty depends on the AI method employed and how well that method is understood). An example of nondeterministic behavior is a nonplayer character learning to adapt to the fighting tactics of a player. Such learning could use a neural network, a Bayesian technique, or a genetic algorithm.
Deterministic AI techniques are the bread and butter of game AI. These techniques are predictable, fast, and easy to implement, understand, test, and debug. Although they have a lot going for them, deterministic methods place the burden of anticipating all scenarios and coding all behavior explicitly on the developers' shoulders.

Further, deterministic methods do not facilitate learning or evolving. And after a little gameplay, deterministic behaviors tend to become predictable. This limits a game's play-life, so to speak.
Nondeterministic methods facilitate learning and unpredictable gameplay. Further, developers don't have to explicitly code all behaviors in anticipation of all possible scenarios. Nondeterministic methods also can learn
and extrapolate on their own, and they can promote so-called emergent behavior, or behavior that emerges without explicit instructions.

Developers traditionally have been a bit wary of AI that is nondeterministic, although this is changing.
Unpredictability is difficult to test and debughow can you test all possible variations of player action to make sure the game doesn't do something silly in some cases? Game developers face an ever-shortening development cycle that makes developing and testing new technology to production-ready standards extremely difficult. Such short development periods make it difficult for developers to understand cutting-edge AI technologies fully and to see their implications in a mass-market commercial game.

At least until recently, another factor that has limited game AI development is the fact that developers have been focusing most of their attention on graphics quality. As it turns out, such focus on developing better and faster
graphics techniques, including hardware acceleration, might now afford more resources to be allocated toward developing better, more sophisticated AI. This fact, along with the pressure to produce the next hit game, is encouraging game developers to more thoroughly explore nondeterministic techniques.

Established Game AI
Perhaps the most widely used AI technique in games is cheating. For example, in a war simulation game the computer team can have access to all information on its human opponentslocation of their base; the types,
number, and location of units, etc.without having to send out scouts to gather such intelligence the way a human player must. Cheating in this manner is common and helps give the computer an edge against intelligent human players. However, cheating can be bad. If it is obvious to the player that the computer is cheating, the player likely will assume his efforts are futile and lose interest in the game. Also, unbalanced cheating can give
computer opponents too much power, making it impossible for the player to beat the computer. Here again, the player is likely to lose interest if he sees his efforts are futile. Cheating must be balanced to create just enough of a challenge for the player to keep the game interesting and fun.
Of course, cheating isn't the only well-established AI technique. Finite state machines are a ubiquitous game AI technique.

Developers commonly use fuzzy logic in fuzzy state machines to make the resulting actions somewhat less predictable and to reduce the burden of having to enumerate huge numbers of if-then rules. Rather than have a
rule that states if distance = 10 and health = 100 then attack, as you might in a finite state machine, fuzzy logic enables you to craft rules using less precise conditions, such as if close and healthy then attack aggressively.
Effective and efficient pathfinding is a fundamental task that nonplayer characters must accomplish in all sorts of games. Nonplayer character units in a war simulation must be able to navigate over terrain and avoid barriers to reach the enemy. Creatures in a first-person shooter must be able to navigate through dungeons or buildings to reach or escape from the player. The scenarios are endless, and it's no wonder that AI developers give path finding tremendous attention .
These are only a few of the established game AI techniques; others include scripting, rules-based systems, and some artificial life (A-life) techniques, to name a few. A-life techniques are common in robotic applications, and developers have adapted and used them with great success in video games. Basically, an A-life system is a synthetic system that exhibits natural behaviors. These behaviors are emergent and develop as a result of the combined effect of lower-level algorithms.

Chasing and Evading:

The chasing/evading problem consists of two parts. The first part involves the decision to initiate a chase or to evade. The second part involves effecting the chase or evasionthat is, getting your predator to the prey, or
having the prey get as far from the predator as possible without getting caught. In a sense, one could argue that the chasing/evading problem contains a third element: obstacle avoidance. Having to avoid obstacles while chasing or evading definitely complicates matters, making the algorithms more difficult to program.
The simplest, easiest-to-program, and most common method you can use to make a predator chase its prey involves updating the predator's coordinates through each game loop such that the difference between the
predator's coordinates and the prey's coordinates gets increasingly small. This algorithm pays no attention to the predator and prey's respective headings (the direction in which they're traveling) or their speeds.
For example, in games that incorporate real-time physics engines you can employ methods that consider the positions and velocities of both the predator and its prey so that the predator can try to intercept its prey instead of relentlessly chasing it. In this case the relative position and velocity information can be used as input to an algorithm that will determine appropriate force actuation steering forces, for exampleto guide the predator to the target. Yet another method involves using potential functions to influence the behavior of the predator in a manner that makes it chase its prey, or more specifically, makes the prey attract the predator. Similarly, you can use such potential functions to cause the prey to run from or repel a predator.

Basic chase algorithm

if (predatorX > preyX)
predatorX--;
else if (predatorX < preyX)
predatorX++;
if (predatorY > preyY)
predatorY--;
else if (predatorY < preyY)
predatorY++;

In this example, the prey is located at coordinates preyX and preyY, while the predator is located at coordinates predatorX and predatorY. During each cycle through the game loop the predator's coordinates are checked against the prey's. If the predator's x-coordinate is greater than the prey's x-coordinate, the predator's x coordinate is decremented, moving it closer to the prey's x-position. Conversely, if the predator's x-coordinate is less than the prey's, the predator's x-coordinate is incremented. Similar logic applies to the predator's y coordinate based on the prey's y-coordinate. The end result is that the predator will move closer and closer to the prey each cycle through the game loop.

Basic evade algorithm


if (preyX > predatorX)
preyX++;
else if (preyX < predatorX)
preyX--?>;
if (preyY > predatorY)
preyY++;
else if (preyY < predatorY)
preyY--;

In tile-based games the game domain is divided into discrete tilessquares, hexagons, etc.and the player's position is fixed to a discrete tile. Movement goes tile by tile, and the number of directions in which the player
can make headway is limited. In a continuous environment, position is represented by floating-point coordinates, which can represent any location in the game domain. The player also is free to head in any direction.

You can apply the approach illustrated in these two examples whether your game incorporates tile-based or continuous movement. In tile-based games, the xs and ys can represent columns and rows in a grid that encompasses the game domain. In this case, the xs and ys would be integers. In a continuous environment, the xs and ysand zs if yours is a 3D gamewould be real numbers representing the coordinates in a Cartesian coordinate system encompassing the game domain.

There's no doubt that although it's simple, this method works. The predator will chase his prey with unrelenting determination.

Basic tile-based chase example

if (predatorCol > preyCol)
predatorCol--;
else if (predatorCol < preyCol)
predatorCol++;
if (predatorRow> preyRow)
predatorRow--;
else if (predatorRow
predatorRow++;


BuildPathToTarget function

void ai_Entity::BuildPathToTarget (void)
{
int nextCol=col;
int nextRow=row;
int deltaRow=endRow-row;
int deltaCol=endCol-col;
int stepCol, stepRow;
int currentStep, fraction;


Path initialization

for (currentStep=0;currentStep
{
pathRow[currentStep]=-1;
pathCol[currentStep]=-1;
}
currentStep=0;
pathRowTarget=endRow;
pathColTarget=endCol;

Path direction calculation
if (deltaRow < 0) stepRow=-1; else stepRow=1;
if (deltaCol < 0) stepCol=-1; else stepCol=1;
deltaRow=abs(deltaRow*2);
deltaCol=abs(deltaCol*2);
pathRow[currentStep]=nextRow;
pathCol[currentStep]=nextCol;
currentStep++;


Bresenham algorithm


if (deltaCol >deltaRow)
{
fraction = deltaRow *2-deltaCol;
while (nextCol != endCol)
{
if (fraction >=0)
{
nextRow =nextRow +stepRow;
fraction =fraction -deltaCol;
}
nextCol=nextCol+stepCol;
fraction=fraction +deltaRow;
pathRow[currentStep]=nextRow;
pathCol[currentStep]=nextCol;
currentStep++;
}
}
else
{
fraction =deltaCol *2-deltaRow;
while (nextRow !=endRow)
{
if (fraction >=0)
{
nextCol=nextCol+stepCol;
fraction=fraction -deltaRow;
}
nextRow =nextRow +stepRow;
fraction=fraction +deltaCol;
pathRow[currentStep]=nextRow;
pathCol[currentStep]=nextCol;
currentStep++;
}
}
}

The initial if conditional uses the values in deltaCol and deltaRow to determine which axis is the longest. The first block of code after the if statement will be executed if the column axis is the longest. The else part will be executed if the row axis is the longest.

Wait for the next topic on AI in Gaming