Steering Behaviors: Unaligned Collision Avoidance

Posted by: rocketman on July 23, 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.

Unaligned Collision Avoidance, click to watch.

Unaligned Collision Avoidance tries to keep vehicles from colliding with each other. Think of a crowded city. There are a lot of people moving around, but no one runs into someone else. If a person detects a approaching collision, he will steer away from the potential collision. The more crowded an area, the closer a person looks. The less crowded an area is, the further away a person searches for a collision. Using the behavior, the look ahead distance can change based on density of vehicles. That is what this steering behavior tries to simulate.

To do this, each vehicle looks at every other vehicle. It uses the velocity to determine if the two will collide. If a collision will happen, it takes action to avoid the collision.

In code, its quite similar to obstacle avoidance, except it uses velocities in the projection.

public function unalignedAvoidance(vehicles:Array):void {
for(var i:int = 0; i < vehicles.length; i++) { //check each vehicle
var forward:Vector2D = velocity.cloneVector().normalize(); //get the forward vector
var diff:Vector2D = vehicles[i].position.cloneVector().add(vehicles[i].velocity.cloneVector().normalize().multiply(checkLength)).subtract(position);

That line is an important one. First it takes the other vehicle's position. Then it adds its velocity in the length we are checking (this could be time based as well, just multiply velocity by time instead of normalizing it). Finally, it subtracts the current vehicles position to get the difference between the two.

var dotProd:Number = diff.dotProduct(forward);//dot product between forward and difference
if(dotProd > 0) {//they may meet in the future
var ray:Vector2D = forward.cloneVector().multiply(checkLength); //cast a ray in the forward direction
var projection:Vector2D = forward.cloneVector().multiply(dotProd); //project the forward vector
var dist:Number = projection.cloneVector().subtract(diff).length; //get the distance
if(dist < vehicles[i].radius + width && projection.length < ray.length) { //they will meet in the future, we need to fix it
var force:Vector2D = forward.cloneVector().multiply(maxSpeed);//get the maximum change
force.angle += diff.sign(velocity) * Math.PI / 4;//rotate it away from the site of the collision
force.multiply(1 - projection.length / ray.length);//scale it based on the distance between the position and collision site
velocity.add(force);//adjust the velocity
velocity.multiply(projection.length / ray.length);//scale the velocity
}
}
}
}

This will stop most collisions, but it isn't perfect, especially around the edges of the screen. The vehicles currently don't look over the edges for potential collisions, so when the wrap around the edge, there may be a collision. This is easily fixable in two ways. Either make it so the vehicles don't wrap around the edges or vehicles look around the edges.

Click here to see unaligned collision avoidance in action.

2DMathSteering BehaviorVector

Currently unrated


Comments

  • Konstantin 4 years, 1 month ago

    Great site :) But it lacks a couple of things.
    I've looked thru all of your AI tuts, but there's no tuts on combination of 2 or more behaviors. I think it would be great if you create, for example, a combination of pursue and obstacle avoidance behaviors :)
    The combinations of them are probably the most annoying parts for the beginners. And even thought I'm not a beginner, it still causes me some troubles from time to time

    Link / Reply
  • rocketman 4 years ago

    I was planning on doing some on combining the steering behaviors, and will be doing some posts on it shortly.

    Link / Reply
  • P48l0 2 years, 2 months ago

    Very usefull article, thanks a lot! It was very clear and easy to follow.

    Link / Reply
  • keyone 1 year, 7 months ago

    Why do we calculating dist if we have difference, isn't that the same thing?

    Link / Reply
  • keyone 1 year, 7 months ago

    Why do we calculating dist if we have difference, isn't that the same thing

    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