• Create Account

## Collision detection with tiles

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

7 replies to this topic

### #1Kain5056  Members

502
Like
0Likes
Like

Posted 01 February 2013 - 04:52 AM

Hello everybody.

I'm trying to learn how to make games with SDL and C++ using mainly LazyFoo's tutorials.

Everything was going relatively well, until I stumbled upon a problem I do not know how to solve.

I have a tile based map, and up until now I was capping the frame rate and the character moved fine around the map. When the player contacted a tile, I was subtraction the velocity from the player's position, and it worked fine.

But after I started using frame independent movement, subtracting the velocity obviously stopped working, and I'm not sure what to do now.

The ideal, I think, would be to set the player's contacting side to not be greater than the tile's (kind of like I handle the player's contact with the level's boundaries), but the way I handle the tile map I don't know how to get the tile's position.

Here is my code. I'm very new at programming, so it might be a bit crude:

Collision detection:

bool collision( SDL_Rect a , SDL_Rect b )
{
int lefta , leftb;
int righta , rightb;
int topa , topb;
int bottoma , bottomb;

lefta = a.x;
righta = a.x + a.w;
topa = a.y;
bottoma = a.y + a.h;

leftb = b.x;
rightb = b.x + b.w;
topb = b.y;
bottomb = b.y + b.h;

if( righta <= leftb || lefta >= rightb || bottoma <= topb || topa >= bottomb ) return false;

return true;
}


Tile setting and tile collision detection:

bool collision( SDL_Rect a , tile * tiles[] )
{
for( int t = 0 ; t < TOTAL_TILES ; t++ )
{
if( tiles[t]->get_type() == PLATFORM )
{
if( collision( a , tiles[t]->get_box() ) ) return true;
}
}

return false;
}

bool set_tiles( tile * tiles[] )
{
int x = 0;
int y = 0;

std::ifstream map( "tilemap.map" );

if( map == NULL ) return false;

for( int t = 0 ; t < TOTAL_TILES ; t++ )
{
int type = 0;
map >> type;

if( map.fail() )
{
map.close();
return false;
}

if( type >= 0 && type < TILE_SPRITES ) tiles[t] = new tile( x , y , type );
else
{
map.close();
return false;
}

x += TILE_WIDTH;

if( x >= LEVEL_WIDTH )
{
x = 0;
y += TILE_HEIGHT;
}
}

map.close();
return true;
}


Player movement:

void player::move( Uint32 delta_ticks , tile * tiles[] )
{
x += xvel * ( delta_ticks / 1000.f );

if( x < 0 ) x = 0;
if( x + PLAYER_WIDTH > LEVEL_WIDTH ) x = LEVEL_WIDTH - PLAYER_WIDTH;

if( collision( box , tiles ) )
{
if( xvel > 0 ) ///WHAT DO I DO HERE?///
else if( xvel < 0 ) ///WHAT DO I DO HERE?///
}

y += yvel * ( delta_ticks / 1000.f );

if( collision( box , tiles ) )
{
if( yvel >= 0 )
{
///WHAT DO I DO HERE?///
jumping = false;
}
else ///WHAT DO I DO HERE?///
}
else yvel += gravity;

if( yvel >= VELOCITY * 8 ) yvel = VELOCITY * 8;

if( y > LEVEL_HEIGHT + 50 )
{
y = 0;
x = 0;
status = FACING_RIGHT;
}

box.x = x;
box.y = y;
}


I have also tried to seperate vertical from horizontal collision detection, but it did not seem to help.

The best I could think of to do it is this:

bool horizontal_collision( SDL_Rect a , SDL_Rect b )
{
int lefta , leftb;
int righta , rightb;
int topa , topb;
int bottoma , bottomb;

lefta = a.x;
righta = a.x + a.w;
topa = a.y;
bottoma = a.y + a.h;

leftb = b.x;
rightb = b.x + b.w;
topb = b.y;
bottomb = b.y + b.h;

if( righta >= leftb && lefta <= rightb && bottoma > topb && topa < bottomb ) return true;

return false;
}

bool vertical_collision( SDL_Rect a , SDL_Rect b )
{
int lefta , leftb;
int righta , rightb;
int topa , topb;
int bottoma , bottomb;

lefta = a.x;
righta = a.x + a.w;
topa = a.y;
bottoma = a.y + a.h;

leftb = b.x;
rightb = b.x + b.w;
topb = b.y;
bottomb = b.y + b.h;

if( bottoma >= topb && topa <= bottomb && righta > leftb && lefta < rightb ) return true;

return false;
}


I've been trying various thing for three days now, but nothing seems to work. So a little help from someone more experienced would be appreciated.

### #2Khatharr  Members

7687
Like
1Likes
Like

Posted 01 February 2013 - 05:19 AM

The best solution is to pass small enough timeslices into the simulation that you only move one pixel at a time. Then if you collide you can simply undo the motion (subtract velocity*timeslice). If this is too heavy then another option is to run the simulation with moderately sized slices and then if you detect a collision reverse the simulation with minimal steps until you don't anymore. From there you can check x and y motion independently to see if one or the other is solely responsible for the collision in order to find out if you hit a wall, ceiling, ground or corner or whatever.

So in other words if your maximum speed is 10 pixels per second you'd want the maximum timeslice to be 1/10 seconds. If 3/10 seconds have passed then just update the simulation 3 times with 1/10 seconds and then render once.

void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

### #3BeerNutts  Members

4288
Like
1Likes
Like

Posted 01 February 2013 - 10:49 AM

But after I started using frame independent movement, subtracting the velocity obviously stopped working, and I'm not sure what to do now.

That doesn't make any sense to me.  Why does it "obviously" stop working?  Frame independent or not, if the previous time through the loop, the player wasn't colliding, and the next time, you move the player, and now he IS colliding, then moving him back the amount he just moved should place you in the previous location.

void player::move( Uint32 delta_ticks , tile * tiles[] )
{
double previousX = x;
double previousY = y;
x += xvel * ( delta_ticks / 1000.f );

if( x < 0 ) x = 0;
if( x + PLAYER_WIDTH > LEVEL_WIDTH ) x = LEVEL_WIDTH - PLAYER_WIDTH;

if( collision( box , tiles ) )
{
x = previousX; // just reset him to where he was
}


My Gamedev Journal: 2D Game Making, the Easy Way

---(Old Blog, still has good info): 2dGameMaking
-----
"No one ever posts on that message board; it's too crowded." - Yoga Berra (sorta)

### #4Kain5056  Members

502
Like
0Likes
Like

Posted 01 February 2013 - 11:20 AM

It seems I had a serious case of analysis paralysis, overthinking this all along.

Thank you both so much for the help. Thanks to both of your suggestions, I got it to work almost perfectly.

When I have it in perfect working order, I will post the code here.

Thank you again!

### #5fastcall22  Moderators

9747
Like
1Likes
Like

Posted 01 February 2013 - 11:57 AM

Then if you collide you can simply undo the motion (subtract velocity*timeslice)

... then moving him back the amount he just moved should place you in the previous location.

I would advise against undoing the motion of colliding objects. What would happen if a moving platform collides with an idle player? With this approach, the player would be stuck until the platform stops colliding with the player because the player cannot move far enough to avoid collision inside the platform. What would happen if a player tries to slide against a wall while falling? Because the motion is the motion (including gravity) is undone, and the player sticks to the wall.

You might want to consider a function to determine the minimal amount of movement needed the x and y direction that a colliding object will need to move in order to prevent collision. This can be determined by comparing the distances between the left and right, top and bottom of the first object with the left and right, top and bottom of the second object. You can also determine which side(s) of an object is hit by the colliding object.

Edited by fastcall22, 01 February 2013 - 12:00 PM.

zlib: eJzVVLsSAiEQ6/1qCwoK i7PxA/2S2zMOZljYB1TO ZG7OhUtiduH9egZQCJH9 KcJyo4Wq9t0/RXkKmjx+ cgU4FIMWHhKCU+o/Nx2R LEPgQWLtnfcErbiEl0u4 0UrMghhZewgYcptoEF42 YMj+Z1kg+bVvqxhyo17h nUf+h4b2W4bR4XO01TJ7 qFNzA7jjbxyL71Avh6Tv odnFk4hnxxAf4w6496Kd OgH7/RxC

### #6Khatharr  Members

7687
Like
0Likes
Like

Posted 02 February 2013 - 04:21 AM

fastcall22, on 01 Feb 2013 - 10:05, said:
You might want to consider a function to determine the minimal amount of movement needed the x and y direction that a colliding object will need to move in order to prevent collision.

That's... Kind of exactly what we were just talking about....

???
void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

### #7Kain5056  Members

502
Like
0Likes
Like

Posted 11 February 2013 - 08:41 AM

No, now that I'm trying to implement moving tiles, I understand exactly what he means.

If the colliding tile moves and the player stands still, there is no previous x for the player to move back to.

So I made "return x" and "return y" functions in the tile class, and now I'm trying to make a collision detection function that returns 1 if the right side of the player collides with the left side of the tile, and 2 if the left side of the player collides with the right side of the tile.

Then another function returns the tile's x minus the player's width in the first case, and the tile's x plus the tile's width in the second case.

All I have to do then, is give the return value of the last function to the player's x.

For some reason, though, the collision detection function only returns the first case.

int hor_collision( SDL_Rect a , SDL_Rect b )
{
int lefta , leftb;
int righta , rightb;
int topa , topb;
int bottoma , bottomb;

lefta = a.x;
righta = a.x + a.w;
topa = a.y;
bottoma = a.y + a.h;

leftb = b.x;
rightb = b.x + b.w;
topb = b.y;
bottomb = b.y + b.h;

if( righta >= leftb && ( bottoma >= topb || topa <= bottomb ) ) return 1;
if( lefta <= rightb && ( bottoma >= topb || topa <= bottomb ) ) return 2;

return 0;
}

So as it is now it always returns 1, and if I do this...

    if( lefta <= rightb && ( bottoma >= topb || topa <= bottomb ) ) return 2;
if( righta >= leftb && ( bottoma >= topb || topa <= bottomb ) ) return 1;

return 0;
}

...It always returns 2.

Edited by Kain5056, 11 February 2013 - 08:43 AM.

### #8Khatharr  Members

7687
Like
0Likes
Like

Posted 11 February 2013 - 03:11 PM

Kain5056, on 11 Feb 2013 - 06:49, said:
No, now that I'm trying to implement moving tiles, I understand exactly what he means.
If the colliding tile moves and the player stands still, there is no previous x for the player to move back to.

That's just a different handling case, isn't it? Collision in that case would be driven by the platform entity rather than the player entity. You just have to decide on and implement a reaction to the collision when it's driven by the platform. If the platform is pushing on the player then it doesn't make sense to look at the player's previous position. It only makes sense to look at that when the player is being moved.

Unless I'm totally missing something here.

?
void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.