Lightweight Simple Fast-Object Collision Detection Algorithm/Logic

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.

I've reserched on those algorithms for a while but they all seem so unecessary complicated, checking all the wall's lines (being that the wall is a rectangle, 4 lines needed to check for each wall..) and maybe resource-expensive...

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 (sloppy and half-assed) 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?

Answer 1

Your objects are moving so quickly that they can pass through walls. This is called tunneling. There are a couple ways to deal with tunneling. One way is to simply stop using small, fast objects. If you want to keep your fast objects, you might want to reduce the timestep of your physics simulation.

This means that rather than running your collision detection code 60 times a second (or whatever it currently is), you would run it much more frequently. This stops objects from passing through walls, and doesn't require you to write your own collision detection code.

Answer 2

You could use a swept volume, which is one of the common ways of dealing with this case.

A swept volume is what you get if you take an object's previous position and "sweep" its shape like a paint brush to its current position. In the example of your circle, the swept volume will be a single capsule. For rectangles the shape is a little more complex. For arbitrary polygonal shapes it's more complex still, of course.

Using this volume you can more easily test collisions. You can also find out where along the swept volume a collision first occurs and then figure out the time t of the collision to properly handle it.

Swept volumes do not work exceedingly well when you have rotating objects. There are significantly more intricate methods available that handle these, which you can research in more detail by searching for continuous collision detection.

A simpler alternative for particularly small objects (bullet fire) is to just use a raycast instead of full object-object collision detection. You'll want to ensure that you can do fast ray casts (or line segment casts more accurately, in some cases) as many elements in a game's physics must (or usually are) faked with such ray casts. A player character controller is often just a capsule for rough collision handling and a crap load of ray casts to handle the finer details.

Answer 3

My suggestion, choose a simple algorithm, like rectangle intersection, but with the following addition: remember your previous position. If difference between previous position and current is more than your sprite width, then divide that by your sprite width, or half your sprite width, and do your rectangle intersection in a loop, advancing that chosen distance each iteration in the same frame of simulation. This way you don't miss objects that are between your previous position and your current one even even if their are not wide enough to intersect your sprite in any of both positions.

You already realized the need to save the previous position, now you only need to divide your displacement in steps equal or less than your sprite width.

For a similar question I tried to illustrate what is my solution in ASCII in this other answer (Collision detection problems using AABB's). I think my writing could be a bit more efficient but I think It is understandable. Ignore the part about AABB as you already picked rectangle intersection.

Another solution, by brute force, reduce the time step between frames by and "absurd" number. For example, fix your fps at 200 or 400, probably only possible if you have your screen refreshes separated from your simulation. I don't know if you are already doing this, if not and you want to try it, this helped me a lot: http://gafferongames.com/game-physics/fix-your-timestep/