Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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:

enter image description here

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?

share|improve this question
    
Box2D solved this, objects that are marked as bullets are treated differently. The sources are available if you want to take a look. –  sm4 Jul 10 '13 at 3:36
2  
If by chance both the bullet and target are traveling at a constant rate and direction, then an alternative would be that no collision detection is required. At the time the bullet is fired, pre-calculate impact location and time and wait for the clock to tick around and simply register the collision. this is a popular approach in tower defense games. (thinking this may work for you because bullets usually fly constant speed/direction and walls usually do not move... constant speed/direction there. :) ) –  Steve H Jul 10 '13 at 14:13
    
add comment

3 Answers

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.

share|improve this answer
2  
While OK advice generally speaking, this isn't actually answering the question. –  Byte56 Jul 10 '13 at 2:07
    
the question was about the best way to prevent tunneling. I described how to do so. –  Ian Markowitz Jul 10 '13 at 2:12
2  
I want an algorithm against tunneling, not a hack to prevent it –  Xkynar Jul 10 '13 at 2:14
    
This is in no way a 'hack' to prevent tunneling. It is the commonest and simplest method of stopping objects from passing through walls. See aorensoftware.com/blog/2011/06/01/when-bullets-move-too-fast for more methods and information –  Ian Markowitz Jul 10 '13 at 2:19
    
@IanMarkowitz But the asker is trying to make his own algorithm to prevent tunnelling. He has a problem in one specific case. He is asking how to improve his idea to prevent tunnelling. Not about other ideas. –  sm4 Jul 10 '13 at 3:28
show 2 more comments

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.

share|improve this answer
add comment

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/

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.