How to determine collision direction between two rectangles?

Question

I am trying to figure out how to determine the direction a collision occurs between two rectangles.

One rectangle does not move. The other rectangle has a velocity in any direction. When a collision occurs, I want to be able to set the position of the moving rectangle to the point of impact.

I seem to be stuck in determining from what direction the impact occurs. If I am moving strictly vertically or horizontally I manage great detection. But when moving in both directions at the same time, strange things happen.

What is the best way to determine what direction a collision occurs between two rectangles?

Answer 1

I seem to be stuck in determining from what direction the impact occurs. If I am moving strictly vertically or horizontally I manage great detection. But when moving in both directions at the same time, strange things happen.

tl;dr The solution is to move and check for collisions one axis at a time.

I had this very same problem. I bet that the update phase of your game loop looks something like this:

• object.x += object.vx
• object.y += object.vy
• check for collisions
• repsond to collisions

The trick here is to move and check for collisions one axis at a time. As you said, "If I am moving strictly vertically or horizontally I manage great detection." So you've already solved 99% of the problem. Just change your logic to look like this:

• object.x += object.vx
• check/respond collisions
• object.y += object.vy
• check/respond collisions

In simple cases, it doesn't matter which axis you do first. If you don't feel good about choosing one or the other arbitrarily, it's reasonable to check first the axis where the object's absolute velocity is the greatest.

Answer 2

As per larsbutler's answer, for simple cases, it doesn't matter whether you check for x or y collisions first. This can quickly lead to inaccuracy, later down the road, however (especially with more complex shapes, greater velocities, and more objects).

If anybody is interested in implementing a more sophisticated collision detection algorithm, here's a rundown of what's needed:

1. First, the algorithm does a sweep and prune to narrow down the number of objects needed to check. If you're checking every object against every other object, it can be quite expensive, computationally. Basically, you predict whether an object is likely to collide in the future; if its not very likely, you don't do the calculations.
2. After pruning, you perform a preliminary collision test. Each object has a bounding rectangle or circle (something that is easy to calculate collisions). Detecting whether two circles/rectangles collide is quite simple, and can quickly eliminate unnecessary calculations between two objects on opposite sides of the screen.
3. If a preliminary detection was made, you need to loop through the edges of each shape and detect any points of collision (intersection of two line segments). In Jon's case, this would be the collision point on the vertical axis and horizontal axis.
4. Once you have a list of collision points, you need to calculate the exact collision point. There are a number of ways you can do this, and it all depends on how accurate you want to be. One option is to half the time increment (of your physics integrator), recalculate the shapes' positions, and rerun the collision detection until there is only one collision point. Basically, you're approximating the "moment of impact". If your simulation doesn't have very many partial differential forces, you can just use the velocity of the previous integration, with subsequent time halvings.
5. The results of step four will give you the approximate collision points (within an upper/lower bound- like 3px or something). If there is more than one collision point, you'll have to treat them as an imaginary edge. You can then perform collision resolution calculations (velocity, momentum, friction, etc)

Hope this helps someone.

Specific to Jon's question:

The step you are missing of the collision algorithm is step #4. From what I understand, your rectangles intersect diagonally and end up getting two collision points (one horizontally and one vertically). Determining which collision point occurred first really depends on what you're using for physics integration.

From your description, it sounds like the rectangles don't rotate and things like partial differential forces aren't of much concern. If this is the case, finding which edge collides first is fairly simple. Here is some pseudo code:

/*
   Assume Obj1 is stationary
   Assume Obj2's velocity is -x and -y (to bottom left)
   From this, we know the collision edges are:
*/
colEdgesObj1 = [1,0]; //right, top
colEdgesObj2 = [0,1]; //left, bottom
//... where [0=left/1=right, 0=top/1=bottom]

//Calculate distances between Obj1 edges and Obj2 edges
distX = Math.Abs(Obj1[colEdgesObj1[0] ? "right" : "left"] -
                 Obj2[colEdgesObj2[0] ? "right" : "left"]);
distY = Math.Abs(Obj1[colEdgesObj1[1] ? "bottom" : "top"] -
                 Obj2[colEdgesObj2[1] ? "bottom" : "top"]);

//Calculate time object would take to go those distances
//(assuming Obj2 is the only moving object)
timeX = distX/Obj2.VelX;
timeY = distY/Obj2.VelY;

//If time is greater, that axis has been colliding longer
if timeX > timeY
    //collided X axis first
else if timeY > timeX
    //collided Y axis first
else
    //collided at a corner