Sorry your browser is not supported!

A couple of months ago Philip posted a bunch of code regarding autonomous steering behaviors (found here), and I found the thread and was really interested. Then, looking at the original paper, here, I saw the part about "Unaligned Collision Avoidance."

With normal (static) Obstace avoidance, line-sphere intersection is sufficient to calculate avoidance. However, unaligned collision avoidance, where both of the bodies in question are moving, is a little more complicated.

The obvious answer is to project the position of each vehicle a given distance in front on it's current position based on its velocity. However, when the vehicle turns, it will not detect vehicles that are too close.

So, I was wondering if anyone here had any ideas for how to do maybe cylinder-line intersection, or something similar which could efficiently calculate these kind of potential collisions.

A diagram from the original paper, demonstrating what I'm talking about:



Basically, I want to know when the two lines are closest to each other, so that the vehicles in question can manuver away from the point of potential collision. (this is in 3d, btw, not 2d, as the image suggests)

(Stops nibbling on a jam sandwich)

Hark! Do I hear my immortal name mention'd?



It is me! This is the droid, er I mean bear, that you are looking for. Take me to your leader.



Mathematically speaking, there are quite a few ways to do this. A quick hack way would be to treat one of the two movement vectors, such as the red line in your picture, as a plane, with the normal vector that describes the plane pointing towards the current position of the other object, namely green ship. Treat the green ship movement vector as being a vector and do a vector / plane collision test. Take the position at which the green vector hits the plane and then do a distance between point and red vector test. Then check if that distance is within the radius of the spheres.

Thats one idea.

If you want to go for a less bodged effort, you'll need to do a dynamic test. What I would suggest is that you treat both red and green objects as moving spheres. The usual approach is then to assume one sphere is stationary and to test against the movement of the other. The equation is then:

t = e dot d - sqrt( (e dot d)2 + radius2 - e dot e)

where

t is the time when intersection occurs

e is the vector described by position of stationary sphere minus the position of the moving sphere

d is the normalised vector describing the DIFFERENCE of the two movement vectors of the two spheres (moving sphere vector minus stationary sphere vector)

the 2s are supposed to be squareds

radius is the combined radius of the two spheres

Note:

if the value inside the sqrt is negative, there is no intersection

If you want to know how this works (and check my math), its worth doing a few google searches. Or look at page 289 and page 290 of Fletcher Dunn and Ian Parberry's 3d Math Primer for Graphics and Game Development

Awesome, that helps a ton!

And, just for clarification:

e is the difference in position of the bodies, and

d is a normalized vector representing how fast the bodies are approaching each other? (difference in velocities)

(also, btw, is there a normalize() function in dbpro?)

EDIT: nevermind, just found normalize vector3

Okay, so one final question:

Will this equation ever give a negative value of t?

Yes, theoretically it can. But only if the collision does not occur within the time being considered. Bear in mind that is only a problem if you de-construct the quadratic equation back to:

0 = t2 - 2(e dot d)t + e dot e - r2

because with the equation posted originally above you are finding t.

If t = 0 that means there is an instant collision.

I just ask because I want to have a function for this, and I want to specify that any return value of less than 0 means that there is no imminent collision, so I just needed to make sure that a negative value of t won't be returned when I don't expect it - thanks!