Sign in to follow this  
Svalorzen

Collision Detection Problem

Recommended Posts

Svalorzen    128
Hello everybody! I'm kind of going crazy over an absurd problem of collision detection. Basically, the system ( which is HGE ) reports a collision when my player box is standing on the floor ( player_box.low_y = floor.high_y ). This not only does not make any sense, but the same result does not happen when I hardcode two boxes one standing over the other, so I don't really know what to think.. This is my code:
void Fighter::think () {
    // H COLLISIONS HANDLING
    hgeRect fTry = fSpace;				// Copies Fighter bounding box
    // hSpeed > 0 :     RIGHT
    // hSpeed = 0 :     NOT MOVING
    // hSpeed < 0 :     LEFT
    float hSpeed = fSoul.getDx();		// Gets Fighter horizontal speed

    if ( hSpeed != 0 ) {				// If there is a possible collision to manage..

        // Projects Self into the Future
        if ( hSpeed > 0 )				// Expands the bounding box in the moving direction
            fTry.x2 += hSpeed;
        else
            fTry.x1 += hSpeed;

        // if cannot go there ( foreach square TODO )
        if ( fTry.Intersect( &rightWall ) ) {
            // Limits hSpeed
            if ( hSpeed > 0 )
                fSoul.setDx( rightWall.x1 - fSpace.x2 );	// Limits speed to space between Fighter and the wall
            else
                fSoul.setDx( rightWall.x2 - fSpace.x1 );
        }

    }

    // V COLLISIONS HANDLING
    fTry = fSpace;						// Resets try bounding box
    // vSpeed > 0 :     FALLING
    // vSpeed = 0 :     NOT MOVING
    // vSpeed < 0 :     RAISING
    float vSpeed = fSoul.getDy();		// Gets Fighter vertical speed

    if ( vSpeed != 0 ) {				// If there is a possible collision to manage..
										// NOTE: Due to gravity, vSpeed is usually never 0; at least 0.3
        // Projects Self into the Future
        if ( vSpeed > 0 )
            fTry.y2 += vSpeed;
        else
            fTry.y1 += vSpeed;

        // Cannot go there ( foreach square TODO )
        if ( fTry.Intersect( &floor ) ) {
            // FLOW ENTERS HERE EVEN THOUGH IT SHOULDN'T
            // Limits hSpeed
            if ( vSpeed > 0 ) {
                fSoul.setDy( floor.y1 - fSpace.y2 );
                // Resets Available Jumps
                fJumps = N_JUMPS;
            }
            else ; // AND ENDS UP HERE
                // commented this because otherwise my sprite vanishes =P
                // fSoul.setDy( floor.y2 - fSpace.y1 );
        }
    }
}

The handling for the horizontal and vertical part are exactly the same, but the problem rises when I try to jump after I'm landed on the floor. Then the game detects an intersection between my sprite and the floor, even though that is impossible ( I've debugged tracking all the variables.. ). It seems all right to me =( If you need additional information just let me know! Thanks in advance for any advices!

Share this post


Link to post
Share on other sites
hallgeir    154
One thing that comes to mind is floating point precision errors. If you have two floating point numbers (I assume that player_box.low_y and floor.high_y is floating point and not integers), you can't guarantee that the check (player_box.low_y == floor.high_y) returns true even if they seems to be equal. In the same way, you can't guarantee that player_box.low_y - floor.high_y returns 0, even if they are equal.

I had an error like that yesterday as well, and it took a while to find the problem (collisions were missed randomly, or so it seemed). I noticed that when my collision box' lower y value and the ground surface's y value were equal, the distance wasn't 0, it was something like 1e-15, or sometimes -1e-15 (or some other very small number).

So what you can try is what I did, do a "if (abs(player_box.low_y - floor.high_y) < 1e-12) distance = 0; else distance = player_box.low_y - floor.high_y;" on your distance calculations, and other floating point operations which may be sensitive to precision errors.

Hope this helps.

Edit: My numbers are based on double precision floats. Since you're using single precision floats, you might need a higher threshold.

Share this post


Link to post
Share on other sites
Narf the Mouse    322
Also, if your sprite is subject to gravity, it might go like this: Sprite lands. Sprite is dragged down Y distance by gravity. Sprite is checked for a collision, which now exists. Sprite is moved up Y distance to resolve the collision.

From the computer's viewpoint, the sprite is always colliding. But, because the collision is fixed before the player can see it...

Edit: Nevermind, you check for that. Provided that check works, it shouldn't happen.

Share this post


Link to post
Share on other sites
Svalorzen    128
Thanks for the heads up!

I've checked my code and these are the results:

- if I put a
if ( player_box.low_y != floor.high_y )
check_collision_code();
it works. ( but I cannot use this solution as it introduces a new couple of bugs, and it's also bad code which I really cannot stand )

- if I put a
if ( abs( player_box.low_y - floor.high_y ) < 1e-12 )
player_box.low_y = floor.high_y;
before the check collision code it still doesn't work, even though it actually enters the if.

There are another couple of things I didn't say about this problem:

1) I've debugged my code, and usually the variable watches signal when there is a problem with floats ( for example, my gravity offset is reported as 0.29999999998 ), but the Ys of the two boxes do not have any floating part.

2) If I set the floor bounding box a little more higher, let's say above 600, my code works. If I move the floor lower, at 700, the bug reappears. This could be related to non-integer movement; though to me it seems unlikely, because the limit that trigger the bug is precise ( 639 ).


Also, is there a way to automatically round floats to max 2 decimal digits? If I could do that I could avoid in block all this kind of problems..

Share this post


Link to post
Share on other sites
Narf the Mouse    322
My first instinct there would be to check collision to make sure I'm checking against either all relative or all absolute positions and not, say, relative and absolute positions, somewhere.

Share this post


Link to post
Share on other sites
Svalorzen    128
I'm sure I'm doing the check with the absolute position of every box, mostly because I never use a relative position for anything =P

Share this post


Link to post
Share on other sites
Svalorzen    128
x1, y1 stand for the coordinates of the top-left vertex of the box.
x2, y2 stand for the coordinates of the bottom-right vertex of the box.

The intersection function is not mine, it's the one written in the HGE engine, so I think it's correct.

I've found the bug though.
It's here, when I expand the fighter's box:


if ( vSpeed > 0 )
fTry.y2 += vSpeed;
else
fTry.y1 += vSpeed; // This triggers the bug with the intersection


Now I've found it.. but still this line shouldn't trigger a collision downwards!

Ideas?

Share this post


Link to post
Share on other sites
Mussi    4408
Quote:
Then the game detects an intersection between my sprite and the floor, even though that is impossible


Why?

Quote:
// Projects Self into the Future
if ( vSpeed > 0 )
fTry.y2 += vSpeed;
else
fTry.y1 += vSpeed;


This shrinks and grows your collision box?

Quote:

if ( fTry.Intersect( &floor ) ) {
// FLOW ENTERS HERE EVEN THOUGH IT SHOULDN'T
// Limits hSpeed
if ( vSpeed > 0 ) {
fSoul.setDy( floor.y1 - fSpace.y2 );


I assume if you fall down that floor.y1 is bigger than fSpace.y2, right? This would give you a positive speed in the y direction, is that correct?

And since this problem you're having is jump related, what actually happens when you jump?

Share this post


Link to post
Share on other sites
Svalorzen    128
Quote:

Quote:

Then the game detects an intersection between my sprite and the floor, even though that is impossible

Why?


Because I've checked the values at running time, and the Intersection function shouldn't return 1..

Quote:

Quote:

// Projects Self into the Future
if ( vSpeed > 0 )
fTry.y2 += vSpeed;
else
fTry.y1 += vSpeed;

This shrinks and grows your collision box?


Actually, it should only grow it. More precisely, it should reduce the lower side while the player is falling, or it should raise the upper side while the player is rising, in this order.

Quote:

I assume if you fall down that floor.y1 is bigger than fSpace.y2, right? This would give you a positive speed in the y direction, is that correct?

And since this problem you're having is jump related, what actually happens when you jump?


Since floor.y1 is the y coordinate of the floor upper side, it should always be >= of every y coordinate of the player ( since it should be down =P ), regardeless of the player speed. However, when the player is falling, the test box y2 could be lower than floor.y1, since it's been expanded to check for future collisions.

The problem I'm having happens when I try to jump after been landed on the floor. Then, the code registers that I'm trying to go upwards, expands the hitbox in that sense, and then checks for collisions with the floor.
Then it actually checks for collisions, decides ( and why is beyond my comprehension ) that there IS actually a collision, it enters the collision handling code as if the player was colliding with the ceiling ( since he is trying to go upwards ) and then it calculates a new speed ( which is ofc wrong ) and the player gets shot downwards.

However, if I comment the code that expands the hitbox when the player is rising, this bug disappears ( but the collision detection with ceilings is consequently deactivated ). And this doesn't make any sense, because the collision with the floor should be dependant from the player.y2 and floor.y1, neither of which is modified by that else..

I hope I've been clear! Sorry for my baaad english xD

Share this post


Link to post
Share on other sites
Svalorzen    128
Ok, since at every debug step I'm convincing more myself that the bug is in the HGE collision, I'm posting the intersection code. I'll try to understand what it does, but if someone sees bugs before me it's better ^_^

bool hgeRect::Intersect(const hgeRect *rect) const
{
if(fabs(x1 + x2 - rect->x1 - rect->x2) < (x2 - x1 + rect->x2 - rect->x1))
if(fabs(y1 + y2 - rect->y1 - rect->y2) < (y2 - y1 + rect->y2 - rect->y1))
return true;

return false;
}






I think the problem arises with floats, even though I'm still not sure how..

EDIT:
Added the function with my actual data, taken from the debugger:


player.x1 = 200
player.y1 = 630.299988
player.x2 = 250
player.y2 = 690

floor.x1 = 0
floor.y1 = 690
floor.x2 = 800
floor.y2 = 700

if(fabs(200 + 250 - 0 - 800) < (250 - 200 + 800 - 0))
if(fabs(630.299988 + 690 - 690 - 700) < (690 - 630.299988 + 700 - 690))
return true;

if ( fabs ( -350 ) < ( 850 ) )
if ( fabs ( -69,700012 ) < 69,700012 ) )
return true;





So this

fabs(630.299998 + 690 - 690 - 700) < (690 - 630.299998 + 700 - 690)

and also this

fabs(630.3f + 690.0f - 690.0f - 700.0f) < (690.0f - 630.3f + 700.0f - 690.0f)

SHOULDN'T return true, even though they do.

What should I do? =(

[Edited by - Svalorzen on May 3, 2010 7:41:51 PM]

Share this post


Link to post
Share on other sites
Mussi    4408
Quote:
Because I've checked the values at running time, and the Intersection function shouldn't return 1..


My question why shouldn't it return 1, as in what criteria have you met for that result to be impossible.

Quote:
Actually, it should only grow it. More precisely, it should reduce the lower side while the player is falling, or it should raise the upper side while the player is rising, in this order.


Doesn't the rectangle work like windows rectangles? So top of the screen is 0, going down increases that number. Or better yet, isn't y1 smaller than y2? If that is the case then you should do a fTry.y1 -= vSpeed for the upper side to raise.

What sign(- or +) for the speed makes you go up or down? are you sure the sign changes when you jump?

Share this post


Link to post
Share on other sites
Svalorzen    128
Quote:

Quote:

Because I've checked the values at running time, and the Intersection function shouldn't return 1..

My question why shouldn't it return 1, as in what criteria have you met for that result to be impossible.


Because the two boxes I chech with the intersection function are not colliding; at running time I have fTry.y1 < fTry.y2 = floor.y1 < floor.y2

Quote:

Doesn't the rectangle work like windows rectangles? So top of the screen is 0, going down increases that number. Or better yet, isn't y1 smaller than y2? If that is the case then you should do a fTry.y1 -= vSpeed for the upper side to raise.

What sign(- or +) for the speed makes you go up or down? are you sure the sign changes when you jump?


Yes, it works like windows rectangles. The top left corner of the screen is 0,0; the bottom right is window_width, window_height. y1 must be always less or equal than y2 ( though in my case it's always less ). My code is right, and I should fTry.y1 += vSpeed to rise the upper side because if the player is rising his speed is < 0, so adding it to y1 is equal to subtracting the abs value of the speed. And finally, yes, I'm sure that the sign changes ( from looking the debugger watches ).

As I said, I actually found the root of the problem, which is in the result of the fabs inequalities in the intersection code ( which is not mine ). In fact, they do not work when I have certain values for the floating point variables.
Now my only problem is what should I do to make the collision function work with any values..

Share this post


Link to post
Share on other sites
Narf the Mouse    322
One other collision code you could try is just to check wether the left side of box A is farther right than the right side of box B, reverse respectively and check top and bottom the same.

CenterA.X - HalfSizeA.X > CenterB.X + HalfSizeB.X and whatnot. Tired.

Share this post


Link to post
Share on other sites

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