Sign in to follow this  

Velocity Independent Collision detection and reaction

This topic is 3723 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

(Edit) Here's the cliff notes version of my problem: What's the best way to find the collision point of collision box A trying to pass through collision box B? I'm trying to do this completely independent of collision box position and velocity. The rest of the post is a highly detailed explanation of my problem.
==Warning: Wall of Text/Source Code==
I'm working a simple platforming demo that has a block jump around and interacts with a set of platforms with the force of gravity. I've done this before only I cheated and had the offsets and velocities set in a certain way so the square would never pass through a platform. In this demo I want to have it so no matter what velocity the of the block or the position/size of the platforms the program will still work. Simple enough right? Except I've spent just about a week of my spare time trying to get this work 100% as it should. I tried different approaches and each one has had varying success. This setting back my all projects (including my website) and I know some has pulled this off successfully before. There's no point wasting this much time in reinventing the wheel. As far as I can figure, my method should be working. I'm not sure if there's something wrong with my design, math, algorithms, or if it's just a quirk of floating points. Knowing my luck, it'll probably be something embarrassingly simple like a missing equal sign. Here's what going wrong: at what seems to be near random the block gets stuck. You can try out the program yourself here. If you come in from the right angle the box will get stuck on the side of the platform. Another bug that's easy to replicate is if you go under the platforms while holding up (the program uses WASD style controls). Keep going back and forth holding w under the platforms and eventually you'll get stuck until you let go of one of the buttons. First let me go over the design of my square's move function: In my square's move() function I take in a vector of platforms as object "pf". The platform class is essentially the FRect data type with some added functionality. A FRect is floating point rectangle data type with float x, y, w, and h variables. At the top of the program I check if the box is touching the top, bottom, left or right of any of the platforms.
void Square::move( std::vector<Platform> &pf )
{
    FRect newColl = box, prevColl = box;
    Uint8 *keystates = SDL_GetKeyState( NULL );
    
    top = false, bottom = false, left = false, right = false;
    
    //Check for touching platforms
    for( int c = 0; c < pf.size(); c++ )
    {
        if( pf[ c ].on_top( box ) == true )
        {
            top = true;    
        }
        if( pf[ c ].below( box ) == true )
        {
            bottom = true;    
        }
        if( pf[ c ].left_of( box ) == true )
        {
            left = true;    
        }
        if( pf[ c ].right_of( box ) == true )
        {
            right = true;    
        }
    }



Then I handle when the box touches a ceiling/floor, gravity and when the user want to jump.
    //Roof/Ceiling collision
    if( top || bottom )
    {
        yVel = 0;    
    }
    
    //Gravity
    yVel += 1;
    
    //Jump
    if( top && keystates[ SDLK_w ] )
    {
        yVel = -JUMP_VEL;    
    }



Then I handle when the user wants to move left or right
    //Walking
    xVel = 0;
    if( keystates[ SDLK_a ] )
    {
        xVel += -DOT_VEL;
    }
    else if( keystates[ SDLK_d ] )
    {
        xVel += DOT_VEL;
    }



Now that the user input set the velocities, I set the new x and y offsets (nX,nY) of where the block wants to go. If the block is trying to go through a floor/ceiling/wall, I set the new x or y offset to be the old one.
    //Reset new offsets
    nX = box.x;
    nY = box.y;
    
    //Set new offsets 
    nX += xVel;
    nY += yVel;

    //Wall handling
    if( top && ( nY >= box.y ) )
    {
        nY = box.y;
    }
    if( bottom && ( nY <= box.y ) )
    {
        nY = box.y;
    }

    //Floor/Ceiling handling
    if( left && ( nX >= box.x ) )
    {
        nX = box.x;
    }
    if( right && ( nX <= box.x ) )
    {
        nX = box.x;
    }



Then I go through the platforms and using check_delta collision() I check if the block tries to pass through any of the platforms trying to get to it new offsets. If it does, I find the collision point using collision_point(). collision_point() returns a version of the block's collision box at the point it collided with the platform.
    //Search for collision
    int index = -1;
        
    for( int c = 0; c < pf.size(); c++ )
    {
        if( check_delta_collision( box.x, box.y, nX, nY, box, pf[ c ] ) == true )
        {
            newColl = collision_point( box.x, box.y, nX, nY, box, pf[ c ] );



Since it's possible for the block to try to pass through multiple platforms, I find the nearest collision point.
            //No previous collision
            if( index == -1 )
            {
                index = c;
                prevColl = newColl;
            }
            //New collision
            else
            {
                if( distance( box.x, box.y, newColl.x, newColl.y ) <
                distance( box.x, box.y, prevColl.x, prevColl.y ) )
                {
                    index = c;
                    prevColl = newColl;
                }
            }
                
        }
    }



If a collision is found, the block moves to the collision point. Otherwise it simply moves to the new points. At the bottom of the move() function I have a debug mechanism.
    //Collision found
    if( index != -1 )
    {
        box = newColl;
    }
    else
    {
        box.x = nX;
        box.y = nY;
    }
    
    char string[ 100 ] = "";
    sprintf( string, "Gravity x:%f y:%f nX:%f nY:%f I:%d", box.x, box.y, nX, nY, index );
    SDL_WM_SetCaption( string, NULL );
}



Is there anything wrong with my design or is there a better way to do this? If not, then there's either something wrong with my math, algorithms or there's a floating point quirk. Using that debug mechanism at the bottom of the move() function I found out that collision_point() doesn't return the proper collision point. Here's the code I use to find the collision point:
FRect collision_point( float x1, float y1, float x2, float y2, FRect a, FRect b )
{
    FRect start = a, end = a, test = start;
    float slope = get_slope( x1, y1, x2, y2 );
    
    start.x = x1;
    start.y = y1;
    end.x = x2;
    end.y = y2;
    
    //Left collision
    if( start.x < end.x )
    {
        test.x = b.x - test.w;
        test.y = slope * ( test.x - start.x ) + start.y;
        
        if( ( test.y > b.y + b.h ) || ( test.y + test.h < b.y ) )
        {
            test = start;
        }
        else
        {
            return test;   
        }
    }
    //Right collision
    if( start.x > end.x )
    {
        test.x = b.x + b.w;
        test.y = slope * ( test.x - start.x ) + start.y;
        
        if( ( test.y > b.y + b.h ) || ( test.y + test.h < b.y ) )
        {
            test = start;
        }
        else
        {
            return test;
        }
    }
    
    //Top Collision
    if( start.y < end.y )
    {
        test.y = b.y - test.h;
        
        if( slope != 0 )
        {
            test.x = ( ( test.y - start.y ) / slope ) + start.x;
        }
        
        if( ( test.x > b.x + b.w ) || ( test.x + test.w < b.x ) )
        {
            test = start;
        }
        else
        {
            return test;
        }
    }
    //Bottom Collision
    if( start.y > end.y )
    {
        test.y = b.y + b.h;
        
        if( slope != 0 )
        {
            test.x = ( ( test.y - start.y ) / slope ) + start.x;
        }
        
        if( ( test.x > b.x + b.w ) || ( test.x + test.w < b.x ) )
        {
            test = start;
        }
        else
        {
            return test;
        }
    }

    /*
    test.x = x2;
    test.y = y2;
    */
    
    return test;
}



When collision_point() can't find the proper collision point it just returns the initial point. This is what is causing it to get stuck in one place since it detects a collision but it can't find a proper collision point. I have commented out a band aid solution that would move it to the new offsets. This semi-works because in the next frame it'll put it where it should be, but if the wall is really thin or the block is going really fast it'll go clean though. If there's nothing wrong with the math or my algorithm for finding the collision point, could it be some floating point quirk? Or should I just scrap everything and try a different approach? [Edited by - Lazy Foo on October 1, 2007 5:13:39 PM]

Share this post


Link to post
Share on other sites
I just read the cliff notes version and know you've got a problem with collision, so sorry if this is ignorant to your question.

Some things that may cause problems if you don't do them.

1. Don't run collision detection once. Do it, and if there was a collision, do it again to make sure there isn't another collision where the object was moved to. Repeat as needed.

2. Don't move your object any distance in one cycle greater than the size of your tiles. If you do, test for collision along it's movement path every (tile_width) until you get to the corner of the object in the direction it's moving.

That might help.

Share this post


Link to post
Share on other sites
Quote:
Original post by JavaMava
2. Don't move your object any distance in one cycle greater than the size of your tiles. If you do, test for collision along it's movement path every (tile_width) until you get to the corner of the object in the direction it's moving.


This is precisely what I'm trying to avoid. I want to have this completely independent of how fast the block is moving or where the platforms are placed.

I could do an "inching" mechanism where the block moves a pixel at a time, check for collision, block moves another pixel, check again, etc, etc but this would waste CPU.

Share this post


Link to post
Share on other sites
Quote:
Original post by Lazy Foo
Quote:
Original post by JavaMava
2. Don't move your object any distance in one cycle greater than the size of your tiles. If you do, test for collision along it's movement path every (tile_width) until you get to the corner of the object in the direction it's moving.


This is precisely what I'm trying to avoid. I want to have this completely independent of how fast the block is moving or where the platforms are placed.

I could do an "inching" mechanism where the block moves a pixel at a time, check for collision, block moves another pixel, check again, etc, etc but this would waste CPU.
I also only skimmed the bulk of the post, but have you looked into using a swept separating axis test? This is the most effective and straightforward method I'm aware of for handling continuous collision detection between polytopes in 2D, and when coupled with a discrete test as a 'backup' it can produce very nice (and robust) results.

Eliminating the kinds of glitches you're talking about can be tricky regardless of what collision detection method is used, but I think you might have better luck with swept SAT than with your current method (which, although I only glanced at your code samples, I gather is not a traditional SAT implementation).

Also, FYI, swept SAT with axis-aligned boxes is covered in one of the 'collision detection' articles here on GDNet (I think the author is Gomez).

Share this post


Link to post
Share on other sites
Quote:
Original post by Lazy Foo
I could do an "inching" mechanism where the block moves a pixel at a time, check for collision, block moves another pixel, check again, etc, etc but this would waste CPU.


If you're really stuck, and want to improve on this approach, you could try (in effect) a binary search for the time of collision. Check for collision at t + dt, then t + .5dt, then t + (.25 or .75)dt etc.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
If you're really stuck, and want to improve on this approach, you could try (in effect) a binary search for the time of collision. Check for collision at t + dt, then t + .5dt, then t + (.25 or .75)dt etc.
No. That (alone) doesn't work. In the case where you terminate with no collision at time t+dt you could in fact have tunnelled past an object when dt is large or the object is small. To ensure there is no tunnelling you need to change the BV bounds when you do the interval halving.


Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
I also only skimmed the bulk of the post, but have you looked into using a swept separating axis test? This is the most effective and straightforward method I'm aware of for handling continuous collision detection between polytopes in 2D, and when coupled with a discrete test as a 'backup' it can produce very nice (and robust) results.

Eliminating the kinds of glitches you're talking about can be tricky regardless of what collision detection method is used, but I think you might have better luck with swept SAT than with your current method (which, although I only glanced at your code samples, I gather is not a traditional SAT implementation).

Also, FYI, swept SAT with axis-aligned boxes is covered in one of the 'collision detection' articles here on GDNet (I think the author is Gomez).


Yeah I found it. I don't understand it, but I just skimmed over it. Right now I need to get my next article out.

This will probably be a better solution considering my next game will require collision detection with triangles, circles, and rotated squares.

Share this post


Link to post
Share on other sites

This topic is 3723 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this