Circle-circle and line-point collision detection example
From J2me wiki
Anything beyond bounding box collision detection can be pretty tough in J2ME. The following example shows two pretty obscure ways of handling two of the trickier forms of CD, circle-circle and line-point. Both examples avoid floating point math of any kind and only use multiplication, addition and subtraction. As they don't need any sin tables, etc either they're fast and easy on heap size and jar size.
NOTE: the line-point collision detection is based on the equation of the line and the line tested against is therefore infinite and looks in both directions along the line. But simple bounding box collision detection can fix that !
If you make a project called CollisionDetection and put the following code into it's main .java you can try it out in the WTK.
//**************************************************************************** //************ Fast Integer-only Collision Detection example ************** //************ 2006 Clarity Games Ltd. ************** //************ Circle-circle and line-point collision detection ************** //************ without resorting to using floating point or ************** //************ sin tables. Heap size and .jar size friendly. ************** //****************************************************************************
//Use the lasers on your UFO to kill the comets //Fire key - reverse direction
import javax.microedition.lcdui.*; import javax.microedition.midlet.*; import java.io.*; import java.io.IOException; import java.util.Random;
public class CollisionDetection
extends MIDlet
implements CommandListener, Runnable {
private boolean running;
private boolean FirstComet = true;
//Line drawing variables. As the algorithms in this example are all vector based, so is the
//'rotating line' code.
private int AimingX;
private int AimingY;
private int AimingDirX;
private int AimingDirY;
private int Kills = 0;
private int CometX;
private int CometY;
private int CometXvec;
private int CometYvec;
private int Count = 30;
private long frameTime = 0;
private long lastFrameTime = 0;
//***** collision detection variables
//1. Line-point
//The line - point algorithm returns a value that approaches zero the nearer the point gets to the line.
//This example uses two ways of testing this variable for collision which, when both used, yield
//excellent results
//1a Sensitivity test
//Sensitivity is a value that tells the algorithm how near to zero to allow the point to get before registering
//a collision. Make this value too small and you risk the algorithm missing collision altogether.
//Make it too large and collision will occur when the object represented by the point is still not being hit by the line.
private static final int SENSITIVITY = 10;
//1b 'Side' Sweep test
//for collision between a line and a point you need to keep track of which side of the line the point's currently
//on and which side it was on on the previous test.
private int Side = 0;
private long LastSide = 0;
//2. Circle-circle
//for a collision between two circles, start off with the radius in pixels of the two circles...
private static final int PLAYER_RADIUS = 16;
private static final int ENEMY_RADIUS = 8;
//if the length between the centers of two circles is less than the sum of the radii of the circles then they're overlapping.
//for overlapping read COLLIDING
private int COLLISION_LENGTH = PLAYER_RADIUS+ENEMY_RADIUS;
//We need to square the collision length and use this as the 'limit' of our collision test to remove the need for
//a square root in our calculations. This keeps all the mathematics simple and integer based.
//The resulting 'collision limit' value makes the test for circle-circle collision a doddle!
private int COLLISION_LIMIT = COLLISION_LENGTH*COLLISION_LENGTH;
//****** End of collision detection variables
private MyCanvas myCanvas;
private Display display;
private Graphics myGraphics;
private Random random = new Random();
private Command quit;
class MyCanvas extends Canvas
{
protected void paint(Graphics graphics)
{
int PlayerVectorX;
int PlayerVectorY;
int EnemyVectorX;
int EnemyVectorY;
int CenterX = getWidth()/2;
int CenterY = getHeight()/2;
int LoopCount = 4;
myGraphics = graphics;
if (FirstComet)
{
NewComet();
FirstComet=false;
}
frameTime = System.currentTimeMillis();
long Duration = frameTime-lastFrameTime;
while ((Duration > 5) && (LoopCount >0))
{
LoopCount--;
myGraphics.setColor(0,0,0);
myGraphics.drawLine (CenterX,CenterY,AimingX,AimingY);
PlayerVectorX = (AimingX-CenterX);
PlayerVectorY = (AimingY-CenterY);
myGraphics.drawLine (CenterX-PlayerVectorX,CenterY-PlayerVectorY,CenterX,CenterY);
AimingX+=AimingDirX;
AimingY+=AimingDirY;
if ((AimingX>=getWidth()) && (AimingY==0))
{
AimingX = getWidth()-1;
AimingDirX=0;
AimingDirY=1;
};
if ((AimingX<0) && (AimingY==0))
{
AimingX = 0;
AimingDirX=0;
AimingDirY=1;
};
if ((AimingX>=getWidth()) && (AimingY==(getHeight()-1)))
{
AimingX = getWidth()-1;
AimingDirX=0;
AimingDirY=-1;
};
if ((AimingX<0) && (AimingY==(getHeight()-1)))
{
AimingX = 0;
AimingDirX=0;
AimingDirY=-1;
};
if ((AimingY>=getHeight()) && (AimingX==0))
{
AimingY = getHeight()-1;
AimingDirX=1;
AimingDirY=0;
};
if ((AimingY<0) && (AimingX==0))
{
AimingY = 0;
AimingDirX=1;
AimingDirY=0;
};
if ((AimingY>=getHeight()) && (AimingX==(getWidth()-1)))
{
AimingY = getHeight()-1;
AimingDirX=-1;
AimingDirY=0;
};
if ((AimingY<0) && (AimingX==(getWidth()-1)))
{
AimingY = 0;
AimingDirX=-1;
AimingDirY=0;
};
Duration-=5;
//both our collision detection algorithms use vector arithmetic so they can share some calculations,
//yet another advantage of vector based CD/R
PlayerVectorX = (AimingX-CenterX);
PlayerVectorY = (AimingY-CenterY);
EnemyVectorX = (CenterX-CometX);
EnemyVectorY = (CenterY-CometY);
//Collision detection between a line and a point is trickier than other forms of CD as it's not based
//on proximity. Fortunately there's a simple vector based algorithm that can return a simple integer
//value that can be used for TWO methods of line-point collision detection.
//This algorithm is based upon a very simple premise, that if two lines both start at the same point and
//both lines have the same gradient (angle), then both lines point in the same direction.
//In our example the single point that both lines start from is the center of the screen.
//The first line is the actual 'laser line' and the second is an imaginary line between the center of
//the screen and the center of the comet. If Gradient of 1st line = Gradient of 2nd line then COLLISION !!!
//Now gradient arithmetic has lots of nasty pitfalls, divisions that need to be floating point to be accurate, //problems with division by zeroes and gradients so large they overflow the variables, etc. so gradient //arithmetic isn't a great tool for collision detection in J2ME. But, of course, a quick bit of cross //multiplication can make it into something a lot friendlier...
//The gradient equation Gradient1 = Gradient2 in full looks like this :-
// ... (y2-y1) / (x2-x1) = (y3-y1) / (x3-x1)
// ... Cross multiply to get rid of the divisions and you get
// ... (x3-x1)*(y2-y1) = (x2-x1)*(y3-y1)
// ... You can also say this like this:-
// ... (x3-x1)*(y2-y1) - (x2-x1)*(y3-y1) = 0
//Which, as we already know the values of things like x3-x1 (the vectors we calculated earlier)
//becomes a VERY simple calculation:-
Side = EnemyVectorX * PlayerVectorY - PlayerVectorX*EnemyVectorY;
//You can check to see if the value of Side is approaching zero as a form of collision detection but
//you can ALSO use the value of side to tell which SIDE of the 'laser line' the comet is currently on,
//the 'positive' side or the 'negative'. Collision can then also be said to occur when, from
//one frame to the next, the point (comet) has switched sides - i.e. the laser line has 'swept'
//over the point (comet) between the two frames. This method is a kind of 'sweep test' in that it
//doesn't require fast fps speeds to be accurate but has the disadvantage of needing to wait
//until the line is just past the comet before registering a 'hit', making it more accurate but slower
//than the 'sensitivity' test. This is why I use both. First I test for sensitivity as it's faster..
if (((Side >=0) && (Side < SENSITIVITY)) || ((Side<=0) && (Side > SENSITIVITY)))
{
//Simple collision detection, tests if 'side' value is near to zero
Kills++;
NewComet();
}
//Then I 'sweep' test to catch any collisions that the sensitivity test may have missed...
if (Side<=0)
{
if (LastSide > 0)
{
//Current 'side' is negative but the previous frame it was positive...
Kills++;
NewComet();
}
} else {
if (LastSide < 0)
{
//Current 'side' is positive but the previous frame it was negative...
Kills++;
NewComet();
}
}
LastSide = Side;
//as the enemy comets move a lot slower than the laser line there's no need to do the circle-circle
//collision detection of the comet hitting the player's UFO as often
Count--;
if (Count == 0)
{
//enemy code
Count = 30;
CometX+=CometXvec;
CometY+=CometYvec;
//circle on circle collision detection is based upon the vector calculation of length, which states
//that the length between two points in 2D space can be calculated by getting the vector between the
//two points and using the calculation LENGTH = Square Root of (X-VECTOR SQUARED + Y-VECTOR SQUARED)
//As we want to avoid square roots we can simplify this to
//LENGTH SQUARED = X-VECTOR SQUARED + Y-VECTOR SQUARED
//This makes for a nice quick calculation requiring only integer addition and integer multiplication
int Length = EnemyVectorX*EnemyVectorX + EnemyVectorY*EnemyVectorY;
if (Length <= COLLISION_LIMIT)
{
//a comet has hit the UFO, quit the game !
destroyApp(true);
notifyDestroyed();
}
//Draw the comet
for (int i = 0;i<8;i++)
{
myGraphics.setColor(31*i,30*i,24*i);
myGraphics.fillArc(CometX-CometXvec*(7-i)-8,CometY-CometYvec*(7-i)-8,16,16,0,360);
}
}
myGraphics.setColor(128,192,255);
myGraphics.drawLine (CenterX,CenterY,AimingX,AimingY);
myGraphics.drawLine (CenterX-PlayerVectorX,CenterY-PlayerVectorY,CenterX,CenterY);
lastFrameTime=frameTime;
}
//draw the ufo
myGraphics.setColor(128,160,255);
myGraphics.fillArc(CenterX-16,CenterY-16,32,32,0,360);
myGraphics.drawString(" "+Kills,0,0,Graphics.LEFT | Graphics.TOP);
}
protected void keyPressed(int keyCode)
{
int Key;
try {
Key = getGameAction(keyCode);
} catch (Exception e)
{
Key = 0;
}
if (Key ==FIRE)
{
AimingDirX=-AimingDirX;
AimingDirY=-AimingDirY;
}
}
}
public CollisionDetection()
{
myCanvas = new MyCanvas();
quit = new Command("Quit",Command.EXIT,2);
myCanvas.addCommand(quit);
myCanvas.setCommandListener(this);
running = true;
AimingY = 0;
AimingX = myCanvas.getWidth() / 2;
AimingDirX = 1;
AimingDirY = 0;
lastFrameTime = System.currentTimeMillis();
Thread t = new Thread(this);
t.start();
}
private void NewComet()
{
myGraphics.setColor(0,0,0);
myGraphics.fillRect(0,0,myCanvas.getWidth(),myCanvas.getHeight());
if (rnd(2) ==0)
{ //along top or bot
CometX=rnd(myCanvas.getWidth());
CometXvec=rnd(4);
if (rnd(2)==0)
{//along top
CometY = 0;
CometYvec = 5-CometXvec;
} else {
CometY = myCanvas.getHeight()-1;
CometYvec = -(5-CometXvec);
}
if (CometX> myCanvas.getWidth()/2) CometXvec=-CometXvec;
} else { //along left or right
CometY=rnd( myCanvas.getHeight());
CometYvec=rnd(4);
if (rnd(2)==0)
{//along left
CometX = 0;
CometXvec = 5-CometYvec;
} else {
CometX = myCanvas.getWidth()-1;
CometXvec = -(5-CometYvec);
}
if (CometY> myCanvas.getHeight()/2) CometYvec=-CometYvec;
}
}
public void startApp()
{
Display.getDisplay(this).setCurrent(myCanvas);
myCanvas.repaint();
}
public void pauseApp()
{
myCanvas.repaint();
}
public void destroyApp(boolean unconditional)
{
}
public void commandAction(Command c, Displayable s)
{
if (c==quit)
{
destroyApp(true);
notifyDestroyed();
}
}
public void run()
{
while (running)
{
myCanvas.repaint();
myCanvas.serviceRepaints();
}
}
private int rnd(int bound)
{
return random.nextInt(bound);
}
}
