Game Career Guide is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Get the latest Education e-news
 
  • Book Excerpt: AI for Game Developers

    [09.29.06]
    - Glenn Seeman and David Bourg

  • Feature!Follow the Leader

    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.

    Once a leader is established, we could implement any number of rules or techniques to have the leader do something meaningful. We could have the leader execute some prescribed pattern, or chase something, or perhaps evade. In this example, we'll have the leader chase or intercept the user-controlled unit. Further, we'll break up the computer-controlled units into two types: regular units and interceptors. Interceptors will be somewhat faster than regular units and will follow the intercepting algorithms we discussed earlier in this book. The regular units will travel more slowly and will follow the chase algorithms we discussed earlier. You can define or classify units in an infinite number of ways. We chose these to illustrate some possibilities.

    Example 4-13 shows a few lines of code that you must add to the block of code shown in Example 4-3; the one that calculates all the neighbor data for a given unit.

    Example 4-13. Leader check
    .
    .
    .
    if(((w.y > 0) &&
    (fabs(w.x) < fabs(w.y)*_FRONT_VIEW_ANGLE_FACTOR)))
    if(d.Magnitude() <=
    (Units[i].fLength * _NARROWVIEW_RADIUS_FACTOR))
    Nf++;
    .
    .
    .
    if(InView &&
    (Units[i].Interceptor == Units[j].Interceptor))
    {
    .
    .
    .
    }
    .
    .
    .
    The first if block shown here performs a check, using the same narrow-visibility model we've already discussed, to determine the number of units directly in front of and within view of the current unit under consideration. Later, this information will be used to determine whether the current unit should be a leader. Essentially, if no other units are directly in front of a given unit, it becomes a leader and can have other units flocking around or behind it. If at least one unit is in front of and within view of the current unit, the current unit can't become a leader. It must follow the flocking rules only.

    The second if block shown in Example 4-13 is a simple modification to the InView test. The additional code checks to make sure the types of the current unit and Units[j] are the same so that interceptor units flock with other interceptor units and regular units flock with other regular units, without mixing the two types in a flock. Therefore, if you download and run this example program and toggle one of the flocking modes on, you'll see at least two flocks form: one flock of regular units and one flock of interceptor units. (Note that the player-controlled unit will be shown in green and you can control it using the keyboard arrow keys.)

    Example 4-14 shows how the leader rules are implemented for the two types of computer-controlled units.

    Example 4-14. Leaders, chasing and intercepting

    .
    .
    .
    // Chase the target if the unit is a leader
    // Note: Nf is the number of units in front
    // of the current unit.
    if(Chase)
    {
    if(Nf == 0)
    Units[i].Leader = true;
    else
    Units[i].Leader = false;
    if(Units[i].Leader)
    {
    if(!Units[i].Interceptor)
    {
    // Chase
    u = Units[0].vPosition;
    d = u - Units[i].vPosition;
    w = VRotate2D(-Units[i].fOrientation, d);
    if(w.x < 0) m = -1;
    if(w.x > 0) m = 1;
    Fs.x += m*_STEERINGFORCE;
    } else {
    // Intercept
    Vector s1, s2, s12;
    double tClose;
    Vector Vr12;
    Vr12 = Units[0].vVelocity -
    Units[i].vVelocity;
    s12 = Units[0].vPosition -
    Units[i].vPosition;
    tClose = s12.Magnitude() /
    Vr12.Magnitude();
    s1 = Units[0].vPosition +
    (Units[0].vVelocity * tClose);
    Target = s1;
    s2 = s1 - Units[i].vPosition;
    w = VRotate2D(-Units[i].fOrientation, s2);
    if(w.x < 0) m = -1;
    if(w.x > 0) m = 1;
    Fs.x += m*_STEERINGFORCE;
    }
    }
    }
    .
    .
    .

    If you toggle the chase option on in the example program, the Chase variable gets set to true and the block of code shown here will be executed. Within this block, a check of the number of units, Nf, in front of and within view of the current unit is made to determine whether the current unit is a leader. If Nf is set to 0, no other units are in front of the current one and it thus becomes a leader.

    If the current unit is not a leader, nothing else happens; however, if it is a leader, it will execute either a chase or an intercept algorithm, depending on its type. These chase and intercept algorithms are the same as those we discussed earlier in the book, so we won't go through the code again here.

    These new leader rules add some interesting behavior to the example program. In the example program, any leader will turn red and you'll easily see how any given unit can become a leader or flocking unit as the simulation progresses. Further, having just the two simple types of computer-controlled units yields some interesting tactical behavior. For example, while hunting the player unit, one flock tails the player while the other flock seems to flank the player in an attempt to intercept him. The result resembles a pincer-type maneuver.

    Certainly, you can add other AI to the leaders to make their leading even more intelligent. Further, you can define and add other unit types to the mix, creating even greater variety. The possibilities are endless, and the ones we discussed here serve only as illustrations as to what's possible.

Comments

comments powered by Disqus