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

• ### Cohesion

Cohesion implies that we want all the units to stay together in a group; we don't want each unit breaking from the group and going its separate way. As we stated earlier, to satisfy this rule, each unit should steer toward the average position of its neighbors. Figure 4-6 illustrates a unit surrounded by several neighbors. The small dashed circle in the figure represents the average position of the four neighbors that are within view of the unit shown in bold lines with the visibility arc around itself.

Figure 4-6. Average position and heading of neighbors The average position of neighbors is fairly easy to calculate. Once the neighbors have been identified, their average position is the vector sum of their respective positions divided by the total number of neighbors (a scalar). The result is a vector representing their average position. Example 4-3 already shows where the positions of the neighbors are summed once they've been identified. The relevant code is repeated here in Example 4-7 for convenience.

Example 4-7. Neighbor position summation

.
.
.
if(InView)
{
if(d.Magnitude() <= (Units[i].fLength *
{
Pave += Units[j].vPosition;
Vave += Units[j].vVelocity;
N++;
}
}
.
.
.

The line that reads Pave += Units[j].vPosition; sums the position vectors of all neighbors. Remember, Pave and vPosition are Vector types, and the overloaded operators take care of vector addition for us.

After DoUnitAI takes care of identifying and collecting information on neighbors, you can apply the flocking rules. The first one handled is the cohesion rule, and the code in Example 4-8 shows how to do this.

Example 4-8. Cohesion rule

.
.
.
// Cohesion Rule:
if(DoFlock && (N > 0))
{
Pave = Pave / N;
v = Units[i].vVelocity;
v.Normalize();
u = Pave - Units[i].vPosition;
u.Normalize();
w = VRotate2D(-Units[i].fOrientation, u);
if(w.x < 0) m = -1;
if(w.x > 0) m = 1;
if(fabs(v*u) < 1)
Fs.x += m * _STEERINGFORCE * acos(v * u) / pi;
}
.
.
.

Notice that the first thing this block of code does is check to make sure the number of neighbors is greater than zero. If so, we can go ahead and calculate the average position of the neighbors. Do this by taking the vector sum of all neighbor positions, Pave, and dividing by the number of neighbors, N.

Next, the heading of the current unit under consideration, Units[i], is stored in v and normalized. It will be used in subsequent calculations. Now the displacement between Units[i] and the average position of its neighbors is calculated by taking the vector difference between Pave and Units[i]'s position. The result is stored in u and normalized. u is then rotated from global coordinates to local coordinates fixed to Units[i] and the result is stored in w. This gives the location of the average position of Units[i]'s neighbors relative to Units[i]'s current position.

Next, the multiplier, m, for the steering force is determined. If the x-coordinate of w is greater than zero, the average position of the neighbors is located to the starboard side of Units[i] and it has to turn left (starboard). If the x-coordinate of w is less than zero, Units[i] must turn right (port side).

Finally, a quick check is made to see if the dot product between the unit vectors v and u is less than 1 and greater than minus -1. This must be done because the dot product will be used when calculating the angle between these two vectors, and the arc cosine function takes an argument between +/−1.

The last line shown in Example 4-8 is the one that actually calculates the steering force satisfying the cohesion rule. In that line the steering force is accumulated in Fs.x and is equal to the direction factor, m, times the prescribed maximum steering force times the angle between the current unit's heading and the vector from it to the average position of its neighbors divided by pi. The angle between the current unit's heading and the vector to the average position of its neighbors is found by taking the arc cosine of the dot product of vectors v and u. This comes from the definition of dot product. Note that the two vectors, v and u, are unit vectors. Dividing the resulting angle by pi yields a scale factor that gets applied to the maximum steering force. Basically, the steering force being accumulated in Fs.x is a linear function of the angle between the current unit's heading and the vector to the average position of its neighbors. This means that if the angle is large, the steering force will be relatively large, whereas if the angle is small, the steering force will be relatively small. This is exactly what we want. If the current unit is heading in a direction far from the average position of its neighbors, we want it to make a harder corrective turn. If it is heading in a direction not too far off from the average neighbor position, we want smaller corrections to its heading.