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

I'm trying to determine whether Object1 will collide with Object2 given the fol开发者_JAVA百科lowing 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.

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.

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)

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.