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

 Home Features Book Excerpt: AI for Game Developers
• # Book Excerpt: AI for Game Developers

[09.29.06]
- Glenn Seeman and David Bourg

• ### Separation

Separation implies that we want the units to maintain some minimum distance away from each other, even though they might be trying to get closer to each other as a result of the cohesion and alignment rules. We don't want the units running into each other or, worse yet, coalescing at a coincident position. Therefore, we'll enforce separation by requiring the units to steer away from any neighbor that is within view and within a prescribed minimum separation distance.

Figure 4-7 illustrates a unit that is too close to a given unit, the bold one. The outer arc centered on the bold unit is the visibility arc we've already discussed. The inner arc represents the minimum separation distance. Any unit that moves within this minimum separation arc will be steered clear of it by the bold unit.

Figure 4-7. Separation The code to handle separation is just a little different from that for cohesion and alignment because for separation, we need to look at each individual neighbor when determining suitable steering corrections rather than some average property of all the neighbors. It is convenient to include the separation code within the same j loop shown in Example 4-3 where the neighbors are identified. The new j loop, complete with the separation rule implementation, is shown in Example 4-10.

Example 4-10. Neighbors and separation

.
.
.
for(j=1; j<_MAX_NUM_UNITS; j++)
{
if(i!=j)
{
InView = false;
d = Units[j].vPosition - Units[i].vPosition;
w = VRotate2D(-Units[i].fOrientation, d);
if(WideView)
{
InView = ((w.y > 0) || ((w.y < 0) &&
(fabs(w.x) >
fabs(w.y)*_BACK_VIEW_ANGLE_FACTOR)));
}
if(LimitedView)
{
InView = (w.y > 0);
}
if(NarrowView)
{
InView = (((w.y > 0) && (fabs(w.x) <
fabs(w.y)*_FRONT_VIEW_ANGLE_FACTOR)));
}
if(InView)
{
if(d.Magnitude() <= (Units[i].fLength *
{
Pave += Units[j].vPosition;
Vave += Units[j].vVelocity;
N++;
}
}
if(InView)
{
if(d.Magnitude() <=
(Units[i].fLength * _SEPARATION_FACTOR))
{
if(w.x < 0) m = 1;
if(w.x > 0) m = -1;
Fs.x += m * _STEERINGFORCE *
(Units[i].fLength *
_SEPARATION_FACTOR) /
d.Magnitude();
}
}
}
}
.
.
.

The last if block contains the new separation rule code. Basically, if the j unit is in view and if it is within a distance of Units[i].fLength ∗_SEPARATION_FACTOR from the current unit, Units[i], we calculate and apply a steering correction. Notice that d is the distance separating Units[i] and Units[j], and was calculated at the beginning of the j loop.

Once it has been determined that Units[j] presents a potential collision, the code proceeds to calculate the corrective steering force. First, the direction factor, m, is determined so that the resulting steering force is of such a direction that the current unit, Units[i], steers away from Units[j]. In this case, m takes on the opposite sense, as in the cohesion and alignment calculations.

As in the cases of cohesion and alignment, steering forces get accumulated in Fs.x. In this case, the corrective steering force is inversely proportional to the actual separation distance. This will make the steering correction force greater the closer Units[j] gets to the current unit. Notice here again that the minimum separation distance is scaled as a function of the unit's length and some prescribed separation factor. This occurs so that separation scales just like visibility, as we discussed earlier.

We also should mention that even though separation forces are calculated here, units won't always avoid each other with 100% certainty. Sometimes the sum of all steering forces is such that one unit is forced very close to or right over an adjacent unit. Tuning all the steering force parameters helps to mitigate, though not eliminate, this situation. You could set the separation steering force so high as to override any other forces, but you'll find that the units' behavior when in close proximity to each other appears very erratic. Further, it will make it difficult to keep flocks together. In the end, depending on your game's requirements, you still might have to implement some sort of collision detection and response algorithm similar to that discussed in Physics for Game Developers (O'Reilly) to handle cases in which two or more units run into each other.

You also should be aware that visibility has an important effect on separation. For example, while in the wide-view visibility model, the units maintain separation very effectively; however, in the narrow-view model the units fail to maintain side-to-side separation. This is because their views are so restricted, they are unaware of other units right alongside them. If you go with such a limited-view model in your games, you'll probably have to use a separate view model, such as the wide-view model, for the separation rule. You can easily change this example to use such a separate model by replacing the last if block's condition to match the logic for determining whether a unit is in view according to the wide-view model.

Once all the flocking rules are implemented and appropriate steering forces are calculated for the current unit, DoUnitAI stores the resulting steering forces and point of application in the current unit's member variables. This is shown in Example 4-11.

Example 4-11. Set Units[i] member variables

void DoUnitAI(int i)
// Do all steering force calculations...
.
.
.
Units[i].Fa = Fs;
Units[i].Pa = Pfs;
}

Once DoUnitAI returns, UpdateSimulation becomes responsible for applying the new steering forces and updating the positions of the units (see Example 4-1).