2D Physics collision
Author
The last few days I have been working on simple 2D physics for a platform game (I even have wall kick implemented ;) )
I came up with what may be quite a complicated collision routine between 2 rectangles that checks if rectA collides with rectB.
This is done by checking if any of the points from rectA is in rectB then if only one point is in, this means that it's a corner collision and could come from x or y direction, it checks which axis component is deepest into the other rect and assumes this is the direction it is coming from then calculates the distance to move back in that direction and returns it.
If 2 points are inside then its either a straight collision from the side or on top/bottom.
This is easier to get direction for.
So things work fine untill I tested with a block that is smaller than the characters collision rectangle. This can allow you to run through the block without ever having a point inside it and thus no collision is ever detected.
The only way I can think of to compensate for this is rewrite the whole routine, I'm sure there is a simpler method out there? Or check collision with rect1 -> rect2 and then rect2->rect2 which although won't slow down my pc seems really messy and may be loads slower on say a phone.
Or I could just make everything bigger than the character but that seriously limits the design.
Thanks for any replys
The standard way for collsion detection, would be to use, point in polygon tests and line to line intersection tests.
Testing if any point from one rectangle appears inside the polygon of the other rectangle and vice versa.
Also, if any line from one rectangle inersects ( crosses ) any lines from the other rectangle and vice versa.
Both tests are necessary to cover all eventualities of collision.
Along with that, you have the possibility that one rectangle was moving so fast that it passed right through the other, although the above tests all fail, reporting no collision had occured.
Therefore, both velocities of each rectangle need to be checked in order to see if they too intersect.
If a collsiion is detected, then the velocity vectors of each will tell you which direction the collsions occured from.
Just reversing the velocity vector and moving each rectangle away from each other, by the penetration amount is all thats needed to complete the collision .
KJM
Testing if any point from one rectangle appears inside the polygon of the other rectangle and vice versa.
Also, if any line from one rectangle inersects ( crosses ) any lines from the other rectangle and vice versa.
Both tests are necessary to cover all eventualities of collision.
Along with that, you have the possibility that one rectangle was moving so fast that it passed right through the other, although the above tests all fail, reporting no collision had occured.
Therefore, both velocities of each rectangle need to be checked in order to see if they too intersect.
If a collsiion is detected, then the velocity vectors of each will tell you which direction the collsions occured from.
Just reversing the velocity vector and moving each rectangle away from each other, by the penetration amount is all thats needed to complete the collision .
KJM
Author
K_J_M: thanks for the reply.
However I can't think of a situation (even drawing it out) when a line intersection will occur without a point intersection. Do you have an example?
Also how would I test if the velocities intersect?
I'm assuming for now I can use my methods or an easily modified version to compute the penetration distance. Though if you have a quick easy example that would be a bonus.
Thanks again..
However I can't think of a situation (even drawing it out) when a line intersection will occur without a point intersection. Do you have an example?
Also how would I test if the velocities intersect?
I'm assuming for now I can use my methods or an easily modified version to compute the penetration distance. Though if you have a quick easy example that would be a bonus.
Thanks again..
I think you are overcomplicating things. Using a min,max representation for your rectangles allows simple (and reliable) collision detection in all cases:
If you need the penetration depths, it is just a matter of subtracting each coordinate from the matching coordinate in the second rectangle.
class Rect: # x1, y1 are min point, x2, y2 are max point def __init__(self, x1, y1, x2, y2): self.x1, self.y1 = x1, y1 self.x2, self.y2 = x2, y2 # check if we intersect with another rect - trivial def intersects(self, r): if self.x2 < r.x1 or self.y2 < r.y1 or self.x1 > r.x2 or self.y1 > r.y2: return False return True # calculate the intersection rect between us and another rect - also trivial def intersection(self, r): n = Rect( max(self.x1, r.x1), max(self.y1, r.y1), min(self.x2, r.x2), min(self.y2, r.y2) ) return nIf you need the penetration depths, it is just a matter of subtracting each coordinate from the matching coordinate in the second rectangle.
........................##############.
........................#.......................#.
........................#.......................#.
.................############################.
.................#......#.......................#.................#.
.................#......#.......................#.................#.
.................#......#.......................#.................#.
.................#......#.......................#.................#.
.................#......#.......................#.................#.
.................#......#.......................#.................#.
.................#......#.......................#.................#.
.................############################
........................#.......................#.
........................#.......................#.
........................##############.
I hope this example explains a situation.
The text formatting made it pretty difficult to draw the rectangles, but i think you can see, that both rectangles intersect, while all points are outside.
Min / max tests work, if your rectangles do not rotate.
If rotations are possible then you'll need aabb ( arbitry aligned bounding box ) collision detection.
Google searches for the above term will yield loads of hits.
KJM
[Edited by - K_J_M on January 7, 2009 4:44:51 AM]
........................#.......................#.
........................#.......................#.
.................############################.
.................#......#.......................#.................#.
.................#......#.......................#.................#.
.................#......#.......................#.................#.
.................#......#.......................#.................#.
.................#......#.......................#.................#.
.................#......#.......................#.................#.
.................#......#.......................#.................#.
.................############################
........................#.......................#.
........................#.......................#.
........................##############.
I hope this example explains a situation.
The text formatting made it pretty difficult to draw the rectangles, but i think you can see, that both rectangles intersect, while all points are outside.
Min / max tests work, if your rectangles do not rotate.
If rotations are possible then you'll need aabb ( arbitry aligned bounding box ) collision detection.
Google searches for the above term will yield loads of hits.
KJM
[Edited by - K_J_M on January 7, 2009 4:44:51 AM]
Author
K_J_M: Just got a duh moment lol, dunno how I couldn't imagine that when that is the exact collision that gave me this problem.
swiftcoder:I have a function that calculates the intersection like you give. And calculating the penetration distance is quite simple the way you give it (if I understood correctly) though my functions currently do this anyway.
However with the example that K_J_M gave, I can't compute the direction or the distance of where to move back, unless I maybe take into account the initial position or something.
Any tips on this?
Maybe I just need to do some more research on collision resolution/response.
swiftcoder:I have a function that calculates the intersection like you give. And calculating the penetration distance is quite simple the way you give it (if I understood correctly) though my functions currently do this anyway.
However with the example that K_J_M gave, I can't compute the direction or the distance of where to move back, unless I maybe take into account the initial position or something.
Any tips on this?
Maybe I just need to do some more research on collision resolution/response.
for that, it's quite simple. The distance and direction of intersection can be given as the smallest vector long the two axis (X and Y) that yield the minimum intersection distance.
for two boxes, such intersection distance is always a combination of the min of one box and the max of the other box. You take the minimum of the four possibilities, and you have your intersection amount. That's usually called the MTD (minimum translation distance).
shameless plug.
for two boxes, such intersection distance is always a combination of the min of one box and the max of the other box. You take the minimum of the four possibilities, and you have your intersection amount. That's usually called the MTD (minimum translation distance).
bool BoxIntersect(Vector amin, Vector amax, Vector bmin, Vector bmax, Vector& mtd){ mtd = Vector(0, 0); float left = (bmin.x - amax.x); float right = (bmax.x - amin.x); float top = (bmin.y - amax.y); float right = (bmax.y - amin.y); // box dont intersect if(left > 0 || right < 0) return false; if(top > 0 || bottom < 0) return false; // box intersect. work out the mtd on both x and y axes. if (fabs(left) < right) mtd.x = left; else mtd.x = right; if (fabs(top) < bottom) mtd.y = top; else mtd.y = bottom; // 0 the axis with the largest mtd value. if(fabs(mtd.x) < fabs(mtd.y)) mtd.y = 0; else mtd.x = 0; return true;}shameless plug.
Author
I've tried everything and there is still one piece I can't get right.
And that is the collision that K_J_M points out (even though sometimes according to the debugger this is accounted for)
It must be to do with the velocity of the player, it lets me run right through a block.
I've put up a demo here
The controls are A and D to move left and right and W to jump.
When you jump into a wall push W again to do a wall kick.
Now this is how I reproduce the error, sometimes running really fast into the pink block or wall kick opff the big white wall so that you come down on the left side of the pink block.
The main code I use is here
and the rectangle collision class
Anyone able to give a solution to this? It must be to do with velocity but I don't know how to stop this since the block has no velocity.
Thanks again people.
And that is the collision that K_J_M points out (even though sometimes according to the debugger this is accounted for)
It must be to do with the velocity of the player, it lets me run right through a block.
I've put up a demo here
The controls are A and D to move left and right and W to jump.
When you jump into a wall push W again to do a wall kick.
Now this is how I reproduce the error, sometimes running really fast into the pink block or wall kick opff the big white wall so that you come down on the left side of the pink block.
The main code I use is here
[Source]void DoCollision(CollisionRectangle r1, CollisionRectangle r2) { CollisionResolution resolution; if(CollisionRectangle::RectangleCollision(r1, r2)) { resolution = CollisionRectangle::RectangleCollisionResolution(r1, r2); if(resolution.ZeroPointCollision == false) { switch(resolution.direction) { case CollisionResolution::DOWN : character.YPosition -= resolution.distance; character.YVelocity = 0; character.Jumping = false; break; case CollisionResolution::UP : character.YPosition += resolution.distance; character.YVelocity = 0; character.Jumping = false; break; case CollisionResolution::LEFT : character.XPosition -= resolution.distance; character.XVelocity = 0; character.canWallKick = true; break; case CollisionResolution::RIGHT : character.XPosition += resolution.distance; character.XVelocity = 0; character.canWallKick = true; break; }; } else { switch(resolution.direction) { case CollisionResolution::LEFT : character.XPosition -= resolution.distance; character.XVelocity = 0; character.canWallKick = true; break; case CollisionResolution::RIGHT : character.XPosition += resolution.distance; character.XVelocity = 0; character.canWallKick = true; break; }; } } }[/Source]and the rectangle collision class
[Source]class CollisionRectangle{public: CollisionRectangle() { }; ~CollisionRectangle() {}; const CollisionRectangle &operator +=(const Vector2D &v) { min += v; max += v; return *this; } //x an y are the co-ordinates of top left Vector2D min, max;static bool MTD(CollisionRectangle r1, CollisionRectangle r2, Vector2D &mtd) { mtd = Vector2D(0, 0); float left = (r2.min.x - r1.max.x); float right = (r2.max.x - r1.min.x); float top = (r2.min.y - r1.max.y); float bottom = (r2.max.y - r1.min.y); // box dont intersect if(left > 0 || right < 0) return false; if(top < 0 || bottom > 0) return false; // box intersect. work out the mtd on both x and y axes. if (fabs(left) < right) mtd.x = left; else mtd.x = right; if (fabs(top) < bottom) mtd.y = top; else mtd.y = bottom; // 0 the axis with the largest mtd value. if(fabs(mtd.x) < fabs(mtd.y)) mtd.y = 0; else mtd.x = 0; return true; } static bool RectangleCollision(CollisionRectangle r1, CollisionRectangle r2){ if(r1.max.x < r2.min.x || r1.min.x > r2.max.x || r1.max.y > r2.min.y || r1.min.y < r2.max.y) return false; //check not just touching if(r1.min.x == r2.max.x || r1.max.x == r2.min.x || r1.min.y == r2.max.y || r1.max.y == r2.min.y) return false; return true;}static bool PointInsideRectangle(Point p, CollisionRectangle r){ if(p.x > r.min.x && p.x < r.max.x && p.y < r.min.y && p.y > r.max.y) return true; else return false;}static CollisionResolution RectangleCollisionResolution(CollisionRectangle r1, CollisionRectangle r2){ int pointCount = 0; bool topLeftInside = false, topRightInside = false, bottomLeftInside = false, bottomRightInside = false; Point topLeft(r1.min.x, r1.min.y); Point topRight(r1.max.x, r1.min.y); Point bottomLeft(r1.min.x, r1.max.y); Point bottomRight(r1.max.x, r1.max.y); if(PointInsideRectangle(topLeft, r2)) { pointCount++; topLeftInside = true; } if(PointInsideRectangle(topRight, r2)) { pointCount++; topRightInside = true; } if(PointInsideRectangle(bottomLeft, r2)) { pointCount++; bottomLeftInside = true; } if(PointInsideRectangle(bottomRight, r2)) { pointCount++; bottomRightInside = true; } CollisionResolution result; if(pointCount == 1) { if(topLeftInside == true) { if(r2.max.x - topLeft.x > topRight.y - r2.max.y) { result.direction = CollisionResolution::RIGHT; result.distance = r2.max.x - topLeft.x; } else { result.direction = CollisionResolution::DOWN; result.distance = topRight.y - r2.max.y; } } if(topRightInside == true) { if(topRight.x - r2.min.x > topRight.y - r2.max.y) { result.direction = CollisionResolution::LEFT; result.distance = topRight.x - r2.min.x; } else { result.direction = CollisionResolution::DOWN; result.distance = topRight.y - r2.max.y; } } if(bottomLeftInside == true) { if(r2.max.x - bottomLeft.x > r2.min.y - bottomLeft.y) { result.direction = CollisionResolution::RIGHT; result.distance = r2.max.x - bottomLeft.x; } else { result.direction = CollisionResolution::UP; result.distance = r2.min.y - bottomLeft.y; } } if(bottomRightInside == true) { if(bottomRight.x - r2.min.x > r2.min.y - bottomRight.y) { result.direction = CollisionResolution::LEFT; result.distance = bottomRight.x - r2.min.x; } else { result.direction = CollisionResolution::UP; result.distance = r2.min.y - bottomRight.y; } } } if(pointCount == 2) { if(topLeftInside == true) { if(topRightInside) { result.direction = CollisionResolution::DOWN; result.distance = topRight.y - r2.max.y; } else { //must be bottom left result.direction = CollisionResolution::RIGHT; result.distance = r2.max.x - topLeft.x; } } if(topRightInside == true) { if(bottomRightInside) { result.direction = CollisionResolution::LEFT; result.distance = topRight.x - r2.min.x; } } if(bottomRightInside == true) { if(bottomLeftInside) { result.direction = CollisionResolution::UP; result.distance = r2.min.y - bottomRight.y; } } } if(pointCount == 0) { Vector2D mtd; MTD(r1, r2, mtd); if(mtd.x > 0) { result.direction = CollisionResolution::RIGHT; result.distance = mtd.x; result.ZeroPointCollision = true; } else if(mtd.x < 0) { result.direction = CollisionResolution::LEFT; result.distance = mtd.x; result.ZeroPointCollision = true; } else { } if(mtd.y > 0) { result.direction = CollisionResolution::UP; result.distance = mtd.y; result.ZeroPointCollision = true; } else if(mtd.y < 0) { result.direction = CollisionResolution::DOWN; result.distance = mtd.y; result.ZeroPointCollision = true; } else { } } return result;}Anyone able to give a solution to this? It must be to do with velocity but I don't know how to stop this since the block has no velocity.
Thanks again people.
that's a classic problem called tunneling.
- split the collision timestep into smaller chunk (say, check should be made < 0.25 the box size)
- use a swept test.
EDIT : on second view of the code, looks like a logic problem.
[Edited by - oliii on January 8, 2009 3:13:21 PM]
- split the collision timestep into smaller chunk (say, check should be made < 0.25 the box size)
- use a swept test.
EDIT : on second view of the code, looks like a logic problem.
[Edited by - oliii on January 8, 2009 3:13:21 PM]
Author
oliii: When I step through in the debugger it looks like I catch the collision when the character is way past the block and underneath it.
Maybe it is a logic problem but I just can't see it just now. You know when you've stared at the same code for that long it gets harder to see any differences?
I will check out tunnelling also to see if that helps.
Thanks.
If anyone can spot a simple logic fix please feel free to post.
Maybe it is a logic problem but I just can't see it just now. You know when you've stared at the same code for that long it gets harder to see any differences?
I will check out tunnelling also to see if that helps.
Thanks.
If anyone can spot a simple logic fix please feel free to post.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
