Exploring Types of Game AI

There are many different types of AI systems and even more specific algorithms that carry out those systems. Even when you limit AI to the world of games, there is still a wide range of information and options from which to choose when it comes to adding AI to a game of your own. Many different AI solutions are geared toward particular types of games ”with a plethora of different possibilities that can be applied in different situations.

What I'm getting at is that there is no way to just present a bunch of AI algorithms and tell you which one goes with which particular type of game. Rather, it makes more sense to give you the theoretical background on a few of the most important types of AI, and then let you figure out how they might apply to your particular gaming needs. Having said all that, I've broken game- related AI down into three fundamental types:

• Roaming AI

• Behavioral AI

• Strategic AI

Please understand that these three types of AI are in no way meant to encompass all the AI approaches used in games; they are simply the most common types to recognize and use. Feel free to do your own research and expand on these if you find AI to be an interesting topic worthy of further study.

Roaming AI

Roaming AI refers to AI that models the movement of game objects ”that is, the decisions game objects make that determine how they roam around a virtual game world. A good example of roaming AI is in shoot-em-up space games such as the classic arcade game Galaga, where aliens often tend to track and go after the player. Similarly, aliens that fly around in a predetermined pattern are also implemented using roaming AI. Basically, roaming AI is used whenever a computer-controlled object must make a decision to alter its current path ”either to achieve a desired result in the game or simply to conform to a particular movement pattern. In the Galaga example, the desired result is following a pattern while also attempting to collide with and damage the player's ship.

Implementing roaming AI is usually fairly simple; it typically involves altering an object's velocity or position (the alien) based on the position of another object (the player's ship). The roaming movement of the object can also be influenced by random or predetermined patterns. Three different types of roaming AI exist: chasing, evading , and patterned . The next few sections explore these types of roaming AI in more detail.

Chasing

Chasing is a type of roaming AI in which a game object tracks and goes after another game object or objects. Chasing is the approach used in many shoot-em-up games, where an alien chases after the player's ship. It is implemented by altering the alien's velocity or position based on the current position of the player's ship. Following is an example of a simple chasing algorithm involving an alien and a ship:

 if (iXAlien > iXShip)   iXAlien--; else if (iXAlien < iXShip)   iXAlien++; if (iYAlien > iYShip)   iYAlien--; else if (iYAlien < iYShip)   iYAlien++; 

As you can see, the XY position ( iXAlien and iYAlien ) of the alien is altered based on where the ship is located ( iXShip and iYShip ). The only potential problem with this code is that it could work too well; the alien will hone in on the player with no hesitation, basically giving the player no chance to dodge it. This might be what you want, but more than likely, you want the alien to fly around a little while it chases the player. You probably also want the chasing to be a little imperfect, giving the player at least some chance of out-maneuvering the alien. In other words, you want the alien to have a tendency to chase the player without going in for an all-out blitz.

One method of smoothing out the chasing algorithm is to throw a little randomness into the equation, like this:

 if ((rand() % 3) == 0) {   if (iXAlien > iXShip)     iXAlien--;   else if (iXAlien < iXShip)     iXAlien++; } if ((rand() % 3) == 0) {   if (iYAlien > iYShip)     iYAlien--;   else if (iYAlien < iYShip)     iYAlien++; } 

In this code, the alien has a one in three chance of tracking the player in each direction. Even with only a one in three chance, the alien will still tend to chase the player aggressively, while allowing the player a fighting chance at getting out of the way. You might think that a one in three chance doesn't sound all that effective, but keep in mind that the alien only alters its path to chase the player. A smart player will probably figure this out and change directions frequently.

If you aren't too fired up about the random approach to leveling off the chase, you probably need to look into patterned movement. But you're getting a little ahead of yourself; let's take a look at evading first.

Evading

Evading is the logical counterpart to chasing; it is another type of roaming AI in which a game object specifically tries to get away from another object or objects. Evading is implemented in a similar manner to chasing, as the following code shows:

 if (iXAlien > iXShip)   iXAlien++; else if (iXAlien < iXShip)   iXAlien--; if (iYAlien > iYShip)   iYAlien++; else if (iYAlien < iYShip)   iYAlien--; 

This code basically does the opposite of the code used by the chasing algorithm ”with the only differences being the unary operators ( ++ , -- ) used to change the alien's position so that it runs away, as opposed to chasing. Similar to chasing, evading can be softened using randomness or patterned movement. A good example of evading is the ghosts in the classic arcade game Pac Man, who run away from the player when you eat a power pellet. Of course, the Pac-Man ghosts also take advantage of chasing when you don't have the ability to eat them.

Another good example of using the evading algorithm would be a computer-controlled version of the player's ship in a space game with a computer player. If you think about it, the player is using the evading algorithm to dodge the aliens; it's just implemented by hitting keys rather than in a piece of computer-controlled code. If you want to provide a demo mode in a game like this where the computer plays itself, you would use an evading algorithm to control the player's ship. Hour 23, "Showing Off Your Game with Demo Mode," shows you exactly how to create a demo mode for your games.

Patterned Roaming

Patterned movement refers to a type of roaming AI that uses a predefined set of movements for a game object. Good examples of patterned movement are the aliens in the classic Galaga arcade game, which perform all kinds of neat aerobatics on their way down the screen. Patterns can include circles, figure eights, zigzags, or even more complex movements. An even simpler example of patterned movement is the Space Invaders game, where a herd of aliens slowly and methodically inch across and down the screen.

In truth, the aliens in Galaga use a combined approach of both patterned and chasing movement; although they certainly follow specific patterns, the aliens still make sure to come after the player whenever possible. Additionally, as the player moves into higher levels, the roaming AI starts favoring chasing over patterned movement in order to make the game harder. This is a really neat usage of combined roaming AI. This touches on the concept of behavioral AI, which you learn about in the next section.

Patterns are usually stored as an array of velocity or position offsets (or multipliers) that are applied to an object whenever patterned movement is required of it, like this:

 int iZigZag[2][2] = { {3, 2}, {-3, 2} }; iXAlien += iZigZag[iPatternStep][0]; iYAlien += iZigZag[iPatternStep][1]; 

This code shows how to implement a very simple vertical zigzag pattern. The integer array iZigZag contains pairs of XY offsets used to apply the pattern to the alien. The iPatternStep variable is an integer representing the current step in the pattern. When this pattern is applied, the alien moves in a vertical direction at a speed of 2 pixels per game cycle, while zigzagging back and forth horizontally at a speed of 3 pixels per game cycle.

Behavioral AI

Although the types of roaming AI strategies are pretty neat in their own right, a practical gaming scenario often requires a mixture of all three. Behavioral AI is another fundamental type of gaming AI that often uses a mixture of roaming AI algorithms to give game objects specific behaviors. Using the trusted alien example again, what if you want the alien to chase some times, evade other times, follow a pattern still other times, and maybe even act totally randomly every once in a while? Another good reason for using behavioral AI is to alter the difficulty of a game. For example, you could favor a chasing algorithm more than random or patterned movement to make aliens more aggressive in higher levels of a space game.

To implement behavioral AI, you would need to establish a set of behaviors for the alien. Giving game objects behaviors isn't too difficult, and usually involves establishing a ranking system for each type of behavior present in the system, and then applying it to each object. For example, in the alien system, you would have the following behaviors: chase, evade, fly in a pattern, and fly randomly. For each different type of alien, you would assign different percentages to the different behaviors, thereby giving them each different personalities. For example, an aggressive alien might have the following behavioral breakdown: chase 50% of the time, evade 10% of the time, fly in a pattern 30% of the time, and fly randomly 10% of the time. On the other hand, a more passive alien might act like this: chase 10% of the time, evade 50% of the time, fly in a pattern 20% of the time, and fly randomly 20% of the time.

This behavioral approach works amazingly well and yields surprising results considering how simple it is to implement. A typical implementation simply involves a switch statement or nested if-else statements to select a particular behavior. A sample implementation for the behavioral aggressive alien would look like this:

 int iBehavior = abs(rand() % 100); if (iBehavior < 50)   // chase else if (iBehavior < 60)   // evade else if (iBehavior < 90)   // fly in a pattern else   // fly randomly 

As you can see, creating and assigning behaviors is open to a wide range of creativity. One of the best sources of ideas for creating game object behaviors is the primal responses common in the animal world (and unfortunately all too often in the human world, too). As a matter of fact, a simple fight or flight behavioral system can work wonders when applied intelligently to a variety of game objects. Basically, just use your imagination as a guide and create as many unique behaviors as you can dream up.

Strategic AI

The final fundamental type of game AI I want to mention is strategic AI , which is basically any AI designed to play a game with a fixed set of well-defined rules. For example, a computer-controlled chess player would use strategic AI to determine each move based on trying to improve the chances of winning the game. Strategic AI tends to vary more based on the nature of the game simply because it is so tightly linked to the rules of the game. Even so, there are established and successful approaches to applying strategic AI to many general types of games, such as games played on a rectangular board with pieces. Checkers and chess immediately come to mind as fitting into this group , and likewise have a rich history of AI research devoted to them.

Strategic AI, especially for board games, typically involves some form of look-ahead approach to determining the best move to make. The look-ahead is usually used in conjunction with a fixed table of predetermined moves. For a look-ahead to make sense, however, there must be a method of looking at the board at any state and calculating a score. This is known as weighting , and is often the most difficult part of implementing strategic AI in a board game. As an example of how difficult weighting can be, watch a game of chess or checkers and try to figure out who is winning after every single move. Then go a step further and think about trying to calculate a numeric score for each player at each point in the game. Obviously, near the end of the game it gets easier, but early on it is very difficult to tell who is winning simply because there are so many different things that can happen. Attempting to quantify the state of the game in a numeric score is even more difficult.

Nevertheless, there are ways to successfully calculate a weighted score for strategic games. Using a look-head approach with scoring, a strategic AI algorithm can test, for every possible move for each player, multiple moves into the future and determine which move is the best. This move is often referred to as the "least worst" move rather than the best because the goal typically is to make the move that helps the other player the least rather than the other way around. Of course, the end result is basically the same, but it is an interesting way to look at a game, nevertheless. Even though look-ahead approaches to implementing strategic AI are useful in many cases, they can require a fair amount of processing if very much depth is required (in other words, if the computer player needs to be very smart).

To better understand strategic AI, consider the case of a computer Backgammon player. The computer player has to choose two or four moves from possibly several dozen , as well as decide whether to double or resign. A practical Backgammon program might assign weights to different combinations of positions and calculate the value of each position reachable from the current position and dice roll. A scoring system would then be used to evaluate the worth of each potential position, which gets back to the often difficult proposition of scoring, even in a game such as Backgammon, with simple rules. Now apply this scenario to a hundred-unit war game ”with every unit having unique characteristics, and the terrain and random factors complicating the issue still further. The optimal system of scoring simply cannot be determined in a reasonable amount of time, especially with the limited computing power of a workstation or PC.

The solution in these cases is to settle for a "good enough" move, rather than the "best" move. One of the best ways to develop the algorithm for finding the "good enough" move is to set up the computer to play both sides in a game, using a lot of variation between the algorithms and weights playing each side. Then sit back and let the two computer players battle it out and see which one wins the most. This approach typically involves a lot of tinkering and trial-and-error with the AI code, but it can result in very good computer players.