Sign in to follow this  
schupf

Simple collision response

Recommended Posts

Hello,

I need a simple collision response between AABB vs AABB. Most of my objects are static AABBs and some are moving AABBs. I just need to resolve the collision of the few moving AABBs (aka if one of the moving AABBs penetrated a static or other moving AABB, I want to push it out of the intersected AABB).

I googled a lot, but I have found surprisingly few articles about this topic (even though its a common problem).
I have found 2 short articles (like this http://lj9.mexinetica.com/bloginetica/comentarios.shtml?2011.01.14.14.04.11.+01. ), but I wonder why they just operate on the AABBs and never take into account the movement direction of the moving AABB.

I added a sketch as attachment to show you what I mean. In both cases the moving box (red one) moves to the right and the blue box is static. All the algorithms I have found just search the smallest overlap and push the box away about this overlap distance. This means the red box would be pushed to the left about dx (smallest overlap) in case A, which is correct.

But now assume the box is moving really fast (case B). Again I just push the box about the smallest overlap which would push the box to the right. But this is wrong, since the box came from the left side it should have been moved to the left!

To put a long story short: How can you handle this problem? Do you know any code/articles/tutorials about a simple AABB v AABB collision response?

Share this post


Link to post
Share on other sites
create a collision green box that is the combined shape of the original position red box and the unobstructed fully frame time travelled red box. collide this with the blue box. if there is a collision, slide red box up to and just touching blue box. collision accomplished.

once you've slide red box up to blue box. the amount you moved can be divided by the full frame time unobstructed distance to produce a fractional value if you wanted to add a level of impact or by removing the component of velocity perpendicular to line of collision, you can apply the fractional to the parallel component to allow some frictional sliding...

Share this post


Link to post
Share on other sites
I posted a response to this a while ago . The subject is a bit tricky so i will just post u my code and how i handled it..

this is the a part of the object function:

[code]

u_int8_t collision=0;
this->collisionWithTile(current_map, collision);



if (collision == 0)

{

bool alreadyhit = false;

int i;

Rect2D temp = this->getRect();

for (i = 0; i < current_map.getNPCcounter(); i++)

{

if (!alreadyhit )

{

Rect2D temp2 = current_map.getNPC(i).getRect();

alreadyhit = this->collisionWithObject(temp, temp2, collision, current_map.getNPC(i).getHeight());

if (alreadyhit)

{



// now we can work with the particular npc

if (this->viewDirection == UP)

current_map.getNPC(i).setViewDirection(DOWN);

else if (this->viewDirection == LEFT)

current_map.getNPC(i).setViewDirection(RIGHT);

else if (this->viewDirection == RIGHT)

current_map.getNPC(i).setViewDirection(LEFT);

else if (this->viewDirection == DOWN)

current_map.getNPC(i).setViewDirection(UP);



current_map.getNPC(i).setInPlayerFocus(true);

}

}

}

if (collision==0)

{

for (i = 0; i < current_map.getObjectCounter(); i++)

{

if (!alreadyhit)

{

Rect2D temp2 = current_map.getObject(i).getRect();

alreadyhit = this->collisionWithObject(temp, temp2, collision, current_map.getObject(i).getHeight());

if (alreadyhit)

{

current_map.getObject(i).setInPlayerFocus(true);

}

}

}

}

}



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

{

this->rect.pos.y = temp.y-COL_OFFSET_DOWN;

this->isMoving=false;

}

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

{



this->rect.pos.x = temp.x+COL_OFFSET_LEFT;

this->isMoving=false;

}

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

{



this->rect.pos.x = temp.x-COL_OFFSET_RIGHT;

this->isMoving=false;

}

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

{



this->rect.pos.y = temp.y+COL_OFFSET_UP;

this->isMoving=false;

}


[/code]

So, how do i collect collision data?

Well, first i check with which Tile the Object does collide and i write the direction into the char collision..


[code]
void AnimatedSprite::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;

bool transportTileAlreadyHit=false;

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

{

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

{

if ((current_map.getTileAt(i, j).data>>24

&0x1)==false || (current_map.getTileAt(i, j).flags&0xff)!=0) // tile is collision tile or special tile

{



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

collision = 0;

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

collision = 0;

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

collision = 0

;

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

collision = 0;

else

{



// COLLISION

// check for flags

if ((current_map.getTileAt(i, j).flags&0xff)==TILE_FLAG_TRANSPORTTILE && !transportTileAlreadyHit &&this->isPlayer)

{

transportTileAlreadyHit = true;

Point2D destination;

destination.x = current_map.getTileAt(i, j).flags>>8&0xff;

destination.y = current_map.getTileAt(i, j).flags>>16&0xff;

current_map.suicide(destination, current_map.getTileAt(i, j)._string);

}



//check for collision tile collision tile:

if ((current_map.getTileAt(i, j).data>>24

&0x1)==false)

{

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

{

coldown = true;

}

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

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

{

colleft = true;

}

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

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

{

colright = true;

}

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

{

colup = true;

}

}

}

}

}

}

// write all values in collision

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

}


[/code]

I do the same with other moving objects like this:

[code]
bool AnimatedSprite::collisionWithObject(Rect2D &a, Rect2D &b, u_int8_t &collision, int heightOfObject)

{

bool alreadyhit = 0;

bool colup = 0;

bool colleft = 0;

bool colright = 0;

bool coldown = 0;



float offsetY;

if (heightOfObject > 1)

offsetY = b.pos.y+b.height/heightOfObject;

else

offsetY = b.pos.y;



if (a.pos.x + a.width-15 < b.pos.x)

collision = 0;

else if (a.pos.x > b.pos.x + b.width-10)

collision = 0;

else if (a.pos.y + a.height-15 < offsetY)

collision = 0;

else if (a.pos.y + a.height/2 > b.pos.y + b.height)

collision = 0;

else

{

// COLLISION



if (a.pos.y + a.height > b.pos.y && a.pos.y < b.pos.y)

{

coldown = true;

}

if (a.pos.x < b.pos.x + b.width &&

a.pos.x + a.width > b.pos.x + b.width)

{

colleft = true;

}

if (a.pos.x + a.width > b.pos.x &&

a.pos.x < b.pos.x)

{

colright = true;

}

if (a.pos.y < b.pos.y+b.height && a.pos.y + a.height > b.pos.y + b.height)

{

colup = true;

}



alreadyhit = true;



}



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



return alreadyhit;

}



[/code]

and than i have all my info in the char collision.

Hope it helped if u need further explanation than say

Share this post


Link to post
Share on other sites
This is a problem I've worked on extensively- and I now finally have a fantastic system.

When you work on this you'll find there are several problems:

1. We have the list of objects we're currently colliding with- found through some efficient manner (tips below), now what?

2. Once you have your collisions- which way do we move our object to resolve them?

3. My objects have "sticky corners" (this is one of the largest problems I've encountered)

4. I want different objects to respond differently to collisions- but my system doesn't let me do that.

Let's tackle this head on.

1. && 2. Well you have options. No doubt you've tried the "shallow edge" solution and found ops this doesn't work. Here are some solutions I've come up with/seen
-shallow edge : find the side with the smallest penetration depth and resolve that axis
-multiple boxes : set up around the outside of your object (each is checked with your detection system) resolve based on results
-largest velocity : resolve the axis with the largest velocity
-prev pos : if the previous right side was outside of the other object's previous left side, we resolve the right hand collisions- continue with all sides
this was the method that I was using and still am using (though augmented, get to that in a second) it has a very annoying problem

With this method comes number 3:

[img]http://i.imgur.com/ASieF.png[/img]


Now how in the world do we fix this?
Here's my solution- once we find all the object's we're colliding with- use a sorting function to sort out the list in order of distance to the object- then run right down the list. If you have tiles of the same size this works perfectly well.

A more ideal approach would be : sort based on nearest side, not center or center of side (aka, is anything directly to the right of my center?)

With this fairly simple solution you'll have a world of collidable blocks.

4. This was a bit trickier- what I ended up doing in my engine is sending a event to the objects in question- they can then respond however they darn well please with a custom handle_event() method. (this allows for some really cool dynamic maps, and really easy level creation)

Any questions?

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