Chapter 23. Shooting a Gun


Grouping the Boids

The FlockBehavior class is a flock manager and, consequently, must maintain a list of boids. The obvious data structure for the task is an ArrayList , but there's a subtle problem: boids may be deleted from the list, as when a prey boid is eaten. This can cause synchronization problems because of the presence of multiple behavior threads in the application.

For example, the PredatorBehavior thread may delete a prey boid from the prey list at the same time that PreyBehavior is about to access the same boid in the list. The solution is to synchronize the deleting and accessing operations so they can't occur simultaneously . This is the purpose of the BoidsList class:

public class BoidsList extends ArrayList
    {
      public BoidsList(int num)
      {  super(num);  }
   
      synchronized public Boid getBoid(int i)
      // return the boid if it is visible; null otherwise
      { if (i < super.size(  ))
          return (Boid)get(i);
        return null;
      }
   
     synchronized public boolean removeBoid(int i)
     // attempt to remove the i'th boid
     { if (i < super.size(  )) {
          super.remove(i);
          return true;
       }
       return false;
     }
   
    }  // end of BoidsList class

Another consequence of the dynamic change of the boids list is that code should not assume that the list's length stays the same. This means, for instance, that for loops using the list size should be avoided. If a for loop was utilized, then a change in the boids list may cause a boid to be processed twice, or skipped , because of its index position changing.


Flock Behavior

The public and protected methods and data of the FlockBehavior class and its PredatorBehavior and PreyBehavior subclasses are shown in Figure 22-7.

Figure 22-7. FlockBehavior and its subclasses

FlockBehavior has two main tasks :

  • To call animateBoid( ) on every boid periodically

  • To store the velocity rules, which require an examination of the entire flock

FlockBehavior doesn't create boids since that's handled by its subclasses, and the information required for each type of boid is too specialized to be located in the superclass. PredatorBehavior creates a series of PredatorBoid s, and PreyBehavior handles PreyBoid s. But the subclass behaviors do use the inherited boidsList list for storage.

Animate the Boids

The calls to animateBoid( ) are carried out in processStimulus( ) :

public void processStimulus(Enumeration en)
    { Boid b;
      int i = 0;
      while((b = boidsList.getBoid(i)) != null) {
        b.animateBoid(  );
        i++;
      }
      wakeupOn(timeOut);   // schedule next update
    }

Velocity Rules Again

FlockBehavior is a general-purpose flock manager, so it stores the basic velocity methods used by all boids: Reynolds' cohesion, separation, and alignment rules. All the rules have a similar implementation since they examine nearby flockmates and build an aggregate result. This is converted into a velocity and scaled before being returned.

As explained at the start of this chapter, Reynolds' notion of flockmates is based on a distance measure and an angle around the forward direction of the boid. However, the rules in Flocking3D only utilize the distance value, effectively including flockmates from all around the boid. The angle measure is dropped because of the overhead of calculating it and because the behavior of the boids seems realistic enough without it. A boid using an angle component is only influenced by the boids within its field of vision. The general effect is that a flock is more affected by changes to boids near the front and less affected by changes toward the back.

The cohesion( ) method is shown below. It calculates a velocity that encourages the boid to fly toward the average position of its flockmates:

public Vector3f cohesion(Vector3f boidPos)
    { avgPosn.set(0,0,0);     // the default answer
      int numFlockMates = 0;
      Vector3f pos;
      Boid b;
   
      int i = 0;
      while((b = boidsList.getBoid(i)) != null) {
        distFrom.set(boidPos);
        pos = b.getBoidPos(  );
        distFrom.sub(pos);
        if(distFrom.length(  ) < PROXIMITY) {   // is boid a flockmate?
          avgPosn.add(pos); // add position to tally
          numFlockMates++;
        }
        i++;
      }
      avgPosn.sub(boidPos);     // don't include the boid itself
      numFlockMates--;
   
      if(numFlockMates > 0) {   // there were flockmates
        avgPosn.scale(1.0f/numFlockMates);   // calculate avg position
        // calculate a small step towards the avg. posn
        avgPosn.sub(boidPos);
        avgPosn.scale(COHESION_WEIGHT);
      }
      return avgPosn;
    }

avgPosn and distPosn are global Vector3f objects to reduce the creation of temporary objects when the method is repeatedly executed. The while loop uses getBoid( ) to iterate through the boids list. The loop's complexity is O( n ) , where n is the number of boids. Since the method is called for every boid, checking the entire flock for cohesion is O( n 2) . If there are m velocity rules, then each update of the flock will have a complexity of O( m * n 2) . This is less than ideal and one reason why flocking systems tend to have few boids.

A well-designed boids list data structure will reduce the overhead of the calculations; for example, one simple optimization is to utilize boid position in the list's ordering. A search algorithm using spatial information should find a nearby boid in constant time ( O(1) ), reducing the cost of a flock update to O( m * n ) . For example, if there are 1,000 boids and 10 rules, then the current algorithm takes time proportional to O(107) , whereas the improved version would be O(104) , potentially a 1,000-fold improvement

In cohesion( ) , nearness is calculated by finding the absolute distance between the boid ( boidPos ) and each neigboring boid. The PROXIMITY constant can be adjusted to change the number of neighbors.

The choice of scaling factor ( COHESION_WEIGHT in this case) is a matter of trial and error, determined by running the system with various values and observing the behavior of the flock. Part of the difficulty when deciding on a good value is that the rules interact with each other to produce an overall effect. For example, the cohesion rule brings boids together while the separation rules keep them apart. This interplay is what makes boid behavior hard to predict and so interesting.

The Prey's Behavior

PreyBehavior has three tasks:

  • To create boids (e.g., PreyBoid s) and store them in the boids list

  • To store the velocity rules specific to PreyBoid s, which require an examination of the entire flock

  • To delete a PreyBoid when a predator eats it

Boid creation is done in createBoids( ) , called from the class's constructor:

private void createBoids(int numBoids, Obstacles obs)
    { // preyBoids can be detached from the scene
      boidsBG.setCapability(BranchGroup.ALLOW_CHILDREN_WRITE);
      boidsBG.setCapability(BranchGroup.ALLOW_CHILDREN_EXTEND);
   
      PreyBoid pb;
      for(int i=0; i < numBoids; i++){
        pb = new PreyBoid(obs, this);
        boidsBG.addChild(pb);   // add to BranchGroup
        boidsList.add(pb);      // add to BoidsList
      }
      boidsBG.addChild(this);   // store the prey behavior with its BG
    }

boidsBG is the inherited BranchGroup holding the boids in the scene; boidsBG 's capabilities must allow changes to its children so prey boids can be detached from it at run-time (after they're eaten).

When a PreyBoid object is created, it's passed a reference to the obstacles (passed to the behavior from WrapFlocking3D ) and a reference to the behavior itself, so its velocity rules can be accessed.

createBoid( ) creates a scene branch such as that shown in Figure 22-8.

Figure 22-8. Scene branch for PreyBoid nodes

Velocity Rules and Other Flocks

PreyBehavior 's second task is complicated by the need to access the other flock (the predators), which means that it must reference the PredatorBehavior object. WrapFlocking3D delivers the reference via PreyBehavior 's setPredBeh( ) :

public void setPredBeh(PredatorBehavior pb)
    { predBeh = pb; }

predBeh is a global, used by the seePredators( ) velocity rule.


seePredators( ) is coded in a similar way to the rules in FlockBehavior : a loop tests each of the boids in the predator flock for proximity. If a predator is within range, the velocity will be set to a scaled move in the opposite direction:

public Vector3f seePredators(Vector3f boidPos)
    {
      predsList = predBeh.getBoidsList(  );  // refer to pred list
      avoidPred.set(0,0,0);  // reset
      Vector3f predPos;
      PredatorBoid b;
   
      int i = 0;
      while((b = (PredatorBoid)predsList.getBoid(i)) != null) {
        distFrom.set(boidPos);
        predPos = b.getBoidPos(  );
        distFrom.sub(predPos);
        if(distFrom.length(  ) < PROXIMITY) {   // is pred boid close?
          avoidPred.set(distFrom);
          avoidPred.scale(FLEE_WEIGHT);  // scaled run away
          break;
        }
        i++;
      }
      return avoidPred;
    } // end of seePredators(  )

An important difference in this code from earlier rules is the first line, where a reference to the predators list is obtained by calling getBoidsList( ) in PredatorBehavior . The prey examine this list to decide if they should start running.

Goodbye Prey

PreyBehavior contains an eatBoid( ) method, called by PredatorBehavior when the given boid has been eaten:

public void eatBoid(int i)
    { ((PreyBoid)boidsList.getBoid(i)).boidDetach(  );
      boidsList.removeBoid(i);
    }

eatBoid( ) deletes a boid by detaching it from the scene graph, and removing it from the boids list.

The Predator's Behavior

PredatorBehavior has similar tasks to PreyBehavior :

  • To create its boids (e.g., PredatorBoid s) and store them in the boids list

  • To store the velocity rules specific to PredatorBoid s, which require an examination of the entire flock

  • To eat prey when they're close enough

Boid creation is almost identical to that done in PreyBehavior , except that PredatorBoid s are created instead of PreyBoid s. PredatorBoid has a method, setPredBeh( ) , which allows WrapFlocking3D to pass it a reference to the PreyBehavior object .

The velocity rule is implemented by findClosePrey( ) : the method calculates the average position of all the nearby PreyBoid s and moves the predator a small step toward that position. The code is similar to other rules, except that it starts by obtaining a reference to the prey list by calling getBoidsList( ) in PreyBehavior .

preyList = preyBeh.getBoidsList(  );  // get prey list
    int i = 0;
    while((b = (PreyBoid)preyList.getBoid(i)) != null) {
      pos = b.getBoidPos(  );  // get prey boid position
      // use pos to adjust the predator's velocity
    }

Lunch Time

The third task for PredatorBehavior eating nearby preyisn't a velocity rule but a method called at the start of each predator's update in animateBoid( ) . However, the coding is similar to the velocity rulesit iterates through the prey boids checking for those near enough to eat:

public int eatClosePrey(Vector3f boidPos)
    { preyList = preyBeh.getBoidsList(  );
      int numPrey = preyList.size(  );
      int numEaten = 0;
      PreyBoid b;
   
      int i = 0;
      while((b = (PreyBoid)preyList.getBoid(i)) != null) {
        distFrom.set(boidPos);
        distFrom.sub( b.getBoidPos(  ) );
        if(distFrom.length(  ) < PROXIMITY/3.0) { // boid v.close to prey
          preyBeh.eatBoid(i);   // found prey, so eat it
          numPrey--;
          numEaten++;
          System.out.println("numPrey: " + numPrey);
        }
        else
          i++;
      }
      return numEaten;
    } // end of eatClosePrey(  )

The reference to PreyBehavior is used to get a link to the prey list and to call eatBoid( ) to remove the i th boid. When a boid is removed, the next boid in the list becomes the new i th boid, so the i index mustn't be incremented.