2D Physics collision

This topic is 3448 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

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

Share on other sites
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

Share on other sites

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..

Share on other sites
I think you are overcomplicating things. Using a min,max representation for your rectangles allows simple (and reliable) collision detection in all cases:
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 n

If you need the penetration depths, it is just a matter of subtracting each coordinate from the matching coordinate in the second rectangle.

Share on other sites
........................##############.
........................#.......................#.
........................#.......................#.
.................############################.
.................#......#.......................#.................#.
.................#......#.......................#.................#.
.................#......#.......................#.................#.
.................#......#.......................#.................#.
.................#......#.......................#.................#.
.................#......#.......................#.................#.
.................#......#.......................#.................#.
.................############################
........................#.......................#.
........................#.......................#.
........................##############.

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.

KJM

[Edited by - K_J_M on January 7, 2009 4:44:51 AM]

Share on other sites
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.

Share on other sites
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).

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.

Share on other sites
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
[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.

Share on other sites
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]

Share on other sites
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.

• 38
• 12
• 10
• 10
• 9
• Forum Statistics

• Total Topics
631365
• Total Posts
2999583
×