Greenfoot

2014/7/10

#

Hello, when two non-rotatable rectangles (aabb) collide, how can we determine which sides collided? For example: ___ ___ | A| | B | |__| |___| If box A moves right and box B moves left, they will collide. The side of collision for A will be RIGHT and for B it will be LEFT. But how do I determine that? (I am using vectors for velocity, so the moving is described, too). Thank to everyone for help.

lordhershey

2014/7/10

#

What about detect the collision, if it happened then back the 2 object up to see where they initially were and you can get an idea of what sides hit first.

Kartoffelbrot

2014/7/10

#

Nice idea, but how to differ between up and left in this situation? ____ |___| ____ |___| Note: Both move at the same time, not after another.

lordhershey

2014/7/10

#

I am gonna have to grab a pencil and some paper. :p

Kartoffelbrot

2014/7/10

#

I've done that, too :D. Maybe you can take the vector of a box, turning it, and then for all corners of the object: get the line from the corner to the point the vector is pointing at from this point -> check for intersection of this line with all sides of the other box and then the side, where this line intersects is the line? But how to consider both boxes moving seperately? Don't you have to notice both vectors at the same time?

davmac

2014/7/11

#

If the sides collide, the left side of one rectangle will be close to the right side of the other. If the top/bottom collides, then the top of one will be close to the bottom of the other. This is really pretty straightforward :) In pseudo code, roughly:

if (a.left == b.right) {
   // a's left collides with b's right
}
else if (a.right == b.left) {
   // a's right collides with b's left
}
else if (a.top == b.bottom) {
    // a's top with b's bottom
}
else if (a.bottom = b.top) {
    // a's bottom with b's top
}

If you want to to check for slight overlap, you can do instead:

if (b.right - a.left < 5 && b.right - a.left >= 0) {
   // a's left collides with b's right
}
// and so on

If you want to make the movement into account, you can use the movement vector(s) to decide which edges you need to check. I.e. if the movement vector of rectangle a is essentially left, then you need to check for a.left == b.right. If it's up-and-left, you can check both those edges.

But how to consider both boxes moving seperately? Don't you have to notice both vectors at the same time?

In practice, you probably don't need to worry about this. Your original question implies that you have already detected collision, but you just want to see what side collided - is that not the case?

Kartoffelbrot

2014/7/12

#

Are you talking about the state before or after the collision? And I don't really get the a.left == b.right... This is a very rarely state. Mostly both rectangles are overlapping after the collision.

davmac

2014/7/12

#

Are you talking about the state before or after the collision?

After the collision, since your question was "how can we determine which sides collided?" - implying the collision has already occurred.

And I don't really get the a.left == b.right... This is a very rarely state. Mostly both rectangles are overlapping after the collision.

I specifically addressed this:

davmac wrote...

If you want to to check for slight overlap, you can do instead:

(etc). I also asked this:

Your original question implies that you have already detected collision, but you just want to see what side collided - is that not the case?

... because I was wondering if what you actually want is to find out which sides will collide, not which sides already collided, but you haven't answered that. :)

Kartoffelbrot

2014/7/12

#

I wanted to check which sides have collided. So if I have this state, ____ |A__|___ |_|__|B | |_____| I want to know on which side A has entered B.

davmac

2014/7/13

#

Right, then I think my earlier post has answered this.

Kartoffelbrot

2014/7/13

#

But there is a problem I suppose. ____ |A__|___ |_|__|B | |_____| Usually people would think A came from top or the left. But what if A was fast enough in one frame and came from the right? It was only as fast to come so far.

danpost

2014/7/13

#

I would think that if you added the equal and opposite vector of the colliding box with the vector of the collided box, you can narrow the possibilities to one horizontal and one vertical. Then you just need to determine whether the vertical sides or the horizontal sides came into contact first. This should be possible by getting the percentage of overlap with respect to the vertical and horizontal parts of that same vector sum. I cannot help but think that there is something missing from this, however. If the objects clip corners, I believe the above will give false results. One more check needs to be done to correct that; I will have to put some thought into it when I have some time.

Kartoffelbrot

2014/7/13

#

I've found a solution so far, but I am not sure if it works correctly, everytime:

/**
     * @return At which side rectangle a has has entered b.
     */
    private static Side whereDoesCollisionHappened(BoxCollider a, BoxCollider b){
        //get the entities (objects in world) these boxcolliders are appended to
        Entity aEntity = a.getBoundingEntity();
        Entity bEntity = b.getBoundingEntity();
        //getLocations of both last frame
        double axLastFrame = a.getX() - aEntity.getVector().dx();
        double ayLastFrame = a.getY() - aEntity.getVector().dy():
        //get side axis positions of A
        int lastALeftBound = (int)(axLastFrame - a.getWidth()/2);
        int lastARightBound = (int)(axLastFrame + a.getWidth()/2);
        int lastAUpperBound = (int)(ayLastFrame - a.getHeight()/2);
        int lastALowerBound = (int)(ayLastFrame + a.getHeight()/2);
        //get side axis positions of B
        int bLeftBound = (int)(b.getX() - b.getWidth()/2);
        int bRightBound = (int)(b.getX() + b.getWidth()/2);
        int bUpperBound = (int)(b.getY() - b.getHeight()/2);
        int bLowerBound = (int)(b.getY() + b.getHeight()/2);
        //if a and b has overlapped on the x axis
        boolean xAxisOverlapLastFrame = 
            (bLeftBound < lastALeftBound && lastALeftBound < bRightBound) ||
            (bLeftBound < lastARightBound && lastARightBound < bRightBound)
        ;
        //if a and b has overlapped on the y axis
        boolean yAxisOverlapLastFrame = 
            (bUpperBound < lastAUpperBound && lastAUpperBound < bLowerBound) ||
            (bUpperBound < lastALowerBound && lastALowerBound < bLowerBound)
        ;
        //getting the entering side
        if(xAxisOverlapLastFrame)//solve in y axis
            return (ayLastFrame > b.getY())?Side.DOWN:Side.UP;
        else if(yAxisOverlapLastFrame)//solve in x axis
            return (axLastFrame > b.getX())?Side.RIGHT:Side.LEFT;
        else{//calculating on which side a entered first. This is part of that danpost has wrote
            double rateX = (b.getX() - axLastFrame) / aEntity.getVector().dx();
            double rateY = (b.getY() - ayLastFrame) / aEntity.getVector().dy();
            if(rateX > rateY)//resolve in x
                return (axLastFrame > b.getX())?Side.RIGHT:Side.LEFT;
            else//resolve in y
                return (ayLastFrame > b.getY())?Side.DOWN:Side.UP;
        }
    }

Here your thoughts are used partwise.

danpost

2014/7/13

#

From what I gave above, you should at least have the two possible collision points (time-wise). You could move the actor back one of the percentages of the vector sum and one of two things would happen-- the actors will be at the collision point (time of collision), which can be checked for; or, the actors will not be close enough to be considered at the collision point. Comparing the x and y coordinates as stated previously in this discussion at the collision point (time of collision) should determine the colliding sides. Do not forget to move the actor back.

Kartoffelbrot

2014/7/13

#

No I havent forgot to move them back. I use this method to move them back:

private static void resolveCollision(BoxCollider a, BoxCollider b){
        Entity aEntity = a.getBoundingEntity();
        Entity bEntity = b.getBoundingEntity();
        double speedA = aEntity.getVector().getAmount();
        double speedB = bEntity.getVector().getAmount();
        //calculating the relative directions both rectangles has to walk
        double partA = speedA/(speedA + speedB);
        double partB = speedB/(speedA + speedB);
        if(a.isFixed()){
            if(b.isFixed())
                return;
            else{
                partA = 0;
                partB = 1;
            }
        }else if(b.isFixed()){
            partB = 0;
            partA = 1;
        }else if(speedA + speedB == 0.0){
            partA = 0.5;
            partB = 0.5;
        }
        if(Double.isNaN(partA) || Double.isInfinite(partA))
            partA = 0;
        if(Double.isNaN(partB) || Double.isInfinite(partB))
            partB = 0;
        //getting the colliding side
        Side sideOfCollision = whereDoesCollisionHappened(a, b);
        //resolving the collision
        double penetrationDepth = 0;
        double directionForA = 1;
        switch(sideOfCollision){
            case LEFT:
            directionForA = -1;
            case RIGHT://calculating the overlapping width
            penetrationDepth = Math.min(a.getX() + a.getWidth()/2, b.getX() + b.getWidth()/2) - Math.max(a.getX() - a.getWidth()/2, b.getX() - b.getWidth()/2);
            //calculating the distances both have to walk
            partA *= penetrationDepth *  directionForA;
            partB *= penetrationDepth * -directionForA;
            aEntity.setLocation(aEntity.getX() + partA, aEntity.getY());
            bEntity.setLocation(bEntity.getX() + partB, bEntity.getY());
            return;

            case UP:
            directionForA = -1;
            case DOWN://calculating the overlapping height
            penetrationDepth = Math.min(a.getY() + a.getHeight()/2, b.getY() + b.getHeight()/2) - Math.max(a.getY() - a.getHeight()/2, b.getY() - b.getHeight()/2);
            partA *= penetrationDepth *  directionForA;
            partB *= penetrationDepth * -directionForA;
            aEntity.setLocation(aEntity.getX(), aEntity.getY() + partA);
            bEntity.setLocation(bEntity.getX(), bEntity.getY() + partB);
            break;
        }
    }

Activity

About

Documentation

Download

Discuss

Scenarios

Axis Aligned Bounding Box