Search code examples
performancealgorithm2dcollision-detection

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 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.

Solution

  • 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.