(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]
