Tricks of the Windows Game Programming Gurus:Making Silicon Think with Artificial Intelligence

All ITKnowledge Source Code Search Tips Advanced Search |

| Tricks of the Windows Game Programming Gurus by Andre LaMothe Sams, Macmillan Computer Publishing ISBN: 0672313618 Pub Date: 09/27/99

Search this book:

Previous | Table of Contents | Next

#### 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.

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` 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.

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` 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.

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. Adyjust 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

Previous | Table of Contents | Next

Copyright © Macmillan Computer Publishing, Inc.

Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.