Flock Behavior

Types of Boids

The public and protected methods and data of the Boid class and its PredatorBoid and PreyBoid subclasses are shown in Figure 22-6.

Figure 22-6. The Boid class and subclasses

Boid represents a boid using a BranchGroup, transformGroup, and BoidShape (a Shape3D node). The TRansformGroup moves the boid about in the scene, and the BranchGroup permits the boid to be removed from the scene (e.g., after being eaten). Only a BranchGroup can be detached from a scene graph. The subgraph is built in the Boid( ) constructor:

     private TransformGroup boidTG = new TransformGroup(  );  // global         public Boid(...)     { // other initialization code, and then ...           // set TG capabilities so the boid can be moved       boidTG.setCapability(TransformGroup.ALLOW_TRANSFORM_WRITE);       boidTG.setCapability(TransformGroup.ALLOW_TRANSFORM_READ);       addChild(boidTG);  // add TG to Boid BranchGroup           // add the boid shape to the TG       boidTG.addChild( new BoidShape(boidColour) );     } // end of Boid(  )     

Boid Movement

The most important attributes for a boid are its current position and velocity. These are set to random values (within a certain range) in the Boid constructor:

     // globals     protected Vector3f boidPos = new Vector3f(  );     protected Vector3f boidVel = new Vector3f(  );         // code in the Boid constructor     boidPos.set(randPosn(  ),(float)(Math.random(  )*6.0), randPosn(  ));     boidVel.set( randVel(  ), randVel(  ), randVel(  )); 

The moveBoid( ) method uses them to orient and position the boid in the scene:

     // global used for repeated calculations     private Transform3D t3d = new Transform3D(  );         private void moveBoid(  )     { t3d.setIdentity(  );   // reset t3d       t3d.rotY( Math.atan2( boidVel.x, boidVel.z) );  // around y-axis                // atan2(  ) handles 0 value input arguments       t3d.setTranslation(boidPos);       boidTG.setTransform(t3d);   // move the TG     } // end of moveBoid(  ) 

The boid position and velocity vectors (boidPos and boidVel) are protected, so subclasses that need to access or change their values can do so easily. moveBoid( ) uses the current velocity to calculate a rotation around the y-axis, and positions the boid with boidPos. A limitation of moveBoid( ) is that the boid doesn't rotate around the x- or z-axes, which means a boid always remains parallel to the XZ plane. For example, a boid can't turn downward into a nose dive or lean over as it turns sharply. This restriction can be removed by adding extra TRansformGroup nodes above the boid's current transformGroup to handle the other forms of rotation.

Animating the Boid

animateBoid( ) is the top-level method for animating a boid and is called by the FlockBehavior class at each update for every boid. animateBoid( ) can be overridden by Boid subclasses (e.g., by PredatorBoid) to modify the animation activities.

animateBoid( ) begins with code related to boid perching, which is when a boid is stationary on the floor:

     // global constants for perching     private final static int PERCH_TIME = 5;   // how long to perch     private final static int PERCH_INTERVAL = 100;  // how long between perches             // global variables for perching     private int perchTime = 0;     private int perchInterval = 0;     private boolean isPerching = false;             public void animateBoid(  )     { if (isPerching) {         if (perchTime > 0) {           perchTime--;  // perch a while longer           return;       // skip rest of boid update         }         else {   // finished perching           isPerching = false;           boidPos.y = 0.1f;   // give the boid a push up off the floor           perchInterval = 0;  // reset perching interval         }       }       // update the boid's vel & posn, but keep within scene bounds       boidVel.set( calcNewVel(  ) );       boidPos.add(boidVel);       keepInBounds(  );       moveBoid(  );     } // end of animateBoid(  ) 

keepInBounds( ) contains the rest of the perching code:

     perchInterval++;     if ((perchInterval > PERCH_INTERVAL) &&          (boidPos.y <= MIN_PT.y)) {   // let the boid perch       boidPos.y = 0.0f;        // set down on the floor       perchTime = PERCH_TIME;  // start perching time       isPerching = true;     } 

Perching sessions occur at fixed intervals, and each session lasts for a fixed amount of time. During the PERCH_INTERVAL time, the boid must fly about, until the interval is met; then the boid can perch for PERCH_TIME time units before it must start flying again. animateBoid( ) is called repeatedly by the FlockBehavior object, and perchInterval records the number of calls. When the count exceeds the number stored in PERCH_INTERVAL, perching is initiated.

isPerching is set to true when perching starts, and perchTime is set to PERCH_TIME. Each time that animateBoid( ) is called after that, perchTime is decremented. When perchTime reaches 0, perching stops. The perchInterval counter is reset to 0, and the perching interval can start being measured off again.

This code illustrates how the timing of boid activities can be implemented using counters. This is possible since animateBoid( ) is called at fixed intervals by FlockingBehavior.

If the boid is not perching, then calcNewVel( ) calculates the boid's new velocity and updates boidVel and boidPos with this velocity. keepInBounds( ) checks these values to decide if they specify a new position for the boid outside the scene's boundaries. If they do, then the values are modified so that when they're applied to the boid, it will stay within the boundary. Back in animateBoid( ), the boid in the scene is moved by moveBoid( ).

Velocity Rules

calcNewVel( ) calculates a new velocity for a boid by executing all of the velocity rules for steering the boid. Each rule returns a velocity, and these velocities are summed by calcNewVel( ) to get a total.

An important design aim is that new velocity rules can be easily added to the system (e.g., by subclassing Boid), so calcNewVel( ) doesn't make any assumptions about the number of velocity rules being executed. Each velocity rule adds its result to a global ArrayList, called velChanges. calcNewVel( ) iterates through the list to find all the velocities.

Two other issues are obstacle avoidance and limiting the maximum speed. If the boid has collided with an obstacle, then the velocity change to avoid the obstacle takes priority over the other velocity rules. The new velocity is limited to a maximum value, so a boid cannot attain the speed of light, or something similar by the combination of the various rules:

     protected ArrayList velChanges = new ArrayList(  ); // globals     protected FlockBehavior beh;             private Vector3f calcNewVel(  )     { velChanges.clear(  );   // reset velocities ArrayList           Vector3f v = avoidObstacles(  );         // check for obstacles       if ((v.x == 0.0f) && (v.z == 0.0f))    // if no obs velocity         doVelocityRules(  );    // then carry out other velocity rules       else         velChanges.add(v);    // else only do obstacle avoidance           newVel.set( boidVel );     // re-initialise newVel       for(int i=0; i < velChanges.size(  ); i++)         newVel.add( (Vector3f)velChanges.get(i) );  // add vels            newVel.scale( limitMaxSpeed(  ) );       return newVel;     }  // end of calcNewVel(  )             protected void doVelocityRules(  )     // override this method to add new velocity rules     {       Vector3f v1 = beh.cohesion(boidPos);       Vector3f v2 = beh.separation(boidPos);       Vector3f v3 = beh.alignment(boidPos, boidVel);       velChanges.add(v1);       velChanges.add(v2);       velChanges.add(v3);     } // end of doVelocityRules(  ) 

avoidObstacles( ) always returns a vector even when there is no obstacle to avoid. The "no obstacle" vector has the value (0, 0, 0), which is detected by calcNewVel( ).

To reduce the number of temporary objects, calcNewVel( ) reuses a global newVel Vector3f object in its calculations.

doVelocityRules( ) has protected visibility so subclasses can readily extend it to add new steering rules. In addition to executing a rule, adding the result to the velChanges ArrayList is necessary. The three rules executed in Boid are Reynolds' rules for cohesion, separation, and alignment.

beh is a reference to the FlockBehavior subclass for the boid. Velocity rules that require the checking of flockmates, or boids from other flocks, are stored in the behavior class, which acts as the flock manager.

Obstacle Avoidance

Obstacle avoidance can be computationally expensive, easily crippling a flocking system involving hundreds of boids and tens of obstacles. The reason is two-fold: the algorithm has to keep looking ahead to detect a collision before the boid image intersects with the obstacle and, therefore, should calculate a rebound velocity that mimics the physical reality of a boid hitting the obstacle.

As usual, a trade-off is made between the accuracy of the real-world simulation and the need for fast computation. In Flocking3D, the emphasis is on speed, so there's no look-ahead collision detection and no complex rebound vector calculation. A boid is allowed to hit (and enter) an obstacle and rebounds in the simplest way possible.

The boid is represented by a bounding sphere, whose radius is fixed but center moves as the boid moves. The sphere is tested for intersection with all the obstacles, and if an intersection is found, then a velocity is calculated based on the negation of the boid's current (x, z) position, scaled by a factor to reduce its effect:

     private Vector3f avoidObstacles(  )     { avoidOb.set(0,0,0);   // reset       // update the BoundingSphere's position       bs.setCenter( new Point3d( (double)boidPos.x,                         (double)boidPos.y, (double)boidPos.z) );       if ( obstacles.isOverlapping(bs)) {         avoidOb.set( -(float)Math.random(  )*boidPos.x, 0.0f,                      -(float)Math.random(  )*boidPos.z);         // scale to reduce distance moved away from the obstacle         avoidOb.scale(AVOID_WEIGHT);       }       return avoidOb;     } 

There's no adjustment to the boid's y-velocity, which means that if it hits an obstacle from the top, its y-axis velocity will be unchanged (i.e., it'll keep moving downward) but it will change its x- and z-components.

Instead of creating a new temporary object each time obstacle checking is carried out, the code utilizes a global Vector3f object called avoidOb. The bs BoundingSphere object is created when the boid is first instantiated.

Staying in Bounds

keepInBounds( ) checks a bounding volume defined by two points, MIN_PT and MAX_PT, representing its upper and lower corners. If the boid's position is beyond a boundary, then it's relocated to the boundary, and its velocity component in that direction is reversed.

The following code fragment shows what happens when the boid has passed the upper x-axis boundary:

     if (boidPos.x > MAX_PT.x) {     // beyond upper x-axis boundary       boidPos.x = MAX_PT.x;         // put back at edge       boidVel.x = -Math.abs(boidVel.x);   // move away from boundary     } 

The same approach is used to check for the upper and lower boundaries along all the axes.

The Prey Boid

A prey boid has an orange body and wants to avoid being eaten by predators. It does this by applying a velocity rule for detecting and evading predators. It has a higher maximum speed than the standard Boid, so it may be able to outrun an attacker.

Since a PreyBoid can be eaten, it must be possible to detach the boid from the scene graph:

     public class PreyBoid extends Boid     {       private final static Color3f orange = new Color3f(1.0f,0.75f,0.0f);           public PreyBoid(Obstacles obs, PreyBehavior beh)       { super(orange, 2.0f, obs, beh);     // orange and higher max speed         setCapability(BranchGroup.ALLOW_DETACH);   // prey can be "eaten"       }           protected void doVelocityRules(  )       // Override doVelocityRules(  ) to evade nearby predators       { Vector3f v = ((PreyBehavior)beh).seePredators(boidPos);         velChanges.add(v);         super.doVelocityRules(  );       }  // end of doVelocityRules(  )           public void boidDetach(  )       { detach(  ); }     } 

The benefits of inheritance are clear, as it's simple to define PreyBoid. doVelocityRules( ) in PreyBoid adds a rule to the ones present in Boid and calls the superclass's method to evaluate those rules as well.

seePredators( ) is located in the PreyBehavior object, the manager for the prey flock. The method looks for nearby predators and returns a flee velocity. seePredators( ) is inside PreyBehavior because it needs to examine a flock.

The Predator Boid

A predator gets hungry. Hunger will cause it to do two things: eat a prey boid, if one is sufficiently close (as defined by the eatClosePrey( ) method), and trigger a velocity rule to make the predator subsequently pursue nearby prey groups:

     public class PredatorBoid extends Boid     { private final static Color3f yellow = new Color3f(1.0f, 1.0f,0.6f);       private final static int HUNGER_TRIGGER = 3;                            // when hunger affects behavior       private int hungerCount;           public PredatorBoid(Obstacles obs, PredatorBehavior beh)       { super(yellow, 1.0f, obs, beh);   // yellow boid, normal max speed         hungerCount = 0;       }            public void animateBoid(  )       // extend animateBoid(  ) with eating behavior       { hungerCount++;          if (hungerCount > HUNGER_TRIGGER)   // time to eat            hungerCount -= ((PredatorBehavior)beh).eatClosePrey(boidPos);          super.animateBoid(  );       }           protected void doVelocityRules(  )       // extend VelocityRules(  ) with prey attack       { if (hungerCount > HUNGER_TRIGGER) {  // time to eat           Vector3f v = ((PredatorBehavior)beh).findClosePrey(boidPos);           velChanges.add(v);         }         super.doVelocityRules(  );       }         } // end of PredatorBoid class 

Eating prey isn't a velocity rule, so it is carried out by extending the behavior of animateBoid( ). eatClosePrey( ) is located in PredatorBehavior because it examines (and modifies) a flock, which means that it's handled by the flock manager. The method returns the number of prey eaten (usually 0 or 1), reducing the predator's hunger.

The movement toward prey is a velocity rule, so it is placed in the overridden doVelocityRules( ) method. Since findClosePrey( ) is looking at a flock, it's carried out by PredatorBehavior.