2D Pool Ball Collisions

Math and Physics Programming

Started by adam23 October 20, 2006 04:20 PM

5 comments, last by Enselic 17 years, 5 months ago

164

Author

October 20, 2006 04:20 PM

I have been working on a pool game to play around with physics and collision detection. I have the physics for the balls colliding with eachother. I have been trying to think of a realistic way to make the balls bounce into the pockets. Originally I was checking bounds and just reversing the direction of the ball when it hit the side of the table. Then I decided maybe doing a line segment circle collision would be better because I could line the whole table with line segments that store several properties including what to multiply the balls velocity by to make it go in the right direction. So I set out to line the table with line segments using this structure


//Struct Used to define the Lines in the Pool Game
struct LineSegment
{
	D3DXVECTOR2 points[2];
	//Multiply factor is used to change the angle of the ball when there is
	//a collision with the table
	D3DXVECTOR2 multiplyFactor;
	//Vector that stores the direction the wall is going so it does not have to 
	//be calculated each time
	D3DXVECTOR2 direction;
};

Now I've only added the major line segments, and I even render them to make sure they are positioned right. My first thought was to do a closest point to line, and then calculate the distance to determine if there is a collision. This works perfectly except it makes the lines continue in there direction forever, not accounting for both end points. Here is what I have now.


void CollisionManager::CheckCollisionsWithWalls(LinkedList<Ball> &m_list, const std::list<LineSegment> *m_walls)
{
	std::list<LineSegment>::const_iterator iter;
	float distance = 100.0f;
	while (m_list.Iterate())
	{
		for(iter = m_walls->begin(); iter != m_walls->end(); iter++)
		{
			distance = CheckDistanceFromPoint((*iter).points[0],(*iter).direction, m_list.GetCurrent()->getCenter());
			if(distance < 12.0f)
			{
				//Move the ball back to a position of 12.1f units from the wall
				//To prevent the a second successful collision test
				D3DXVECTOR2 velocity = m_list.GetCurrent()->getVelocity();
				D3DXVECTOR2 tmp;
				D3DXVec2Normalize(&tmp, &velocity);
				tmp *= -1; //Reverse of velocity vector
				distance = 12.1f - distance;
				tmp *= distance;
				D3DXVECTOR3 position = m_list.GetCurrent()->getPosition();
				position.x += tmp.x;
				position.y += tmp.y;
				m_list.GetCurrent()->setPosition(position);

				velocity.x *= (*iter).multiplyFactor.x;
				velocity.y *= (*iter).multiplyFactor.y;
				m_list.GetCurrent()->setVelocity(velocity.x, velocity.y);
			}
		}
	}
}
float CollisionManager::CheckDistanceFromPoint(D3DXVECTOR2 point, D3DXVECTOR2 direction, D3DXVECTOR2 centerPoint)
{
	//12 would be the distance for a collision
	D3DXVECTOR2 tmp = point - centerPoint;
	float distance = D3DXVec2CCW(&tmp, &direction);
	distance = abs(distance);
	return distance;
}

As you can see I use the Cross product to calculate the distance from the center of the ball to the closest point on the line. I need a way to account for just the line segment, or maybe even a better method for doing collision detection with the table. Thanks in advance for any help Adam [Edited by - adam23 on October 25, 2006 11:44:25 AM]

Adamhttp://www.allgamedevelopment.com

Mashiniblik

122

October 20, 2006 07:08 PM

G'day,
I don't know much about collision detection, however I know a lot about pool, and the ball almost never bounces back on the same angle it hits the cusion. If you're snookered, placing side spin on the white ball and bouncing it off the walls at a funky angle is a key skill in playing pool.

Hope it all works out mate, everyone loves a good pool game :)

Zakwayda

2,389

October 20, 2006 08:00 PM

Regarding the problem of finding the closest point on a line segment to a point, it's quite straightforward:

// O = segment origin, D = segment direction, P = query pointVector d = P-O;float t = dot(d,D)/dot(D,D);t = clamp(t, 0.0f, 1.0f); // You supply clamp()return O+t*D;

From here you can compute the other values you need to detect the collision and respond accordingly.

The algorithm works in any dimension.

adam23

164

Author

October 25, 2006 11:58 AM

I ended up getting the line segments to detect collisions properly. I have a list of all edges on the table, and then I do a quick test to see if the ball interesects that plane.

float CollisionManager::CheckDistanceFromPoint(D3DXVECTOR2 point, D3DXVECTOR2 direction, D3DXVECTOR2 centerPoint){	//12 would be the distance for a collision	D3DXVECTOR2 tmp = point - centerPoint;	float distance = D3DXVec2CCW(&tmp, &direction);	distance = abs(distance);	return distance;}

Then I create a system of equations and solve for the intersection point and the amount of overlap.

Anyway, I ran into a new problem, that seems a lot simplier than it is. I wanted to minimize the number of collision tests I run in a second to about 30. When I lowered it to 100, 50, and then 30 I started getting some strange results. Right now I am doing well over 900 collision tests a second and everything seems to work fairly decent. When I lower the number of tests a couple of the balls seem to stick together and then orbit around eachother. I have been looking for a decent way to move the balls away from eachother so that they don't get stuck.
Here is an image of some of the possible scenarios. I was originally thinking that I would calculate the new velocity and then just seperate them based on there new speed/totalspeed * overshoot, but this will only work in straight lines.
http://adamwlarson.com/pictures/poolballs.JPG

Should I move the balls away from eachother first and the correct there velocity, or should I calc the new velocity and move the ball along that path based on there new speed. Either way I'm not really sure because I calculate the exchange of momentum based on the angle of collision compared to the velocity vector.

		if(ball1->getCurrentSpeed() > ball2->getCurrentSpeed())		{			//Ball 1 is moving faster			//Get the collison Vector between the two balls			D3DXVECTOR2 collisionVector = ball2->getCenter()-ball1->getCenter();			D3DXVec2Normalize(&collisionVectorNormalized, &collisionVector);			//Store ball1's Velocity			temp = ball1->getVelocity();			D3DXVECTOR2 ball1VelocityNorm;			//Normalize the velocity vector so it can be used to calc the DotProduct			D3DXVec2Normalize(&ball1VelocityNorm, &temp);			//Determine Dot product to figure out percentage of impact			float dotValue = D3DXVec2Dot(&ball1VelocityNorm, &collisionVectorNormalized);			collisionVectorNormalized *= (ball1->getCurrentSpeed() * dotValue);			collisionVectorNormalized += ball2->getVelocity();			//Subtract the transferred momentum from the Ball1's current velocity			temp.x -= collisionVectorNormalized.x;			temp.y -= collisionVectorNormalized.y;			//Set the new velocities			ball1->setVelocity(temp.x, temp.y);			ball2->setVelocity(collisionVectorNormalized.x, collisionVectorNormalized.y);		}

I need to fine tune the algorithm some to account for the transfer of ball2's velocity, but you can see what I'm getting at.

Thanks in advance

Adamhttp://www.allgamedevelopment.com

David Bonnet

170

October 26, 2006 11:30 AM

Hello,

Quote:Original post by adam23
When I lower the number of tests a couple of the balls seem to stick together and then orbit around eachother.

I had exactly the same problem in a 2d pool game i wrote a long time ago. The problem is that in very rare cases the 2 balls can be colliding, but still their velocities are such that the 2 balls are not going into each other. In this case, your collision handling function will make them go into each other instead of letting them being separated naturally.
What i can suggest is that before you apply the new velocities to the balls (or even before you calculate them), you should check if the balls are not actually already going away from each other. It means you have to check the sign of the dot product of the relative speed of the balls
(ball2->getVelocity() - ball1->getVelocity()) and collisionVector.
If it is positive then do nothing.

adam23

164

Author

October 27, 2006 07:59 AM

That may be the problem, I never thought about that.

Thanks for the suggestion
Adam

Adamhttp://www.allgamedevelopment.com

Enselic

829

October 28, 2006 05:37 AM

I suggest another method for solving the stickiness problem, it is a bit more advanced, but yeilds a more correct behaviour. Without it, balls may go "through" each other when they in a real game would touch each other.

Instead of checking the velocities of the balls when they are intersecting, and skip collision calculations if they are moving away from each other already, you should revert the simulation to the time when they are just about to en begin intersecting each other, and then calculate the new velocities at that time.

If two balls are intersecting, there always exists a time when the balls are moving into each other (because otherwise the intersection would not occur in the first place).

The tricky part involves calculating the negative deltaTime that corresponds to the time when the balls are just about to intersect, but I belive I have read such an article on gamasutra once, so it might be worth checking out.

[s]--------------------------------------------------------[/s]chromecode.com - software with source code

2D Pool Ball Collisions

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

2D Pool Ball Collisions

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines