"Perfect" Collision Detection Algorithm Fixing

Question

I'm making a game where i need to give my objects collision, but i have many fast small objects and normal collision algorithms (Intersection of shapes and such) do not work, because the position+speed iteration advances the walls and there's never actually an Intersection.

So i've started constructing my own (Maybe it already exists but i didnt see it anywhere) collision algorithm based on saving the last position the object was.

Please see the following image:

The idea is demonstrated in frame 1 and 2 of the image. Basicly by checking if there's a wall between the left side of the last rectangle and the right side of the new rectangle, i never skip zones while i check collision, and there's no risk of skipping a wall (so i thought).

This is the code of the algorithm:

    private void bounce(GameElement b, Terrain t)
{
    Rectangle tR = t.getRectangle();
    int tRleft = tR.x;
    int tRright = tR.x+tR.width;
    int tRup = tR.y;
    int tRdown = tR.y+tR.height;

    Rectangle bRnow = b.getRectangle();
    int bRnowLeft = bRnow.x;
    int bRnowRight = bRnow.x+bRnow.width;
    int bRnowUp = bRnow.y;
    int bRnowDown = bRnow.y+bRnow.height;

    Rectangle bRlast = b.getRectangleLast();
    int bRlastLeft = bRlast.x;
    int bRlastRight = bRlast.x+bRlast.width;
    int bRlastUp = bRlast.y;
    int bRlastDown = bRlast.y+bRlast.height;

    boolean leftRight = false, rightLeft=false, upDown=false, downUp=false;
    boolean betweenX = false, betweenY = false;

    if(bRnow.x>bRlast.x)leftRight=true;
    if(bRnow.x<bRlast.x)rightLeft=true;
    if(bRnow.y>bRlast.y)upDown=true;
    if(bRnow.y<bRlast.y)downUp=true;

    if(bRlastRight>tRleft && bRlastLeft<tRright) betweenX = true;
    if(bRlastDown>tRup && bRlastUp<tRdown) betweenY=true;

    if(leftRight)
        if((tRleft>bRnowLeft || tRleft>bRlastLeft) && tRleft<bRnowRight && betweenY)
        {
            b.setX(tR.x-bRnow.width - 1);
        }

    if(rightLeft)
        if((tRright<bRnowRight || tRright<bRlastRight) && tRright>bRnowLeft && betweenY)
        {
            b.setX(tR.x+tR.width + 1);
        }

    if(upDown)
        if((tRup>bRnowUp || tRup>bRlastUp) && tRup<bRnowDown && betweenX)
        {
            b.setY(tR.y-bRnow.height - 1);
        }

    if(downUp)
        if((tRdown<bRnowDown || tRdown<bRlastDown) && tRdown>bRnowUp && betweenX)
        {
            b.setY(tR.y+tR.height + 1);
        }   
}

Its called bounce because its not really organized atm, i still have to think how to structure the algorithm so it becomes more generalized and pratical (Would appreciate help on that too)

This way of doing collision has one bug at the moment which is seen in image 3 (sorry for drawing circles, they are supposed to be squares) because FAST objects still pass diagonals :/ On the other hand, direct hits on walls are pretty neat.

How could i improve, optimize and organize this algorithm? Or is there any better algorithm and im just thinking too much for nothing? I appreciate your help.

Answer 1

Axis aligned bounding box trees are usually well suited to detecting object collisions. Here is a tutorial with some code - its examples are for 3D collision detection, but the data structure can be easily adapted to 2D collision detection.