Sign in to follow this  

collision test between two 2D sprites

This topic is 4227 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

There are two rectangular sprites. The red sprite is at a fixed position, The cyan sprite is moving from one position to another with delta dx and dy. Both sprites can have arbitrary sizes but their collision is always rectangular. They're in a 2D world. Image Hosted by ImageShack.us I'd like to detect whether the moving sprite will collide with the red one or not. If it collides, I want it to stop right at the location where it starts colliding (the green box in the picture). How to do this in an efficient and not too messy way?

Share this post


Link to post
Share on other sites
Separating axis theorem. Assuming your rects are axis-aligned, there's a nice article on the subject (with code) in the gdnet articles section. (It's a gamasutra article, by Gomez I believe, and the swept AABB test is included.)

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk there's a nice article on the subject (with code) in the gdnet articles section. (It's a gamasutra article, by Gomez I believe, and the swept AABB test is included.)
By coincidence.. I was just locating the same article
AABB Sweep Tests (Gomez)
It's explained very well, but his implementation ain't great.
He doesn't include (or take account of) a number of "early outs"..
eg.: The AABB begin seperated (not overlapping) and are seperating (moving apart) in any axis...

That said, the algorithm is simple enough, it shouldn't be too taxing to produce you own implementation based on his description.

Share this post


Link to post
Share on other sites
I was struggling with this simple problem myself for a while, but heres a basic example how you do it.

Lets assume this is a 2d tiled world, 32x32 pixel tiles. We have a 2d array representing the world.

BYTE world[100][100];

Ok now in order to detect collsions theres a simple way to do it. Basicly you just divide the player X and Y positions against the tile pixel size wich is 32. For example:


// example player position
// player_x = 345;
// player_y = 653;

tile_position_x = player_x / 32;
tile_position_y = player_y / 32;

// tile_position_x == 10
// tile_position_y == 20








ok, thats great we got our current tile position of our character, but theres one problem. The position you test is just one pixel! So our top-left corner is basicly the only part of the character we have tested. There is a solution to that. What we need to do is test all 4 corners of the character.

Here is a full example of the collistion detection on all 4 corners. One note I want to add is the fact you have to first align the character to the tile going from a left or right then up or down motion. In other words you check the left and right sides of the character first, then check the top and bottom. This aligns the character on one axis before testing the other so there arnt any conflicts.



/* RUN THIS COLLISION TEST AFTER ONE FRAME OF PLAYER/CHARACTER MOVEMENT HAS BEEN COMPLETE */
#define TILE_SIZE = 32
#define NO_WALK = 0

// convert pixel positions to tile position on each corner
int x_left = player.x - 16 / TILE_SIZE; // LEFT SIDE
int x_right = player.x + 16 / TILE_SIZE; // RIGHT SIDE
int y_top = player.y - 16 / TILE_SIZE; // TOP SIDE
int y_bottom = player.y + 16 / TILE_SIZE; // BOTTOM SIDE


//------------------------------------------
// test left and right sides
//------------------------------------------
if( player.velx > 0 ) // player moving EAST -->>
{
// tests top right and bottom right corners (right side)
if( world[y_top][x_right] == NO_WALK || world[y_bottom][x_right] == NO_WALK)
{
player.x -= player.velx; // move back
}
}
if( pos[i].velx < 0 ) // player moving WEST <<--
{
// tests top left and bottom left corners (left side)
if( world[y_top][x_left] == NO_WALK || world[y_bottom][x_left] == NO_WALK)
{
player.x -= player.velx; // move back
}
}

//------------------------------------------
// test top and bottom sides
//------------------------------------------

/* note: we are reseting the tile position because we might
have moved player position while checking x axis */

int x_left = player.x - 16 / TILE_SIZE; // LEFT SIDE
int x_right = player.x + 16 / TILE_SIZE; // RIGHT SIDE
int y_top = player.y - 16 / TILE_SIZE; // TOP SIDE
int y_bottom = player.y + 16 / TILE_SIZE; // BOTTOM SIDE

/* player moving NORTH /\ */
if( player.vely < 0 )
{
// tests top left and top right corners (top side)
if( world[y_top][x_left] == NO_WALK || world[y_top][x_right] == NO_WALK)
{
player.y -= player.vely; // subtract velocity
}
}
/* player moving SOUTH \/ */
if( pos[i].vely > 0 )
{
// tests bottom left and bottom right corners (bottom side)
if( world[y_bottom][x_left] == NO_WALK || world[y_bottom][x_right] == NO_WALK)
{
player.y -= player.vely; // subtract velocity
}
}









Basicly your checking adding and subtracting the origin of the characters sprite, and depending on the pixel width/height you need to subtract/add to get to the "bounding box" of the sprite and just align against the tiles you dont want to walk through by stepping the sprite back.

Hope you can understand what im trying to say...i tried as hard as i could lol.

video i got bored and made a video of the "game" im working on with a few tanks running around into walls and changing random directions :D

[Edited by - NegativeGeForce on May 21, 2006 7:12:51 PM]

Share this post


Link to post
Share on other sites

This topic is 4227 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