Sign in to follow this  
MottMan

[SDL] Efficient collision detection?

Recommended Posts

MottMan    100
I have been using the following code to check for collision detection for the player and the wall:


[code]
void Player::move()
{
player_outline.x += xVel;
if (...check_collision(player_outline, wall_outline))
player_outline.x -= xVel;

player_outline.y += yVel;
if (...check_collision(player_outline, wall_outline))
player_outline.y -= yVel;
}[/code]


This works fine but if there are a lot of different walls, barrels, obstacles, then the if statement will become quite large and system hogging. Is there a more efficient way to determine what to check/how to check for collision? I'm sure there must be.
Thanks in advance.

Share this post


Link to post
Share on other sites
0x3a    109
What you could do is write a general physics manager which you update every tick. When you create a new object ( a wall for example ) this is added to your list of physics objects and the physics manager calculates all the proper information in terms of collisions ( if there is any ), speed, acceleration, etc. This way you really only write gameplay and don't deal with physics inside the game itself, just an update call to your manager.

If that is too much work you can always go for a library to do this, if you work only in 2D I suggest using Box2D.

Share this post


Link to post
Share on other sites
MottMan    100
I'm more interested in writing it myself. Could you provide a link to an example?

I'm not worrying (or required to worry) about velocity, speed, or any other variables other than location. If you hit a wall, you should stop. I'm working with 2D strictly, yes.

Share this post


Link to post
Share on other sites
MottMan    100
Thanks [img]http://public.gamedev.net/public/style_emoticons/default/laugh.gif[/img]

Glancing at the source it seems overly complicated for what I need it for but should be helpful nonetheless.

Share this post


Link to post
Share on other sites
kdmiller3    178
What you want is a "spatial query", which allows you to ask what objects are in a particular area. There are a bunch of ways to do that depending on the size of your world and range of sizes of your objects. I'll throw out some terms for you to google: Spatial Hash (what Chipmunk uses), Sweep and Prune or Mark and Sweep (what Box2D used to use), and Bounding Volume Hierarchy (what Box2D uses now).

I'd look at how Chipmunk does it since its system is a lot simpler.

Spatial Hash divides the world into a grid and places objects into whatever grid cells they overlap. This works particularly well if your game is tile-based, since most objects will end up in at most one grid cell. When adding or removing an object, find what cells it covers and add it to or remove it from the hash table using the grid coordinates of those cells as keys. To find what objects are in an area, go through each cell that the area covers and return any objects you find. Depending on size and position, objects can cover more than one grid cell at a time so you need to mark objects so you don't return them more than once. Increment a counter every time you run a query, store that value into the object record when you visit it, and only return an object if the counter and the stored value don't match.

Share this post


Link to post
Share on other sites
MottMan    100
If I understand correctly there should be a piece of data in an obstacle and the player that identifies it's location on a grid (possibly an array) so that the collision detection function can see what obstacles are near the player and might be causing a collision?

Share this post


Link to post
Share on other sites
[quote name='MottMan' timestamp='1311613549' post='4840055']
If I understand correctly there should be a piece of data in an obstacle and the player that identifies it's location on a grid (possibly an array) so that the collision detection function can see what obstacles are near the player and might be causing a collision?
[/quote]

i just implemented a collision detection in my 2d Engine. You can take a look at the pictures on my blog how it works . Each tile has a bool value 0 or zero, which states if a tile is walkable or not.

then when i move the character, i scan all the tiles around the character (not all on the screen, because thats unnecessary) and if he collides i scan from which side. than i write everything in an char and go on..

here is the code

[code]
void AnimatedChar::collisionWithTile(WorldMap &current_map, u_int8_t &collision)

{

int m,n,i2,j2;



Rect2D tempRect;



tempRect.pos.y = this->rect.pos.y+this->rect.height/2;

tempRect.pos.x = this->rect.pos.x;

tempRect.width = this->rect.width;

tempRect.height = this->rect.height/2;



// starting points

m = tempRect.pos.x / TILE_SIZE;

n = tempRect.pos.y / TILE_SIZE;



// end points

i2 = ((tempRect.width+tempRect.pos.x)/ TILE_SIZE);

j2 = ((tempRect.pos.y+tempRect.height)/TILE_SIZE);



bool colup = false;

bool coldown = false;

bool colleft = false;

bool colright = false;

for (int i=m-2; i < i2+2; i++)

{

for (int j=n-1; j < j2+2; j++)

{

if (current_map.returnTileAt(i, j).isWalkable==false)

{



if (tempRect.pos.x + tempRect.width-CHARACTER_COLL_OFFSET < current_map.returnTileAt(i, j).x)

collision = NO_COLLISION;

else if (tempRect.pos.x+CHARACTER_COLL_OFFSET > current_map.returnTileAt(i, j).x + TILE_SIZE)

collision = NO_COLLISION;

else if (tempRect.pos.y + tempRect.height-CHARACTER_COLL_OFFSET+2 < current_map.returnTileAt(i, j).y)

collision = NO_COLLISION;

else if (tempRect.pos.y+CHARACTER_COLL_OFFSET > current_map.returnTileAt(i, j).y + TILE_SIZE)

collision = NO_COLLISION;

else

{




// COLLISION

if (tempRect.pos.y + tempRect.height > current_map.returnTileAt(i, j).y && tempRect.pos.y < current_map.returnTileAt(i, j).y)

{

coldown = true;

}

if (tempRect.pos.x < current_map.returnTileAt(i, j).x + TILE_SIZE &&

tempRect.pos.x + tempRect.width > current_map.returnTileAt(i, j).x + TILE_SIZE)

{

colleft = true;

}

if (tempRect.pos.x + tempRect.width > current_map.returnTileAt(i, j).x &&

tempRect.pos.x < current_map.returnTileAt(i, j).x)

{

colright = true;

}

if (tempRect.pos.y < current_map.returnTileAt(i, j).y+TILE_SIZE && tempRect.pos.y + tempRect.height > current_map.returnTileAt(i, j).y + TILE_SIZE)

{

colup = true;

}






}

}

}

}

// write all values in collision

collision = (coldown<<3)|(colleft<<2)|(colright<<1)|colup;

}


[/code]

Then i check when the character moves the following:

[code]
void AnimatedChar::update_position(WorldMap &current_map)

{

if (this->isMoving)

{

if (this->rect.pos.x < 0)

{

this->rect.pos.x = 0;

}

else if (this->rect.pos.y < 0-this->rect.height/2)

{

this->rect.pos.y = 0-this->rect.height/2;

}

else if (this->rect.pos.x+this->rect.width > current_map.get_world_width())

{

this->rect.pos.x = current_map.get_world_width()-this->rect.width;

}

else if (this->rect.pos.y+this->rect.height > current_map.get_world_height())

{

this->rect.pos.y = current_map.get_world_height()-this->rect.height;

}

else

{

Point2D temp;

temp.x = rect.pos.x;

temp.y = rect.pos.y;



if (this->viewDirection==DOWN)

{

this->rect.pos.y += this->movingSpeed;

}

else if(this->viewDirection==LEFT)

{

this->rect.pos.x -= this->movingSpeed;

}

else if(this->viewDirection==RIGHT)

{

this->rect.pos.x += this->movingSpeed;

}

else if(this->viewDirection==UP)

{

this->rect.pos.y -= this->movingSpeed;

}



u_int8_t collision=0;

this->collisionWithTile(current_map, collision);



if (this->viewDirection==DOWN && collision>>3&0x1)

{

this->rect.pos.y = temp.y-6.0f;

this->isMoving=false;

}

if (this->viewDirection==LEFT && collision>>2&0x1)

{




this->rect.pos.x = temp.x+1.0f;

this->isMoving=false;

}

if (this->viewDirection==RIGHT && collision>>1&0x1)

{




this->rect.pos.x = temp.x-1.0f;

this->isMoving=false;

}

if (this->viewDirection==UP && collision&0x1)

{




this->rect.pos.y = temp.y+1.0f;

this->isMoving=false;

}



}

}

}

[/code]







maybe it helps u a little bit, if u have any questions feel free to ask.







Share this post


Link to post
Share on other sites
_Zac_    138
Like what KDMiller3 said, you should create a function that will tell you if there is nothing taking space in the location you want to move to. So like if(areaAvailabe(<where player wants to move>)) returns true then proceed to move the player there. Though it's mostly the reverse of what you're doing now.

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