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

**Example 4-1. UpdateSimulation function**

void UpdateSimulation(void)

{

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)

{

if(Units[i].Leader)

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;

int RadiusFactor;

// 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)));

RadiusFactor = _WIDEVIEW_RADIUS_FACTOR;

}

if(LimitedView)

{

InView = (w.y > 0);

RadiusFactor = _LIMITEDVIEW_RADIUS_FACTOR;

}

if(NarrowView)

{

InView = (((w.y > 0) && (fabs(w.x) <

fabs(w.y)*

_FRONT_VIEW_ANGLE_FACTOR)));

RadiusFactor = _NARROWVIEW_RADIUS_FACTOR;

}

if(InView)

{

if(d.Magnitude() <= (Units[i].fLength *

RadiusFactor))

{

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.

Comments

comments powered by Disqus