Inhaltsverzeichnis von AI for Game Developers

Inhaltsvorschau

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.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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;

                 .

                 .

                 .

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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;

          }

}

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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,

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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 (

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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,

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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

}

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

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 optimizing the algorithms we discussed in this chapter. Keep in mind that these suggestions are general in nature and their actual implementation will vary depending on your game architecture.

The first optimization you could make to the obstacle avoidance algorithm is to simply not perform the force calculation for objects that are too far away from the unit to have any influence on it. What you could do here is put in a quick check on the separation distance between the given obstacle and the unit, and if that distance is greater than some prescribed distance, skip the force calculation. This potentially could save many division and exponent operations.

Another approach you could take is to divide your game domain into a grid containing cells of some prescribed size. You could then assign each cell an array to store indices to each obstacle that falls within that cell. Then, while the unit moves around, you can readily determine which cell it is in and perform calculations only between the unit and those obstacles contained within that cell and the immediately adjacent cells. Now, the actual size and layout of the cells would depend on your specific game, but generally such an approach could produce dramatic savings if your game domain is large and contains a large number of obstacles. The tradeoff here is, of course, increased memory requirements to store all the lists, as well as some additional bookkeeping baggage.

You could use this same grid-and-cell approach to optimize the swarming algorithm. Once you've set up a grid, each cell would be associated with a linked list. Then, each time through the game loop, you traverse the unit's array once and determine within which cell each unit lies. You add a reference to each unit in a cell to that particular cell's linked list. Then, instead of going through nested loops, comparing each unit with every other unit, you need only traverse the units in each cell's list, plus the lists for the immediately adjacent cells. Here, again, bookkeeping becomes more complicated, but the savings in CPU usage could be dramatic. This optimization technique is commonly applied in computational fluid dynamics algorithms and effectively reduces order N

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Many different types of pathfinding problems exist. Unfortunately, no one solution is appropriate to every type of pathfinding problem. The solution depends on the specifics of the pathfinding requirements for any given game. For example, is the destination moving or stationary? Are obstacles present? If so, are the obstacles moving? What is the terrain like? Is the shortest solution always the best solution? A longer path along a road might be quicker than a shorter path over hills or swampland. It's also possible that a pathfinding problem might not even require reaching a specific destination. Perhaps you just want a game character to move around or explore the game environment intelligently. Because there are so many types of pathfinding problems, it wouldn't be appropriate to select just one solution. The A∗ algorithm, for example, although an ideal solution for many pathfinding problems, isn't appropriate for every situation. This chapter explores some of the techniques you can use for situations in which the A∗ algorithm might not be the best solution. We'll cover the venerable A∗ algorithm in Chapter 7.

At its most basic level, pathfinding is simply the process of moving the position of a game character from its initial location to a desired destination. This is essentially the same principle we used in the basic chasing algorithm we showed you in Chapter 2. Example 6-1 shows how you can use this algorithm for basic pathfinding.

Example 6-1. Basic pathfinding algorithm


if(positionX > destinationX)

       positionX--;

else if(positionX < destinationX)

       positionX++;

if(positionY > destinationY)

       positionY--;

else if(positionY < destinationY)

       positionY++;

In this example, the position of the game character is specified using the positionX and positionY variables. Each time this code is executed, the positionX and positionY coordinates are either increased or decreased so that the game character's position moves closer to the destinationX

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

At its most basic level, pathfinding is simply the process of moving the position of a game character from its initial location to a desired destination. This is essentially the same principle we used in the basic chasing algorithm we showed you in Chapter 2. Example 6-1 shows how you can use this algorithm for basic pathfinding.

Example 6-1. Basic pathfinding algorithm


if(positionX > destinationX)

       positionX--;

else if(positionX < destinationX)

       positionX++;

if(positionY > destinationY)

       positionY--;

else if(positionY < destinationY)

       positionY++;

In this example, the position of the game character is specified using the positionX and positionY variables. Each time this code is executed, the positionX and positionY coordinates are either increased or decreased so that the game character's position moves closer to the destinationX and destinationY coordinates. This is a simple and fast solution to a basic pathfinding problem. However, like its chasing algorithm counterpart from Chapter 2, it does have some limitations. This method produces an unnatural-looking path to the destination. The game character moves diagonally toward the goal until it reaches the point where it is on the same x- or y-axis as the destination position. It then moves in a straight horizontal or vertical path until it reaches its destination. Figure 6-1 illustrates how this looks.

Figure 6-1: Simple path movement

As Figure 6-1 shows, the game character (the triangle) follows a rather unnatural path to the destination (the circle). A better approach would be to move in a more natural line-of-sight path. As with the line-of-sight chase function we showed you in Chapter 2, you can accomplish this by using the Bresenham line algorithm. Figure 6-2 illustrates how a line-of-sight path using the Bresenham line algorithm appears relative to the basic pathfinding algorithm shown in Example 6-1.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Breadcrumb pathfinding can make computer-controlled characters seem very intelligent because the player is unknowingly creating the path for the computer-controlled character. Each time the player takes a step, he unknowingly leaves an invisible marker, or breadcrumb, on the game world. When a game character comes in contact with a breadcrumb, the breadcrumb simply begins following the trail. The game character will follow in the footsteps of the player until the player is reached. The complexity of the path and the number of obstacles in the way are irrelevant. The player already has created the path, so no serious calculations are necessary.

The breadcrumb method also is an effective and efficient way to move groups of computer-controlled characters. Instead of having each member of a group use an expensive and time-consuming pathfinding algorithm, you can simply have each member follow the leader's breadcrumbs.

Figure 6-8 shows how each step the player takes is marked with an integer value. In this case, a maximum of 15 steps are recorded. In a real game, the number of breadcrumbs dropped will depend on the particular game and how smart you want the game-controlled characters to appear. In this example, a troll randomly moves about the tile-based environment until it detects a breadcrumb on an adjacent location.

Figure 6-8: Breadcrumb trail

Of course, in a real game, the player never sees the breadcrumb trail. It's there exclusively for the game AI. Example 6-3 shows the class we use to track the data associated with each game character.

Example 6-3. ai_Entity class


#define   kMaxTrailLength   15

class	   ai_Entity

{

       public:

       int   row;

       int   col;

       int   type;

       int   state;

       int   trailRow[kMaxTrailLength];

       int   trailCol[kMaxTrailLength];

       ai_Entity();

       ~ai_Entity();

};

The initial

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Pathfinding is often thought of solely as a problem of moving from a starting point to a desired destination. Many times, however, it is necessary to move computer-controlled characters in a game environment in a realistic way even though they might not have an ultimate destination. For example, a car-racing game would require the computer-controlled cars to navigate a roadway. Likewise, a strategy or role-playing game might require troops to patrol the roads between towns. Like all pathfinding problems, the solution depends on the type of game environment. In a car-racing game the environment probably would be of a continuous nature. In this case the movement probably would be less rigid. You would want the cars to stay on the road, but in some circumstances that might not be possible. If a car tries to make a turn at an extremely high rate of speed, it likely would run off the road. It could then attempt to slow down and steer back in the direction of the road.

You can use a more rigid approach in a tile-based game environment. You can think of this as more of a containment problem. In this scenario the game character is confined to a certain terrain element, such as a road. Figure 6-11 shows an example of this.

Figure 6-11: Following the road

In Figure 6-11, all the terrain elements labeled as 2s are considered to be the road. The terrain elements labeled as 1s are considered to be out of bounds. So, this becomes a matter of containing the computer-controlled troll to the road area of the terrain. However, we don't want the troll to simply move randomly on the road. The result would look unnatural. We want the troll to appear as though it's walking along the road. As you'll notice, the road is more than one tile thick, so this isn't just a matter of looking for the next adjacent tile containing a 2 and then moving there. We need to analyze the surrounding terrain and decide on the best move. A tile-based environment typically offers eight possible directions when moving. We examine all eight directions and then eliminate those that are not part of the road. The problem then becomes one of deciding which of the remaining directions to take. Example 6-8 shows how we begin to analyze the surrounding terrain.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Another method of pathfinding that is very useful in game development is wall tracing. Like path-following, this method doesn't calculate a path from a starting point to an ending point. Wall tracing is more of an exploration technique. It's most useful in game environments made of many small rooms, although you can use it in maze-like game environments as well. You also can use the basic algorithm for tracing around obstacles, as we described in the previous section on obstacle tracing. Games rarely have every computer-controlled adversary simultaneously plotting a path to the player. Sometimes it's desirable for the computer-controlled characters to explore the environment in search of the player, weapons, power-ups, treasure, or anything else a game character can interact with. Having the computer-controlled characters randomly move about the environment is one solution that game developers frequently implement. This offers a certain level of unpredictability, but it also can result in the computer-controlled characters getting stuck in small rooms for long periods of time. Figure 6-15 shows a dungeon-like level that's made up of many small rooms.

Figure 6-15: Wall tracing

In the example shown in Figure 6-15, we could make the troll move in random directions. However, it would probably take it a while just to get out of the upper-left room. A better approach would be to make the troll systematically explore the entire environment. Fortunately, a relatively simple solution is available. Basically, we are going to use a lefthanded approach. If the troll always moves to its left, it will do a thorough job of exploring its environment. The trick is to remember that the troll needs to move to its left whenever possible, and not necessarily to the left from the point of view of the player. This is illustrated in Figure 6-16.

Figure 6-16: Facing player's right

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Pathfinding can be a very time-consuming and CPU-intensive operation. One way to reduce this problem is to precalculate paths whenever possible. Waypoint navigation reduces this problem by carefully placing nodes in the game environment and then using precalculated paths or inexpensive pathfinding methods to move between each node. Figure 6-19 illustrates how to place nodes on a simple map consisting of seven rooms.

Figure 6-19: Placing nodes

In Figure 6-19, you'll notice that every point on the map is in the line of sight of at least one node. Also, every node is in the line of sight of at least one other node. With a game environment constructed in this way, a game-controlled character always will be able to reach any position on the map using a simple line-of-sight algorithm. The game AI simply needs to know how the nodes connect to one another. Figure 6-20 illustrates how to label and connect each node on the map.

Figure 6-20: Labeling nodes

Using the node labels and links shown in Figure 6-20, we can now determine a path from any room to any other room. For example, moving from the room containing node A to the room containing node E entails moving through nodes ABCE. The path between nodes is calculated by a line-of-sight algorithm, or it can be a series of precalculated steps. Figure 6-21 shows how a computer-controlled character, indicated by the triangle, would calculate a path to the player-controlled character, indicated by the square.

Figure 6-21: Building a path

The computer-controlled character first calculates which node is nearest its current location and in its line of sight. In this case, that is node A. It then calculates which node is nearest the player's current location and in the player's line of sight. That is node

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

In this chapter we are going to discuss the fundamentals of the A∗ pathfinding algorithm. Pathfinding is one of the most basic problems of game AI. Poor pathfinding can make game characters seem very brainless and artificial. Nothing can break the immersive effect of a game faster than seeing a game character unable to navigate a simple set of obstacles. Handling the problem of pathfinding effectively can go a long way toward making a game more enjoyable and immersive for the player.

Fortunately, the A∗ algorithm provides an effective solution to the problem of pathfinding. The A∗ algorithm is probably one of the most, if not the most used pathfinding algorithm in game development today. What makes the A∗ algorithm so appealing is that it is guaranteed to find the best path between any starting point and any ending point, assuming, of course, that a path exists. Also, it's a relatively efficient algorithm, which adds to its appeal. In fact, you should use it whenever possible, unless, of course, you are dealing with some type of special-case scenario. For example, if a clear line of sight exists with no obstacles between the starting point and ending point, the A∗ algorithm would be overkill. A faster and more efficient line-of-sight movement algorithm would be better. It also probably wouldn't be the best alternative if CPU cycles are at a minimum. The A∗ algorithm is efficient, but it still can consume quite a few CPU cycles, especially if you need to do simultaneous pathfinding for a large number of game characters. For most pathfinding problems, however, A∗ is the best choice.Unfortunately, understanding how the A∗ algorithm works can be difficult for new game developers. In this chapter we step through the inner workings of the A∗ algorithm to see how it builds a path from a starting point to an ending point. Seeing the step-by-step construction of an A∗ path should help make it clear how the A∗ algorithm does its magic.

The first step in pathfinding is to define the search area. We need some way to represent the game world in a manner that allows the search algorithm to search for and find the best path. Ultimately, the game world needs to be represented by points that both the game characters and objects can occupy. It is the pathfinding algorithm's job to find the best path between any two points, avoiding any obstacles. How the actual game world will be represented depends on the type of game. In some cases, the game world might have to be simplified. For example, a game which uses a continuous environment would probably be made up of a very large number of points that the game characters would be able to occupy. The A

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The first step in pathfinding is to define the search area. We need some way to represent the game world in a manner that allows the search algorithm to search for and find the best path. Ultimately, the game world needs to be represented by points that both the game characters and objects can occupy. It is the pathfinding algorithm's job to find the best path between any two points, avoiding any obstacles. How the actual game world will be represented depends on the type of game. In some cases, the game world might have to be simplified. For example, a game which uses a continuous environment would probably be made up of a very large number of points that the game characters would be able to occupy. The A∗ algorithm would not be practical for this type of search space. It simply would be too large. However, it might work if the search area could be simplified. This would involve placing nodes throughout the game world. We then would be able to build paths between nodes, but not necessarily between every possible point in the world. This is illustrated in Figure 7-1.

Figure 7-1: Simplifying the search area

The tanks in Figure 7-1 are free to occupy any point in their coordinate system, but for the purposes of pathfinding, the game world is simplified by placing nodes throughout the game environment. These nodes do not correspond directly to every possible tank position. That would require too many nodes. We need to reduce the nodes to a manageable number, which is what we mean when we say we need to simplify the search area.

Of course, we need to maintain a list of the connections between the nodes. The search algorithm needs to know how the nodes connect. Once it knows how they link together, the A∗ algorithm can calculate a path from any node to any other node. The more nodes placed in the world, the slower the pathfinding process. If pathfinding is taking too many CPU cycles, one alternative is to simplify the search area by using fewer nodes.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Once we have simplified the search area so that it's made up of a reasonable number of nodes, we are ready to begin the search. We will use the A∗ algorithm to find the shortest path between any two nodes. In this example, we will use a small tiled environment. Each tile will be a node in the search area and some nodes will contain obstacles. We will use the A∗ algorithm to find the shortest path while avoiding the obstacles. Example 7-1 shows the basic algorithm we will follow.

Example 7-1. Example 7-1. A∗ pseudo code


add the starting node to the open list

while the open list is not empty

   {

      current node=node from open list with the lowest cost

      if current node = goal node then

          path complete

      else

          move current node to the closed list

          examine each node adjacent to the current node

          for each adjacent node

            if it isn't on the open list

               and isn't on the closed list

                  and it isn't an obstacle then

                     move it to open list and calculate cost

   }

Some of the particulars of the pseudo code shown in Example 7-1 might seem a little foreign, but they will become clear as we begin stepping through the algorithm.

Figure 7-3 shows the tiled search area that we will use. The starting point will be the spider near the center. The desired destination will be the human character. The solid black squares represent wall obstacles, while the white squares represent areas the spider can walk on.

Figure 7-3: Creating a tiled search area

Like any pathfinding algorithm, A∗ will find a path between a starting node and an ending node. It accomplishes this by starting the search at the starting node and then branching out to the surrounding nodes. In the case of this example, it will begin at the starting tile and then spread to the adjacent tiles. This branching out to adjacent tiles continues until we reach the destination node. However, before we start this branching search technique, we need a way to keep track of which tiles need to be searched. This is typically called the

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Ultimately, we will use path scoring to determine the best path from the starting tile to the destination tile. To actually score each tile, we basically add together two components. First, we look at the cost to move from the starting tile to any given tile. Next, we look at the cost to move from the given tile to the destination tile. The first component is relatively straightforward. We start our search from the initial location and branch out from there. This makes calculating the cost of moving from the initial location to each tile that we branch out to relatively easy. We simply take the sum of the cost of each tile that leads back to the initial location. Remember, we are saving links to the parents of each tile. Back-stepping to the initial location is a simple matter. However, how do we determine the cost of moving from a given tile to the destination tile? The destination tile is the ultimate goal, which we haven't reached yet. So, how do we determine the cost of a path that we haven't determined yet? Well, at this point, all we can do is guess. This is called the heuristic. We essentially make the best guess we can make, given the information we have. Figure 7-7 shows the equation we use for scoring any given tile.

Figure 7-7: Calculating the path score

So, we calculate each tile's score by adding the cost of getting there from the starting location to the heuristic value, which is an estimate of the cost of getting from the given tile to the final destination.

We use this score when determining which tile to check next from the open list. We will first check the tiles with the lowest cost. In this case, a lower cost will equate to a shorter path. Figure 7-8 shows the score, cost, and heuristic applied to each tile we have checked so far.

Figure 7-8: Initial tile path scores

The s value shown in each open tile is the cost of getting there from the starting tile. In this case, each value is 1 because each tile is just one step from the starting tile. The

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

It's always possible that no valid path exists between any two given points, so how do we know when we have reached a dead end? The simple way to determine if we've reached a dead end is to monitor the open list. If we reach the point where no members are in the open list to examine, we've reached a dead end. Figure 7-18 shows such a scenario.

Figure 7-18: Dead end

As Figure 7-18 shows, the A∗ algorithm has branched out to every possible adjacent tile. Each one has been examined and moved to the closed list. Eventually, the point was reached where every tile on the open list was examined and no new tiles were available to add. At that point we can conclude that we've reached a dead end and that it simply isn't possible to build a path from the starting point to the desired destination.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

As the previous example shows, path scoring already plays a major role in the A∗ algorithm. The standard A∗ algorithm in its most basic form simply determines path cost by the distance traveled. A longer path is considered to be more costly, and hence, less desirable. We often think of a good pathfinding algorithm as one that finds the shortest possible path. However, sometimes other considerations exist. For example, the shortest path isn't always the fastest path. A game environment can include many types of terrain, all of which can affect the game characters differently. A long walk along a road might be faster than a shorter walk through a swamp. This is where terrain cost comes into play. The previous example shows how we calculate each node's cost by adding its distance from the initial location to the heuristic value, which is the estimated distance to the destination. It might not have been obvious, but the previous example basically did calculate terrain cost. It just wasn't very noticeable because all the terrain was the same. Each step the game character took added a value of 1 to the path cost. Basically, every node had the same cost. However, there's no reason why we can't assign different cost values to different nodes. It requires just a minor change to the cost equation. We can update the cost equation by factoring in the terrain cost. This is shown in Figure 7-19.

Figure 7-19: Scoring with terrain cost

This results in paths that are longer, but that involve easier terrain. In an actual game this can result in a game character getting from point A to point B in a shorter amount of time, even if the actual path is longer. For example, Figure 7-20 shows several hypothetical types of terrain.

Figure 7-20: Types of terrain

The previous example essentially had only open terrain. The cost of moving from one node to another was always 1. As Figure 7-20 shows, we will now introduce two new types of terrain. The first new terrain type is grassland, which has a cost of 3. The second new type of terrain is swampland, which has a cost of 5. In this case, cost ultimately refers to the amount of time it takes to traverse the node. For example, if it takes a game character one second to walk across a node of open terrain, it will take three seconds to walk across a node of grassland, and five seconds to walk across a node of swampland. The actual physical distances might be equal, but the time it takes to traverse them is different. The A

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The previous section showed how different terrain elements can affect how the A∗ algorithm calculates a path. Terrain cost is usually something that the game designer hardcodes into the game world. Basically, we know beforehand where the grasslands, swamplands, hills, and rivers will be located. However, other elements can influence path cost when calculating a path with A∗. For example, nodes that pass through the line of sight of any enemy might present a higher cost. This isn't a cost that you could build into a game level because the position of the game characters can change. Influence mapping is a way to vary the cost of the A∗ nodes depending on what is happening in the game. This is illustrated in Figure 7-26.

Figure 7-26: Influenced by the enemy firing zone

As Figure 7-26 shows, we have assigned a cost to each node. Unlike the terrain cost we showed you in the previous section, however, this cost is influenced by the position and orientation of the tank shown at position (8, 4). This influence map will change as the tank's position and orientation change. Like the terrain cost from the previous section, the influence map cost will be added to each node's s value when calculating possible paths. This will result in the tank's target possibly taking a longer and slower route when building a path. However, the tiles in the line of fire still are passable, just at a higher cost. If no other path is available, or if the alternate paths have a higher cost, the game character will pass through the line of fire.

You can use influence mapping in other ways to make game characters seem smarter. You can record individual game incidents in an influence map. In this case, we aren't using the position and orientation of a game character to build an influence map. We are instead using what the character does. For example, if the player repeatedly ambushes and kills computer-controlled characters at a given doorway, that doorway might increase in cost. The computer could then begin to build alternate paths whenever possible. To the player, this can make the computer-controlled characters seem very intelligent. It will appear as though they are learning from their mistakes. This technique is illustrated in Figure 7-27.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Steven Woodcock reported in his “2003 Game Developer's Conference AI Roundtable Moderator's Report” that AI developers essentially considered pathfinding solved. Other game AI resources all over the Web echo this sentiment. What developers mean is that proven algorithms are available to solve pathfinding problems in a wide variety of game scenarios and most effort these days is focused on optimizing these methods. The workhorse pathfinding method is by far the A∗ algorithm. Current development effort is now focused on developing faster, more efficient A∗ algorithms. Game Programming Gems (Charles River Media) and AI Game Programming Wisdom (Charles River Media) contain several interesting articles on A∗ optimizations.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

This chapter discusses some of the techniques you can use to apply a scripting system to the problem of game AI, and the benefits you can reap from doing this. At its most basic level, you can think of scripting as a very simple programming language tailored to a specific task related to the game in question. Scripting can be an integral part of the game development process, as it enables the game designers rather than the game programmers to write and refine much of the game mechanics. Players also can use scripting to create or modify their own game worlds or levels. Taken a step further, you can use a scripting system in a massively multiplayer online role-playing game (MMORG) to alter the game behavior while the game is actually being played.

You can take several approaches when implementing a scripting system. A sophisticated scripting system might interface an already existing scripting language, such as Lua or Python, for example, with the actual game engine. Some games create a proprietary scripting language designed for the needs of the individual game. Although it's sometimes beneficial to use those methods, it's easier to have the game parse standard text files containing the scripting commands. Employing this approach, you can create scripts using any standard text editor. In a real game, the scripts can be read in and parsed when the game first starts, or at some other specified time. For example, scripts that control creatures or events in a dungeon can be read in and parsed when the player actually enters the dungeon area.

In the scope of game AI, you can use scripting to alter opponent attributes, behavior, responses, and game events. This chapter looks at all these uses.

The actual scripting language used in a game is ultimately up to the game designers and programmers. It can resemble preexisting languages such as C or C++, or it can take a totally unique approach; perhaps even a graphical rather than a text-based approach. Deciding how the scripting system looks and works depends primarily on who will be using the scripting system. If your target is the end player, a more natural language or graphical approach might be beneficial. If the system is primarily for the designers and programmers, it might not be beneficial to spend your development time on a complex and time-consuming natural language parsing system. A quick and dirty approach might be better.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The actual scripting language used in a game is ultimately up to the game designers and programmers. It can resemble preexisting languages such as C or C++, or it can take a totally unique approach; perhaps even a graphical rather than a text-based approach. Deciding how the scripting system looks and works depends primarily on who will be using the scripting system. If your target is the end player, a more natural language or graphical approach might be beneficial. If the system is primarily for the designers and programmers, it might not be beneficial to spend your development time on a complex and time-consuming natural language parsing system. A quick and dirty approach might be better.

You also should consider other factors when developing a scripting system. Perhaps you want the script to be easy to read and write for the game designers, but not necessarily for the game players. In this case, you might want to use a form of encryption. You also could develop a script compiler so that the end result is less readable to humans.

In this chapter we create simple scripting commands and save them in standard text files. We want to avoid the need for a complex language parser, but at the same time we have been careful to choose a vocabulary that makes it relatively easy for humans to read and write the scripts. In other words, we use words that accurately reflect the aspect of the game that the script is altering.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

It's common and beneficial to specify all the basic attributes of each AI opponent by using some type of scripting. This makes it easy to tweak the AI opponents throughout the development and testing process. If all the vital data were hardcoded into the program, you would have to recompile for even the most basic change.

In general, you can script opponent attributes such as intelligence, speed, strength, courage, and magical ability. In reality, there is no limit to the possible number or types of attributes you can script. It really comes down to the type of game you're developing. Of course, the game engine ultimately will use these attributes whenever a computer-controlled friend or foe interacts with the player. For example, an opponent that has a higher intelligence attribute would be expected to behave differently from one of lower intelligence. Perhaps a more intelligent opponent would use a more sophisticated pathfinding algorithm to track down a player, while a less intelligent opponent might become easily confused when trying to reach the player.

Example 8-1 shows a basic script you can use to set game attributes.

Example 8-1. Basic script to set attributes


CREATURE=1;

INTELLIGENCE=20;

STRENGTH=75;

SPEED=50;

END

In this example, our script parser has to interpret five commands. The first, CREATURE, indicates which AI opponent is being set. The next three, INTELLIGENCE, STRENGTH, and SPEED, are the actual attributes being set. The final command, END, tells the script parser that we are finished with that creature. Anything that follows comprises a new and separate block of commands.

It would be just as easy to include the numbers 1,20,75,50 in a file and thus avoid any need for parsing the script text. That approach works and developers use it frequently, but it does have some disadvantages. First, you lose quite a bit of readability. Second, and most important, your scripting system can increase in complexity to the point where specifying attributes by just including their numerical values in a file becomes impractical. Example 8-2 shows how a script can become more complicated by using a conditional statement.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Now that we've shown what a basic attribute script looks like, we're going to explore how a game reads and parses a script. As an example, we will use a basic script to set some of the attributes for a troll. We will create a text file called Troll Settings.txt. Example 8-3 shows the contents of the troll settings file.

Example 8-3. Basic script to set attributes


INTELLIGENCE=20;

STRENGTH=75;

SPEED=50;

Example 8-3 is a simple example that sets only three creature attributes. However, we will set up our code so that we can easily add more attributes with very little change to our script parser. Basically, we are going to set up our parser so that it will search a given file for a specified keyword and then return the value associated with the keyword. Example 8-4 shows how this might look in an actual game.

Example 8-4. Basic script to set attributes


intelligence[kTroll]=fi_GetData("Troll Settings.txt,

                                "INTELLIGENCE");

strength[kTroll]= fi_GetData("Troll Settings.txt,

                             "STRENGTH");

speed[kTroll]= fi_GetData("Troll Settings.txt,

                          "SPEED");

Example 8-4 shows three hypothetical arrays that can store creature attributes. Rather than hardcoding these values into the game, they are loaded from an external script file called Troll Settings.txt. The function fi_GetData traverses the external file until it finds the specified keyword. It then returns the value associated with that keyword. The game designers are free to tweak the creature setting without the need to recompile the program code after each change.

Now that we have seen how you can use the fi_GetData function to set the attributes for a troll, let's go a step further. Example 8-5 shows how the function accomplishes its task.

Example 8-5. Reading data from a script


int fi_GetData(char filename[kStringLength], char searchFor[kStringLength])

{	

FILE   *dataStream;

char   inStr[kStringLength];

char   rinStr[kStringLength];

char   value[kStringLength];

long   ivalue;

int    i;

int    j;

dataStream = fopen(filename, "r" );

if (dataStream != NULL)

   {

       while (!feof(dataStream))

           {

              if (!fgets(rinStr,kStringLength,dataStream))

                 {

                    fclose( dataStream );

                    return (0);

                 }

            j=0;

            strcpy(inStr,"");

            for (i=0;i<strlen(rinStr);i++)

               if (rinStr[i]!=' ')

                  {

                     inStr[j]=rinStr[i];

                     inStr[j+1]='\0';

                     j++;

                  }

            if (strncmp(searchFor, inStr,

                        strlen(searchFor)) == 0)

               {

                  j=0;

                  for(i=strlen(searchFor);

                      i<kStringLength;

                      i++)

                     {

                        if (inStr[i]==';')

                           break;

                        value[j]=inStr[i];

                        value[j+1]='\0';

                        j++;

                     }

                  StringToNumber(value, &ivalue);

                  fclose( dataStream );

                  return ((int)ivalue);

               }

            }

         fclose( dataStream );

         return (0);

      }

   return (0);

}

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Directly affecting an opponent's behavior is one of the most common uses of scripting in game AI. Some of the previous examples showed how scripting attributes can have an indirect effect on behavior. This included such examples as modifying a creature's intelligence attribute, which presumably would alter its behavior in the game.

Scripting behavior enables us to directly manipulate the actions of an AI opponent. For this to be useful, however, we need some way for our script to see into the game world and check for conditions that might alter our AI behavior. To accomplish this we can add predefined global variables to our scripting system. The actual game engine, not our scripting language, will assign the values in these variables. They are used simply as a way for the script to evaluate a particular condition in the game world. We will use these global variables in conditional scripting statements. For example, in our scripting system we might have a global boolean variable called PlayerArmed which will direct a cowardly troll to ambush only unarmed opponents. Example 8-6 shows how such a script might look.

Example 8-6. Basic behavior script


If (PlayerArmed==TRUE)

   BEGIN

      DoFlee();

   END

ELSE

   BEGIN

      DoAttack();

   END

In Example 8-6, the script does not assign the value PlayerArmed. It represents a value within the game engine. The game engine will evaluate the script and link this behavior to the cowardly troll.

In this example, the value PlayerArmed is a simple boolean value that represents nothing more than another boolean value within the game engine. There certainly is nothing wrong with this, but scripting is more useful when you use simple global variables which represent a more complex series of evaluations. For example, in this sample script we checked whether the player was armed. Although that might be useful for an opponent to know, it doesn't necessarily represent how challenging the opponent will be in a fight.

Many factors could contribute to how challenging a potential opponent will be. We can make our scripting system even more powerful if we evaluate these conditions in the game engine and then make the result available to the script as a single global variable. For example, we could use a Bayesian network to evaluate how tough an opponent the player is and then make the result available in a variable such as

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The benefits of scripting go beyond just making an AI opponent more sophisticated and challenging. Many types of games incorporate intelligent behavior in ways that aren't meant to be a direct challenge to the player. A role-playing game, for example, might provide the player with a series of subtle hints meant to move the story along. Scripting is an excellent way to enable the game designer to create a compelling story without the need to alter the actual game program.

Intelligent behavior can make a game more challenging, but verbal responses that are intelligent and appropriate to the situation can go even farther when creating an immersive environment for the player. Verbal interaction can range from helpful hints from a friendly nonplayer character to taunts from an adversary. Verbal interaction seems most intelligent and immersive when it relates to the current game situation. This means the game AI needs to check a given set of game parameters and then respond to them accordingly.

For example, how a player is armed might be one parameter that can be checked. We can then have an adversarial AI character comment on how ineffective that weapon will be once combat starts. This seems more intelligent and immersive because it's not just a random taunt. It applies to the current game situation. It makes it seem as though the computer-controlled characters are aware of what's happening in the game. A quick example of how this script might look is shown in Example 8-9.

Example 8-9. Verbal taunt script


If (PlayerArmed ==Dagger)

   Say("What a cute little knife.");

If (PlayerArmed ==Bow)

   Say("Drop the bow now and I'll let you live.");

If (PlayerArmed ==Sword)

   Say("That sword will fit nicely in my collection.");

If (PlayerArmed ==BattleAxe)

   Say("You're too weak to wield that battle axe.");

As Example 8-9 shows, knowing a bit about the current game situation can add an immersive effect to gameplay. This is much more effective than simply adding random general taunts.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Now let's examine some of the other ways scripting can make gameplay more immersive. The previous sections showed how scripts alter the behavior of AI characters. Scripting behavior goes a long way toward making games and AI characters seem more real. However, you can use scripting to make games more entertaining and realistic in other ways as well. In this section we examine how scripts trigger in-game events that might not be related directly to AI characters. For example, perhaps stepping on a particular location will trigger a trap. Example 8-16 shows how this might look in a text-based scripting language.

Example 8-16. Trap event script


If (PlayerLocation(120,76))

   Trigger(kExposionTrap);

If (PlayerLocation(56,16))

   Trigger(kPoisonTrap);

As Example 8-16 shows, the scripting system can compare the player position to some predetermined value and then trigger a trap if they are equal. Of course, you can make this much more sophisticated by making the triggering mechanism more complex. Perhaps the trap is triggered only if the player is holding a certain item or wearing a particular piece of armor.

Scripting also can be an effective way to add a sense of ambience to gameplay. For example, you can link certain situations or objects to particular sound effects. If the player walks on a dock, a seagull sound effect might be triggered. You could use an entire scripting file solely for linking sound effects to different situations.

Figure 8-4 shows the player standing in a doorway. This would be an excellent situation to link to a creaking-door sound effect.

Figure 8-4: Door Sound script

Example 8-17 shows how the player location or game situation, such as the game time, can trigger relevant sound effects.

Example 8-17. Triggered sound script


If (PlayerLocation(kDoorway))

  PlaySound(kCreakingDoorSnd);

If (PlayerLocation(kDock))

  PlaySound (kSeagullSnd);

If (PlayerLocation(kBoat))

  PlaySound (kWavesSnd);

If (GameTime==kNight)

  PlaySound (kCricketsSnd);

If (GameTime==kDay)

  PlaySound (kBirdsSnd);

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

In this chapter we showed you how to implement basic scripting that enables you to alter game AI outside the main game program. Such scripting can be very effective. Indeed, we successfully implemented these techniques in an MMORG to enable game masters to change the game AI and other game parameters in real time. Implementing a full-fledged scripting engine can be very challenging, and it involves additional concepts that we have not yet covered. These concepts include finite state machines and rule-based systems, which we'll get to in Chapters 9 and 11 of this book.

If you decide to pursue scripting even further than we do in this book, you might find the following resources to be particularly helpful:

AI Application Programming by M.Tim Jones (Charles River Media)
AI Game Programming Wisdom by Steve Rabin, ed. (Charles River Media)

In the first reference, author Tim Jones shows how to implement a scripted rule-based system from scratch. His approach combines concepts we covered in this chapter and those we will cover in Chapter 11. The second reference includes seven articles written by game programming veterans focusing specifically on issues related to implementing scripting engines for games.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

A finite state machine is an abstract machine that can exist in one of several different and predefined states. A finite state machine also can define a set of conditions that determine when the state should change. The actual state determines how the state machine behaves.

Finite state machines date back to the earliest days of computer game programming. For example, the ghosts in Pac Man are finite state machines. They can roam freely, chase the player, or evade the player. In each state they behave differently, and their transitions are determined by the player's actions. For example, if the player eats a power pill, the ghosts' state might change from chasing to evading. We'll come back to this example in the next section.

Although finite state machines have been around for a long time, they are still quite common and useful in modern games. The fact that they are relatively easy to understand, implement, and debug contributes to their frequent use in game development. In this chapter, we discuss the fundamentals of finite state machines and show you how to implement them.

The diagram in Figure 9-1 illustrates how you can model a simple finite state machine.

Figure 9-1: Generic finite state machine diagram

In Figure 9-1, each potential state is illustrated with a circle, and there are four possible states {Si, S1, S2, S3}. Of course, every finite state machine also needs a means to move from one state to another. In this case, the transition functions are illustrated as {t1, t2, t3, t4, t5}. The finite state machine begins with the initial state Si. It remains is this state until the t1 transition function provides a stimulus. Once the stimulus is provided, the state switches to S1. At this point, it's easy for you to see which stimulus is needed to move from one state to another. In some cases, such as with S1, only the stimulus provided by t5 can change the machine's state. However, notice that in the case of

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The diagram in Figure 9-1 illustrates how you can model a simple finite state machine.

Figure 9-1: Generic finite state machine diagram

In Figure 9-1, each potential state is illustrated with a circle, and there are four possible states {Si, S1, S2, S3}. Of course, every finite state machine also needs a means to move from one state to another. In this case, the transition functions are illustrated as {t1, t2, t3, t4, t5}. The finite state machine begins with the initial state Si. It remains is this state until the t1 transition function provides a stimulus. Once the stimulus is provided, the state switches to S1. At this point, it's easy for you to see which stimulus is needed to move from one state to another. In some cases, such as with S1, only the stimulus provided by t5 can change the machine's state. However, notice that in the case of S3 and S2 two possible stimuli result in a state change.

Now that we've shown you a simple state machine model, let's look at a more practical and slightly more complex example. Figure 9-2 shows a finite state machine that might appear in an actual game.

Figure 9-2: Ghost finite state machine diagram

Look closely at Figure 9-2, and you can see that the behavior of the finite state machine models a behavior similar to that of a ghost in Pac Man. Each oval represents a possible state. In this case, there are three possible states: roam, evade, and chase. The arrows show the possible transitions. The transitions show the conditions under which the state can change or remain the same.

In this case, the computer-controlled AI opponent begins in the initial rRoam state. Two conditions can cause a change of state. The first is blue=true. In this case, the AI opponent has turned blue because the player has eaten a power pill. This results in a state change from roam to evade. The other condition that can change the state is see=

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Now we will discuss some of the methods you can use to implement a finite state machine in a game. Finite state machines actually lend themselves very well to game AI development. They present a simple and logical way to control game AI behavior. In fact, they probably have been implemented in many games without the developer realizing that a finite state machine model was being used.

We'll start by dividing the task into two components. First, we will discuss the types of structures we will use to store the data associated with the game AI entity. Then we will discuss how to set up the functions we will use to transition between the machine states.

Games that are developed using a high-level language, such as C or C++, typically store all the data related to each game AI entity in a single structure or class. Such a structure can contain values such as position, health, strength, special abilities, and inventory, among many others. Of course, besides all these elements, the structure also stores the current AI state, and it's the state that ultimately determines the AI's behavior. Example 9-2 shows how a typical game might store a game AI entity's data in a single class structure.

Example 9-2. Game AI structure


class AIEntity

   {

      public:

         int type;

         int state;

         int row;

         int column;

         int health;

         int strength;

         int intelligence;

         int magic;

   };

In Example 9-2, the first element in the class refers to the entity type. This can be anything, such as a troll, a human, or an interstellar battle cruiser. The next element in the class is the one that concerns us most in this chapter. This is where the AI state is stored. The remaining variables in the structure show typical values that generally are associated with a game AI entity.

The state itself typically is assigned using a global constant. Adding a new state is as simple as adding a new global constant. Example 9-3 shows how you can define such constants.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The objective in this example of our finite state machine is to create a finite state machine simulation consisting of two teams of AI ants. The purpose of the simulation is for the ants to collect food and return it to their home position. The ants will have to follow certain obstacles and rules in the simulation. First, the ants will move randomly in their environment in an attempt to locate a piece of food. Once an ant finds a piece of food, it will return to its home position. When it arrives home, it will drop its food and then start a new search for water rather than food. The thirsty ants will roam randomly in search of water. Once an ant finds water, it will resume its search for more food.

Returning food to the home position also will result in a new ant emerging from the home position. The ant population will continue to grow so long as more food is returned to the home position. Of course, the ants will encounter obstacles along the way. In addition to the randomly placed food will be randomly placed poison. Naturally, the poison has a fatal effect on the ants.

Figure 9-3 presents a finite state diagram that illustrates the behavior of each ant in the simulation.

Figure 9-3: Ant finite state machine diagram

As Figure 9-3 shows, each ant begins in the initial forage state. From that point, the state can change in only two ways. The state can change to go home with the found food transition function, or it can encounter the found poison transition, which kills the ant. Once food is found, the state changes to go home. Once again, there are only two ways out of this state. One is to meet the objective and find the home position. This is illustrated by the found home transition arrow. The other possible transition is to find poison. Once the home position is found, the state changes to thirsty. Like the previous states, there are two ways to change states. One is to meet the goal by finding water, and the other is to find poison. If the goal is met, the ant returns to the initial forage state.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Finite state machines are ubiquitous in games. It's no surprise that virtually every game development book covers them to some degree. Further, the Internet is full of resources covering finite state machines. Here are just a few Internet resources that discuss finite state machines:

http://www.gamasutra.com
http://www.gameai.com
http://www.generation5.org
http://www.aboutai.net

If you perform an Internet search using the keywords “finite state machine,” you're sure to find a few hundred more resources. Also, try performing a search using the keywords “fuzzy state machine.” Fuzzy state machines are a popular variant of finite state machines that incorporate probability in state transitions. We cover probability in Chapter 12.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

In 1965 Lotfi Zadeh, a professor at the University of California Berkeley, wrote his original paper laying out fuzzy set theory. We find no better way of explaining what fuzzy logic is than by quoting the father of fuzzy logic himself. In a 1994 interview of Zadeh conducted by Jack Woehr of Dr. Dobbs Journal, Woehr paraphrases Zadeh when he says “fuzzy logic is a means of presenting problems to computers in a way akin to the way humans solve them.” Zadeh later goes on to say that “the essence of fuzzy logic is that everything is a matter of degree.” We'll now elaborate on these two fundamental principles of fuzzy logic.

What does the statement “problems are presented to computers in a way similar to how humans solve them” really mean? The idea here is that humans very often analyze situations, or solve problems, in a rather imprecise manner. We might not have all the facts, the facts might be uncertain, or perhaps we can only generalize the facts without the benefit of precise data or measurements.

For example, say you're playing a friendly game of basketball with your buddies. When sizing up an opponent on the court to decide whether you or someone else should guard him, you might base your decision on the opponent's height and dexterity. You might decide the opponent is tall and quick, and therefore, you'd be better off guarding someone else. Or perhaps you'd say he is very tall but somewhat slow, so you might do fine against him. You normally wouldn't say to yourself something such as, “He's 6 feet 5.5 inches tall and can run the length of the court in 5.7 seconds.”

Fuzzy logic enables you to pose and solve problems using linguistic terms similar to what you might use; in theory you could have the computer, using fuzzy logic, tell you whether to guard a particular opponent given that he is very tall and slow, and so on. Although this is not necessarily a practical application of fuzzy logic, it does illustrate a key point—fuzzy logic enables you to think as you normally do while using very precise tools such as computers.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

You can use fuzzy logic in games in a variety of ways. For example, you can use fuzzy logic to control bots or other nonplayer character units. You also can use it for assessing threats posed by players. Further, you can use fuzzy logic to classify both player and nonplayer characters. These are only a few specific examples, but they illustrate how you can use fuzzy logic in distinctly different scenarios. Let's consider each example in a little more detail.

Fuzzy logic is used in a wide variety of real-world control applications such as controlling trains, air conditioning and heating systems, and robots, among other applications. Video games also offer many opportunities for fuzzy control. You can use fuzzy control to navigate game units—land vehicles, aircraft, foot units, and so on—smoothly through waypoints and around obstacles. You also can accomplish as well as improve upon basic chasing and evading using fuzzy control.

Let's say you have a unit that is traveling along some given heading, but it needs to travel toward some specific target that might be static or on the move. This target could be a waypoint, an enemy unit, some treasure, a home base, or anything else you can imagine in your game. We can solve this problem using deterministic methods similar to those we've already discussed in this book; however, recall that in some cases we had to manually modulate steering forces to achieve smooth turns. If we didn't modulate the steering forces, the units abruptly would change heading and their motion would appear unnatural. Fuzzy logic enables you to achieve smooth motion without manually modulating steering forces. You also can gain other improvements using fuzzy logic. For example, recall the problem with basic chasing whereby the unit always ended up following directly behind the target moving along one coordinate axis only. Earlier we solved this problem using other methods, such as line-of-sight chasing, interception, or potential functions. Fuzzy logic, in this case, would yield results similar to interception. Basically, we'd tell our fuzzy controller that our intended target is to the far left, or to the left, or straight ahead, or to the right, and so on, and let it calculate the proper steering force to apply to facilitate heading toward the target in a smooth manner.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Now that you have an idea of what fuzzy logic is all about and how you can use it in games, let's take a close look at how fuzzy logic works and is implemented. If the concept of fuzzy logic is still a little, well, fuzzy to you at this point, don't worry. The concepts will become much clearer as we go over the details in the next few sections.

The fuzzy control or inference process comprises three basic steps. Figure 10-1 illustrates these steps.

Figure 10-1: Fuzzy process overview

The first part of the process is called the fuzzification process. In this step, a mapping process converts crisp data (real numbers) to fuzzy data. This mapping process involves finding the degree of membership of the crisp input in predefined fuzzy sets. For example, given a person's weight in pounds, we can find the degree to which the person is underweight, overweight, or at an ideal weight.

Once you have expressed all the inputs to the system in terms of fuzzy set membership, you can combine them using logical, fuzzy rules to determine the degree to which each rule is true. In other words, you can find the strength of each rule or the degree of membership in an output, or action, fuzzy set. For example, given a person's weight and activity level as input variables, we can define rules that look something such as the following:

If overweight AND NOT active then frequent exercise
If overweight AND active then moderate diet

These rules combine the fuzzy input variables using logical operators to yield a degree of membership, or degree or truth, of the corresponding output action, which in this case is the recommendation to engage in frequent exercise or go on a moderate diet.

Often, having a fuzzy output such as frequent exercise is not enough. We might want to quantify the amount of exercise—for example, three hours per week. This process of taking fuzzy output membership and producing a corresponding crisp numerical output is called

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

In the control example at the beginning of this chapter we wanted to use fuzzy control to steer a computer-controlled unit toward some objective. This objective could be a waypoint, an enemy unit, and so on. To achieve this, we'll set up several fuzzy sets that describe the relative heading between the computer-controlled unit and its objective. The relative heading is simply the angle between the computer-controlled unit's velocity vector and the vector connecting the positions of the computer-controlled unit and the objective. Using techniques we've discussed in earlier examples—namely, the chase and evade examples—you can determine this relative heading angle, which will be a scalar angle in degrees.

What we now aim to do is use that relative heading as input to a fuzzy control system to determine the appropriate amount of steering force to apply to guide the computer-controlled unit to the target. This is a very simple example, as there is only one input variable and thus only one set of fuzzy membership functions to define. For this example, we set up the membership functions and fuzzy sets illustrated in Figure 10-13.

Figure 10-13: Relative heading fuzzy sets

We have five fuzzy sets in this case. Reading from left to right, each set represents relative headings qualitatively as Far Left, Left, Ahead, Right, and Far Right. The Far Left and Far Right membership functions are grade functions, while the Left and Right functions are trapezoids. The Ahead function is a triangle. Given any relative heading angle, you can use the C functions shown in Example 10-1 to calculate membership in each fuzzy set.

Let's say that at some given time in the game, the relative heading angle is found to be a positive 33 degrees. Now we need to calculate the degree to which this relative heading falls within each of the five fuzzy sets. Clearly, the degree will be 0 for all sets, with the exception of the Right and Far Right sets. However, we'll go ahead and show code for all membership calculations for completeness. Example 10-1 shows the code.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

In the threat assessment example we discussed at the beginning of this chapter, we wanted to process two input variables, enemy force and the size of force, to determine the level of threat posed by this force. Ultimately, we want to determine the appropriate number for defensive units to deploy as protection against the threatening force. This example requires us to set up several fuzzy rules and defuzzify the output to obtain a crisp number for the number of defensive units to deploy. The first order of business, however, is to define fuzzy sets for the two input variables. Figures 10-14 and 10-15 show what we've put together for this example.

Figure 10-14: Range fuzzy sets

Figure 10-15: Force size fuzzy sets

Referring to Figure 10-14 and going from the left to the right, these three membership functions represent the sets Close, Medium, and Far. The range can be specified in any units appropriate for your game. Let's assume here that the range is specified in hexes.

Referring to Figure 10-15 and going from left to right, these membership functions represent the fuzzy sets Tiny, Small, Moderate, and Large. With these fuzzy sets in hand, we're ready to perform some calculations.

Let's assume that during a given cycle through the game loop this fuzzy system is called upon to assess the threat posed by an enemy force eight units strong at a range of 25 hexes. So, now we need to fuzzify these crisp input values, determining the degree to which these variables fall within each predefined fuzzy set. Example 10-1 shows the code for this step.

Example 10-6. Fuzzification of range and force size variables


mClose      = FuzzyTriangle(25, -30, 0, 30);

mMedium     = FuzzyTrapezoid(25, 10, 30, 50, 70);

mFar        = FuzzyGrade(25, 50, 70);

mTiny       = FuzzyTriangle(8, -10, 0, 10);

mSmall      = FuzzyTrapezoid(8, 2.5, 10, 15, 20);

mModerate   = FuzzyTrapezoid(8, 15, 20, 25, 30);

mLarge      = FuzzyGrade(8, 25, 30);

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

In this chapter we're going to study rule-based AI systems. Rule-based AI systems are probably the most widely used AI systems for both real-world and game AI applications. In their simplest form, rule-based systems consist of a set of if-then style rules that are used to make inferences or action decisions. Technically, we've already looked at one form of rule-based system in Chapter 9 on finite state machines. There we used rules to handle state transitions. We also looked at another type of rule-based system in the previous chapter on fuzzy logic, Chapter 10.

In this chapter, we're going to look specifically at rule-based systems that commonly are used in so-called expert systems. Examples of real-world, rule-based expert systems include medical diagnosis, fraud protection, and engineering fault analysis. One advantage of rule-based systems is that they mimic the way people tend to think and reason given a set of known facts and their knowledge about the particular problem domain. Another advantage of this sort of rule-based system is that it is fairly easy to program and manage because the knowledge encoded in the rules is modular and rules can be coded in any order. This gives some flexibility both when coding the system and modifying the system at a later time. These advantages hopefully will become clearer to you as we move through the material in this chapter. Before we get into the details, though, let's discuss a couple of game examples that can use rule-based systems.

Imagine you're writing a real-time strategy simulation game involving the typical technology tree, whereby players must train peasants, build facilities, and harvest resources. An illustrative technology tree is shown in Figure 11-1.

Figure 11-1: Example technology tree

What we aim to do here is enable the computer opponent to keep track of the player's current state of technology so that the computer opponent can plan and deploy offensive and defensive resources accordingly. Now, you could cheat and give the computer opponent perfect knowledge of the player's state of technology. However, it would be fair and more realistic to have the computer gain knowledge and make inferences on the state of the player's technology in much the same way that the player will have to so that she can assess the computer opponent's state of technology. Both player and computer will have to send out scouts to collect information and then make inferences given the information as it is received. We can achieve this using a fairly simple rule-based system, as you'll see in this chapter.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Rule-based systems have two main components: the working memory and the rules memory. The working memory stores known facts and assertions made by the rules. The rules memory, or rules, for short, contains if-then style rules that operate over the facts stored in working memory. As rules are triggered, or fired in rule-based system lingo, they can trigger some action or state change, such as in a finite state machine, or they can modify the contents of the working memory by adding new information called assertions.

Example 11-1 shows how the working memory for a real-time, strategy-game technology tree might look.

Example 11-1. Example working memory


enum TMemoryValue{Yes, No, Maybe, Unknown};

TMemoryValue    Peasants;

TMemoryValue    Woodcutter;

TMemoryValue    Stonemason;

TMemoryValue    Blacksmith;

TMemoryValue    Barracks;

TMemoryValue    Fletcher;

TMemoryValue    WoodWalls;

TMemoryValue    StoneWalls;

TMemoryValue    Cavalry;

TMemoryValue    FootSoldier;

TMemoryValue    Spearman;

TMemoryValue    Archer;

TMemoryValue    Temple;

TMemoryValue    Priest;

TMemoryValue    Crossbowman;

TMemoryValue    Longbowman;

For this example, we made each element in working memory a TMemoryValue type that can take on any one of four values: Yes, No, Maybe, or Unknown. The idea here is to keep track of the computer opponent's current perception of the state of technology of the player opponent. A value of Yes implies that the player has the particular technology, whereas a value of No implies that she does not. If the player meets all the criteria to gain or posses a certain technology, but the state has yet to be confirmed by a scout, the value of Maybe is used. If the computer knows nothing about a particular technology capability for the player, Unknown is used.

The computer can gather facts on the player's current state of technology by sending out scouts and making observations. For example, if the computer sends out a scout and sees that the player has built a temple,

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

In this example, we aim to predict a human opponent's next strike in a martial arts fighting game. The basic assumption is that the player will try to use combinations of strikes to find the most effective combination. These combinations can be something such as low kick, low kick, high kick; or punch, punch, power kick; and so on. We want the computer opponent to somehow learn to anticipate which strike the player will throw next given the most recently thrown strikes and some history of the player's strike patterns. If the computer can anticipate the next strike, it can throw an appropriate counter strike, or block, or take evasive action such as side-stepping or back-stepping. This will add a higher level of realism to the combat simulation and present new challenges for the player.

To achieve this, we're going to implement a rule-based system with a learning capability. We will achieve this learning by weighting each rule to reinforce some while suppressing others. In Chapter 13 we'll look at an alternative approach to this problem whereby instead of rules, we'll use conditional probabilities to help predict the next strike.

To keep this example manageable for discussion purposes, we're going to simplify things a bit. We'll assume that the player's strikes can be classified as punch, low kick, or high kick. And we're going to track three-strike combinations. Even with these simplifications we still end up with 27 rules to capture all possible three-strike combinations of punch, low kick, and high kick. We'll look at the rules in a moment, but first let's take a look at the structures and classes we need to implement the working memory and rules memory.

Example 11-6 shows how the working memory is implemented.

Example 11-6. Working memory


enum TStrikes {Punch, LowKick, HighKick, Unknown};

struct TWorkingMemory {

        TStrikes        strikeA; // previous, previous strike (data)

        TStrikes        strikeB; // previous strike (data)

        TStrikes        strikeC; // next, predicted, strike (assertion)

        // note: can add additional elements here for things such as which counter

to throw, etc....

};

TWorkingMemory  WorkingMemory;  // global working memory variable

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

We've only scratched the surface of rule-based systems in this chapter. Although we covered all the fundamental concepts and showed how effective rule-based systems are, other aspects to rule-based systems are worthwhile investigating if you plan to implement them for large-scale systems.

Optimization is one area that deserves attention. For small rule sets, forward chaining does not take much processing time; however, for larger sets of rules where many rules can match a given set of facts, it's wise to optimize the conflict resolution phase. The most common algorithm for this is the so-called Rete algorithm. (Check out the article “Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem,” by C. L. Forgy, Artificial Intelligence, 1982.) Most textbooks on rule-based, or expert, systems cover the Rete algorithm.

As you saw with our fighting example, you don't have to use if-then statements in a rule-based system. You don't even have to use the sort of enumerated types or other types, such as integers, Booleans, and so on. You can use strings to represent facts in working memory and string matching routines to determine if the antecedents of a rule (also, strings) match facts stored in working memory. This approach opens the door to scripting rules outside of the compiled program, which paves the way for designers to script AI rules. Indeed, developers have been using scripting languages, such as the well-known Prolog, Lisp, and CLIPS languages, for scripting rule-based systems for decades now. (There's even a relatively new Java-based language called JESS.) Another advantage to using a scripting language to implement rule-based systems is that it's easy to change, delete, or expand upon the rules without having to modify the compiled game code.

Instead of using a third-party scripting language, you can write your own; however, caution is in order here. Writing a scripted rule system to handle facts that can take on a range of values, along with rules with compound antecedents and consequents that might even trigger other events, is far more complicated than writing a rule system with only Boolean facts and simple rule structures. If you'd like to see how you might go about such a task, check out Chapter 8 of

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Developers use probability in games for such things as hit probabilities, damage probabilities, and personality (e.g., propensity to attack, run, etc.). Games use probabilities to add a little uncertainty. In this chapter, we review elementary principles of probability and discuss how you can apply these basic principles to give the game AI some level of unpredictability. A further aim of this chapter is to serve as a primer for the next chapter, which covers decisions under uncertainty and Bayesian analysis.

Bayesian analysis for decision making under uncertainty is fundamentally tied to probability. Genetic algorithms also use probability to some extent—for example, to determine mutation rates. Even neural networks can be coupled with probabilistic methods. We cover these rather involved methods to various extents later in this book.

Because the examples we discuss rely heavily on generating random numbers, let's look at some code to generate random numbers. The standard C function to generate a random number is rand(), which generates a random integer in the range from 0 to RAND_MAX. Typically RAND_MAX is set to 32727. To get a random integer between 0 and 99, use rand() % 100. Similarly, to get a random number between 0 and any integer N-1, use rand() % N. Don't forget to seed the random number generator once at the start of your program by calling srand (seed). Note that srand takes a single unsigned int parameter as the random seed with which to initialize the random number generator.

In a very simple example, say you decide to program a little randomness to unit movement in your game. In this case, you can say the unit, when confronted, will move left with a 25% probability or will move right with a 25% probability or will back up with a 50% probability. Given these probabilities, you need only generate a random number between 0 and 99 and perform a few tests to determine in which direction to move the unit. To perform these tests, we'll assign the range 0 to 24 as the possible range of values for the move-left event. Similarly, we'll assign the range of values 75 to 99 as the possible range of values for the move-right event. Any other value between 25 and 74 (inclusive) indicates the backup event. Once a random number is selected, we need only test within which range it falls and then make the appropriate move. Admittedly, this is a very simple example, and one can argue that this is not intelligent movement; however, developers commonly use this technique to present some uncertainty to the player, making it more difficult to predict where the unit will move when confronted.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Bayesian analysis for decision making under uncertainty is fundamentally tied to probability. Genetic algorithms also use probability to some extent—for example, to determine mutation rates. Even neural networks can be coupled with probabilistic methods. We cover these rather involved methods to various extents later in this book.

Because the examples we discuss rely heavily on generating random numbers, let's look at some code to generate random numbers. The standard C function to generate a random number is rand(), which generates a random integer in the range from 0 to RAND_MAX. Typically RAND_MAX is set to 32727. To get a random integer between 0 and 99, use rand() % 100. Similarly, to get a random number between 0 and any integer N-1, use rand() % N. Don't forget to seed the random number generator once at the start of your program by calling srand (seed). Note that srand takes a single unsigned int parameter as the random seed with which to initialize the random number generator.

In a very simple example, say you decide to program a little randomness to unit movement in your game. In this case, you can say the unit, when confronted, will move left with a 25% probability or will move right with a 25% probability or will back up with a 50% probability. Given these probabilities, you need only generate a random number between 0 and 99 and perform a few tests to determine in which direction to move the unit. To perform these tests, we'll assign the range 0 to 24 as the possible range of values for the move-left event. Similarly, we'll assign the range of values 75 to 99 as the possible range of values for the move-right event. Any other value between 25 and 74 (inclusive) indicates the backup event. Once a random number is selected, we need only test within which range it falls and then make the appropriate move. Admittedly, this is a very simple example, and one can argue that this is not intelligent movement; however, developers commonly use this technique to present some uncertainty to the player, making it more difficult to predict where the unit will move when confronted.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The question posed here—what is probability?—is deceptively simple to answer in that there's no single definition of probability. One can interpret probability in several different ways, depending on the situation being considered and who's doing the considering. In the following sections, we consider three common interpretations of probability, all of which have a place in games in some form or another. We keep these discussions general in nature to keep them easy to understand.

Classical probability is an interpretation of probability that refers to events and possibilities, or possible outcomes. Given an event, E, which can occur in n ways out of a total of N possible outcomes, the probability, p, of occurrence of the event is:

Here, P(E) is the probability of event E, which is equal to the number of ways E occurs out of N possible ways. P(E) usually is called the probability of success of the event. The probability of failure of the event is 1-P(E). In summary:

Note that probabilities range in value from 0 to 1 and the sum of the probabilities of success and failure, p _s + p _f, must equal 1.

Let's consider a simple example. Say you roll a six-sided die; the probability that a four will show up is 1/6 because there's only one way in which a four can show up out of six possible outcomes in a single roll. In this example, the event, E, is the event that a four will show up. For the roll of a single die, a four can show up in only one way; therefore, n = 1. The total number of possible outcomes, N, is six in this case; therefore, P(E = 4) = 1/6. Clearly, in this case the probability of any given number showing up is 1/6 because each number can show up in only one possible way out of six ways.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Formal probability theory includes several rules that govern how probabilities are calculated. We'll go over these rules here to lay some groundwork for the next chapter. Although we've already discussed a few of these rules, we'll restate them again here for completeness. In the discussion that follows, we state the rules in general terms and don't provide specific examples. We will, however, see these rules in action in the next chapter. If you're interested in seeing specific examples of each rule, you can refer to any introductory-level book on probability.

This rule states the probability of an event, P(A), must be a real number between 0 and 1, inclusive. This rule serves to constrain the range of values assigned to probabilities. On one end of the scale we can't have a negative probability, while on the other end the probability of an event can't be greater than 1, which implies absolute certainty that the event will occur.

As sort of an extension of rule 1, if S represents the entire sample space for the event, the probability of S equals 1. This says that because the sample space includes all possible outcomes, there is a 100% probability that one of the outcomes therein will occur. Here, it helps to visualize the sample space and events using Venn diagrams. Figure 12-3 illustrates a Venn diagram for the sample space S and events A and B within that sample space.

Figure 12-3: Venn diagram

The dots represent samples taken within the space, and the relative sizes of the circles for A and B indicate their relative probabilities—more specifically, their areas indicate their probabilities.

If the probability that an event, A, will occur is P(A) and the event that A will not occur is designated A', the probability of the event not occurring, P(A'), is 1- P(A). This rule simply states that an event either occurs or does not occur and the probability of this event either occurring or not occurring is 1—that is, we can say with certainty the event either will occur or will not occur. Figure 12-4 illustrates events

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

When events are not independent, they are said to be conditional. For example, if you arrive home one day to find your lawn wet, what is the probability that it rained while you were at work? It is possible that someone turned on your sprinkler system while you were at work, so the outcome of your grass being wet is conditional upon whether it rained or whether someone turned on your sprinkler. You can best solve this sort of scenario using Bayesian analysis, which we cover in the next chapter. But as you'll see in a moment, Bayesian analysis is grounded in conditional probability.

In general, if event A depends on whether event B occurred, we can't use the formula shown earlier in rule 6 for independent events. Given these two dependent events, we denote the probability of A occurring given that B has occurred as P(A|B). Likewise, the probability of B occurring given that A has occurred is denoted as P(B|A). Note that P(A|B) is not necessarily equal to P(B|A).

To find the compound probability of both A and B occurring, we use the following formula:

This formula states that the probability of both dependant events A and B occurring at the same time is equal to the probability of event A occurring times the probability of event B occurring given that event A has occurred.

We can extend this to three dependent events, A, B, and C, as follows:

This formula states that the probability of events A, B, and C all occurring at once is equal to the probability of event A occurring times the probability of event B occurring given that A has occurred times the probability of event C occurring given that both events A and B have occurred.

Often we are more interested in the probability of an event given that some other condition or event has occurred. Therefore, we'll often write:

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

This chapter introduces Bayesian inference and Bayesian networks and shows how you can use these techniques in games. Specifically, we'll show you how to use these techniques to enable nonplayer characters (NPCs) to make decisions when the states of the game world are uncertain. We'll also show you how simple Bayesian models enable your computer-controlled characters to adapt to changing situations. We'll make heavy use of probability, so if that subject is not fresh in your mind, you might want to read Chapter 12 first and then come back to this chapter.

Before getting into the details of Bayesian networks, let's discuss a hypothetical example. Suppose you're writing a role-playing game in which you enable players to store valuables in chests located around the game world. Players can use these chests to store whatever they want, but they run the risk of NPCs looting the chests. To deter looting, players can trap the chests if they have the skill and materials to set such traps. Now, as a game developer, you're faced with the issue of how to code NPC thieves for them to decide whether to open a given chest that they discover.

One option is to have NPCs always attempt to open any given chest. Although simple to implement, this option is not so interesting and has some undesirable consequences. First, having the NPCs always open the chest defeats the purpose of players trapping chests as a deterrent. Second, if players catch on that NPCs always will attempt to open a chest no matter what, they might try to exploit this fact by trapping empty chests for the sole purpose of weakening or even killing NPCs without having to engage them in direct combat.

Your other option is to cheat and give NPCs absolute knowledge that any given chest is trapped (or not) and have them avoid trapped chests. Although this might render traps adequate deterrents, it can be viewed as unfair. Further, there's no variety, which can get boring after a while.

A potentially better alternative is to give NPCs some knowledge, though not perfect, and to enable them to reason given that knowledge. Further, if we enable NPCs to have some sort of memory, they potentially can learn or adapt, thus avoiding such exploits as the trapped empty chest we discussed a moment ago. We'll take a closer look at this example later in this chapter. When we do, we'll use probabilities and statistical data collected in-game as NPC memory and Bayesian models as the inference or decision-making mechanism for NPCs.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Bayesian networks are graphs that compactly represent the relationship between random variables for a given problem. These graphs aid in performing reasoning or decision making in the face of uncertainty. Such reasoning relies heavily on Bayes' rule, which we discussed in Chapter 12. In this chapter, we use simple Bayesian networks to model specific game scenarios that require NPCs to make decisions given uncertain information about the game world. Before looking at some specific examples, let's go over the details of Bayesian networks.

Bayesian networks consist of nodes representing random variables and arcs or links representing the causal relationship between variables. Figure 13-1 shows an example Bayesian network. Imagine a game in which an NPC can encounter a chest that can be locked or unlocked. Whether it is locked depends on whether it contains treasure or whether it is trapped.

Figure 13-1: Example Bayesian network

In this example, the nodes labeled T, Tr, and L represent random variables (often referred to as events in the probabilistic sense). The arrows connecting each node represent causal relationships. You can think of nodes at the tail of the arrows as parents and nodes at the head of the arrows as children. Here, parents cause children. For example, Figure 13-1 shows that Locked is caused by Trapped or Treasure or both Trapped and Treasure. You should be aware that this causal relationship is probabilistic and not certain. For example, the chest being Trapped does not necessarily always cause the chest to be Locked. There's a certain probability that Trapped might cause Locked, but it's possible that Trapped might not cause Locked.

You measure the strength of the connections between events in terms of probabilities. Each node has an associated conditional probability table that gives the probability of any outcome of the child event given all possible combinations of outcomes of its parents. For our purposes, we're going to consider discrete events only. What we mean here is that any event, any variable, can take on any one of a set of discrete values. These values are assumed to be mutually exclusive and exhaustive. For example,

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Let's say you're writing a game in which NPCs can loot chests potentially filled with players' treasure and other valuables. Players can put their valuables in these chests for storage and they have the option of trapping the chests (if they have the skill) along with the option of locking the chests. NPCs can attempt to loot such chests as they find them. An NPC can observe the chest and determine whether it is locked, but he can't make a direct observation as to whether any given chest is trapped. The NPC must decide whether to attempt to loot the chest. If successful, he keeps the loot. If the chest is trapped, he incurs damage, which could kill him. We'll use a simple Bayesian network along with some fuzzy rules to make the decision for the NPC.

The Bayesian network for this is among the simplest possible. The network is a two-node chain, as illustrated in Figure 13-3.

Figure 13-3: Two-node chain

Each event, Trapped and Locked, can take on one of two discrete states: true or false. Therefore, we have the following probability tables, shown in Tables 13-2 and 13-3, associated with each event node.

Table 13.2: Trapped probabilities
P(Trapped)
True	False
p_T	(1-p_T)

Table 13.3: Locked conditional probabilities
	P(Locked \| Trapped)

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

In this next example, we're going to build on the simple Bayesian network we used in the previous example. Specifically, we want to allow the NPC to consider the likelihood of a chest containing treasure in addition to the likelihood of it being trapped before deciding whether to open it. To this end, let's add a new event node to the network from the previous problem to yield a three-node chain. The new event node is the Treasure event—that is, Treasure is TRUE if the chest contains treasure and Treasure is FALSE if it does not. Figure 13-6 shows the new network.

Figure 13-6: Three-node chain

In this case, we're assuming that whether a chest is locked is an indication of the state of the chest being trapped and the state of the chest being trapped is an indication of whether the chest contains treasure.

Each event—Treasure, Trapped, and Locked—can take on one of two discrete states: true or false. Therefore, we have the following probability tables, Tables 13-4, 13-5 and 13-6, associated with each event node.

Table 13.4: Treasure probabilities
P(Treasure)
True	False
p_Tr	(1-p_Tr)

Table 13.5: Trapped conditional probabilities
	P(Trapped \| Treasure)
Treasure	True

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

For this next example, let's assume you're writing a war simulation in which the player can attack the computer-controlled army by land, by air, or by land and air. Our goal here is to estimate the chances of the player winning a battle given how he chooses to attack. We then can use the probabilities of the player winning to determine what sort of targets and defense should be given higher priority by the computer-controlled army. For example, say that after every game played you have the computer keep track of who won, the player or computer, along with how the player attacked—that is, by air, land, or both air and land. You then can keep a running count of these statistics to determine the conditional probability of the player winning given his attack mode. Suppose your game finds that the player is most likely to win if he attacks by air. Perhaps he found a weakness in the computer's air defenses or has come up with some other winning tactic. If this is the case, it would be wise for the computer to make construction of air defenses a higher priority. Further, the computer might give enemy aircraft production facilities higher target priority. Such an approach would allow the computer to adjust its defensive and offensive strategies as it learns from past battles.

The Bayesian network for this simple example looks like that shown in Figure 13-8.

Figure 13-8: Attack mode network

Notice that we have two causes for the player-winning result: air and land attacks. We assume these events are not mutually exclusive—that is, the player can make a land attack, or an air attack, or both. Each event node can take on one of two values: true or false. For example, Air Attack could be true or false,Land Attack could be true or false, and so on.

If instead we allowed only a land or air attack but not both, the network would look like that shown in Figure 13-9.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

For our final example we're going to assume we're writing a fighting game and we want to try to predict the next strike the player will throw. This way, we can have the computer-controlled opponents try to anticipate the strike and defend or counter accordingly. To keep things simple, we're going to assume the player can throw one of three types of strikes: punch, low kick, or high kick. Further, we're going to keep track of three-strike combinations. For every strike thrown we're going to calculate a probability for that strike given the previous two strikes. This will enable us to capture three-strike combinations. You easily can keep track of more, but you will incur higher memory and calculation costs because you'll end up with larger conditional probability tables.

The Bayesian network we're going to use for this example is shown in Figure 13-10.

Figure 13-10: Strike network

In this model, we call the first strike in the combination event A, the second strike event B, and the third strike event C. We assume that the second strike thrown, event B, in any combination is dependent on the first strike thrown, event A. Further, we assume that the third strike thrown, event C, is dependant on both the first and second strikes thrown, events A and B. Combinations can be anything—punch, punch, high kick; or low kick, low kick, high kick; and so on.

Ordinarily we would need to calculate probabilities for A and conditional probabilities for B given A, and conditional probabilities for C given A and B. However, in this example we're always going to observe A and B rendering their prior probabilities irrelevant. Therefore, we need only calculate conditional probabilities for C given every combination of A and B. Because three states exist for each strike event A and B, we'll have to track nine possible combinations of A and B.

We'll again take a frequency approach to determining these conditional probabilities. After every strike thrown by the player, we'll increment a counter for that strike given the two prior strikes thrown. We'll end up with a conditional probability table that looks like the one shown in Table 13-10.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Hopefully we've achieved our objective in this chapter of introducing Bayesian techniques and showing you how you can use simple Bayesian models in game AI for making decisions under uncertainty and for achieving some level of adaptation using probabilities. We've really only scratched the surface of these powerful methods and a wealth of additional information is available to you should you decide to learn more about these techniques. To set you on your way, we've compiled a short list of references that we find to be very useful. They are as follows:

Bayesian Inference and Decision, Second Edition by Robert Winkler (Probabilistic Publishing)
Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference by Judea Pearl (Morgan Kaufmann Publishers, Inc.)
Bayesian Artificial Intelligence by Kevin Korb and Ann Nicholson (Chapman & Hall/CRC)

The first reference shown here is particularly exceptional in that it covers probability, Bayesian inference, and decision making under uncertainty thoroughly and in plain English. If you decide to pursue complex Bayesian models that are not easily solved using simple calculations, you'll definitely want to check out the second reference, as it presents methods for solving more complicated Bayesian networks for general inference.

Numerous Bayesian resources also are available on the Internet. Here are some links to resources that we find useful:

http://bndev.sourceforge.net/
http://www.niedermayer.ca/papers/bayesian/
http://www.cs.ualberta.ca/~greiner/bn.html
http://www.research.microsoft.com/research/dtg/

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Our brains are composed of billions of neurons, each one connected to thousands of other neurons to form a complex network of extraordinary processing power. Artificial neural networks, hereinafter referred to simply as neural networks or networks, attempt to mimic our brain's processing capability, albeit on a far smaller scale.

Information, so to speak, is transmitted from one neuron to another via the axon and dendrites. The axon carries the voltage potential, or action potential, from an activated neuron to other connected neurons. The action potential is picked up from receptors in the dendrites. The synaptic gap is where chemical reactions take place, either to excite or inhibit the action potential input to the given neuron. Figure 14-1 illustrates a neuron.

Figure 14-1: Neuron

The adult human brain contains about 10₁₁ neurons and each neuron receives synaptic input from about 10₄ other neurons. If the combined effect of all these inputs is of sufficient strength, the neuron will fire, transmitting its action potential to other neurons.

The artificial networks we use in games are quite simple by comparison. For many applications artificial neural networks are composed of only a handful, a dozen or so, neurons. This is far simpler than our brains. Some specific applications use networks composed of perhaps thousands of neurons, yet even these are simple in comparison to our brains. At this time we can't hope to approach the processing power of the human brain using our artificial networks; however, for specific problems our simple networks can be quite powerful.

This is the biological metaphor for neural networks. Sometimes it's helpful to think of neural networks in a less biological sense. Specifically, you can think of a neural network as a mathematical function approximator. Input to the network represents independent variables, while output represents the dependant variable(s). The network itself is a function giving one unique set of output for the given input. The function in this case is difficult to write in equation form and fortunately we don't need to do so. Further, the function is highly nonlinear. We'll come back to this way of thinking a little later.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

Neural networks often are used as neural controllers for robotics applications. In these cases, the robot's sensory system provides relevant inputs to the neural controller, and the neural controller's output, which can consist of one or more output nodes, sends the proper responses to the robot's motor control system. For example, a neural controller for a robot tank might take three inputs, each indicating whether an obstacle is sensed in front of or to either side of the robot. (The range to each sensed obstacle also can be input.) The neural controller can have two outputs that control the direction of motion of its left and right tracks. One output node can set the left track to move forward or backward, while the other can set the right track to move forward or backward. The combination of the resulting outputs has the robot either move forward, move backward, turn left, or turn right. The neural network might look something such as that illustrated in Figure 14-2.

Figure 14-2: Example robot control neural network

Very similar situations arise in games. You can, in fact, have a computer-controlled, half-track mechanized unit in your game. Or perhaps you want to use a neural network to handle the flight controls for a spaceship or aircraft. In each case, you'll have one or more input neurons and one or more output neurons that will control the unit's thrust, wheels, tracks, or whatever means of locomotion you're simulating.

As another example, say you're writing a strategy simulation-type game in which the player has to build technology and train units to fend off or attack the computer-controlled base. Let's say you decide to use a neural network to give the computer-controlled army some means of predicting the type of threat presented by the player at any given time during gameplay. One possible neural network is illustrated in Figure 14-3.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

In this section we're going to dissect a three-layer feed-forward neural network, looking at each of its components to see what they do, why they are important, and how they work. The aim here is to clearly and concisely take the mystery out of neural networks. We'll take a rather practical approach to this task and leave some of the more academic aspects to other books on the subject. We will give references to several such books throughout this chapter.

We focus on three-layer feed-forward networks in this chapter. Figure 14-5 illustrates the basic structure of such a network.

Figure 14-5: Three-layer feed-forward neural network

A three-layer network consists of one input layer, one hidden layer, and one output layer. There's no restriction on the number of neurons within each layer. Every neuron from the input layer is connected to every neuron in the hidden layer. Further, every neuron in the hidden layer is connected to every neuron in the output layer. Also, every neuron, with the exception of the input layer, has an additional input called the bias. The numbers shown in Figure 14-5 serve to identify each node in the three layers. We'll use this numbering system later when we write the formulas for calculating the value of each neuron.

Calculating the output value(s) for a network starts with some input provided to each input neuron. Then these inputs are weighted and passed along to the hidden-layer neurons. This process repeats, going from the hidden layer to the output layer, where the output of the hidden-layer neurons serves as input to the output layer. This process of going from input to hidden to output layer is the feed-forward process. We'll look at each component of this type of network in more detail in the following sections.

Inputs to a neural network obviously are very important; without them there's nothing for the neural network to process. Clearly we need them, but what should you choose as inputs? How many do you need? And what form should they take?

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

So far, we've repeatedly mentioned training a neural network without actually giving you the details as to how to do this. We'll tackle that now in this section.

The aim of training is to find the values for the weights that connect all the neurons such that the input data generates the desired output values. As you might expect, there's more to training than just picking some weight values. Essentially, training a neural network is an optimization process in which you are trying to find optimal weights that will allow the network to produce the right output.

Training can fall under two categories: supervised training and unsupervised training. Covering all or even some of the popular training approaches is well beyond a single chapter, so we'll focus on one of the most commonly used supervised training methods: back-propagation.

Again, the aim of training is to find the values for the weights that connect all the neurons such that the input data generates the desired output values. To do this, you need a training set, which consists of both input data and the desired output values corresponding to that input. The next step is to iteratively, using any of a number of techniques, find a set of weights for the entire network that causes the network to produce output matching the desired output for each set of data in the training set. Once you do this, you can put the network to work and present it with new data, not included in the training set, to produce output that is reasonable.

Because training is an optimization process, we need some measure of merit to optimize. In the case of back-propagation, we use a measure of error and try to minimize the error. Given some input and the generated output, we need to compare the generated output with the known, desired output and quantify how well the results match—i.e., calculate the error. Many error measures are available for you to use, and we'll use one of the most common ones here: the mean square error, which is simply the average of the square of the differences between the calculated output and the desired output.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

At last it's time to look at some actual source code that implements a three-layer feed-forward neural network. The following sections present two C++ classes that implement such a network. Later in this chapter, we'll look at an example implementation of these classes. Feel free to skip to the section entitled “Chasing and Evading with Brains” if you prefer to see how the neural network is used before looking at its internal details.

We need to implement two classes in the three-layer feed-forward neural network. The first class represents a generic layer. You can use it for input, hidden, and output layers. The second class represents the entire neural network composed of three layers. The following sections present the complete source code for each class.

The class NeuralNetworkLayer implements a generic layer in a multilayer feed-forward network. It is responsible for handling the neurons contained within the layer. The tasks it performs include allocating and freeing memory to store neuron values, errors, and weights; initializing weights; calculating neuron values; and adjusting weights. Example 14-1 shows the header for this class.

Example 14-1. NeuralNetworkLayer class


class NeuralNetworkLayer

{

public:

     int               NumberOfNodes;

     int               NumberOfChildNodes;

     int               NumberOfParentNodes;

     double**          Weights;

     double**          WeightChanges;

     double*           NeuronValues;

     double*           DesiredValues;

     double*           Errors;

     double*           BiasWeights;

     double*           BiasValues;

     double            LearningRate;

     bool              LinearOutput;

     bool              UseMomentum;

     double            MomentumFactor;

     NeuralNetworkLayer*     ParentLayer;

     NeuralNetworkLayer*     ChildLayer;

     NeuralNetworkLayer();

     void     Initialize(int NumNodes,

                            NeuralNetworkLayer* parent,

                            NeuralNetworkLayer* child);

     void     CleanUp(void);

     void     RandomizeWeights(void);

     void     CalculateErrors(void);

     void     AdjustWeights(void);

     void     CalculateNeuronValues(void);

};

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The example we're going to discuss in this section is a modification of the flocking and chasing example we discussed in Chapter 4. In that chapter we discussed an example in which a flock of units chased the player-controlled unit. In this modified example, the computer-controlled units will use a neural network to decide whether to chase the player, evade him, or flock with other computer-controlled units. This example is an idealization or approximation of a game scenario in which you have creatures or units within the game that can engage the player in battle. Instead of having the creatures always attack the player and instead of using a finite state machine “brain,” you want to use a neural network to not only make decisions for the creatures, but also to adapt their behavior given their experience with attacking the player.

Here's how our simple example will work. About 20 computer-controlled units will move around the screen. They will attack the player, run from the player, or flock with other computer-controlled units. All of these behaviors will be handled using the deterministic algorithms we presented in earlier chapters; however, here the decision as to what behavior to perform is up to the neural network. The player can move around the screen as he wishes. When the player and computer-controlled units come within a specified radius of one another, we're going to assume they are engaged in combat. We won't actually simulate combat here and will instead use a rudimentary system whereby the computer-controlled units will lose a certain number of hit points every turn through the game loop when in combat range of the player. The player will lose a certain number of hit points proportional to the number of computer-controlled units within combat range. When a unit's hit points reach zero, he dies and is respawned automatically.

All computer-controlled units share an identical brain—the neural network. We're also going to have this brain evolve as the computer-controlled units gain experience with the player. We'll achieve this by implementing the back-propagation algorithm in the game itself so that we can adjust the network's weights in real time. We're assuming that the computer-controlled units evolve collectively.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

As we stated at the beginning of this chapter, the subject of neural networks is far too vast to treat in one chapter. Therefore, we've compiled a short list of pretty good references that you might find useful should you decide to pursue this subject further. The list is as follows:

Practical Neural Network Recipes in C++ (Academic Press)
Neural Networks for Pattern Recognition (Oxford University Press)
AI Application Programming (Charles River Media)

Many other books on neural networks also are available; however, the ones we list above proved very useful to us, especially the first one, Practical Neural Network Recipes in C++. This book provides a wealth of practical tips and advice on the programming and use of neural networks for a variety of applications.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

It is the game designer's job to create a challenging game environment for the player. In fact, a large part of game development involves balancing the game world. It needs to be challenging enough for the players, or the game will seem too easy and they will lose interest. On the other hand, if it's too difficult, the players will become frustrated. Sometimes players can discover loopholes, or exploits, with which they essentially can cheat. This can be a result of a game design issue that the developers simply overlooked. Another game design problem stems from the fact that the skill levels of different players can vary greatly. Creating a truly balanced and challenging game for players of different skill levels can be a daunting task. Fortunately, genetic algorithms can help.

In this chapter, we are not going to attempt to model a true genetic system. A true genetic model probably wouldn't be practical or beneficial in a real computer game. Instead, the system we are going to discuss is merely inspired by a biological genetic system. In some ways it will be similar, but we won't hesitate to bend the rules if it benefits the game design process.

In the real world, species constantly evolve in an attempt to better adapt to their environments. Those that are most fit continue to survive. Charles Darwin proposed this phenomenon in 1859 in his famous work entitled “On the Origin of Species.” Those that are most able to survive in their environments are able to pass on their traits to the next generation. The individual traits are encoded in chromosomes. In the next generation, these chromosomes are combined in a process called crossover. Crossover is a recombination of the chromosomes in the offspring. Figure 15-1 illustrates this process.

Figure 15-1: Crossover

In Figure 15-1 we used random letters to represent chromosomes. As you can see, each parent passes half of its genetic material on to the child. However, in the real world this crossover process might not be exact. Random mutations also can take place. This is illustrated in Figure 15-2.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

You can break down the implementation of genetic algorithms in games into four steps. Figure 15-3 illustrates this four-step process.

Figure 15-3: Evolutionary process

As Figure 15-3 shows, the first step involves creating the first generation. The entire population is seeded with a set of starting traits. Once the population starts interacting with its environment, we need a way to rank the individual members. This is the process of ranking fitness. This tells us which members of the population are the most successful. The process of ranking fitness aids us in the next step, which is selection. In the selection process we choose certain members of the population to create the next generation. We essentially use the most successful traits of the previous generation to create the next generation. The actual step of combining these traits to create a new, and hopefully fitter, generation is referred to as evolution. Genetic algorithms are essentially optimization processes in which we're trying to find the fittest set of traits—we're looking for the optimum solution to a specific problem.

Each individual in the first generation represents a possible solution to the problem at hand. One way to approach the creation of the first generation is to arrange the chromosomes randomly. In a game environment, however, randomly arranging chromosomes might not always be the best solution. If the game designer already knows which combinations of chromosomes are likely to produce a fit individual, a true random combination probably won't be necessary. However, it is still important to create an initial diverse population. If the individuals are too much alike, the genetic process will be less effective.

Encoding is the process of storing the chromosomes in a structure that can be stored in a computer. This, of course, can be any type of structure the programmer chooses to use. Genetic algorithms frequently use strings of bits, but arrays, lists, and trees also commonly are used.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

This first example shows how to apply a genetic algorithm to successive generations of flowers as they attempt to thrive in their environment. We define a series of hypothetical environmental conditions in which the flowers must grow. Each flower then contains genetic information that indicates its ideal growing environment. Flowers whose ideal growing environments most closely match the actual conditions grow the tallest. The tallest flowers will be considered the most fit and have their genetic information passed on to successive generations. This should result in a general increase in flower height as generations progress.

We start by defining the six hypothetical environmental conditions, which we consider to be the actual conditions of the flower world. These are shown in Example 15-1.

Example 15-1. Encoding


Class ai_World

{

public:

      int currentTemperature;

      int currentWater;

      int currentSunlight;

      int currentNutrient;

      int currentBeneficialInsect;

      int currentHarmfulInsect;

      ai_World();

      ~ai_World();

};

As Example 15-1 shows, the six conditions are currentTemperature, currentWater, currentSunlight, currentNutrient, currentBeneficialInsect, and currentHarmfulInsect.

Encoding is the process of storing the chromosomes in a structure that can be stored in a computer. This, of course, can be any type of structure of the programmer's choosing. Example 15-2 shows the structure that we use in the flower evolution example.

Example 15-2. Conditions


#define kMaxFlowers   11

Class ai_World

{

public:

      int temperature[kMaxFlowers];

      int water[kMaxFlowers];

      int sunlight[kMaxFlowers];

      int nutrient[kMaxFlowers];

      int beneficialInsect[kMaxFlowers];

      int harmfulInsect[kMaxFlowers];

      int currentTemperature;

      int currentWater;

      int currentSunlight;

      int currentNutrient;

      int currentBeneficialInsect;

      int currentHarmfulInsect;

      ai_World();

      ~ai_World();

};

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

In games, genetic algorithms are simply a method of finding an optimum solution to a problem. Of course, there are lots of problems to be solved in game AI, and not all of them are good candidates for a genetic algorithm. Pathfinding, for example, can be solved with a genetic algorithm, however it's usually a problem better suited to something such as the A∗ algorithm. Genetic algorithms work best when the elements of the problem are somewhat unpredictable. This allows the game AI to adapt to a situation the game designer might not have been able to predict. In game design, the most unpredictable element of the game environment is the player. To some degree, the game designer must be able to predict the player's behavior to create a challenging adversary. Unfortunately, it can be difficult to predict and account for every possible player behavior.

Genetic algorithms basically involve a trial-and-error approach. You essentially populate the game world with many possible solutions and then determine which solutions work the best. Of course, the solutions won't always be the same for every player. That's the beauty of genetic algorithms. The game AI will adapt to individual players.

Genetic algorithms are useful in any scenario in which a computer-controlled adversary must respond and change due to player behavior. For example, consider a hypothetical multiplayer role-playing game. In this game the players would be able to choose from many different types of character classes and abilities. This means the computer-controlled characters would have to be able to present a challenge to many types of player-controlled characters. A player could choose to play a warrior character that would fight mainly with brute force. Of course, with this class the player would be able to choose from a multitude of weapons. The player could attack with a sword, axe, or any number of other weapons. The fighter class also would be able to wear an assortment of armor. On the other hand, the player might choose a totally different class. A magical class would produce a totally different player behavior. The various combinations of class and weapon types would make it difficult for a game designer to create a single type of computer-controlled individual that would be a challenge to every type of player-controlled character. It could be even more complicated in a multiplayer game. In this type of game the computer will have to be a challenge to a group of diverse players working in combination. The number of possible combinations quickly would become more than a game designer could account for.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

As we stated earlier, many strategies are available for implementing crossover and mutation. Further, many other game problems besides the ones we've discussed could use genetic algorithms effectively. If you're interested in pursuing genetic algorithms further and would like alternative strategies and additional examples, we encourage you to check out the following references:

AI Application Programming (Charles River Media)
AI Techniques for Game Programming (Premier Press)
AI Game Programming Wisdom (Charles River Media)

Mat Buckland's book, AI Techniques for Game Programming, covers both genetic algorithms and neural networks and even shows how to use genetic algorithms to evolve, or train, neural networks. This is an interesting alternative to the back-propagation training method we discussed in Chapter 14.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

This appendix implements a class called Vector that encapsulates all of the vector operations that you need when writing 2D or 3D rigid body simulations. Although, Vector represents 3D vectors, you can easily reduce it to handle 2D vectors by eliminating all of the z-terms or simply constraining the z-terms to zero where appropriate in your implementation.

Vector Class

Magnitude

Vector Functions and Operators

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The Vector class is defined with three components, x, y, and z, along with several methods and operators that implement basic vector operations. The class has two constructors, one of which initializes the vector components to zero and the other of which initializes the vector components to those passed to the constructor.


       //	- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 

       // Vector Class and vector functions

       //	- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 

       class Vector {

       public:

	          float x;

	          float y;

	          float z;

	          Vector(void);

	          Vector(float xi, float yi, float zi);

	          float Magnitude(void);

	          void  Normalize(void);

	          void  Reverse(void);

	          Vector& operator+=(Vector u);

	          Vector& operator-=(Vector u);

	          Vector& operator*=(float s);

	          Vector& operator/=(float s);

	          Vector operator-(void);

       };

	

       // Constructor

       inline Vector::Vector(void)

       {

	            x = 0;

	            y = 0;

	            z = 0;

       }

       // Constructor

       inline Vector::Vector(float xi, float yi, float zi)

       {

	            x = xi;

	            y = yi;

	            z = zi;

       }

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The Magnitude method simply calculates the scalar magnitude of the vector according to the formula

This is for a zero-based vector in which the components are specified relative to the origin. The magnitude of a vector is equal to its length, as illustrated in Figure A-1.

Figure A-1: Vector Length (Magnitude)

Here's the code that calculates the vector magnitude for our Vector class:


        inline        float Vector::Magnitude(void)

        {

	              return (float) sqrt(x*x + y*y + z*z);

        }

Note that you can calculate the components of a vector if you know its length and direction angles. Direction angles are the angles between each coordinate axis and the vector, as shown in Figure A-2.

Figure A-2: Direction Angles

The components of the vector shown in this figure are as follows:

The cosines of the direction angles seen in these equations are known as direction cosines. The sum of the squares of the direction cosines is always equal to 1:

The Normalize method normalizes the vector, or converts it to a unit vector satisfying the following equation:

In other words, the length of the normalized vector is 1 unit. If v is a nonunit vector with components x, y, and z, then the unit vector u can be calculated from v as follows:

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsvorschau

The functions and overloaded operators that follow are useful in performing operations with two vectors, or with a vector and a scalar, where the vector is based on the Vector class.

This addition operator adds vector v to vector u according to the formula

Here's the code:


        inline   Vector operator+ (Vector u, Vector v)

        {

	            return Vector(u.x + v.x, u.y + v.y, u.z + v.z);

        }

This subtraction operator subtracts vector v from vector u according to the formula

Here's the code:


        inline   Vector operator-(Vector u, Vector v)

        {

            	 return Vector(u.x - v.x, u.y - v.y, u.z - v.z);

        }

This cross product operator takes the vector cross product between vectors u and v, u × v, and returns a vector perpendicular to both u and v according to the formula

The resulting vector is perpendicular to the plane that contains vectors u and v. The direction in which this resulting vector points can be determined by the righthand rule. If you place the two vectors, u and v, tail to tail as shown in Figure A-7 and curl your fingers (of your right hand) in the direction from u to v, your thumb will point in the direction of the resulting vector.

Figure A-7: Vector Cross Product

In this case the resulting vector points out of the page along the z-axis, since the vectors u and v lie in the plane formed by the x- and y-axes.

If two vectors are parallel, then their cross product will be zero. This is useful when you need to determine whether or not two vector are indeed parallel.

Ende der Inhaltsvorschau. Der weiterere Inhalt dieses Abschnitts ist hier nicht einsehbar.

Inhaltsverzeichnis

Themen

Buchreihen

Special Interest

International Sites