Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

grom358

Collision between moving balls

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

Firstly I would like to thank those who have helped me so far. My problem is that sometimes the balls get overlapped. See end of post for the source. I have a function testBallCollision(Ball b, int timeSlot) that returns when a collision occurs (where timeSlot is the amount of time since the last frame). If no collision occurs then timeSlot is returned. With the debugging so far I have found that sometimes testBallCollision is returning a large negative number (eg. -160) when AFAIK it should always be between 0 and timeSlot. When this is happening it seems that the calculation of the distance the circle has to travel along its movement vector is a large negative number (eg. -35.777 when the length of the movement vector is only 3.354). I am using the algorithms from Poolhall Lessons: Fast, Accurate Collision Detection between Circles or Spheres - An Algorithm that works and Calculating Bounce. I''ve checked my code and it AFAICT I am implementing these algorithms correctly. I am even checking that the amount of energy is conserved with the calculation of the bounce (at the moment the system is frictionless and the balls are rigid). By the way, I''m going to write a detailed tutorial once I get this going. Going to port it to OpenGL/SDL and make the code available with the tutorial. I find working code the best to learn from, especially if it is kept simple (such as basic bouncing balls).
package net.grom.pool;

import javax.swing.*;

/**
 * @author grom
 */
public class Main extends JApplet implements Runnable {
	Thread gameLogic; // game logic thread

	Table table; // The applet''s content pane


	private void createGUI() {
		// Custom component to draw the current image

		// at a particular offset.

		table = new Table(getWidth(), getHeight());
		setContentPane(table);
	}

	public void init() {
		// Execute a job on the event-dispatching thread:

		// creating this applet''s GUI.

		try {
			javax.swing.SwingUtilities.invokeAndWait(new Runnable() {
				public void run() {
					createGUI();
				}
			});
		} catch (Exception e) {
			System.err.println("createGUI didn''t successfully complete");
		}
	}

	public void start() {
		if (gameLogic == null) {		
			gameLogic = new Thread(this);
			gameLogic.start(); //Start the game.

		} else {
			// resume game

			gameLogic.resume();
		}
	}

	public void stop() {
		// game logic does not use any synchronized locks

		// and therefore this call should be safe

		gameLogic.suspend();
	}
	
	public void run() {
		while (true) {					
			table.nextFrame();
			table.repaint();

			try {
				Thread.sleep(10); // sleep for 10 milliseconds				

			} catch (InterruptedException ex) {
				// do nothing 

			}
		}
	}		
}

package net.grom.pool;

import java.awt.*;
import javax.swing.*;
import java.util.*;

/**
 * @author grom
 */
public class Table extends JComponent {
	private java.util.List balls = new ArrayList();
	private int width;
	private int height;
	
	private long prev_t = -1;
	private int dt = 0; // Time since last frame

	
	public Table(int tableWidth, int tableHeight) {
		setOpaque(true);
		setBackground(Color.WHITE);
		width = tableWidth;
		height = tableHeight;
		
		balls.add(new Ball(this, 10, 10, 5, 2, Color.BLUE));	
		balls.add(new Ball(this, 30, 30, 3, 1, Color.GREEN));
		//balls.add(new Ball(this, 30, 30, 0, 0, Color.GREEN));

		balls.add(new Ball(this, 150, 150, -2, -3, Color.RED));	
	}
	
	public int getTableWidth() {
		return width;
	}
	
	public int getTableHeight() {
		return height;
	}
	
	/**
	 * Moves to next frame
	 */
	public void nextFrame() {
		// calculate time since last frame

		dt = (int) (System.currentTimeMillis() - prev_t);
		if (dt <= 0) {
			// do nothing

			return;
		}
		//System.out.println("" + dt + "ms since last frame");


		double t = dt;
		// if a wall collision occurs

		// then we only paint till the collision

		Ball b;
		for (Iterator i = balls.iterator(); i.hasNext(); ) {
			b = (Ball) i.next();
			t = Math.min(t, b.testWallCollision(dt));	
		}
		
		// test for ball collisions

		java.util.List collisions = new LinkedList();
		int currIndex = 1;
		Ball a;	
		for (Iterator i = balls.iterator(); i.hasNext(); currIndex++) {
			a = (Ball) i.next();
			for (Iterator j = balls.listIterator(currIndex); j.hasNext(); ) {
				b = (Ball) j.next();
				t = Math.min(t, a.testBallCollision(b, dt, collisions));	
			}
		}

		for (Iterator i = balls.iterator(); i.hasNext();) {
			b = (Ball) i.next();
			b.nextFrame(t);
		}
		
		// handle collisions

		Collision c;
		for (Iterator i = collisions.iterator(); i.hasNext(); ) {
			c = (Collision) i.next();
			c.handle();
		}
	}

	protected void paintComponent(Graphics g) {			
		Graphics2D g2d = (Graphics2D) g;

		// clear screen in background 

		g2d.setColor(getBackground());
		g2d.fillRect(0, 0, this.getSize().width, this.getSize().height);

		g2d.setRenderingHint(
			RenderingHints.KEY_ANTIALIASING,
			RenderingHints.VALUE_ANTIALIAS_ON);

		Ball b;
		for (Iterator i = balls.iterator(); i.hasNext();) {
			b = (Ball) i.next();
			b.paint(g2d);
		}
		
		// keep track of when frame was painted

		prev_t = System.currentTimeMillis();
	}
}

package net.grom.pool;

import java.awt.*;

/**
 * @author grom
 */
public class Ball {
	private Color c;
	int radius;
	Point origin;
	Vector velocity;
	
	private Table table;
	private int tableWidth;
	private int tableHeight;
	
	public Ball(Table t, int x, int y, int xSpeed, int ySpeed, Color ballColor) {
		table = t;
		tableWidth = t.getTableWidth();
		tableHeight = t.getTableHeight();
		radius = 10;
		c = ballColor;
		origin = new Point(x, y);
		velocity = new Vector(xSpeed/10d, ySpeed/10d);
	}
	
	public double testWallCollision(int t) {
		// Calculate the movement vector for t

		Vector movec = velocity.scale(t);
		
		double collision_t = t; // no collision

		// time = distance / speed

		if (origin.x - radius + movec.x < 0) {			
			collision_t = (origin.x - radius) / velocity.x;			
		} else if (origin.x + radius + movec.x > tableWidth) {			
			collision_t = (tableWidth - (origin.x + radius)) / velocity.x;
		} else if (origin.y - radius + movec.y < 0) {			
			collision_t = (origin.y - radius) / velocity.y;
		} else if (origin.y + radius + movec.y > tableHeight) {			
			collision_t = (tableHeight - (origin.y + radius)) / velocity.y;
		}
		return Math.abs(collision_t);
	}
	
	public double testBallCollision(Ball b, int t, java.util.List collisions) {
		// Calculate the movement vector a for t

		Vector movea = this.velocity.scale(t);
		
		// Calculate the movement vector b for t

		Vector moveb = b.velocity.scale(t);
		
		// If objects are moving in opposite directions

		// then there is no collision

		if (movea.x > 0 && moveb.x < 0) {
			return t;
		} else if (movea.x < 0 && moveb.x > 0) {
			return t;
		} else if (movea.y > 0 && moveb.y < 0) {
			return t;
		} else if (movea.y < 0 && moveb.y > 0) {
			return t;
		}
		
		// Detect wether the balls are touching

		int deltaX = b.origin.x - this.origin.x;
		int deltaXSquared = deltaX * deltaX; // square

		
		int deltaY = b.origin.y - this.origin.y;
		int deltaYSquared = deltaY * deltaY; // square

		
		int sumRadii = this.radius + b.radius;
		int sumRadiiSquared = sumRadii * sumRadii; // square

		
		// Calculate distance between objects

		int distSquared = deltaXSquared + deltaYSquared;
		
		if (distSquared < sumRadiiSquared) {
			// The balls are touching

			System.out.println("MISSED COLLISION");
			System.out.println("movea => " + movea);
			System.out.println("moveb => " + moveb);			
			System.out.println("dist = " + Math.sqrt(distSquared));
			System.out.println("sumRadii = " + sumRadii);
			Vector movec = movea.subtract(moveb);
			System.out.println("movec => " + movec);
			System.exit(1);
		}
		
		// Reduce dynamic-dynamic collision to dynamic-static

		Vector movec = movea.subtract(moveb);
				
		// If the length of the movement vector is less

		// then the distance between the objects,

		// then there is no way they can hit

		if (movec.getLength() < (Math.sqrt(distSquared) - sumRadii)) {
			System.out.println("MOVEMENT VECTOR TOO SHORT");
			return t; // no collision

		}
		
		// Normalize the movevec

	 	Vector N = movec.normalize();
	 	
		// Find C, the vector from the center of the moving 

		// circle A to the center of B

	 	Vector C = new Vector(b.origin.x - this.origin.x, b.origin.y - this.origin.y);	 	
		
		// D = N . C = ||C|| * cos(angle between N and C)	

		double D = N.dot(C);
			
		// Find the length of the vector C

	 	double lengthC = C.getLength();
			
		double F = (lengthC * lengthC) - (D * D);

		// 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) {
			System.out.println("TOO FAR AWAY");
			return t; // no collision

		}

		// We now have F and sumRadii, two sides of a right triangle. 

		// Use these to find the third side, sqrt(T)

		double 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) {
			System.out.println("CAN NOT FIND T");
			return t; // no collision

		}

		// Therefore the distance the circle has to travel along 

		// the movement vector is D - sqrt(T)

		double distance = D - Math.sqrt(T);

		// Get the magnitude of the movement vector

		double mag = movec.getLength();

		// Finally, make sure that the distance A has to move 

		// to touch B is not greater than the magnitude of the 

		// movement vector. 

		if (mag < distance) {
			System.out.println("mag < distance");
			return t;
		}
		
		// Return the time it takes ball A to travel this distance

		System.out.println("BALL COLLISION t=" + ((distance/mag) * t));
		System.out.println("D = " + D);
		System.out.println("F = " + F);
		System.out.println("T = " + T);
		System.out.println("distance = " + distance);
		System.out.println("mag = " + mag);		
		collisions.add(new Collision(this, b));
		return Math.abs(Math.round((distance/mag) * t));
		//return t;

	}
	
	public void nextFrame(double t) {
		// Calculate the movement vector for t

		Vector movec = velocity.scale(t);
		origin.x += movec.x;
		origin.y += movec.y;
		
		// Bounce in opposite direction from the wall

		if (origin.x - radius <= 0 || origin.x + radius >= tableWidth) {
			velocity.x = -velocity.x;
		} else if (origin.y - radius <= 0 || origin.y + radius >= tableHeight) {
			velocity.y = -velocity.y;
		}		
	}
	
	public void paint(Graphics2D g) {
		g.setColor(c);
		// paint ball

		g.fillOval(origin.x - radius, origin.y - radius, 2 * radius, 2 * radius);
	}
}

package net.grom.pool;

/**
 * @author grom
 */
public class Collision {
	Ball a, b;
	
	public Collision(Ball a, Ball b) {
		this.a = a;
		this.b = b;
	}
	
	public void handle() {
		Vector v1 = a.velocity;
		Vector v2 = b.velocity;
		double m1 = 1;
		double m2 = 1;
		
		// First, find the normalized vector n from the center of 

		// circle1 to the center of circle2

		Vector n = new Vector(b.origin.x - a.origin.x, b.origin.y - a.origin.y);
		n = n.normalize();				
		
		// Find the length of the component of each of the movement

		// vectors along n. 

		// a1 = v1 . n

		// a2 = v2 . n

		double a1 = v1.dot(n);
		double a2 = v2.dot(n);

		//		Using the optimized version, 

		//		optimizedP =  2(a1 - a2)

		//					 -----------

		//					   m1 + m2

		double optimizedP = (2.0 * (a1 - a2)) / (m1 + m2);

		//		Calculate v1'', the new movement vector of circle1

		//		v1'' = v1 - optimizedP * m2 * n

		//Vector v1_ = v1 - optimizedP * a.mass * n;

		Vector v1_ = v1.subtract(n.scale(m1 * optimizedP));

		//		Calculate v1'', the new movement vector of circle1

		//		v2'' = v2 + optimizedP * m1 * n

		//Vector v2_ = v2 + optimizedP * b.mass * n;

		Vector v2_ = v2.add(n.scale(m2 * optimizedP));
		
		a.velocity = v1_;
		b.velocity = v2_;
		
//		System.out.println("optimizedP = " + optimizedP);

//		System.out.println("a1 = " + a1);

//		System.out.println("a2 = " + a2);

//		System.out.println("v1 => " + v1);

//		System.out.println("v1_ => " + v1_);

//		System.out.println("v2 => " + v2);

//		System.out.println("v2_ => " + v2_);

//		System.out.println("KE = " + (v1.add(v2).getLength()) + 

//							  "= " + (v1_.add(v2_).getLength()));

		//System.exit(0);

	}
}

package net.grom.pool;

/**
 * @author grom
 */
public class Vector {
	double angle;
	double length;
	double x, y;
	
	private Vector() {
	}
	
	public Vector(double x, double y) {
		setPosition(x, y);
	}
		
	public double getAngle() {
		return angle;
	}
	
	public void setAngle(double angle) {
		setPolar(angle, length);
	}
	
	public double getLength() {
		return length;
	}
	
	public void setLength(double length) {
		setPolar(angle, length);
	}
	
	public void setPolar(double angle, double length) {
		this.angle = angle;
		this.length = length;
		// Calculate x and y coords

		x = Math.cos(angle) * length;
		y = Math.sin(angle) * length;
	}
	
	public void setPosition(double x, double y) {
		this.x = x;
		this.y = y;
		angle = Math.atan2(y, x);
		length = Math.sqrt(x*x + y*y);
	}	
	
	public double dot(Vector v) {
		// NOTE: A . B = Ax*Bx + Ay*By

		return this.x * v.x + this.y * v.y;
	}
	
	public Vector add(Vector v) {
		return new Vector(this.x + v.x, this.y + v.y);
	}
	
	public Vector subtract(Vector v) {
		return new Vector(this.x - v.x, this.y - v.y);
	}
	
	public Vector scale(double s) {
		return new Vector(x * s, y * s);
	}
	
	public Vector normalize() {
		Vector v = new Vector();
		v.setPolar(angle, 1);
		return v;
	}
	
	public String toString() {
		return "xy(" + x + "," + y + ") => polar(" + length + "," + Math.toDegrees(angle) + ")";
	}
}

Share this post


Link to post
Share on other sites
Advertisement
I don''t think this will solve the specific problem you''re asking about but I have two comments:

1) When you check if the balls are moving away from each other why don''t you just check if the dot product is negative, instead of those if..else clauses (that''s what he did in Pool Hall Lessons).

2) At the end of the next frame method I see you are handling _all_ the collisions you found. This is wrong. You have to only handle the collision that happened first (where t is minimal), all the other collisions could be invalidated by this collision, since it changes the directions of two balls.

The first point is just me nit-picking. But the second point is crucial for your simulation to run correctly, and it might even be the reason for your bug since it messes up the whole algorithm(although I doubt it).

It would be helpful if you told us the output of all those System.out.println()s at the end of testBallCollision() on the ocassions when you''re getting the negative values.

shmoove

Share this post


Link to post
Share on other sites
I concur

test the dot product of relative velocities versus relative position, if it is positive, the balls move away from each other.


when you find a collision, make sure it''s the earliest. once you find the earliest, move all the balls to that time, bounce the two earliest colliding ball, reduce the time left in the collision check (dt -= time_of_earliest_collision) the check again for the whole simulation for collisions in the time range [0, dt].

as for the negative time of collision, if your detection is correct, it simply means that the balls collide back in time, so the balls are actually kind of moving away from each other, and the collision is irrelevant. if you find a collision time between [0, dt], then it is a valid collision, else, you don''t need to consider it. It''s the same principle when you find a time of collision greater than dt. forget about it, the balls won;t collide early enough.

Share this post


Link to post
Share on other sites
That test to see if they were moving away from each other was added after I was getting problems. Anyway I''ve removed that and now I only handle the collision that occurs first.


// handle the first collision that occured

Collision c, first = null;
double min_t = t;
for (Iterator i = collisions.iterator(); i.hasNext(); ) {
c = (Collision) i.next();
if (c.t <= min_t) {
first = c;
min_t = c.t;
}
}
if (first != null) {
first.handle();
}


Anyway is an example debug printout:
MOVEMENT VECTOR TOO SHORT
BALL COLLISION t=3.0308700800113666
D = 18.78297101099823
F = 72.2000000000001
T = 327.7999999999999
distance = 0.6777231529875642
mag = 3.577708763999664
MOVEMENT VECTOR TOO SHORT
MOVEMENT VECTOR TOO SHORT
BALL COLLISION t=-160.0
D = -17.888543819998322
F = 79.99999999999983
T = 320.00000000000017
distance = -35.777087639996644
mag = 3.5777087639996643
MOVEMENT VECTOR TOO SHORT
MOVEMENT VECTOR TOO SHORT
MISSED COLLISION
movea => xy(-6.593982808022922,3.8183381088825223) => polar(7.619731962887305,149.92641217713944)
moveb => xy(-5.406017191977078,0.681661891117477) => polar(5.448824167997494,172.8133210612033)
dist = 18.681541692269406
sumRadii = 20
movec => xy(-1.1879656160458438,3.1366762177650456) => polar(3.3541019662496865,110.74337552474246)


Then adding a check to make sure the collision time is within 0 and dt results in:
MOVEMENT VECTOR TOO SHORT
BALL COLLISION t=3.3781558627046144
D = 20.012832559353274
F = 104.4865329512894
T = 295.5134670487106
distance = 2.822327417016396
mag = 13.367423087491472
MOVEMENT VECTOR TOO SHORT
MOVEMENT VECTOR TOO SHORT
MISSED COLLISION
movea => xy(3.0445843828715358,-6.408816120906802) => polar(7.095239117606972,-64.58938810217984)
moveb => xy(0.2554156171284645,5.808816120906802) => polar(5.814428765061953,87.48230684678786)
dist = 19.924858845171276
sumRadii = 20
movec => xy(2.7891687657430713,-12.217632241813604) => polar(12.531959144523254,-77.140298921278)

Share this post


Link to post
Share on other sites
I have changed the clipping check to:

System.out.println("Testing Ball" + num + " and Ball" + b.num);
if (distSquared < sumRadiiSquared) {
int sensitivity = 2;
// The balls are touching

double dist = Math.sqrt(distSquared);
if (dist < sumRadii - sensitivity) {
System.out.println("MISSED COLLISION");
System.exit(1);
}
}


After further debugging I have found that after the previous collision test exited due to "collision_t out of range" we get "MISSED COLLISION". Below are example printouts of the variables when we exit with "collision_t out of range":
collision_t = -0.7141734353210153
t = 31
movec => xy(11.866556705093648,-5.607337233423616) => polar(13.124686620431813,-25.292270553869088)
C => xy(18.0,-8.0) => polar(19.697715603592208,-23.962488974578182)
N => xy(0.9041401938405467,-0.42723589488943775) => polar(1.0,-25.292270553869088)
D = 19.692410648245342
F = 0.20896286087338467
T = 399.7910371391266
distance = -0.3023645977814695
mag = 13.124686620431813


collision_t = -0.5030340540340816
t = 16
movec => xy(9.920000000000002,8.96) => polar(13.367423087491472,42.08916217383224)
C => xy(5.0,19.0) => polar(19.6468827043885,75.25643716352927)
N => xy(0.7421026427511382,0.67028625796877) => polar(1.0,42.08916217383224)
D = 16.44595211516232
F = 115.53065902578794
T = 284.46934097421206
distance = -0.42026681423060097
mag = 13.367423087491472


Share this post


Link to post
Share on other sites

  • 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!