Algorithm to find whether 2 objects on a 2D Plane will collide

Question

I'm trying to determine whether Object1 will collide with Object2 given the following information:

1) Objects' bounding boxes (uses bounded-box collision detection)

2) Objects' speeds

3) Object's current locations (x, y coordinate)

4) Objects' directions (Up, Down, Left, or Right)

For a bit of imagery, imagine the objects traveling on a 2D grid, and they can only move on the lines of that grid.

So given the above information, I need an efficient, but readable algorithm to determine whether those objects will collide. By efficient I mean constant time with time spent on computations minimized. Psuedocode or a link is fine.

Answer 1

First, find the time interval during which the boxes will overlap on the X axis. Second, find the time interval during which the boxes will overlap on the Y axis. Finally, check if the two time intervals overlap. If so, the earliest point in time that is in both intervals is the moment they are going to collide.

Answer 2

What you are looking for is called "Separating Axis test for moving convex Objects".

Here is a link to google books that explains the details:

http://books.google.de/books?id=WGpL6Sk9qNAC&pg=PA219&lpg=PA219&dq=separating+axis+test+movement&source=bl&ots=Pl5MmM1bfQ&sig=_1VXYm5WFaV9AFj0ws63SAPtjck&hl=de&ei=coVVTML3BtGVOI26oJ8O&sa=X&oi=book_result&ct=result&resnum=3&ved=0CCIQ6AEwAg#v=onepage&q=separating%20axis%20test%20movement&f=false

(sorry for the large link - it wasn't my idea)

Answer 3

Your best approach is to work out:

1. The linear time range (possibly never) in which the x co-ordinates will overlap
2. The linear time range (possibly never) in which the y co-ordinates will overlap

And then test if the two time ranges intersect. This will as an added bonus give you the collision time.

This will be a simple constant time operation overall.