Recently I’ve been trying to implement Craig Reynolds steering behaviors into my program, and as I’ve come up to obstacle avoidance, I’ve found it difficult to replicate his example. (Video of what I’m trying to make)
I’ve looked over various websites and papers, but I’ve been a bit confused about how to calculate the avoidance force. The avoidance force is the force that the vehicle needs to take to avoid an obstacle (Represented as circles).
Lots of websites use an ahead vector (a vector projected to the vehicles future location) to calculate it, but it doesn’t seem very realistic. Any questions, advice or tips are welcome.
There is a main axis defined by your system, from the center of your vehicle to the center of the obstacle.
There is also a heading, which is a secondary axis that is defined from the center of your vehicle to the tip of it.
If the heading aligns with the main axis, you are in a collision course. You need to apply a force that is:
Direction: Perpendicular to your motion, which is dictated by your heading.
The magnitude should be proportional to the distance between the center of your vehicle and the obstacle. Consider:
a) If the vehicle is really close to the obstacle, then you need to hurry and change the direction fast: You need a big force
b) If you are far away from the obstacle, then you need a small force that needs to be applied continuously until the vehicle is not in collision course anymore. Notice there is a minimum force that, if applied continuously, it will ensure you are not in collision if your vehicle moved toward the target during the same distance. However, you can apply a larger force which means that it will avoid the obstacle sooner.
Notice at the end, the force intensity that need to be applied to the vehicle depends on:
theta, the angle between the main axis and the heading
The distance between the vehicle and the obstacle
The speed of the vehicle (I am assuming the obstacle does not move)
This would be my approach. I have broken it down into steps and hopefully you can use this to create your algorithm. Sorry I couldn’t see your video. I have problems on this computer to access certain sites.
Thanks for your advice! I’ve gotten started on it now, and I’ve had a question about how to tell which direction the lateral force should be applied in. For example in this case:
To know the direction you might want to get the angle between the line that goes from your ship the the center of the object and the line that represent the direction of your ship:
Adding to @jb4x post, I think I would use the dot product to get the angle between the two axis. If you are using PVector, you could also use heading() for each axis which provides an angle and then subtract both angles. If you get a positive value, then the force is applied towards one side, negative then would be the opposite side.
In addition to .heading(), PVector has .dot() and .angleBetween(). If you have the centers of the two shapes and the tangent point then you could get the angleBetween of those two vectors to get the turning angle.
Interesting.
If the vehicle angle to the obstacle is 90-270 degrees then it is always good, no turning needed.
If the angle is exactly 0 it is always bad, and the vehicle could turn left or right arbitrarily.
Anything in-between 0-90 (or 270-0) will be bad IF the angle is less than the tangent line to the circle:
…but that tangent is constantly changing as the vehicle approaches, so then questions like how big / close / fast could come into play.
Is the goal to have different turning speeds for different situations, or are the number of degrees turned per frame fixed (i.e. keep turning away at a constant angular momentum until you are clear or crash)?
Right now I’m just applying a lateral force, but ideally, I’d want to have the forces vary based on different factors (distance to the obstacle, distance from obstacles center).
Currently, I have a problem trying to be able to have two forces acting on the boid. (Such as seeking and avoiding).
For example, if the boid is seeking mouseX and mouseY, when it avoids it the lateral force would make it turn away, but when it is turned away the avoidance force would no long be applied, so the seeking force would turn it back into the obstacle, and so on. This seems to result in a jittery and unrealistic movement.
The yellow cross is the desired position. One of the blue line is the current direction of the boids and the other one the straight path to the desired position.
As you can see, we are in a scenario where, for exemple, the boid were going straight into the obstacle but you applied a lateral force to make it avoid it so now it is not in the path of the obstacle anymore.
Now you can see that if no obstacle force is applied anymore, the boid will start following the straight path and hit the obstacle again so you will apply a new lateral force and so on and so on resulting in your jittery behavior.
Based on that you can have 2 kinds of avoidance behavior:
An obstacle is directly in the path of the boid: you can apply a force that is perpendicular to the boids (or it can also depends on the angle between your boid direction and the center of the obstacle if you want something more fancy)
An obstacle is not directly in the path of the boid but is if you consider the direct path to the target. In this case you can also apply an avoidance force but with different rules so it looks more organic.
I would also apply the previous rule only when close enough to an obstacle.
I think the first option will be more reliable in long-term, as I eventually would like a bunch of boids to wander while avoiding objects.
I’ve also been experimenting with making two lines that point 45º in each direction, and if there is an object colliding with either of the lines, don’t turn in that direction. Is that an efficient way of doing it?
I meant to use both of them in the same time. It would be like 2 mode of avoidance:
Direct avoidance when the boid head directly to the obstacle
Indirect avoidance when the boid do not head directly to the obstacle but the direct path to the target do
It is pretty excluding and you will find yourself with not taking into account all the obstacles that can be in between. Not sure it sill be really efficient.
The problem is that determining whether a rotated box (the detecting box) intersects with a circle (obstacle collision area) is not a trivial matter. It is even less trivial to determining the intersection coordinates, which are needed to calculate the lateral and breaking forces.
The trick here is to calculate the obstacle position in the boid’s coordinate space.
In this diagram the radius of the grey circles is the obstacle collision radius plus half the width of the detection box, we call this the extended collision radius.
So if we consider each obstacle in turn.
A we can ignore because it has a negative x position (i.e. behind the boid)
B we can ignore because it x position is greater than the detection box length plus the extended collision radius.(i…e. out of range)
C we can ignore because its absolute y position is greater than the extended collision radius.
D we must test this because its absolute y position is less than the extended collision radius.
The next step is to calculate the 2 intersection points between the extended collision radius and the x axis, x0 and x1. We iterate over possible obstacles and use the one with the closest intersection point i.e. smallest x0
The lateral force will be proportional to the obstacles collision radius minus its y position so that the force diminishes with the obstacle’s distance from the x axis. This force would also be inversely proportional to the obstacles x position so that it increases as we get closer to the obstacle.
Finally the breaking force will be inversely proportional to the distance x0 so it increases as the boid approaches the obstacle.
