I've made an application for testing circle-circle collision in Java. There are two balls; one that the use can move around (A), another that's stationary (B). A is moved forward at a constant velocity using the up arrow key, while the left and right arrow keys change the angle that it moves. There's no inertia, so the ball just stops when the up arrow key isn't pressed.
When I try to move ball A over ball B, I want them to only be able to just touch each other. My problem is that when I move ball A to either the east or west side of ball B some overlap is allowed. Colliding from north or south of ball B is better, but sometimes ball A is blocked a little bit away from ball B, leaving a narrow gap that can't be crossed without turning A around.
Here's some pics:
Good collision: <http://img222.echo.cx/img222/3408/goodcollision0lw.jpg>
Not-so-good collision: <http://img213.echo.cx/img213/9162/notsogoodcollision5lc.jpg>
Bad collision: <http://img213.echo.cx/img213/7633/badcollision0bu.jpg>
I'm posting the code so that people might be able to point out what's wrong. I took the collision algorithm from Gamasutra's article "Pool Hall Lessons" (http://www.gamasutra.com/features/20020118/vandenhuevel_01.htm).
Display.java - Just a JPanel in a JFrame that shows all the graphics.
[source="java"]
/************************** Created on May 22, 2005 *
* @author Aaron MacDonald *
\*************************/
package collisionTests;
// A panel to draw the test's graphics on.
import javax.swing.JFrame;
import javax.swing.JPanel;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Image;
import java.awt.RenderingHints;
import java.awt.event.KeyAdapter;
import java.awt.event.KeyEvent;
import java.awt.Graphics2D;
public class Display extends JPanel implements Runnable {
static final long serialVersionUID = 0L;
// Size of panel.
private static final int WIDTH = 700;
private static final int HEIGHT = 700;
/* Number of frames with a delay of 0 ms before the animation thread
yields to other running threads. */
private static final int NO_DELAYS_PER_YIELD = 16;
// # of frames that can be skipped in any one animation loop.
private static int MAX_FRAME_SKIPS = 5;
private Thread animator; // Thread for controling animation.
private boolean running = false; // For stopping animation.
private boolean isPaused = false; // For pausing.
// Used by gameRender().
private Graphics2D dbg2D;
private Image dbimage = null;
private final long period; // How long each update/render should take;
Simulation sim;
public Display(long period) {
this.period = period;
setBackground(Color.white);
setPreferredSize(new Dimension(WIDTH, HEIGHT));
setFocusable(true);
requestFocus(); // JPanel now revieves key events.
readyForTermination();
// Creates simulation.
sim = new Simulation(WIDTH, HEIGHT);
}
private void readyForTermination() {
addKeyListener(new KeyAdapter() {
// Listen for esc and arrow keys.
public void keyPressed(KeyEvent e) {
int keyCode = e.getKeyCode();
if (keyCode == KeyEvent.VK_ESCAPE)
running = false;
else if (keyCode == KeyEvent.VK_UP)
sim.changeMoves(0, true);
else if (keyCode == KeyEvent.VK_LEFT)
sim.changeMoves(1, true);
else if (keyCode == KeyEvent.VK_RIGHT)
sim.changeMoves(2, true);
}
public void keyReleased(KeyEvent e) {
int keyCode = e.getKeyCode();
if (keyCode == KeyEvent.VK_UP)
sim.changeMoves(0, false);
else if (keyCode == KeyEvent.VK_LEFT)
sim.changeMoves(1, false);
else if (keyCode == KeyEvent.VK_RIGHT)
sim.changeMoves(2, false);
}
});
}
// Start game after panel added to a JFrame.
public void addNotify() {
super.addNotify();
startGame();
}
// Initializes and starts the thread.
private void startGame() {
if (animator == null || !running) {
animator = new Thread(this);
animator.start();
}
}
// Used by user to end game.
public void stopGame() {
running = false;
}
// Pauses game.
public void pauseGame() {
isPaused = true;
}
// Resumes game.
public void resumeGame() {
isPaused = false;
}
/* Update, render, sleep, repeat. Loop should take about as long as
<period> nsecs. Sleep inaccuracies are handled.
Overruns in update/renders will cause extra updates to be carried
out so that the # of updates per second (UPS) is about equal to
the requested # of frames per second (FPS). */
public void run() {
long beforeTime, afterTime, timeDiff, sleepTime;
long overSleepTime = 0L;
int noDelays = 0;
long excess = 0L;
beforeTime = System.nanoTime();
running = true;
while (running) {
gameUpdate(); // Update game state.
gameRender(); // Render to a buffer.
paintScreen(); // Draw buffer to screen.
afterTime = System.nanoTime();
timeDiff = afterTime - beforeTime;
sleepTime = (period - timeDiff) - overSleepTime;
if (sleepTime > 0) { // Some time left in cycle.
try {
Thread.sleep(sleepTime/1000000L); // nano -> ms.
}
catch (InterruptedException e){};
overSleepTime = (System.nanoTime() - afterTime) - sleepTime;
}
else { // sleepTime <= 0; cycle took longer than expected.
excess -= sleepTime; // Store excess value.
overSleepTime = 0L;
if (++noDelays >= NO_DELAYS_PER_YIELD) {
Thread.yield(); // Gives another chance to run.
noDelays = 0;
}
}
beforeTime = System.nanoTime();
/* If frame animation is taking too long, update the game state
without rendering it to get the UPS nearer to the required
FPS. */
int skips = 0;
while ((excess > period) && (skips < MAX_FRAME_SKIPS)) {
excess -= period;
gameUpdate(); // Update state but don't render.
skips++;
}
}
System.exit(0); // End of animation/game. Quit.
}
// Update game state.
private void gameUpdate() {
if (!isPaused) {
sim.update();
}
}
/* Draws buffer into it's own Graphics object, which represents an image
the size of the screen. */
private void gameRender() {
// Draw image to image buffer.
if (dbimage == null) { // Must create buffer.
dbimage = createImage(WIDTH, HEIGHT);
if (dbimage == null) {
System.out.println("image is null.");
return;
}
else
dbg2D = (Graphics2D)dbimage.getGraphics();
}
// Turn on antialiasing.
dbg2D.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
RenderingHints.VALUE_ANTIALIAS_ON);
// Clear background.
dbg2D.setColor(Color.black);
dbg2D.fillRect(0, 0, WIDTH, HEIGHT);
// Draw sim.
sim.draw(dbg2D);
}
// Actively render buffer image to screen.
private void paintScreen() {
Graphics g;
try {
g = this.getGraphics(); // Get panel's graphics context.
if ((g != null) && (dbimage != null))
g.drawImage(dbimage, 0, 0, null);
g.dispose();
}
catch (Exception e) {
System.out.println("Graphics context error: " + e);
}
}
public static void main(String[] args) {
javax.swing.JFrame window
= new javax.swing.JFrame("Circle-Circle Collision Test");
window.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
final int DEFAULT_FPS = 60;
long period = ((long)1000.0/DEFAULT_FPS) * 1000000L;
window.add(new Display(period));
window.pack();
window.setResizable(false);
window.setVisible(true);
}
}
Simulation.java - where the simulated objects are stored and updated.
[source="java"]
/************************** Created on May 22, 2005 *
* @author Aaron MacDonald *
\*************************/
package collisionTests;
// Handles the test itself.
import java.awt.Graphics2D;
public class Simulation {
// Simulation elements.
private Ball A, B; // User moves A. B is stationary.
/* Booleans for ball A movement.
0: thrust
1: turn ccw
2: turn cw */
private boolean[] movesA = new boolean[3];
public Simulation(int w, int h) {
A = new Ball(w, h, (w / 4f), (h / 2f), true);
B = new Ball(w, h, (w / 2f), (w / 2f), false);
}
public void changeMoves(int i, boolean keyIsPressed) {
movesA = keyIsPressed;
}
public void update() {
// Test for collisions.
float Nx = 0, Ny = 0;
boolean willCollide = testForCollision(Nx, Ny);
A.move(willCollide, Nx, Ny);
// Update movements (of ball A).
A.thrust(movesA[0]);
A.turnCCW(movesA[1]);
A.turnCW(movesA[2]);
}
private boolean testForCollision(float Nx, float Ny) {
// Ball B is stationary.
float moveVecX = A.dx();
float moveVecY = A.dy();
float moveVecMag = (float)Math.sqrt((moveVecX * moveVecX)
+ (moveVecY * moveVecY));
// 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.
double dist = Math.sqrt(((B.x() - A.x()) * (B.x() - A.x()))
+ ((B.x() - A.x()) * (B.x() - A.x())));
double sumRadii = (A.radius() + B.radius());
dist -= sumRadii;
if(moveVecMag < dist) {
return false;
}
// Normalize the movevec
Nx = moveVecX / moveVecMag;
Ny = moveVecY / moveVecMag;
// Find C, the vector from the center of the moving
// circle A to the center of B
float Cx = B.x() - A.x();
float Cy = B.y() - A.y();
// D = N . C = NxCx + NyCy
double D = (Nx * Cx) + (Ny * Cy);
// 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) {
return false;
}
// Find the length of the vector C
double lengthC = Math.sqrt((Cx * Cx) + (Cy * Cy));
double F = (lengthC * lengthC) - (D * D);
// 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
double sumRadiiSquared = sumRadii * sumRadii;
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)
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) {
return false;
}
// Therefore the distance the circle has to travel along
// movevec is D - sqrt(T)
double distance = D - Math.sqrt(T);
// Finally, make sure that the distance A has to move
// to touch B is not greater than the magnitude of the
// movement vector.
if(moveVecMag < distance) {
return false;
}
// Set the length of the movevec so that the circles
// will just touch
Nx *= distance;
Ny *= distance;
return true;
}
public void draw(Graphics2D g) {
A.draw(g);
B.draw(g);
}
}
Ball.java - a (potentially movable) ball.
[source="java"]
/************************** Created on May 22, 2005 *
* @author Aaron MacDonald *
\*************************/
package collisionTests;
// A (potentially movable) ball.
import java.awt.Graphics2D;
import java.awt.Color;
import java.awt.geom.Ellipse2D;
public class Ball {
private int pWidth, pHeight; // Dimensions of panel.
private float radius = 50f;
private float x, y;
private float angle; // radians
private float vel = 6f; // pixels/frame
private double turn = Math.PI / 32; // radians/frame
private boolean thrust, turnCCW, turnCW;
private boolean isGreen;
public Ball(int w, int h, float x, float y, boolean isGreen) {
pWidth = w;
pHeight = h;
this.x = x;
this.y = y;
this.isGreen = isGreen;
}
public void draw(Graphics2D g) {
if (isGreen)
g.setColor(Color.green);
else
g.setColor(Color.red);
// Ball itself.
g.fill(new Ellipse2D.Float((x - radius), (y - radius),
(radius * 2), (radius * 2)));
// Center of ball.
g.setColor(Color.yellow);
g.fill(new Ellipse2D.Float((x - 2f), (y - 2f), 4f, 4f));
// Angle of ball.
g.setColor(Color.blue);
g.fill(new Ellipse2D.Float((((float)Math.cos(angle) * radius) - 2f + x),
(((float)Math.sin(angle) * radius) - 2f + y), 4f, 4f));
}
public void thrust(boolean mustDoIt) {
thrust = mustDoIt;
}
public void turnCCW(boolean mustDoIt) {
turnCCW = mustDoIt;
}
public void turnCW(boolean mustDoIt) {
turnCW = mustDoIt;
}
public void move(boolean willCollide, float Nx, float Ny) {
turn();
thrust(willCollide, Nx, Ny);
wraparound();
}
private void turn() {
if (turnCCW != turnCW) {
if (turnCCW) {
angle -= turn;
if (angle < 0)
angle += (2 * Math.PI);
}
else {
angle += turn;
if (angle >= (2 * Math.PI))
angle -= (2 * Math.PI);
}
}
}
private void thrust(boolean willCollide, float Nx, float Ny) {
if (thrust) {
if (willCollide) {
x += Nx;
y += Ny;
}
else {
x += dx();
y += dy();
}
}
}
// If ball goes to edge of panel it wraps around to other side.
private void wraparound() {
if (x > (float)pWidth)
x = 0f;
else if (x < 0f)
x = (float)pWidth;
if (y > (float)pHeight)
y = 0f;
else if (y < 0f)
y = (float)pHeight;
}
public float x() {
return x;
}
public float y() {
return y;
}
public float dx() {
return (float)Math.cos(angle) * vel;
}
public float dy() {
return (float)Math.sin(angle) * vel;
}
public float radius() {
return radius;
}
}
Thank you for any help you may provide.
UPDATE
I think I fixed my problem. I'll put it here to avoid resurrecting an old topic.
I ended up redoing the collision test method, and this time I looked for the time (in one frame) that the balls collided. I think what helped was that I only added one step at a time and tested it before adding any more. This is what I got:
[source="java"]
private double calculateTranslation(Ball A, Ball B) {
// Relative position.
double dPx = B.x() - A.x();
double dPy = B.y() - A.y();
double dP = Math.sqrt((dPx * dPx) + (dPy * dPy));
// Relative velocity.
double dVx = B.dx() - A.dx();
double dVy = B.dy() - A.dy();
double dV = Math.sqrt((dVx * dVx) + (dVy * dVy));
double minDist = (B.radius() + A.radius());
// Distance between A and B.
double dist = dP - minDist;
if (dV < dist)
return 1.0;
// Normalize dV.
double dVNx = dVx / dV;
double dVNy = dVy / dV;
// Are A and B moving away from each other?
// Find dot product of dVN and dP.
double dotProd = (dVNx * dPx) + (dVNy * dPy);
if (dotProd >= 0)
return 1.0;
// dotProd is also the component of dP parallel to the normal of dV.
// This can be used to find the shortest line between the center of B
// and dV, which we'll call F.
// dP is the hypotenuse.
double Fsq = (dP * dP) - (dotProd * dotProd);
double minDistSq = minDist * minDist;
// 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 (Fsq >= minDistSq)
return 1.0;
// F and minDist form a right triangle (minDist the hypotenuse) with a
// third line we'll call T. Tsq is the square of T.
double Tsq = minDistSq - Fsq;
// Check that Tsq isn't negative.
if (Tsq < 0)
return 1.0;
// Therefore the distance the circle has to travel along
// movevec is dotProd - T
double distFinal = Math.abs(dotProd) - Math.sqrt(Tsq);
// Finally, make sure that the distance A has to move
// to touch B is not greater than the magnitude of the
// movement vector.
if (dV <= distFinal)
return 1.0;
// Find the time it will take for A & B to make contact.
double time = distFinal / dV;
return time;
}
I kind of prefer getting the time value over getting the positional translation anyway. I don't even need a boolean; I just pass whatever value I have to the balls' move methods during update.
[Edited by - Zaxx on May 28, 2005 2:24:59 PM]