#AltDevBlogADay

First off, I should say that I’m a huge fan of Craig Reynolds. Both for his pioneering work in the field of what has become known as Steering as well as for his contribution to the field of emergence. His idea that the combination of simple behavioural rules can explain and give rise to complex phenomena (like flocking) was a revelation to me. I do think, however, that we can improve on the specifics of some of his basic behavioural building blocks. It is well known, for example, that collision avoidance is not handled very well by simple steering behaviours and that more advanced techniques like reciprocal velocity objects are better suited, but that subject is far beyond the scope of this post. What I want to talk about today is one of the fundamental composite steering behaviours that is almost considered inviolate – the separation behaviour.

The basic algorithm can be summed up in this diagram. The real question we will deal with below is how should we scale the red vector?

Flocking is typically composed of 3 basic steering behaviours: separation, cohesion, and alignment. The separation force simply computes a force that tries to maintain distance from an entity’s nearest neighbours. Unlike the other two forces separation is useful for more than just flocking. Basically it is useful in any situation where entities are trying to maintain space around them (people milling about in a crowd, standing in an elevator, or even gathering around a fist fight, for example).

One of the most important things to consider when trying to achieve high visual fidelity for your characters is removing discontinuities in motion – the dreaded “pop”. Usually, the physics simulation and animation system are able to smooth out many discontinuities, but they usually can’t get rid of them all. Oscillating discontinuities are especially difficult to get rid of and very noticable. Smoothing out these pops is also more difficult if the entities must be very responsive to input or may travel freely in any direction (like with a biped as opposed to a vehicle). Generally speaking, the fewer discontinuities in the AI’s output the better.

Basically our edict is this: as the positions of entities smoothly change the forces that act on them should also smoothly change.

In most flocking simulations there is a strong physical sim constraining the motion of the boids, but even so if you look closely you can quite clearly see boids abruptly adjust their flight path as other boids enter and exit their neighbourhood. This neighbourhood is simply a fairly small radius around the entity. Obviously we don’t compute forces from every entity to every other entity and so there is a fairly close horizon beyond which other entities are ignored. Interestingly, most of the cost of a flocking simulation is simply deciding which boids are in which neighbourhood.

So how does the stock separation behaviour function with our regard to smoothly changing forces? Unfortunately, not very well. The first problem is that the force from each entity is discontinuous with respect to the radius that each is considered at, but tweaking the repulsion force is the subject of my next post. The more fundamental problem deals with how multiple repulsive forces from different entities are combined to generate a steering force to move away from them. The essence of the original algorithm is this (written inefficiently for clarity):

int numNeighbours = 0;
 
  static const float maxNeighbourDist = 4.f;
 
  Vector3 steer(0.f, 0.f, 0.f);
 
   
 
  for(unsigned int i = 0; i < entities.size(); ++i)
 
  {
 
      Vector3 fromNeighbour = parentEntity.position() - entities[i].position();
 
      float dist = fromNeighbour.magnitude();
 
      if( dist < maxNeighbourDist )
 
      {
 
          float force = SeparationForce( dist );
 
          fromNeighbour.normalize();
 
          steer += (fromNeighbour * force);
 
          ++numNeighbours;
 
      }
 
  }
 
   
 
  if( numNeighbours > 0 )
 
  {
 
      steer /= numNeighbours;
 
      steer.normalize();
 
  }

Now this code isn’t gospel, the original paper only describes the forces from each neighbor and not how they are to be combined, but it appears this way in most implementations including the OpenSteer library which is endorsed by Reynolds. Now I’ve never understood why there is a divide by numNeighbours followed by a normalize, my guess is that the normalize was just added later to fix a problem that dividing by numNeighbours wasn’t handling. Regardless, the normalize at the end means that the minute we have an entity enter or exits our neighbourhood we have a huge discontinuity as this force appears and disappears.

So why don’t we just avoid the normalize at the end? There is no requirement that the force being returned must be normalized or even be less than one. Scaling factors are often applied when combining this normalized output with other steering forces. Not normalizing would be nice because distant entities would only result in very small forces being applied to the entity. However, we are now left with dividing the steering vector by numNeighbours. Something like this is required because we might be summing multiple forces all pushing in the same direction and the resultant vector shouldn’t be overly large (you wouldn’t back up three times as fast from three people walking towards you as you would from one). The problem with this divide by numNeighbours is that as every entity enters and exits the neighbourhood the resultant vector is scaled differently even if their force contribution is tiny (even though it would hardly affect the direction of the vector at all it can drastically alter the magnitude of the vector).

So can we do better? Obviously once we are aware of the problem solutions aren’t terribly difficult to come up with. I typically use two different methods to resolve the problems outlined above. Which solution is more applicable really depends on what your requirements are and what your repulsive forces look like.

So what are our requirements?

1. distant entities should not affect the output force much



2. multiple entities pushing in the same direction (like a wall of entities) should result in a very dominant direction but not one whose magnitude is especially large



3. Optional: large repulsive forces (greater than one) should be able to result in similarly scaled output forces

Now the third requirement is not too common, large repulsive forces will still dominate the direction of output, but large outputs are usually not desirable (the output of 1/x functions when x is less than one for example). But assuming your repulsive force is well behaved this magnitude can be useful. Sometimes forces greater than one are useful to temporarily override the other types of steering behaviours in your system.

Now the first method simply keeps track of the total force being summed over all iterations of the loop and instead of dividing by numNeighbors you divide by the sum of the magnitude of all the forces (this is of course only done if the force is greater than one). This ensures that the resultant force never exceeds one, and that small forces stay small.

So how does our loop change? Well very little actually:

float totalForce = 0.f;
 
  static const float maxNeighbourDist = 4.f;
 
  Vector3 steer(0.f, 0.f, 0.f);
 
   
 
  for(unsigned int i = 0; i < entities.size(); ++i)
 
  {
 
      Vector3 fromNeighbour = parentEntity.position() - entities[i].position();
 
      float dist = fromNeighbour.magnitude();
 
      if( dist < maxNeighbourDist )
 
      {
 
          float force = SeparationForce( dist );
 
          fromNeighbour.normalize();
 
          steer += (fromNeighbour * force);
 
          totalForce += force;
 
      }
 
  }
 
   
 
  if( totalForce > 1.f )
 
  {
 
      steer /= totalForce;
 
  }

One property of this method is that large repulsive forces from an entity (greater than one) can never result in a large resultant steering force The maximum magnitude is one. The other property is that if there are repulsive forces in opposite directions resulting in an output vector that is small then this divide by totalForce will make it even smaller. This can be the opposite of what you want (if you are primarily concerned with getting out of trouble), or it can be exactly what you want if your primary goal is stability in large crowds. Be aware that as you add more people surrounding your character the output vector will get smaller and smaller. This can be objectionable if there is a clear opening out of the surrounding group and the entity in question doesn’t move very strongly to exit out of it, but it does provide the effect that as you become more surrounded you are more constrained.

This point brings us to the other method which will instead result in an entity acting much more strongly to strongly move out of that same situation. The idea is that you keep track of the largest repulsive force used and then truncate the output vector by that amount. The rationale is that forces are still allowed to cancel out, that walls of entities won’t result in combined forces that exceed any of the individual contributions, that any single repulsive force is left alone (regardless of magnitude), and that adding more entities into the neighborhood won’t necessarily affect the magnitude of the output vector (due to scaling that is, they could still cancel each other out if they are in roughly opposite directions).

float maxForce = 0.f;
 
  static const float maxNeighbourDist = 4.f;
 
  Vector3 steer(0.f, 0.f, 0.f);
 
   
 
  for(unsigned int i = 0; i < entities.size(); ++i)
 
  {
 
      Vector3 fromNeighbour = parentEntity.position() - entities[i].position();
 
      float dist = fromNeighbour.magnitude();
 
      if( dist < maxNeighbourDist )
 
      {
 
          float force = SeparationForce( dist );
 
          fromNeighbour.normalize();
 
          steer += (fromNeighbour * force);
 
          maxForce = Max(force, maxForce);
 
      }
 
  }
 
   
 
  steer.truncate(maxForce);

The function truncate() just limits that the magnitude of a vector to a given value.

The main property of the truncate method is that you are more likely to have a large output force if you have many forces acting on the entity and that adding more entities into an entity’s neighborhood won’t result in smaller output vector. If you are more interested in movement (versus stability) and having entities get out of the way or get out of trouble then the truncate method is superior.

I should also mention that other options are also valid, it really requires testing in your particular problem domain. Two variants to the methods above that represent some middle ground between the two would be

1. truncate to length one (removes overly large forces but preserves small ones)
2. scaling the total force by the single largest component force before dividing the output vector by the this force (this preserves the general scale of the component forces)

Anyway, I hope you’ve enjoyed this glimpse at the dark underbelly of steering systems. Next time I’ll go into more detail on the actual repulsive force.