Jump to content
  • Advertisement
Sign in to follow this  
benderB

Circle - Circle Collision Problem

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

Heya, I'm currently implementing a circle - circle collision detection for my engine. I need a function which takes the positions of both circles, their radii and the movement vectors of both circle, which marks the distance which they would like to move in this frame. The function should check if an collision occurs and if yes should calculate the positions along the movement vectors where the circles come to rest (so that they don't collide). I did a search and found this article: http://www.gamasutra.com/features/20020118/vandenhuevel_02.htm It provides the source of a function which does what I want but with one stationary and one moving circle. After the code it is explained how to alter the function to calculate the outcome with 2 circles (Bank Shot: Collision between two moving circles). I implemented the function according to this desciption but it doesn't seem to work right. Sometimes when the two circles touch one of them is sucked a bit into the other one, sometimes they come to rest but touch themselfs a little bit afterall. Here's my source (C++):
bool CSphereBoundingShape::collide(CSphereBoundingShape* enemyShape) {
	// the position of this circle is calculated using the transformation matrix
	// and a point in the base of the coordinate system
	CVector4 myPosition = transformation * CVector4(0.0f, 0.0f, 0.0f, 1.0f);
	// the radius of this circle
	f32 myRadius = radius;
	// the enemyposition is calculated in the same manner
	CVector4 enemyPosition = enemyShape->getTransformation() * CVector4(0.0f, 0.0f, 0.0f, 1.0f);
	// the enemy radius
	f32 enemyRadius = enemyShape->getRadius();
	// the displacement vector is calculated according to the acticle 
	// description 
	CVector4 displacement = getDisplacement() - enemyShape->getDisplacement();


	// Early Escape test: if the length of the movevec is less
	// than distance between the centers of these circles minus
	// their radii, there's no way they can hit. 
	f32 distance = (enemyPosition - myPosition).length();
	f32 sumRadii = myRadius + enemyRadius;
	distance -= sumRadii;

	if(displacement.length() < distance) {
		return false;
	}
	 
	// Normalize the movevec
	CVector4 N = CVector4(displacement);
	N.normalize();


	// Find C, the vector from the center of the moving
	// circle A to the center of B
	CVector4 C = enemyPosition - myPosition;
	f32 D = DotProduct(N, C);


	// Another early escape: Make sure that A is moving
	// towards B! If the dot product between the movevec and
	// B.center - A.center is less that or equal to 0,
	// A isn't isn't moving towards B
	if(D <= 0.0f) {
		return false;
	}

	// Find the length of the vector C
	f32 lengthC = C.length();
	f32 F = pow(lengthC, 2) - pow(D, 2);

	f32 sumRadiiSquared = pow(sumRadii, 2);
	
	// Escape test: if the closest that A will get to B
	// is more than the sum of their radii, there's no
	// way they are going collide
	if(F >= sumRadiiSquared) {
		return false;
	}
	
	// We now have F and sumRadii, two sides of a right triangle.
	// Use these to find the third side, sqrt(T)
	f32 T = sumRadiiSquared - F;

	// If there is no such right triangle with sides length of
	// sumRadii and sqrt(f), T will probably be less than 0.
	// Better to check now than perform a square root of a
	// negative number. 
	if(T < 0.0f) {
		return false;
	}
	
	// Therefore the distance the circle has to travel along
	// movevec is D - sqrt(T)
	f32 newDistance = D - sqrt(T);
	if(newDistance < 0) {
		return false;
	}
	
	// Finally, make sure that the distance A has to move
	// to touch B is not greater than the magnitude of the
	// movement vector. 
	if(displacement.length() < newDistance) {
		return false;
	}
	
	// the displacement for the 2 movement vectors is calculated according to the description
	CVector4 newDisplacement(displacement);

	newDisplacement.normalize();
	newDisplacement *= newDistance;

	f32 displacementFactor = displacement.length() / newDisplacement.length();
	setDisplacement(getDisplacement() * displacementFactor);
	enemyShape->setDisplacement(enemyShape->getDisplacement() * displacementFactor);
	return true;
}

In the paragraph "Bank Shot: Collision between two moving circles" the author says the following: "If they collide, divide the length of the shortened vector by the length of the one you originally passed into the function. The result should be a floating-point number between 0 and 1" this is done via:
CVector4 newDisplacement(displacement);

newDisplacement.normalize();
newDisplacement *= newDistance;

f32 displacementFactor = displacement.length() / newDisplacement.length();
The problem seems to be that the displacementFactor sometimes isn't in the range [0-1]. If someone could tell me what I got wrong it would be greatly appreaciated. Or maybe someone knows an alternative function which provides the same functionality? thanks, benderB

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
Your division looks backwards. It should be

newDisplacement.length() / displacement.length()

Also this is kidn of pointless. The result will be the same as

newDistance / displacement.length()

Share this post


Link to post
Share on other sites
argh...

The algorithm still doesn't work exactly as it should.
The first time two objects hit it is always detected and the correct position is calculated but if one of the objects keeps heading in the direction of the other object at some point one object simple passes through the other without a collision.

I tried it with two moving objects and with a moving and a stationary but always get the same results...

Anybody got experience with this algorithm?
Or has a link to a similar algorithm or an idea what could be going wrong?

thanks,
benderB

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!