Steering Behaviors: Flocking

Posted by: rocketman on October 08, 2010

The next post steering behaviors series is unaligned collision avoidance. We will be using the Vector2D.as and Vehicle.as classes for this. You will need these classes for the this post. This post is based on Craig Reynold’s article Steering Behaviors For Autonomous Characters.

Flocking is created by combining several steering behaviors: Separation, Cohesion and Alignment.

 

 

 


Spearation

Separation


Separation is similar to Unaligned Collision Avoidance. This behavior keeps the vehicles a certain distance away from others. This keeps the vehicles from colliding and crowding to close together.

To calculate separation, check each vehicle against the other vehicles. If the vehicles are too close, repel it using a force based on how close together the vehicles are.

Simply find the too close vehicles and flee them.

Each vehicle adds up all the repelling forces to create the steering force.


 

Cohesion

Cohesion


Cohesion is the force that keeps the vehicles together. When a vehicle finds itself far away from other vehicles, it moves towards the group. Each vehicle moves towards the others to form a group. Separation keeps them from "merging" into one vehicle.

Each vehicle looks for the near-by vehicles, just like in separation. Then it finds the center of the group (the average of the positions). The vehicle steers towards the center position.

Once the center position is found, you can simply seek that position.


Alignment

Alignment


Alignment makes the vehicles line up and head the same direction. Vehicles align with the vehicles around them.

To calculate alignment, first find all the vehicles nearby. Average the vehicles velocities together to get the average velocity. Apply this force to get all the vehicles to align.

The average velocity is the direction all the surrounding vehicles are traveling. When this is applied to the current vehicle, it aligns itself with the other vehicles.

Flocking


Now that we know the three components of flocking, it's time to combine them to produce a flock.

public function flock(vehicles:Array):void {
var averageVelocity:Vector2D = velocity.cloneVector(); // used for alignment.
//starting with the current vehicles velocity keeps the vehicles from stopping
var averagePosition:Vector2D = new Vector2D(); //used for cohesion
var counter:int = 0;//used for cohesion
for(var i:int = 0; i < vehicles.length; i++) {//for each vehicle
var vehicle:Vehicle = vehicles[i] as Vehicle;
if(vehicle != this && isInSight(vehicle)) {//if it is not the current vehicle
//and it is in sight
averageVelocity.add(vehicle.velocity); //add its velocity to the average velocity
averagePosition.add(vehicle.position);//add its position to the average position
if(isTooClose(vehicle)) {//if it is too close
flee(vehicle.position);//flee it, this is separation
}
counter++;//increase the counter to use for finding the average
}
}
if(counter > 0) {//if there are vehicles around
averageVelocity.divide(counter);//divide to find average
averagePosition.divide(counter);//divide to find average
seek(averagePosition);//seek the average, this is cohesion
velocity.add(averageVelocity.subtract(velocity).divide(mass).truncate(_maxForce));
//add the average velocity to the velocity after adjusting the force
//this is alignment
}
}

There's a few references to other functions in there.

First, isInSight. This checks whether the vehicle is close to the current vehicle. If it is, we use it to find averages.

public function isInSight(vehicle:Vehicle):Boolean {
if(position.distance(vehicle.position) > 120) {//this is changed based on the desired flocking style
return false;//you are too far away, do nothing
}
var direction:Vector2D = velocity.cloneVector().normalize();//get the direction
var difference:Vector2D = vehicle.position.cloneVector().subtract(position);//find the difference of the two positions
var dotProd:Number = difference.dotProduct(direction);//dotProduct
if(dotProd < 0) {
return false;//you are too far away and not facing the right direction
}
return true;//you are in sight.
}

The other function is isTooClose.

public function isTooClose(vehicle:Vehicle):Boolean {
return position.distance(vehicle.position) < 80;
}

This returns whether the vehicle is within a certain distance. If it is too close, you flee it, which is separation.
Click here to watch flocking

2DMathSteering BehaviorVector

Current rating: 5


Comments

  • Vinodkumar KN 3 years, 11 months ago

    I've been looking through the book "Programming Game AI through example" and it says somethings about combining all the forces and giving priorities etc.. But I need your help..
    Thanks.

    Link / Reply
  • Vinodkumar KN 3 years, 11 months ago

    There is a difficulty in combining nonlinear avoidance, separation and wander. The seperation is not working .. When the vehicles come nearer, the separation(fleeing) causes them to disappear.\r\nThere is some 1/r parameter in the steering behaviour "manuscripts".. but you are just fleeing them..\r\nCan you give me an example how to combine these in the correct way?\r\n\r\nAnd also I'd also like to see how containment is implied.

    Link / Reply
  • Vinodkumar KN 3 years, 11 months ago

    I may have to include priority and weights to behave it correctly..

    Link / Reply
  • rocketman 3 years, 11 months ago

    I'll have to think about the best way to combine those behaviors, by nonlinear avoidance, you are referring to <a href="http://rocketmandevelopment.com/2010/07/23/steering-behaviors-unaligned-collision-avoidance/" rel="nofollow">unaligned collision avoidance</a>, right?
    For the 1/r, I saw that too. You could use that to calculate the force to repel away from the other vehicle, but I found it easier to simply flee it. It works fine and it's easy so I used it.
    What do you mean by containment? Keeping the vehicles on the screen or do you want to contain vehicles in a smaller shape?

    Link / Reply
  • Vinodkumar KN 3 years, 11 months ago

    Containment means keeping vehicles inside a certain shape.
    Refer here: red3d.com/cwr/steer/Containment.html
    For the separation behavior I had to change
    flee(vehicle.position) to flee(vehicle.position.cloneVector()). It is working, however because there is no weight or priority applied, they changes directions more frequently resulting in a non-realistic movement. The movement can be smoothed by adding acceleration. I'm trying this- Refer here: baileydan.com/Projects/Abundance/steeringbehaviours.html
    Also when doing this we've to make sure the vehicles won't overlap in any circumstances - the vehicles, if they started to overlap must be moved apart without taking their mass or velocity into account.
    Programming Game AI by example is a great book that includes all the things for this 'agents'.. But it is in C++. I can understand somethings because I know some C.. but I couldn't port it to AS3..

    Link / Reply
  • Vinodkumar KN 3 years, 11 months ago

    Containment means keeping vehicles inside a certain shape.
    For the separation behavior I had to change
    lee(vehicle.position) to flee(vehicle.position.cloneVector()). It is working, however because there is no weight or priority applied, they changes directions more frequently resulting in a non-realistic movement. The movement can be smoothed by adding acceleration. I'm trying a this.
    Also when doing this we've to make sure the vehicles won't overlap in any circumstances - the vehicles, if they started to overlap must be moved apart without taking their mass or velocity into account.
    Programming Game AI by example is a great book that includes all the things for this 'agents'.. But it is in C++. I can understand somethings because I know some C.. but I couldn't port it to AS3..
    How can I add some url links here so that I can show you some site references regarding this..

    Link / Reply
  • Vinodkumar KN 3 years, 11 months ago

    Not perfect, but they don't overlap..
    public function seperate(vehicles:Array,penetrationConstraint:Boolean=false):void
    {
    for (var i:int = 0; i &lt; vehicles.length; i++) { //check each vehicle
    if (vehicles[i] == this) { continue; }
    if (isTooClose(vehicles[i])) {//if it is too close flee(vehicles[i].position.cloneVector()); } if(penetrationConstraint){ if (position.distance(vehicles[i].position) &lt; (radius + vehicles[i].radius)) { var distance:Vector2D = vehicles[i].position.cloneVector().subtract(position); var dist:Number = distance.lengtht; var overlapAmount:Number = radius + vehicles[i].radius - dist; var calculatedPosition:Vector2D = distance.divide(dist).multiply(overlapAmount); vehicles[i].position.add(calculatedPosition.multiply(.1)); } } } }

    nAnd also for smoothing animations...\\r\\n\\r\\npublic function update():void {\\r\\n _velocity.add(_acceleration.multiply(.1));\\r\\n _velocity.truncate(_maxSpeed);\\r\\n _position = _position.add(_velocity);\\r\\n... \\r\\n...\\r\\n...\\r\\n}\\r\\n\\r\\nAnd on every velocity update, use acceleration instead velocity. Like this..\\r\\n\\r\\npublic function seek(target:*):void\\r\\n {\\r\\n var desiredVelocity:Vector2D = target.subtract(position).normalize().multiply(maxSpeed);\\r\\n var steeringForce:Vector2D = desiredVelocity.subtract(velocity);\\r\\n acceleration.add(steeringForce.divide(mass));\\r\\n }

    Link / Reply

New Comment

required
required (not published)
optional
  • Back in July, we looked at how to use Ray Casting for collision detection. We also learned how to use the Separation of Axis Theorem. I recently had a request for a way to use the Shapes we created here with the Ray Casting method. First, lets do a quick review of the shape classes. read more
    3 years, 8 months ago
  • Today we will finally be detecting a collision with SAT. We know how SAT works, we've built classes to work with SAT, now we can use all of this to detect a real, live collision! read more
    3 years, 11 months ago
  • A few months ago, I posted on the separation of axis theorem. You can learn all about SAT and how it works here. What that post failed to do was use the SAT. We will explore using SAT for collision detection in this post. read more
    3 years, 11 months ago
  • Some of you have asked for the entire steering behavior source as well as the A* source. Here is the zip with all the classes. In there is the vehicle... read more
    3 years, 11 months ago
  • In the last three posts, we explored the how A* works, then we put A-star into code, then we looked at different heuristics for A*. Now we will combine A*... read more
    3 years, 11 months ago
RSS / Atom