Cover | Table of Contents | Colophon

Table of Contents

Chapter 1: Introduction to Game AI

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

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 dispositions—for example, scared, agitated, and so on.

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

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Deterministic Versus Nondeterministic AI

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

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. The flocking and neural network algorithms we’ll consider in this book are good examples of emergent behavior.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Established Game AI

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

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 opponents—location 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. We cover them in detail in Chapter 9, but basically the idea is to enumerate a bunch of actions or states for computer-controlled characters and execute them or transition between them using if-then conditionals that check various conditions and criteria.

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. We cover fuzzy logic in Chapter 10.

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 pathfinding tremendous attention. We cover general pathfinding techniques in Chapter 6 and the venerable A

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

The Future of Game AI

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

The next big thing in game AI is learning. Rather than have all nonplayer character behavior be predestined by the time a game ships, the game should evolve, learn, and adapt the more it’s played. This results in a game that grows with the player and is harder for the player to predict, thus extending the play-life of the game. It is precisely this unpredictable nature of learning and evolving games that has traditionally made AI developers approach learning techniques with a healthy dose of trepidation.

The techniques for learning and reacting to character behavior fall under the nondeterministic AI we talked about earlier, and its difficulties apply here too. Specifically, such nondeterministic, learning AI techniques take longer to develop and test. Further, it’s more difficult to really understand what the AI is doing, which makes debugging more difficult. These factors have proven to be serious barriers for widespread use of learning AI techniques. All this is changing, though.

Several mainstream games, such as Creatures, Black & White, Battlecruiser 3000AD, Dirt Track Racing, Fields of Battle, and Heavy Gear, used nondeterministic AI methods. Their success sparked a renewed interest in learning AI methods such as decision trees, neural networks, genetic algorithms, and probabilistic methods.

These successful games use nondeterministic methods in conjunction with more traditional deterministic methods, and use them only where they are needed and only for problems for which they are best suited. A neural network is not a magic pill that will solve all AI problems in a game; however, you can use it with impressive results for very specific AI tasks within a hybrid AI system. This is the approach we advocate for using these nondeterministic methods. In this way, you can at least isolate the parts of your AI that are unpredictable and more difficult to develop, test, and debug, while ideally keeping the majority of your AI system in traditional form.

Throughout this book we cover both traditional game AI techniques as well as relatively new, up-and-coming AI techniques. We want to arm you with a thorough understanding of what has worked and continues to work for game AI. We also want you to learn several promising new techniques to give you a head start toward the future of game AI.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Chapter 2: Chasing and Evading

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

In this chapter we focus on the ubiquitous problem of chasing and evading. Whether you're developing a spaceship shooter, a strategy simulation, or a role-playing game, chances are you will be faced with trying to make your game's nonplayer characters either chase down or run from your player character. In an action or arcade game the situation might involve having enemy spaceships track and engage the player's ship. In an adventure role-playing game it might involve having a troll or some other lovely creature chase down your player's character. In first-person shooters and flight simulations you might have to make guided missiles track and strike the player or his aircraft. In any case, you need some logic that enables nonplayer character predators to chase, and their prey to run.

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 evasion—that 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. Although we don't cover obstacle avoidance in this chapter, we will come back to it in Chapters 5 and 6. In this chapter we focus on the second part of the problem: effecting the chase or evasion. We'll discuss the first part of the problem—decision making—in later chapters, when we explore such topics as state machines and neural networks, among others.

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. Although this method is relentlessly effective in that the predator constantly moves toward its prey unless it's impeded by an obstacle, it does have its limitations, as we'll discuss shortly.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Basic Chasing and Evading

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

As we said earlier, the simplest chase algorithm involves correcting the predator's coordinates based on the prey's coordinates so as to reduce the distance between their positions. This is a very common method for implementing basic chasing and evading. (In this method, evading is virtually the opposite of chasing, whereby instead of trying to decrease the distance between the predator and prey coordinates, you try to increase it.) In code, the method looks something like that shown in Example 2-1.

Example 2-1. 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.

Using this same methodology, we can implement evading by simply reversing the logic, as we illustrate in Example 2-2.

Example 2-2. 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 tiles—squares, 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

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Line-of-Sight Chasing

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

In this section we explain a few chasing and evading algorithms that use a line-of-sight approach. The gist of the line-of-sight approach is to have the predator take a straight-line path toward the prey; the predator always moves directly toward the prey's current position. If the prey is standing still, the predator will take a straight line path. However, if the prey is moving, the path will not necessarily be a straight line. The predator still will attempt to move directly toward the current position of the prey, but by the time he catches up with the moving prey, the path he would have taken might be curved, as illustrated in Figure 2-2.

Figure 2-2: Line-of-sight chasing

In Figure 2-2, the circles represent the predator and the diamonds represent the prey. The dashed lines and shapes indicate starting and intermediate positions. In the scenario on the left, the prey is sitting still; thus the predator makes a straight-line dash toward the prey. In the scenario on the right, the prey is moving along some arbitrary path over time. At each time step, or cycle through the game loop, the predator moves toward the current position of the prey. As the prey moves, the predator traces out a curved path from its starting point.

The results illustrated here look more natural than those resulting from the basic-chase algorithm. Over the remainder of this section, we'll show you two algorithms that implement line-of-sight chasing. One algorithm is specifically for tiled environments, while the other applies to continuous environments.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Line-of-Sight Chasing in Tiled Environments

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

As we stated earlier, the environment in a tile-based game is divided into discrete tiles. This places certain limitations on movement that don't necessarily apply in a continuous environment. In a continuous environment, positions usually are represented using floating-point variables. Those positions are then mapped to the nearest screen pixel. When changing positions in a continuous environment, you don't always have to limit movement to adjacent screen pixels. Screen pixels typically are small enough so that a small number of them can be skipped between each screen redraw without sacrificing motion fluidity.

In tile-based games, however, changing positions is more restrictive. By its very nature, tile-based movement can appear jaggy because each tile is not mapped to a screen pixel. To minimize the jaggy and sometimes jumpy appearance in tile-based games, it's important to move only to adjacent tiles when changing positions. For games that use square tiles, such as the example game, this offers only eight possible directions of movement. This limitation leads to an interesting problem when a predator, such as the troll in the example, is chasing its target. The troll is limited to only eight possible directions, but mathematically speaking, none of those directions can accurately represent the true direction of the target. This dilemma is illustrated in Figure 2-3.

Figure 2-3: Tile-based eight-way movement

As you can see in Figure 2-3, none of the eight possible directions leads directly to the target. What we need is a way to determine which of the eight adjacent tiles to move to so that the troll appears to be moving toward the player in a straight line.

As we showed you earlier, you can use the simple chasing algorithm to make the troll relentlessly chase the player. It will even calculate the shortest possible path to the player. So, what's the disadvantage? One concerns aesthetics. When viewed in a tile-based environment, the simple chase method doesn't always appear to produce a visually straight line. Figure 2-4 illustrates this point.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Line-of-Sight Chasing in Continuous Environments

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

The Bresenham algorithm is an effective method for tiled environments. In this section we discuss a line-of-sight chase algorithm in the context of continuous environments. Specifically, we will show you how to implement a simple chase algorithm that you can use for games that incorporate physics engines where the game entities—airplanes, spaceships, hovercraft, etc.—are driven by applied forces and torques.

The example we'll discuss in this section uses a simple two-dimensional, rigid-body physics engine to calculate the motion of the predator and prey vehicles. You can download the complete source code for this sample program, AIDemo2-2, from this book's web site. We'll cover as much rigid-body physics as necessary to get through the example, but we won't go into great detail. For thorough coverage of this subject, refer to Physics for Game Developers (O'Reilly).

Here's the scenario. The player controls his vehicle by applying thrust for forward motion and steering forces for turning. The computer-controlled vehicle uses the same mechanics as the player's vehicle does, but the computer controls the thrust and steering forces for its vehicle. We want the computer to chase the player wherever he moves. The player will be the prey while the computer will be the predator. We're assuming that the only information the predator has about the prey is the prey's current position. Knowing this, along with the predator's current position, enables us to construct a line of sight from the predator to the prey. We will use this line of sight to decide how to steer the predator toward the prey. (In the next section we'll show you another method that assumes knowledge of the player's position and velocity expressed as a vector.)

Before getting to the chase algorithm, we want to explain how the predator and prey vehicles will move. The vehicles are identical in that both are pushed about by some applied thrust force and both can turn via activation of steering forces. To turn right, a steering force is applied that will push the nose of the vehicle to the right. Likewise, to turn left, a steering force is applied that will push the nose of the vehicle to the left. For the purposes of this example, we assume that the steering forces are bow thrusters—for example, they could be little jets located on the front end of the vehicle that push the front end to either side. These forces are illustrated in Figure 2-7.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Intercepting

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

The line-of-sight chase algorithm we discussed in the previous section in the context of continuous movement is effective in that the predator always will head directly toward the prey. The drawback to this algorithm is that heading directly toward the prey is not always the shortest path in terms of range to target or, perhaps, time to target. Further, the line-of-sight algorithm usually ends up with the predator following directly behind the prey unless the predator is faster, in which case it will overshoot the prey. A more desirable solution in many cases—for example, a missile being shot at an aircraft—is to have the predator intercept the prey at some point along the prey's trajectory. This allows the predator to take a path that is potentially shorter in terms of range or time. Further, such an algorithm could potentially allow slower predators to intercept faster prey.

To explain how the intercept algorithm works, we'll use as a basis the physics-based game scenario we described earlier. In fact, all that's required to transform the basic- chase algorithm into an intercept algorithm is the addition of a few lines of code within the chase function. Before getting to the code, though, we want to explain how the intercept algorithm works in principle. (You can apply the same algorithm, building on the line-of-sight example we discussed earlier, in tile-based games too.)

The basic idea of the intercept algorithm is to be able to predict some future position of the prey and to move toward that position so as to reach it at the same time as the prey. This is illustrated in Figure 2-10.

Figure 2-10: Interception

At first glance it might appear that the predicted interception point is simply the point along the trajectory of the prey that is closest to the location of the predator. This is the shortest-distance-to-the-line problem, whereby the shortest distance from a point to the line is along a line segment that is perpendicular to the line. This is not necessarily the interception point because the shortest-distance problem does not consider the relative velocities between the predator and the prey. It might be that the predator will reach the shortest-distance point on the prey's trajectory before the prey arrives. In this case the predator will have to stop and wait for the prey to arrive if it is to be intercepted. This obviously won't work if the predator is a projectile being fired at a moving target such as an aircraft. If the scenario is a role-playing game, as soon as the player sees that the predator is in his path, he'll simply turn away.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Chapter 3: Pattern Movement

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

This chapter covers the subject of pattern movement. Pattern movement is a simple way to give the illusion of intelligent behavior. Basically, the computer-controlled characters move according to some predefined pattern that makes it appear as though they are performing complex, thought-out maneuvers. If you're old enough to remember the classic arcade game Galaga, you'll immediately know what pattern movement is all about. Recall the alien ships swooping down from the top and in from the sides of the screen, performing loops and turns, all the while shooting at your ship. The aliens, depending on their type and the level you were on, were capable of different maneuvers. These maneuvers were achieved using pattern movement algorithms.

Although Galaga is a classic example of using pattern movement, even modern video games use some form of pattern movement. For example, in a role-playing game or first-person shooter game, enemy monsters might patrol areas within the game world according to some predefined pattern. In a flight combat simulation, the enemy aircraft might perform evasive maneuvers according to some predefined patterns. Secondary creatures and nonplayer characters in different genres can be programmed to move in some predefined pattern to give the impression that they are wandering, feeding, or performing some task.

The standard method for implementing pattern movement takes the desired pattern and encodes the control data into an array or set of arrays. The control data consists of specific movement instructions, such as move forward and turn, that force the computer-controlled object or character to move according to the desired pattern. Using these algorithms, you can create a circle, square, zigzag, curve—any type of pattern that you can encode into a concise set of movement instructions.

In this chapter, we'll go over the standard pattern movement algorithm in generic terms before moving on to two examples that implement variations of the standard algorithm. The first example is tile-based, while the second shows how to implement pattern movement in physically simulated environments in which you must consider certain caveats specific to such environments.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Standard Algorithm

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

The standard pattern movement algorithm uses lists or arrays of encoded instructions, or control instructions, that tell the computer-controlled character how to move each step through the game loop. The array is indexed each time through the loop so that a new set of movement instructions gets processed each time through.

Example 3-1 shows a typical set of control instructions.

Example 3-1. Control instructions data structure

 ControlData {
     double turnRight;
     double turnLeft;
     double stepForward;
     double stepBackward;
     };

In this example, turnRight and turnLeft would contain the number of degrees by which to turn right or left. If this were a tile-based game in which the number of directions in which a character could head is limited, turnRight and turnLeft could mean turn right or left by one increment. stepForward and stepBackward would contain the number of distance units, or tiles, by which to step forward or backward.

This control structure also could include other instructions, such as fire weapon, drop bomb, release chaff, do nothing, speed up, and slow down, among many other actions appropriate to your game.

Typically you set up a global array or set of arrays of the control structure type to store the pattern data. The data used to initialize these pattern arrays can be loaded in from a data file or can be hardcoded within the game; it really depends on your coding style and on your game's requirements.

Initialization of a pattern array, one that was hardcoded, might look something such as that shown in Example 3-2.

Example 3-2. Pattern initialization

Pattern[0].turnRight = 0;
Pattern[0].turnLeft = 0;
Pattern[0].stepForward = 2;
Pattern[0].stepBackward = 0;
Pattern[1].turnRight = 0;
Pattern[1].turnLeft = 0;
Pattern[1].stepForward = 2;
Pattern[1].stepBackward = 0;
Pattern[2].turnRight = 10;
Pattern[2].turnLeft = 0;
Pattern[2].stepForward = 0;
Pattern[2].stepBackward = 0;
Pattern[3].turnRight = 10;
Pattern[3].turnLeft = 0;
Pattern[3].stepForward = 0;
Pattern[3].stepBackward = 0;
Pattern[4].turnRight = 0;
Pattern[4].turnLeft = 0;
Pattern[4].stepForward = 2;
Pattern[4].stepBackward = 0;
Pattern[5].turnRight = 0;
Pattern[5].turnLeft = 0;
Pattern[5].stepForward = 2;
Pattern[5].stepBackward = 0;
Pattern[6].turnRight = 0;
Pattern[6].turnLeft = 10;
Pattern[6].stepForward = 0;
Pattern[6].stepBackward = 0;
                 .
                 .
                 .

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Pattern Movement in Tiled Environments

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

The approach we're going to use for tile-based pattern movement is similar to the method we used for tile-based line-of-sight chasing in Chapter 2. In the line-of-sight example, we used Bresenham's line algorithm to precalculate a path between a starting point and an ending point. In this chapter, we're going to use Bresenham's line algorithm to calculate various patterns of movement. As we did in Chapter 2, we'll store the row and column positions in a set of arrays. These arrays can then be traversed to move the computer-controlled character, a troll in this example, in various patterns.

In this chapter, paths will be more complex than just a starting point and an ending point. Paths will be made up of line segments. Each new segment will begin where the previous one ended. You need to make sure the last segment ends where the first one begins to make the troll moves in a repeating pattern. This method is particularly useful when the troll is in a guarding or patrolling mode. For example, you could have the troll continuously walk around the perimeter of a campsite and then break free of the pattern only if an enemy enters the vicinity. In this case, you could use a simple rectangular pattern.

You can accomplish this rectangular pattern movement by simply calculating four line segments. In Chapter 2, the line-of-sight function cleared the contents of the row and column path arrays each time it was executed. In this case, however, each line is only a segment of the overall pattern. Therefore, we don't want to initialize the path arrays each time a segment is calculated, but rather, append each new line path to the previous one. In this example, we're going to initialize the row and column arrays before the pattern is calculated. Example 3-4 shows the function that we used to initialize the row and column path arrays.

Example 3-4. Initialize path arrays

void    InitializePathArrays(void)
{
     int i;
     for (i=0;i<kMaxPathLength;i++)
           {
                  pathRow[i] = --1;
                  pathCol[i] = --1;
          }
}

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Pattern Movement in Physically Simulated Environments

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

So far in this chapter we discussed how to implement patterned movement in environments where you can instruct your game characters to take discrete steps or turns; but what about physically simulated environments? Surely you can take advantage of the utility of pattern movement in physically simulated environments as well. The trouble is that the benefit of using physically simulated environments—namely, letting the physics take control of movement—isn't conducive to forcing a physically simulated object to follow a specific pattern of movement. Forcing a physically simulated aircraft, for example, to a specific position or orientation each time through the game loop defeats the purpose of the underlying physical simulation. In physically simulated environments, you don't specify an object's position explicitly during the simulation. So, to implement pattern movement in this case, you need to revise the algorithms we discussed earlier. Specifically, rather than use patterns that set an object's position and orientation each time through the game loop, you need to apply appropriate control forces to the object to coax it, or essentially drive it, to where you want it to go.

You saw in the second example in Chapter 2 how we used steering forces to make the predator chase his prey. You can use these same steering forces to drive your physically simulated objects so that they follow some pattern. This is, in fact, an approximation to simulating an intelligent creature at the helm of such a physically simulated vehicle. By applying control forces, you essentially are mimicking the behavior of the driver piloting his vehicle in some pattern. The pattern can be anything—evasive maneuvers, patrol paths, stunts—so long as you can apply the appropriate control forces, such as thrust and steering forces.

Keep in mind, however, that you don't have absolute control in this case. The physics engine and the model that governs the capabilities—such as speed and turning radius, among others—of the object being simulated still control the object's overall behavior. Your input in the form of steering forces and thrust modulation, for example, is processed by the physics engine, and the resulting behavior is a function of all inputs to the physics engine, not just yours. By letting the physics engine maintain control, we can give the computer-controlled object some sense of intelligence without forcing the object to do something the physics model does not allow. If you violate the physics model, you run the risk of ruining the immersive experience realistic physics create. Remember, our goal is to enhance that immersiveness with the addition of intelligence.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Chapter 4: Flocking

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Often in video games, nonplayer characters must move in cohesive groups rather than independently. Let's consider some examples. Say you're writing an online role-playing game, and just outside the main town is a meadow of sheep. Your sheep would appear more realistic if they were grazing in a flock rather than walking around aimlessly. Perhaps in this same role-playing game is a flock of birds that prey on the game's human inhabitants. Here again, birds that hunt in flocks rather than independently would seem more realistic and pose the challenge to the player of dealing with somewhat cooperating groups of predators. It's not a huge leap of faith to see that you could apply such flocking behavior to giant ants, bees, rats, or sea creatures as well.

These examples of local fauna moving, grazing, or attacking in herds or flocks might seem like obvious ways in which you can use flocking behavior in games. With that said, you do not need to limit such flocking behavior to fauna and can, in fact, extend it to other nonplayer characters. For example, in a real-time strategy simulation, you can use group movement behavior for nonplayer unit movement. These units can be computer-controlled humans, trolls, orcs, or mechanized vehicles of all sorts. In a combat flight simulation, you can apply such group movement to computer-controlled squadrons of aircraft. In a first-person shooter, computer-controlled enemy or friendly squads can employ such group movement. You even can use variations on basic flocking behavior to simulate crowds of people loitering around a town square, for example.

In all these examples, the idea is to have the nonplayer characters move cohesively with the illusion of having purpose. This is as opposed to a bunch of units that move about, each with their own agenda and with no semblance of coordinated group movement whatsoever.

At the heart of such group behavior lie basic flocking algorithms such as the one presented by Craig Reynolds in his 1987 SIGGRAPH paper, “Flocks, Herds, and Schools: A Distributed Behavioral Model.” You can apply the algorithm Reynolds presented in its original form to simulate flocks of birds, fish, or other creatures, or in modified versions to simulate group movement of units, squads, or air squadrons. In this chapter we're going to take a close look at a basic flocking algorithm and show how you can modify it to handle such situations as obstacle avoidance. For generality, we'll use the term

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Classic Flocking

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Craig Reynolds coined the term boids when referring to his simulated flocks. The behavior he generated very closely resembles shoals of fish or flocks of birds. All the boids can be moving in one direction at one moment, and then the next moment the tip of the flock formation can turn and the rest of the flock will follow as a wave of turning boids propagates through the flock. Reynolds' implementation is leaderless in that no one boid actually leads the flock; in a sense they all sort of follow the group, which seems to have a mind of its own. The motion Reynolds' flocking algorithm generated is quite impressive. Even more impressive is the fact that this behavior is the result of three elegantly simple rules. These rules are summarized as follows:

Cohesion

Have each unit steer toward the average position of its neighbors.

Alignment

Have each unit steer so as to align itself to the average heading of its neighbors.

Separation

Have each unit steer to avoid hitting its neighbors.

It's clear from these three rule statements that each unit must be able to steer, for example, by application of steering forces. Further, each unit must be aware of its local surroundings—it has to know where its neighbors are located, where they're headed, and how close they are to it.

In physically simulated, continuous environments, you can steer by applying steering forces on the units being simulated. Here you can apply the same technique we used in the chasing, evading, and pattern movement examples earlier in the book. (Refer to Chapter 2 and, specifically, to Figure 2-7 and surrounding discussion to see how you can handle steering.) We should point out that many flocking algorithms you'll find in other printed material or on the Web use particles to represent the units, whereas here we're going to use rigid bodies such as those we covered in Chapters 2 and 3. Although particles are easier to handle in that you don't have to worry about rotation, it's very likely that in your games the units won't be particles. Instead, they'll be units with a definite volume and a well defined front and back, which makes it important to track their orientations so that while moving around, they rotate to face the direction in which they are heading. Treating the units as rigid bodies enables you to take care of orientation.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Flocking Example

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

The example we're going to look at involves simulating several units in a continuous environment. Here, we'll use the same rigid-body simulation algorithms we used in the chasing and pattern movement examples we discussed earlier. This example is named AIDemo4, and it's available for download from the book's Web site (http://www.oreilly.com/catalog/ai).

Basically, we're going to simulate about 20 units that will move around in flocks and interact with the environment and with a player. For this simple demonstration, interaction with the environment consists of avoiding circular objects. The flocking units interact with the player by chasing him.

For this example, we'll implement a steering model that is more or less identical to the one we used in the physics-based demo in Chapter 2. You can refer to Figure 2-8 and the surrounding discussion to refresh your memory on the steering model. Basically, we're going to treat each unit as a rigid body and apply a net steering force at the front end of the unit. This net steering force will point in either the starboard or port direction relative to the unit and will be the accumulation of steering forces determined by application of each flocking rule. This approach enables us to implement any number or combination of flocking rules—each rule makes a small contribution to the total steering force and the net result is applied to the unit once all the rules are considered.

We should caution you that this approach does require some tuning to make sure no single rule dominates. That is, you don't want the steering force contribution from a given rule to be so strong that it always overpowers the contributions from other rules. For example, if we make the steering force contribution from the cohesion rule overpower the others, and say we implement an obstacle avoidance rule so that units try to steer away from objects, if the cohesion rule dominates, the units might stay together. Therefore, they will be unable to steer around objects and might run into or through them. To mitigate this sort of unbalance, we're going to do two things: first, we're going to modulate the steering force contribution from each rule; and second, we're going to tune the steering model to make sure everything is balanced, at least most of the time.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Obstacle Avoidance

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

The flocking rules we discussed so far yield impressive results. However, such flocking behavior would be far more realistic and useful in games if the units also could avoid running into objects in the game world as they move around in a flock. As it turns out, adding such obstacle avoidance behavior is a relatively simple matter. All we have to do is provide some mechanism for the units to see ahead of them and then apply appropriate steering forces to avoid obstacles in their paths.

In this example, we'll consider a simple idealization of an obstacle—we'll consider them as circles. This need not be the case in your games; you can apply the same general approach we'll apply here for other obstacle shapes as well. The only differences will, of course, be geometry, and how you mathematically determine whether a unit is about to run into the obstacle.

To detect whether an obstacle is in the path of a unit, we'll borrow from robotics and outfit our units with virtual feelers. Basically, these feelers will stick out in front of the units, and if they hit something, this will be an indication to the units to turn. We'll assume that each unit can see obstacles to the extent that we can calculate to which side of the unit the obstacle is located. This will tell us whether to turn right or left.

The model we just described isn't the only one that will work. For example, you could outfit your units with more than one feeler—say, three sticking out in three different directions to sense not only whether the obstacle is present, but also to which side of the unit it is located. Wide units might require more than one feeler so that you can be sure the unit won't sideswipe an obstacle. In 3D you could use a virtual volume that extends out in front of the unit. You then could test this volume against the game-world geometry to determine an impending collision with an obstacle. You can take many approaches.

Getting back to the approach we'll discuss, take a look at Figure 4-8 to see how our single virtual feeler will work in geometric terms. The vector,

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Follow the Leader

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Modifications to the basic flocking algorithm aren't strictly limited to obstacle avoidance. Because steering forces from a variety of rules are accumulated in the same variable and then applied all at once to control unit motion, you can effectively layer any number of rules on top of the ones we've already considered.

One such additional rule with interesting applications is a follow-the-leader rule. As we stated earlier, the flocking algorithm we discussed so far is leaderless; however, if we can combine the basic flocking algorithm with some leader-based AI, we can open up many new possibilities for the use of flocking in games.

At the moment, the three flocking rules will yield flocks that seem to randomly navigate the game world. If we add a leader to the mix, we could get flocks that move with greater purpose or with seemingly greater intelligence. For example, in an air combat simulation, the computer might control a squadron of aircraft in pursuit of the player. We could designate one of the computer-controlled aircraft as a leader and have him chase the player, while the other computer-controlled aircraft use the basic flocking rules to tail the leader, effectively acting as wingmen. Upon engaging the player, the flocking rules could be toggled off as appropriate as a dogfight ensues.

In another example, you might want to simulate a squad of army units on foot patrol through the jungle. You could designate one unit as the point man and have the other units flock behind using either a wide-visibility model or a limited one, depending on whether you want them in a bunched-up group or a single-file line.

What we'll do now with the flocking example we've been discussing is add some sort of leader capability. In this case, we won't explicitly designate any particular unit as a leader, but instead we'll let some simple rules sort out who should be or could be a leader. In this way, any unit has the potential of being a leader at any given time. This approach has the advantage of not leaving the flock leaderless in the event the leader gets destroyed or somehow separated from his flock.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Chapter 5: Potential Function-Based Movement

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

In this chapter we're going to borrow some principles from physics and adapt them for use in game AI. Specifically, we're going to use potential functions to control the behavior of our computer-controlled game units in certain situations. For example, we can use potential functions in games to create swarming units, simulate crowd movement, handle chasing and evading, and avoid obstacles. The specific potential function we focus on is called the Lenard-Jones potential function. We show you what this function looks like and how to apply it in games.

Let's revisit the chasing and evading problem we discussed at length in Chapter 2. If you recall, we considered a few different techniques for having a computer-controlled unit chase down or evade a player-controlled unit. Those techniques included the basic chase algorithm, in which the computer-controlled unit always moved directly toward the player, and an intercept algorithm. We can use potential functions to achieve behavior similar to what we can achieve using both of those techniques. The benefit to using potential functions here is that a single function handles both chasing and evading, and we don't need all the other conditionals and control logic associated with the algorithms we presented earlier. Further, this same potential function also can handle obstacle avoidance for us. Although this is convenient, there is a price to be paid. As we'll discuss later, the potential function algorithms can be quite CPU-intensive for large numbers of interacting game units and objects.

Another benefit to the potential function algorithm is that it is very simple to implement. All you have to do is calculate the force between the two units—the computer-controlled unit and the player in this case—and then apply that force to the front end of the computer-controlled unit, where it essentially acts as a steering force. The steering model here is similar to those we discussed in Chapters 2 and 4; however, in this case the force will always point along a line of action connecting the two units under consideration. This means the force can point in any direction relative to the computer-controlled unit, and not just to its left or right. By applying this force to the front end of the unit, we can get it to turn and head in the direction in which the force is pointing. By reversing the direction of this force, we can get a unit to either chase or evade as desired. Note that this steering force contributes to the propulsive force, or the thrust, of the unit, so you might see it speed up or slow down as it moves around.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

How Can You Use Potential Functions for Game AI?

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Let's revisit the chasing and evading problem we discussed at length in Chapter 2. If you recall, we considered a few different techniques for having a computer-controlled unit chase down or evade a player-controlled unit. Those techniques included the basic chase algorithm, in which the computer-controlled unit always moved directly toward the player, and an intercept algorithm. We can use potential functions to achieve behavior similar to what we can achieve using both of those techniques. The benefit to using potential functions here is that a single function handles both chasing and evading, and we don't need all the other conditionals and control logic associated with the algorithms we presented earlier. Further, this same potential function also can handle obstacle avoidance for us. Although this is convenient, there is a price to be paid. As we'll discuss later, the potential function algorithms can be quite CPU-intensive for large numbers of interacting game units and objects.

Another benefit to the potential function algorithm is that it is very simple to implement. All you have to do is calculate the force between the two units—the computer-controlled unit and the player in this case—and then apply that force to the front end of the computer-controlled unit, where it essentially acts as a steering force. The steering model here is similar to those we discussed in Chapters 2 and 4; however, in this case the force will always point along a line of action connecting the two units under consideration. This means the force can point in any direction relative to the computer-controlled unit, and not just to its left or right. By applying this force to the front end of the unit, we can get it to turn and head in the direction in which the force is pointing. By reversing the direction of this force, we can get a unit to either chase or evade as desired. Note that this steering force contributes to the propulsive force, or the thrust, of the unit, so you might see it speed up or slow down as it moves around.

As you've probably guessed, the examples we'll consider throughout the remainder of this chapter use the physically simulated model that you saw in earlier chapters. In fact, we use the examples from Chapters 2, 3, and 4 with some minor modifications. As before, you can find the example programs on this book's web site (

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Chasing/Evading

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

To show how to implement potential-based chasing (or evading), we need only add a few bits of code to AIDemo2-2 (see Chapter 2 for more details). In that example program, we simulated the predator and prey units in a continuous environment. The function UpdateSimulation was responsible for handling user interaction and for updating the units every step through the game loop. We're going to add two lines to that function, as shown in Example 5-1.

The following equation shows the Lenard-Jones potential function:

In solid mechanics, U represents the interatomic potential energy, which is inversely proportional to the separation distance, r, between molecules. A and B are parameters, as are the exponents m and n. To get the interatomic force between two molecules, we take the negative of the derivative of this potential function, which yields:

Here, again, A, B, m, and n are parameters that are chosen to realistically model the forces of attraction and repulsion of the material under consideration. For example, these parameters would differ if a scientist were trying to model a solid (e.g., steel) versus a fluid (e.g., water). Note that the potential function has two terms: one involves −A/r ⁿ, while the other involves B/r ^m. The term involving A and n represents the attraction force component of the total force, while the term involving B and m represents the repulsive force component.

The repulsive component acts over a relatively short distance, r, from the object, but it has a relatively large magnitude when r gets small. The negative part of the curve that moves further away from the vertical axis represents the force of attraction. Here, the magnitude of the force is smaller but it acts over a much greater range of separation,

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Obstacle Avoidance

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

As you've probably already realized, we can use the repelling nature of the Lenard-Jones function to our advantage when it comes to dealing with obstacles. In this case, we set the A parameter, the attraction strength, to 0 to leave only the repulsion component. We then can play with the B parameter to adjust the strength of the repulsive force and the m exponent to adjust the attenuation—i.e., the radius of influence of the repulsive force. This effectively enables us to simulate spherical, rigid objects. As the computer-controlled unit approaches one of these objects, a repulsive force develops that forces the unit to steer away from or around the object. Keep in mind that the magnitude of the repulsive force is a function of the separation distance. As the unit approaches the object, the force might be small, causing a rather gradual turn. However, if the unit is very close, the repulsive force will be large, which will force the unit to turn very hard.

In AIDemo5-1, we created several randomly placed circular objects in the scene. Then we created a computer-controlled unit and set it in motion along an initially random trajectory. The idea was to see if the unit could avoid all the obstacles. Indeed, the unit did well in avoiding the objects, as illustrated in Figure 5-3.

Figure 5-3: Obstacle avoidance

Here, the dark circles represent obstacles, while the swerving lines represent the trails the computer-controlled unit left behind as it navigated the scene. It's clear from this screenshot that the unit makes some gentle turns to avoid objects that are some distance away. Further, it takes some rather abrupt turns when it finds itself in very close proximity to an object. This behavior is very similar to what we achieved in the flocking examples in the previous chapter; however, we achieved the result here by using a very different mechanism.

How all this works is conceptually very simple. Each time through the game loop all the objects, stored in an array, are cycled through, and for each object the repulsion force between it and the unit is calculated. For many objects the force is small, as they might be very far from the unit, whereas for others that are close to the unit the force is much larger. All the force contributions are summed, and the net result is applied as a steering force to the unit. These calculations are illustrated in Example 5-3.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Swarming

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Let's consider group behavior as yet another illustration of how to use potential functions for game AI. Specifically, let's consider swarming. This is similar to flocking, however the resulting behavior looks a bit more chaotic. Rather than a flock of graceful birds, we're talking about something more like an angry swarm of bees. Using potential functions, it's easy to simulate this kind of behavior. No rules are required, as was the case for flocking. All we have to do is calculate the Lenard-Jones force between each unit in the swarm. The attractive components of those forces will make the units come together (cohesion), while the repulsive components will keep them from running over each other (avoidance).

Example 5-4 illustrates how to create a swarm using potential functions.

Example 5-4. Swarming

void     DoUnitAI(int i)
{
          int             j;
          Vector   Fs;
          Vector   Pfs;
          Vector   r, u;
          double   U, A, B, n, m, d;
          // begin Flock AI
          Fs.x = Fs.y = Fs.z = 0;
          Pfs.x = 0;
          Pfs.y = Units[i].fLength / 2.0f;
          if(Swarm)
          {
               for(j=1; j<_MAX_NUM_UNITS; j++)
               {
                    if(i!=j)
                    {
                         r = Units[i].vPosition -
                             Units[j].vPosition;
                         u = r;
                         u.Normalize();
                         A = 2000;
                         B = 10000;
                         n = 1;
                         m = 2;
                         d = r.Magnitude()/
                                    Units[i].fLength;
                         U = -A/pow(d, n) +
                                    B/pow(d, m);
                         Fs += VRotate2D(
                                         -Units[i].fOrientation,
                                         U * u);
                    }
               }
          }
          Units[i].Fa = Fs;
          Units[i].Pa = Pfs;
          // end Flock AI
}

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Optimization Suggestions

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

You've probably already noticed that the algorithms we discussed here can become quite computationally intensive as the number of obstacles or units in a swarm increases. In the case of swarming units, the simple algorithm shown in Examples 5-4 and 5-5 is of order N² and would clearly become prohibitive for larger numbers of units. Therefore, optimization is very important when actually implementing these algorithms in real games. To that end, we'll offer several suggestions for op