Collision Detection and Response

[Chuckleluck]

Hello,
I've been having a lot of trouble with collision detection recently. I'm attempting to make a 2D platformer. All I need is rectangle-on-rectangle collision detection, and then to respond on collision by moving the two rectangles involved in opposite directions.

Thanks in advance.

[mrnutty]

Are you rectangles rotated? Do you expect us to just write one for you? Or do you have a specific question?

[Chuckleluck]

Sorry, I was a little rushed in making that first post. Also, thank you for the fast reply :) It doesn't have to deal with rotated rectangles.
I'm writing it in Java using Slick2D, and there is a method in the Slick Rectangle class that allows me to see if it intersects with another rectangle.
My issue is how to detect where the collision occurs-- on the top, bottom, left, or right side of the rectangle. I've tried comparing the centers of the rectangles, but that only works with squares.

[mrnutty]

Do you have a direction associated with the rectangle? For example if the rectangle is going to the right, then it might always be the case for you that the right-side has intersected.

I haven't used Slick2D but you should be able to do a line-rectangle collision test. For example

//assume (rectangle.x,rectangle.y) is the point in the top left corner
Line topLine = Line( rectangle.x , rectangle.y , rectangle.x + rectangle.width, rectangle.y);
Line rightLine = Line(rectangle.x + rectangle.width, rectangle.y, rectangle.x+rectangle.width, rectangle.y+rectangle.height);
//.. so on
bool topLineHit = topLine.intersect( otherRectangle );

[Chuckleluck]

Ok, here's my code in my Sprite class:

enum LastMove {
    VERTICAL,
    HORIZONTAL
}



public void reactToCollision(Sprite other) {

    if(isStatic) {
        return;
    }

    Line thisTop = new Line(pos, new Vector2f(pos.x + getWidth(), pos.y));
    Line thisLeft = new Line(pos, new Vector2f(pos.x, pos.y + getHeight()));
    Line thisRight = new Line(new Vector2f(pos.x + getWidth(), pos.y), new Vector2f(pos.x + getWidth(), pos.y + getHeight()));
    Line thisBottom = new Line(new Vector2f(pos.x, pos.y + getHeight()), new Vector2f(pos.x + getWidth(), pos.y + getHeight()));

    if(lastMove.equals(LastMove.VERTICAL)) {

        if(other.getBoundingBox().intersects(thisTop)) {
            move(0, 1);
        }
        else if(other.getBoundingBox().intersects(thisBottom)) {
            move(0, -1);
        }
    }
    else {
        if(other.getBoundingBox().intersects(thisLeft)) {
            move(-1, 0);
        }
        else if(other.getBoundingBox().intersects(thisRight)) {
            move(1, 0);
        }
    }
}



public void move(float x, float y) {

        if(x != 0)
            lastMove = LastMove.HORIZONTAL;
        if(y != 0)
            lastMove = LastMove.VERTICAL;

        prevPos = pos.copy();
        pos.x += x;
        pos.y += y;
        boundingBox.setX(pos.x);
        boundingBox.setY(pos.y);
    }

Here are some screenshots of my program. The yellow box is non-static, the purple and cyan box is static:
1 2 3

Screenshot 1 shows it working fine. As long as the main sprite is above the static sprite, and on a corner, it works as it should.
One issue can be seen on Screenshot 2. If the main sprite isn't on a corner, but is still above the static sprite, it falls through without any reaction. reactToCollision() is being called, it just isn't reacting.
Another issue is when the main sprite hits the side of the static sprite, like Screenshot 3. The main sprite is pushed above or below the main sprite, without moving left or right at all. When this happened, lastMove was set to HORIZONTAL.
Do you know what could be causing these issues?

[Chuckleluck]

-bump-

[mrnutty]

in your reachToCollision, can you remove the check for lastMove.equals and check collision for all lines? See if you get a collision with that.

[Chuckleluck]

Like this?

public void reactToCollision(Sprite other) {
        Line thisTop = new Line(pos, new Vector2f(pos.x + getWidth(), pos.y));
        Line thisLeft = new Line(pos, new Vector2f(pos.x, pos.y + getHeight()));
        Line thisRight = new Line(new Vector2f(pos.x + getWidth(), pos.y), new Vector2f(pos.x + getWidth(), pos.y + getHeight()));
        Line thisBottom = new Line(new Vector2f(pos.x, pos.y + getHeight()), new Vector2f(pos.x + getWidth(), pos.y + getHeight()));

        if(other.getBoundingBox().intersects(thisTop)) {
            move(0, 1);
        }
        else if(other.getBoundingBox().intersects(thisBottom)) {
            move(0, -1);
        }
        if(other.getBoundingBox().intersects(thisLeft)) {
            move(-1, 0);
        }
        else if(other.getBoundingBox().intersects(thisRight)) {
            move(1, 0);
        }
    }

When I test it, the yellow sprite will be right above the static sprite, and then move to the left, without moving up (to push it back up out of the static sprite). When the yellow sprite reaches the far left corner, it is finally either pushed up or down.
I think this is because the left and right sides of the yellow sprite are intersecting the static sprite. The sprite moves down, and before the code can detect a collision to move it back up, the lowest part of the left and right lines intersect, and then push it to the left (since the code to move it left is reached before the code to move it right).

[mrnutty]

Hmm...is your logic something like so:

 1) sprite.x += vx;
 2) sprite.y += vy;
 3) checkCollision();
 4) reactCollision();

Try checking for collition after step 1 and after step 2.

[bguild]

You need to do some algebra. The algrebra is not very easy and I haven't worked it all out just now, but I can tell you the sort of thing you could to do to figure this problem out.

First, you can forget about using the intersects() method. That's only good for determining if two shapes intersect now, and what you want to know about is intersection over time. Start with t to represent time, with t = 0 being the time before you moved the sprites and t = 1 being the time after you moved the sprites. The position of a sprite is

(pos.x + t * x, pos.y + t * y)

To figure out if two sprites intersect, you need to take the normal test for rectangle intersection and by algrebra re-arrange it into a calculation for the range of values for t in which the rectangles intersect. Then take the lowest value of t in the range and that is the moment when the rectangles first intersected. Using the positions of the rectangles at that moment, you can pretty easily figure out exactly how they came together.

[bguild]

After giving it some thought, I can give a more detailed answer. This is from my carefully worked out algebra manipulations, not something I have tested, so consider it a rough guide rather than a fool-proof system.

We have two rectangles a and b and we represent the top-left corner of a as (a.x, a.y), and the bottom-right corner as (a.x2, a.y2). The amount that a moves is (a.vx, a.vy). So a starts at (a.x, a.y) at t = 0 and moves to (a.x + a.vx, a.y + a.vy) at t = 1.

The rectangles overlap at t = 0 if

a.x <= b.x2 && b.x <= a.x2 && a.y <= b.y2 && b.y <= a.y2

To keep things short, I will skip y for now and talk only about x since the two are done the same way. To check that the rectangles intersect along the x axis at time t, we just have to check:

0 <= t <= 1 && a.x + t * a.vx <= b.x2 + t * b.vx && b.x + t * b.vx <= a.x2 + t * a.vx

There will never be cause to make that check because there's no reason you would ever be given a value of t, but with a little manipulation we can use that check to figure out values of t where the intersection would happen:

0 <= t <= 1 && b.x - a.x2 <= t * (a.vx - b.vx) <= b.x2 - a.x

Let's say abvx = a.vx - b.vx to keep things brief. Then if abvx > 0 we know that (b.x - a.x2) / abvx <= t <= (b.x2 - a.x) / abvx, and if abvx < 0 we know that (b.x2 - a.x) / abvx <= t <= (b.x - a.x2) / abvx. And of course if abvx == 0 then we have a special case where the rectangles are staying the same distance from each other on the x-axis over time, so you can ignore t and just check that b.x - a.x2 <= 0 <= b.x2 - a.x, and if that's not true then the rectangles never touch.

Once you've figured out x and then done the same for y, you will have 3 low values for t: 0, one from the x-axis, and one from the y-axis. Take the greatest of those and you have the time at which the two rectangles first touched, called t0. But you need to check that t0 is less than the three high values for t. If t0 is greater than 1 or greater than the high value you got from either axis, then it means that the rectangles don't really touch and you can stop.

Using t0 you know exactly where the two rectangles were when they touched. The next step is to figure out which sides of the rectangles were touching. To do that just compute the distances between the sides as these four values:

1. Top of a: |(a.y + t0 * a.vy) - (b.y2 + t0 * b.vy)|
2. Bottom of a: |(a.y2 + t0 * a.vy) - (b.y + t0 * b.vy)|
3. Left of a: |(a.x + t0 * a.vx) - (b.x2 + t0 * b.vx)|
4. Right of a: |(a.x2 + t0 * a.vx) - (b.x + t0 * b.vx)|

Compute all four values and which ever one is least gives you the side of a that first touched b. That value should be zero except for inevitable computation error with floating point values. If more than one of the four values is near zero, then a and b touched on their corners.

For any two sprites a and b, if you'd want to respond to their collision and they could possibly collide, then you'll have to do the above calculations. You should probably get a complete list of collisions before you start deciding what you will do for each collision and sort that list so that the collisions with the lowest value of t0 come first. That way you can deal with the collisions in the order that they happen instead of in the order that you discover them.

If a has collided with something and you want to respond by changing a's path, then you'll want to remove all later collisions with a from the list, choose a new a.vx and a.vy according to how you want a to react, and then calculate a new starting position for a, where a would have been if it had always had the new a.vx and a.vy. For a.x, this would be a.x = a.x + t0 * oldVX - t0 * a.vx. Now check for a collision between a and every other sprite just as before, but include t0 as an additional low value for t, because you don't want any collisions that happen before this collision. Insert the collisions you find into the list in sorted order and then continue down the list.

I apologize if I made any algebra mistakes or typing mistakes, but I think this is all correct or quite close to correct. Good luck.