Jump to content
  • Advertisement
Sign in to follow this  

Faulty Collision Handling with Bounding Circles (Java)

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

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]

Share this post


Link to post
Share on other sites
Advertisement
I didnt read you code. Nor do I know howto code in java. Here is how I would do it.

you need the following info. Position of both circles as 2d vectors. and the radius of both circles.

tmpvector = circle1.pos - circle2.pos
tmpvector = abs(tmpvector) //do abs on X and Y components
float len = sqrt(tmpvector.x * tmpvector.x + tmpvector.y * tmpvector.y)

if(len < (circle1.radius + circle2.radius))
// Then they collided.

Share this post


Link to post
Share on other sites
to get the exact point of collision in 2D

once you detect a collision as above (or similar method)

// create a 2D vector from the center of each circle.
Vec2D collideVector = circleMoving.pos() - circleStationary.pos();

// get the length of this vector
float length = collideVector.length();

// normalise the collide vector
collideVector.Normalise();

// now set your position using the spheres radius to push them apart
circleMoving.pos = circleStationary.pos + collideVector * (circleStationaty.Radius() + circleMoving.Radius());



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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!