University of Alaska system



Boid Example Continued, and Lists

Move to Centroid

Let’s start by implementing the centroid concept. The idea is fairly simple – each boid can see some distance away and wants to be close to the center of other boids. For simplicity, let’s make the visible distance of a boid a circle with the boid at the center (yes, this would mean it can see behind itself). For now, we’ll just make this a constant at the top of our form, where the constant represents the radius of a circle, specified in pixels, within which the boid can see:

private const int BOID_VISION_RADIUS = 100; // Radius for a boid's vision

For every other boid within this radius we’d like our current boid to try and move to the centroid of those boids. The centroid is just the average of the x and y coordinates of all the boids within the visible radius. This is illustrated in the diagram below:

[pic]

In this diagram boid X is currently pointed up toward the top of the window. It finds all the other boids (boids A, B, C) within a radius of 100 pixels from its location and ignores the rest (boid D). It then calculates the centroid of boids A, B, and C, where the centroid’s x coordinate is the average of A,B, and C’s x coordinates, and the centroid’s y coordinate is the average of A, B, and C’s y coordinates. In the diagram, the centroid is depicted as a red dot. Boid X then shifts slightly closer toward the centroid. This is shown as the red arrow to the upper left. To simplify things we’ll allow our boids to magically shift location, even if it is moving in the opposite direction. A better (but somewhat more complex approach) would be to figure out what angle the boid should turn so it is facing the centroid, and have it turn a little bit toward that angle.

Before writing actual code, let’s start with some pseudocode.

To calculate the centroid for the boid b:

x1 = X coordinate of boid b

y1 = Y coordinate of boid b

totalX = 0

totalY = 0

numCloseBoids = 0

For each boid i in the array of boids

if (i != b) then

x2 = X coordinate of boid i

y2 = Y coordinate of boid i

if the distance from (x1,y1) to (x2,y2) < BOID_VISION_RADIUS

totalX = totalX + x2

totalY = totalY + y2

numCloseBoids++

End If

End if

Next

centroidX = totalX / NumBoids

centroidY = totalY / NumBoids

To calculate the distance from (x,y) to (x2,y2) we can make a function that returns:

[pic]

Here it is in actual code:

// A helper function to calculate the distance between two points

private double distance(int x1, int y1, int x2, int y2)

{

return Math.Sqrt(Math.Pow(x1-x2,2) + Math.Pow(y1-y2,2));

}

// Calculate the centroid of other boids close to boid b

private void Centroid(int b)

{

int x1, y1, x2, y2; // x1,y1 = coordinate of boid b

// x2,y2 = coordinate of target boid in array

int totalX = 0, totalY = 0; // Total of coordinates for centroid

x1 = Xs[b]; // Set to coordinates of boid b

y1 = Ys[b];

// Loop through every boid's coordinates

// to calculate centroid

int boidsSeen = 0;

for (int i = 0; i < NUMBOIDS; i++)

{

// Don't include boid b in centroid calculations

if (i != b)

{

x2 = Xs[i];

y2 = Ys[i];

// Check if target boid is visible

if (distance(x1, y1, x2, y2) < BOID_VISION_RADIUS)

{

totalX += x2;

totalY += y2;

boidsSeen++;

}

}

}

// Do nothing if no boids in sight

if (boidsSeen == 0)

{

return;

}

// Calculate coordinates of the centroid

int centroidX = totalX / boidsSeen;

int centroidY = totalY / boidsSeen;

// Do nothing if we're already at the centroid

if ((centroidX == x1) && (centroidY == y1))

{

return;

}

// More code will go here to move the boid

}

This code calculates the centroid’s X and Y coordinate, so now we need to move the boid toward that location. As mentioned earlier, ideally we’d change the boid’s heading so it would be going toward the centroid, but to keep things simple we’ll just “transport” the boid a few pixels so that its closer to the centroid:

// Move 2% of the way toward centroid,

// or not at all if within 50 pixels of the centroid

double deltaX = (centroidX - x1) / 50.0;

double deltaY = (centroidY - y1) / 50.0;

Xs[b] += Convert.ToInt32(deltaX);

Ys[b] += Convert.ToInt32(deltaY);

This code would be placed at the end of the Centroid() method. It computes the X and Y distance away from the centroid, then moves it 1/50th of the way, or 2%, of the way there. I’ve used a small number so the boid doesn’t look like it suddenly jumps to a new location in space. Note that there is no change if the centroid is within 50 pixels of the boid, due to the integer conversion.

Lastly, we should update the heading toward the centroid for every boid before we draw it. This can be done by simply adding a call to Centroid in the timer:

// When the timer goes off, update the location of each boid

private void timer1_Tick(object sender, EventArgs e)

{

for (int i = 0; i < NUMBOIDS; i++)

{

// Centroid rule

Centroid(i);

// Set the location of the boid to a new spot moving at

// speed BOID_VELOCITY

Xs[i] += Convert.ToInt32(Math.Cos(Dirs[i]) * BOID_VELOCITY);

Ys[i] += Convert.ToInt32(Math.Sin(Dirs[i]) * BOID_VELOCITY);

// Check for going off the edge of the screen

// and wrap around to the other side

if (Xs[i] > pboxWorld.Width)

{

Xs[i] = Xs[i] - pboxWorld.Width;

}

if (Xs[i] < 0)

{

Xs[i] = pboxWorld.Width + Xs[i];

}

if (Ys[i] > pboxWorld.Height)

{

Ys[i] = Ys[i] - pboxWorld.Height;

}

if (Ys[i] < 0)

{

Ys[i] = pboxWorld.Height + Ys[i];

}

}

// Invalidate the picturebox so it calls the paint subroutine

// and re-draws the boid in the new location

pboxWorld.Invalidate();

}

Upon running the program the boids that are going in close to the same direction should now be somewhat aligned as the centroid draws them closer to each other. Note that at this point the boids can’t change direction, so we only see grouping for the boids going the same direction.

[pic]

Move away from neighbor that’s too close

Whew, we’ve written a fair bit of code, but the good news is that we can reuse a lot of it to implement the final two rules. To counteract the rule of moving toward the centroid, we can add a new rule that we don’t like to be too close to another boid. It might result in a collision (although we don’t detect one) and invades a boid’s personal space.

Let’s add a simple rule that we find the distance to the closest boid. If that distance is less than some threshold, say 30 pixels, then the boid should move a short distance in the OPPOSITE direction. To do this we need to find the coordinates of the closest boid. Here is pseudocode to find the boid closest to boid b:

x1 = X coordinate of boid b

y1 = Y coordinate of boid b

closestDistanceOtherBoid = Some big number

For each boid i in the array of boids

if (i != b) then

x2 = X coordinate of boid i

y2 = Y coordinate of boid i

if the distance from (x1,y1) to (x2,y2) < closestDistanceOtherBoid then

closestX = x2

closestY = y2

closestDistanceOtherBoid = distance from (x1, y1) to (x2, y2)

End If

End if

Next

Return if (closestX = x1 and closestY = y1) // If closest is on top of you, do nothing

// closestX and closestY are the coordinates of the closest boid so now check if

// it’s within the repel distance

if (closestDistanceOtherBoid < BOID_REPEL_DISTANCE)

move away from (closestX, closestY)

You might recognize that the code is fairly similar to calculating the centroid, but instead we remember the coordinates and distance of the closest boid (as long as it’s at least within the boid’s vision). Here is working code. First let’s define another constant, BOID_REPEL_DISTANCE, set to 30:

private const int BOID_REPEL_DISTANCE = 30; // Move away if closer

The method to find the closest boid’s coordinates is below:

// Find the closest boid to boid b and move away if it's too close

private void Repel(int b)

{

int x1, y1, x2, y2; // x1,y1 = coordinate of boid b

// x2,y2 = coordinate of target boid in array

int closestX = -1, closestY = -1; // Coords of closest boid,

// -1 initially for no boid

int closestDistance = 99999; // Initially, nothing is close

x1 = Xs[b]; // Set to coordinates of boid b

y1 = Ys[b];

// Loop through every boid's coordinates

// to find closest

for (int i = 0; i < NUMBOIDS; i++)

{

// Don't include boid b

if (i != b)

{

x2 = Xs[i];

y2 = Ys[i];

// Check if target boid is visible

if (distance(x1, y1, x2, y2) < closestDistance)

{

// Remember distance and coordinates of closest one

closestDistance =

Convert.ToInt32(distance(x1, y1, x2, y2));

closestX = x2;

closestY = y2;

}

}

}

// Do nothing if closest boid is on top of you,

// we'll be moving off in some direction anyway

if ((closestX == x1) && (closestY == y1))

{

return;

}

// Move away from closest if it's too close

if (closestDistance ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download