#### Archived

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

# Collision between moving balls

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

## 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 {

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

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;
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();
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

// Calculate distance between objects

int distSquared = deltaXSquared + deltaYSquared;

// 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));
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

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);
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

}
}

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()) +

//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;
}

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 on other sites
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 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 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
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
movec => xy(2.7891687657430713,-12.217632241813604) => polar(12.531959144523254,-77.140298921278)

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

1. 1
Rutin
27
2. 2
3. 3
4. 4
5. 5

• 11
• 9
• 9
• 9
• 14
• ### Forum Statistics

• Total Topics
633313
• Total Posts
3011315
• ### Who's Online (See full list)

There are no registered users currently online

×