JavaScript EditorFree JavaScript Editor     Ajax Editor 



Main Page
  Previous Section Next Section

Deterministic AI Algorithms

Deterministic algorithms are behaviors that are predetermined or preprogrammed. For example, if you take a look at the AI for the polygon Asteroids demo introduced in Chapter 8, "Vector Rasterization and 2D Transformations" (shown in Figure 12.1), it's very simple.

Figure 12.1. The Asteroids AI.

graphics/12fig01.gif

The AI creates an asteroid and then sends it in a random direction with a random velocity. This is a type of intelligence as shown here:

asteroid_x += asteroid_x_velocity;
asteroid_y += asteroid_y_velocity;

The asteroids have one goal: to follow their course. That's it. The AI is simple—the asteroids don't process any outside input, make course changes, and so on. In a sense they're intelligent, but their intelligence is rather deterministic and predictable. This is the first kind of AI I want to look at—the simple, predictable, programmable kind. In this class of AI, there are a number of techniques that were born in the Pong/Pac-Man era.

Random Motion

Just one step above moving an object in a straight line or curve is moving an object or changing its properties randomly, as shown in Figure 12.2.

Figure 12.2. Random-motion AI.

graphics/12fig02.gif

For example, let's say you wanted to model an atom, fly, or something similar that doesn't have a lot of brains, but does have a fairly predictable behavior—it bounces around in an erratic way. Well, at least it looks that way.

For a starting AI model, you might try something like this to model a fly's brain:

fly_x_velocity = -8 + rand()%16;
fly_y_velocity = -8 + rand()%16;

Then you could move the fly around for a few cycles:

int fly_count = 0; // fly new thought counter

// fly in the same direction for 10 ticks of time
while(++fly_count < 10)
    {
    fly_x+=fly_x_velocity;
    fly_y+=fly+y_velocity;
    } // end while

// .. pick a new direction and loop

In this example, the fly would pick a random direction and velocity, move that way for a moment, and then pick another. That sounds like a fly to me! Of course, you might want to add even more randomness, such as changing how long the motion occurs instead of fixing it at 10 cycles. In addition, you might want to weigh certain directions more heavily than others. For example, you might want to lean toward westward directions to simulate the breeze or something.

In any case, I think you can see that it's possible to make something seem intelligent with very little code. As a working example, check out DEMO12_1.CPP|EXE (16-bit version, DEMO12_1_16B.CPP|EXE) on the CD. It's an example of the artificial fly in action.

Random motion is a very important part of the behavioral modeling of intelligent creatures. I live in Silicon Valley, and I can attest that the people who drive on the roads around here make random lane changes and even drive the wrong direction, which is pretty similar to the fly's brainless motion….

Tracking Algorithms

Although random motion can be totally unpredictable, it's rather boring because no matter what, it works the same way—that is, randomly. The next step up in the AI evolutionary ladder are algorithms, which take into consideration something in the environment and then react to it. As an example of this, I have chosen tracking algorithms. A tracking AI takes into consideration the position of the object being tracked, and then it changes the trajectory of the AI object so that it moves toward the object being tracked.

The tracking can be literally vectored directly toward the object, or it can be a more realistic model, turning toward the object much like a heat-seeking missile would do. Take a look at Figure 12.3.

Figure 12.3. Tracking methods.

graphics/12fig03.gif

For an example of the brute-force method, take a look at this algorithm:

// given: player is at player_x, player_y
// and game creature is at
// monster_x, monster_y

// first test x-axis
if (player_x > monster_x)
   monster_x++;
if (player_x < monster_x)
   monster_x--;

// now y -axis
if (player_y > monster_y)
   monster_y++;
if (player_y < monster_y)
   monster_y--;

If you dropped this AI into a simple demo, it would track you down in Terminator-like fashion! The code is simple but effective. Pac-Man's AI was written in much the same way. Of course, Pac-Man could only make right-angle turns and had to move in a straight line and avoid obstacles, but it's in the same ballpark. For an example, check out DEMO12_2.CPP|EXE (16-bit version, DEMO12_2_16B.CPP|EXE) on the CD. In it, you control a ghost with the keyboard arrow keys while a bat tries to hunt you down.

This kind of tracking is great, but it's a little artificial because the AI-controlled object tracks the target precisely. A more natural approach to tracking might be to change the trajectory vector of the tracking object in the direction defined from the center of the tracking object to the center of the object being tracked. Take a look at Figure 12.4 to see this.

Figure 12.4. Tracking an object based on trajectory vectoring.

graphics/12fig04.gif

The algorithm works as follows: Assume that the AI-controlled object is called tracker and has the following properties:

Position:(tracker.x, tracker.y)
Velocity:(tracker.xv, tracker.yv)

The object to be tracked is called target and has the following properties:

Position:(target.x, target.y)
Velocity:(target.xv, target.yv)

Based on those definitions, here is the general logic cycle that adjusts the velocity vector of the tracker:

  1. Compute the vector from the tracker to the target:

    TV =( target.x – tracker.x, target.y – tracker.y) = (tvx, tvy), normalize TV—in other words, divide (tvx, tvy)/Vector_Length(tvx,tvy) so that the max length is 1.0, and call this TV*. Note that Vector_Length() just computes the length of a vector from the origin (0,0), or in other words the sqrt(x2 + y2).

  2. Adjust the current velocity vector of the tracker by adding TV* scaled by a rate:

    tracker.x+=rate*tvx;
    tracker.y+=rate*tvy;
    

    Note that as rate becomes larger than 1.0, the track vectoring converges more swiftly, and the tracking algorithm tracks the target more closely and makes changes to the target's movements more quickly.

  3. After the tracker's velocity vector has been modified, there's a possibility that the vector velocity has overflowed a maximum rate. In other words, the tracker continues to speed up in the direction of the target once it has a lock. As a result, you should put an upper bound on this and slow the tracker down at some point. Here's an example:

    // get magnitude of velocity vector
    tspeed = Vector_Length(tracker.xv, tracker.yv);
    
    // moving too fast?
    if (tspeed > MAX_SPEED)
        {
        // shrink the velocity vector
        tracker.xv*=0.75;
        tracker.yv*=0.75;
        } // end if
    

There are other choices—0.5 or 0.9—whatever. It's even possible to compute the exact overflow and then shrink the vector by that amount, if perfection's your goal. I know we haven't hit vector math yet, and yet I've been using the terminology in this example, so I thought I would give an example of some tracking code that uses this algorithm, ripped right out of a real game. This code makes these little mines track the player. Look at how the real code performs all the previous steps in a real example:

// mine tracking algorithm

// compute vector toward player
float vx = player_x - mines[index].varsI[INDEX_WORLD_X];
float vy = player_y - mines[index].varsI[INDEX_WORLD_Y];

// normalize vector (sorta :)
float length = Fast_Distance_2D(vx,vy);

// only track if reasonable close
if (length < MIN_MINE_TRACKING_DIST)
   {
   vx=MINE_TRACKING_RATE*vx/length;
   vy=MINE_TRACKING_RATE*vy/length;

   // add velocity vector to current velocity
   mines[index].xv+=vx;
   mines[index].yv+=vy;

   // add a little noise
   if ((rand()%10)==1)
      {
      vx = RAND_RANGE(-1,1);
      vy = RAND_RANGE(-1,1);
      mines[index].xv+=vx;
      mines[index].yv+=vy;
      }// end if

   // test velocity vector of mines
  length = Fast_Distance_2D(mines[index].xv, mines[index].yv);

   // test for velocity overflow and slow
   if (length > MAX_MINE_VELOCITY)
      {
      // slow down
      mines[index].xv*=0.75;
      mines[index].yv*=0.75;
      } // end if
   } // end if
else
   {
   // add a random velocity component
   if ((rand()%30)==1)
      {
      vx = RAND_RANGE(-2,2);
      vy = RAND_RANGE(-2,2);
      // add velocity vector to current velocity
      mines[index].xv+=vx;
      mines[index].yv+=vy;

      // test velocity vector of mines
      length = Fast_Distance_2D(mines[index].xv, mines[index].yv);

      // test for velocity overflow and slow
      if (length > MAX_MINE_VELOCITY)
         {
         // slow down
         mines[index].xv*=0.75;
         mines[index].yv*=0.75;

         } // end if

      } // end if

 } // end else

Although it's obvious that this code was hijacked from a for loop or something that processed a number of mines, that's irrelevant. It's a good example of a clean implementation of the algorithm, but it also has some areas I want to bring to your attention. For example, there's a section of the code that tests if the mine is within a certain distance of the player. If not, the mine doesn't track the player but has its trajectory slightly modified with some random noise. In addition, even when the mine tracks the player, I add some random noise to the result. This adds more realism to the tracking. In space, water, air, or whatever, there are going to be changes in gravity, density, and so forth that would slightly alter the physics. Thus, adding the noise makes things more realistic.

For an example of this trajectory tracking algorithm, check out DEMO12_3.CPP|EXE (16-bit version not available) on the CD. It allows you to move a little ship around in a scrolling universe. Within this universe are mines that follow you by using the previous algorithm. The controls are

Arrow Keys Controls ship
Ctrl Fires ship's weapons
+/- Changes the tracking rate
H Toggles HUDS
S Toggles scanner

Notice how decreasing the tracking rate makes the tracking object look like it's on ice.

This is a good example of a small game, so there's a lot to learn. Study it well.

TIP

Because I'm using GDI to draw text, the text printing slows the game down tremendously. I wanted you to see this. In a real game, you would make your own font engine to draw text.


Anti-Tracking: Evasion Algorithms

Starting to get little quantum disturbances in your brain—that is, ideas? Good! The next AI technique is to enable creatures in the game to get away from you. Remember how the ghosts in Pac-Man fled when you ate the powerups? Making an evasion AI do the same thing is simple. In fact, you already have the code! The previous tracking code is the exact opposite of what you want; just take the code and flip the equalities around. Presto! You'll have an evasion algorithm. Here's the code after the inversions:

// given: player is at player_x, player_y
// and game creature is at
// monster_x, monster_y

// first test x-axis
if (player_x  < monster_x)
   monster_x++;
if (player_x > monster_x)
   monster_x--;

// now y -axis
if (player_y <  monster_y)
   monster_y++;
if (player_y > monster_y)
   monster_y--;

NOTE

If you have a heartbeat, you should have noticed that there is no conditional for equal to (==). This is because I don't want the object to move in this case. I want it to sit on the player. If you want, you can make the == case do something else.


Now you can create a fairly impressive AI system with just random motion, chasing, and evasion. In fact, you have enough to make a Pac-Man brain. Not much, but good enough to sell 100 million or so copies, so that's not too bad! To check out evasion in action, run DEMO12_4.CPP|EXE (16-bit version, DEMO12_4._16BCPP|EXE) on the CD. It's basically the same as DEMO12_2.CPP, but with the evasion AI instead of the tracking AI. Now let's move on to patterns.

      Previous Section Next Section
    



    JavaScript EditorAjax Editor     JavaScript Editor