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

• ### Neighbors

As we discussed earlier, each unit in a flock must be aware of its neighbors. Exactly how many neighbors each unit is aware of is a function of the field-of-view and view radius parameters shown in Figure 4-1. Because the arrangement of the units in a flock will change constantly, each unit must update its view of the world each time through the game loop. This means we must cycle through all the units in the flock collecting the required data. Note that we have to do this for each unit to acquire each unit's unique perspective. This neighbor search can become computationally expensive as the number of units grows large. The sample code we discuss shortly is written for clarity and is a good place to make some optimizations.

The example program entitled AIDemo4, which you can download from the book's web site (https://www.oreilly.com/catalog/ai), is set up similar to the examples we discussed earlier in this book. In this example, you'll find a function called UpdateSimulation that is called each time through the game, or simulation, loop. This function is responsible for updating the positions of each unit and for drawing each unit to the display buffer. Example 4-1 shows the UpdateSimulation function for this example.

{
double dt = _TIMESTEP;
int i;
// Initialize the back buffer:
if(FrameCounter >= _RENDER_FRAME_COUNT)
{
ClearBackBuffer();
DrawObstacles();
}
// Update the player-controlled unit (Units[0]):
Units[0].SetThrusters(false, false, 1);
if (IsKeyDown(VK_RIGHT))
Units[0].SetThrusters(true, false, 0.5);
if (IsKeyDown(VK_LEFT))
Units[0].SetThrusters(false, true, 0.5);
Units[0].UpdateBodyEuler(dt);
if(Units[0].vPosition.x > _WINWIDTH) Units[0].vPosition.x = 0;
if(Units[0].vPosition.x < 0) Units[0].vPosition.x = _WINWIDTH;
if(Units[0].vPosition.y > _WINHEIGHT) Units[0].vPosition.y = 0;
if(Units[0].vPosition.y < 0) Units[0].vPosition.y = _WINHEIGHT;
if(FrameCounter >= _RENDER_FRAME_COUNT)
DrawCraft(Units[0], RGB(0, 255, 0));
// Update the computer-controlled units:
for(i=1; i<_MAX_NUM_UNITS; i++)
{
DoUnitAI(i);
Units[i].UpdateBodyEuler(dt);
if(Units[i].vPosition.x > _WINWIDTH)
Units[i].vPosition.x = 0;
if(Units[i].vPosition.x < 0)
Units[i].vPosition.x = _WINWIDTH;
if(Units[i].vPosition.y > _WINHEIGHT)
Units[i].vPosition.y = 0;
if(Units[i].vPosition.y < 0)
Units[i].vPosition.y = _WINHEIGHT;
if(FrameCounter >= _RENDER_FRAME_COUNT)
{
DrawCraft(Units[i], RGB(255,0,0));
else {
if(Units[i].Interceptor)
DrawCraft(Units[i], RGB(255,0,255));
else
DrawCraft(Units[i], RGB(0,0,255));
}
}
}
// Copy the back buffer to the screen:
if(FrameCounter >= _RENDER_FRAME_COUNT) {
CopyBackBufferToWindow();
FrameCounter = 0;
} else
FrameCounter++;
}
UpdateSimulation performs the usual tasks. It clears the back buffer upon which the scene will be drawn; it handles any user interaction for the player-controlled unit; it updates the computer-controlled units; it draws everything to the back buffer; and it copies the back buffer to the screen when done. The interesting part for our purposes is where the computer-controlled units are updated. For this task, UpdateSimulation loops through an array of computer-controlled units and, for each one, calls another function named DoUnitAI. All the fun happens in DoUnitAI, so we'll spend the remainder of this chapter looking at this function.

DoUnitAI handles everything with regard to the computer-controlled unit's movement. All the flocking rules are implemented in this function. Before the rules are implemented, however, the function has to collect data on the given unit's neighbors. Notice here that the given unit, the one currently under consideration, is passed in as a parameter. More specifically, an array index to the current unit under consideration is passed in to DoUnitAI as the parameter i.

Example 4-2 shows a snippet of the very beginning of DoUnitAI. This snippet contains only the local variable list and initialization code. Normally, we just brush over this kind of code, but because this code contains a relatively large number of local variables and because they are used often in the flocking calculations, it's worthwhile to go through it and state exactly what each one represents.

Example 4-2. DoUnitAI initialization

void DoUnitAI(int i)
{
int j;
int N; // Number of neighbors
Vector Pave; // Average position vector
Vector Vave; // Average velocity vector
Vector Fs; // Net steering force
Vector Pfs; // Point of application of Fs
Vector d, u, v, w;
double m;
bool InView;
bool DoFlock = WideView||LimitedView||NarrowView;
// Initialize:
Fs.x = Fs.y = Fs.z = 0;
Pave.x = Pave.y = Pave.z = 0;
Vave.x = Vave.y = Vave.z = 0;
N = 0;
Pfs.x = 0;
Pfs.y = Units[i].fLength / 2.0f;
.
.
.
}

We've already mentioned that the parameter, i, represents the array index to the unit currently under consideration. This is the unit for which all the neighbor data will be collected and the flocking rules will be implemented. The variable, j, is used as the array index to all other units in the Units array. These are the potential neighbors to Units[i]. N represents the number of neighbors that are within view of the unit currently under consideration. Pave and Vave will hold the average position and velocity vectors, respectively, of the N neighbors. Fs represents the net steering force to be applied to the unit under consideration. Pfs represents the location in body-fixed coordinates at which the steering force will be applied. d, u, v, and w are used to store various vector quantities that are calculated throughout the function. Such quantities include relative position vectors and heading vectors in both global and local coordinates. m is a multiplier variable that always will be either +1 or −1. It's used to make the steering forces point in the directions we need—that is, to either the starboard or port side of the unit under consideration. InView is a flag that indicates whether a particular unit is within view of the unit under consideration. DoFlock is simply a flag that indicates whether to apply the flocking rules. In this demo, you can turn flocking on or off. Further, you can implement three different visibility models to see how the flock behaves. These visibility models are called WideView, LimitedView, and NarrowView. Finally, RadiusFactor represents the r parameter shown in Figure 4-1, which is different for each visibility model. Note the field-of-view angle is different for each model as well; we'll talk more about this in a moment.

After all the local variables are declared, several of them are initialized explicitly. As you can see in Example 4-2, they are, for the most part, initialized to 0. The variables you see listed there are the ones that are used to accumulate some value—for example, to accumulate the steering force contributions from each rule, or to accumulate the number of neighbors within view, and so on. The only one not initialized to 0 is the vector Pfs, which represents the point of application of the steering force vector on the unit under consideration. Here, Pfs is set to represent a point on the very front and centerline of the unit. This will make the steering force line of action offset from the unit's center of gravity so that when the steering force is applied, the unit will move in the appropriate direction as well as turn and face the appropriate direction.
Upon completing the initialization of local variables, DoUnitAI enters a loop to gather information about the current unit's neighbors, if there are any.

Example 4-3 contains a snippet from DoUnitAI that performs all the neighbor checks and data collection. To this end, a loop is entered, the j loop, whereby each unit in the Units array—except for Units[0] (the player-controlled unit) and Units[i] (the unit for which neighbors are being sought)—is tested to see if it is within view of the current unit. If it is, its data is collected.

Example 4-3. Neighbors

.
.
.
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++;
}
}
.
.
.
}
}
.
.
.

After checking to make sure that i is not equal to j—that is, we aren't checking the current unit against itself—the function calculates the distance vector between the current unit, Units[i], and Units[j], which is simply the difference in their position vectors. This result is stored in the local variable, d. Next, d is converted from global coordinates to local coordinates fixed to Units[i]. The result is stored in the vector w.

Next, the function goes on to check to see if Units[j] is within the field of view of Units[i]. This check is a function of the field-of-view angle as illustrated in Figure 4-1; we'll check the radius value later, and only if the field-of-view check passes.

Now, because this example includes three different visibility models, three blocks of code perform field-of-view checks. These checks correspond to the wide-field-of-view, the limited-field-of-view, and the narrow-field-of-view models. As we discussed earlier, a unit's visibility influences the group's flocking behavior. You can toggle each model on or off in the example program to see their effect.

The wide-view model offers the greatest visibility and lends itself to easily formed and regrouped flocks. In this case, each unit can see directly in front of itself, to its sides, and behind itself, with the exception of a narrow blind spot directly behind itself. Figure 4-3 illustrates this field of view.

The test to determine whether Units[j] falls within this field of view consists of two parts. First, if the relative position of Units[j] in terms of local coordinates fixed to the current unit, Units[i], is such that its y-coordinate is positive, we know that Units[j] is within the field of view. Second, if the y-coordinate is negative, it could be either within the field of view or in the blind spot, so another check is required. This check looks at the x-coordinate to determine if Units[j] is located within the pie slice-shaped blind spot formed by the two straight lines that bound the visibility arc, as shown in Figure 4-3. If the absolute value of the x-coordinate of Units[j] is greater than some factor times the absolute value of the y-coordinate, we know Units[j] is located on the outside of the blind spot—that is, within the field of view. That factor times the absolute value of the y-coordinate calculation simply represents the straight lines bounding the field-of-view arc we mentioned earlier. The code that performs this check is shown in Example 4-3, but the key part is repeated here in Example 4-4 for convenience.