Collisions between rectangles

Question

I have been trying to solve this for a few hours, and the internet is pretty unfruitful on the subject.

I need help detecting and solving collisions between rectangles, and not just detecting, but note I mentioned solving as well.

These are two boxes, with x/y width/heights. I simply need to detect when they are overlapping, and push one of the boxes out of the other one smoothly.

Also, note that one box is stationary - and the other is moving.

Does anyone have anything on this (or can give me an example?) I'd really appreciate it.

I need the boxes to be able to rest on top of each other as well.

Thank you!

What *specifically* is the problem? What have you *tried* for detecting overlaps? That's not complicated. — chrylis -cautiouslyoptimistic-, Apr 19 '14 at 03:16
The detection wasn't a problem. The problem was solving the collision. I tried numerous methods (like interpolating between the last working position and the new position to find a new good position, along with stopping the velocities and forcibly placing them outside the box) but none of them worked well. — Anonymous, Apr 19 '14 at 03:17
What constitutes "solving" the collision? What tools are you using? Where's your code? — chrylis -cautiouslyoptimistic-, Apr 19 '14 at 03:20
Successfully moving colliding boxes outside of each other. I don't have any working code worth showing. — Anonymous, Apr 19 '14 at 03:21
public void move(int xa, int ya, Rect another) { this.x += xa; this.y += ya; if (collision(another)) { this.x -= xa; this.y -= ya; } } — Gere, Apr 19 '14 at 03:24
If you are ready to simulate the rectangles as wire frames, there is a nice solution based on the properties of Verlet integration, the standard source is http://www.gamedev.net/page/resources/_/technical/math-and-physics/a-verlet-based-approach-for-2d-game-physics-r2714 — Lutz Lehmann, Apr 21 '14 at 13:25

aeskreis · Accepted Answer · 2014-04-19T03:49:54.557

I'm not sure what the context here is (Are these boxes moving or stationary? Are you looking for a physically accurate resolution, or simply a geometrically correct one?), but it seems like you could accomplish this in the following way:

1) Determine if there is a box collision 2) Determine the intersection of the two boxes, which would produce a third box. The width and height of the box is your penetration depth. 3) move the center of one of the boxes by the penetration depth, (x - width, y - height).

This should cause the boxes to become disjoint.

FYI: Intersection of two boxes can be computed by taking the max of the mins and the mins of the maxes from both boxes.

Here is some code from my engine for box intersection:

bool Bounds::IntersectsBounds(const Bounds &other) const
{
    return !(min.x > other.max.x || max.x < other.min.x
             || min.y > other.max.y || max.y < other.min.y);
}

bool Bounds::Intersection(const Bounds &other, Bounds &outBounds) const
{
    if (!this->IntersectsBounds(other)) {
        return false;
    }

    outBounds.min.x = std::max(min.x, other.min.x);
    outBounds.min.y = std::max(min.y, other.min.y);
    outBounds.max.x = std::min(max.x, other.max.x);
    outBounds.max.y = std::min(max.y, other.max.y);


    return true;
}

In this case, the "outBounds" variable is the intersection of the two boxes (which in this case is your penetration depth). You can use the width/height of this box to perform your collision resolution.

One box is stationary, the other is not. Sorry for not clarifying. I'll revise the question and also try your solution. Thanks! — Anonymous, Apr 19 '14 at 03:25
Can you elaborate on the intersection calculation a bit more please? — Anonymous, Apr 19 '14 at 03:40
This worked, but was very unreliable and caused a lot of bugs. It may be my fault with the implementation - but after an hour of setting up different ways of solving collisions with this method, I was unable to get anything working. — Anonymous, Apr 19 '14 at 17:52
Maybe if you post a github or pastebin with the code I can take a look. — aeskreis, Apr 19 '14 at 20:16

score 0 · Answer 2 · edited Apr 13 '17 at 12:18

Yeah! This is a pretty common problem! You may want to check out the gamedev portion of the stack exchange network!

Detection

bool collide(float x1,float y1,float sx1,float sy1, float x2, float y2, float sx2, float sy2){
 if (x1+sx1 <= x2)
        return false;
 if (x2+sx2 <= x1)
        return false;
 if (y1+sy1 <= y2)
        return false;
 if (y2+sy2 <= y1)
        return false;
 return true;
}

Resolution As far as an answer, this depends on the type of application you are going for. Is it a sidescroller, top-down, tile based? The answer depends on the response to this question. I'll assume something dynamic like a sidescroller or top-down action game.

The code is not difficult, but the implementation can be. If you have few objects moving on the screen you can use a similar system to mine, which goes something like the following:

Get a list of objects you are currently colliding with, in order of distance from the current object.
Iterate through the objects, and resolve collisions using the following method
Check if the object has some special collision type (teleporter, etc) by sending that object a message, and checking on the return value (a teleporter will take care of the collision resolution)
check if the previous bottom position of our current object (A) was above the top side of the object in question(B), if so that means you have had a bottom collision. Resolve by setting the y position of A to the y position of B minus the height of A
(IF THE PREVIOUS FAILED) check if the previous right side of A was to the left of the left side of B, if so that means you have had a right side collision. Resolve by setting the x position of A to B's position minus A's width
(IF THE PREVIOUS FAILED) check if the previous left side of A was to the right of the right side of B, if so that means you have had a left side collision. Resolve by setting the x position of A to B's x position plus B's width
(IF THE PREVIOUS FAILED) check if the previous top side of A was below the bottom side of B, if so you have had a top side collision. Resolve by setting the y position of A to the y position of B plus B's height

Whew. It is important that you have the objects sorted according to distance, it will catch on edges if you check collisions with an object that is farther away!

I hope that makes sense!

The question was primarily on how to resolve it, if you could, please more specific than "detect the collision, and then resolve." Thank you! — Anonymous, Apr 19 '14 at 17:53
Haha, you can figure it out man, you're a programmer! Don't let us do it all for you :D But I'll be a little more specific for you- I understand sometimes we need a bit of outside perspective. — ultifinitus, Apr 19 '14 at 18:40

score 0 · Answer 3 · edited May 23 '17 at 11:46

0

Edit: Apparently doesn't work in Android.

https://stackoverflow.com/a/15515114/3492994

Using the available classes from the 2D Graphics API.

Rectangle r1 = new Rectangle(100, 100, 100, 100);
Line2D l1 = new Line2D.Float(0, 200, 200, 0);
System.out.println("l1.intsects(r1) = " + l1.intersects(r1));

What this doesn't tell you, is where...

edited May 23 '17 at 11:46

Community

1
1

answered Apr 19 '14 at 06:23

Stefnotch

511
2
13
26

You can't use those in Android, unfortunately. – Anonymous Apr 19 '14 at 17:51

Collisions between rectangles

3 Answers3