MIDP irregular shape collision detection
Hi there,
I'm programming a MIDP2.0 game and I have some problems trying to come up with a collision detection mechanism when it comes to irregularly shaped screen items. I've found ways to detect collision between two blocks or a point and a block but I can't find a way to do the same with irregular shapes.
In particular I'm trying to detect collision between a circle (ball) bounching on the ground. The ground is the irregular shape. I represent the floor with an array of integers, each pair of which is the pair of XY coordinates of an angle on the upper surface of the ground.
For example, using array [0, 123, 25, 100, 50, 136, 100, 102, 150, 129]
would result in having 3 peaks and 2 canyons on the surface of the ground, when these points are connected to each other. The problem is that not being able to use floating point numbers I cannot find the coordinates of each and every point (pixel) that lies between any of these points. I thought that I definitely need these coordinations in order to detect collision between the ball and the surface of the ground.
Any ideas on how this could be done will be very much appreciated.
Someone must have done it.... Is it really so hard to detect collision between irregular shapes?I need help please!!!
> The problem is that not being able to use floating point
> numbers I cannot find the coordinates of each and
> every point (pixel) that lies between any of these
> points.
You can use fixed point numbers. Give [url=http://home.rochester.rr.com/ohommes/MathFP/]MathFP[/url] a try.
But, IMHO, you should consider changing your model and representing the floor in a simpler way, without using angles. It might use up a little more memory, but it will be much simpler to use and it will run much faster. Starting to calculate sines and cosines at runtime can get quite expensive. If your concern is JAR size, then you could store the maps originally using your format and when you load them you can convert them to the simpler bigger format.
shmoove
I could narrow the whole problem down to detecting collision betwee the ball and triangles... Is that feasible?
If the triangle is a Polygon, and the ball is an Arc2D, Create 2 Area classes and use the Area intersect(Area) methodNoah
> If the triangle is a Polygon, and the ball is an> Arc2D, Create 2 Area classes and use the Area> intersect(Area) method> > NoahYou're not thinking in J2ME terms here.shmoove
people dont realize how easy it is to detect a colision yourself all you need for 2d is a point and 3 surface normals or ie vectors
for 3d a point and 4 vectors
find the negaticve dot product for a point vs the vector of 1 boundry then the next 2
if all 3 are pointing inwards and the negative dot product returns positive the point is in bounds if
all 3 point outwards and checked against the point all three are negative then the point is in bounds
if all three vectors checked against the point return mixed results then the point is not inbounds
this is the formula for a negative dot product this is used heavily in specular reflection calculations as well
public static final double getDotProduct(double Ax,double Ay,double Az,double Bx,double By,double Bz)
{
return (Ax*Bx)+(Ay*By)+(Az*Bz);
}
normal
that is orthagonal to
any line you have
like the side of a triangle for instance
or the entire surface of a polygon
being at a T to a plane
x = 10
y = 1
z = 1 * now say here is your point at x= 20 , y = 1 ,z = 1;
vector
*>
run the point and the vector thru the dotproduct calculation and you will get a positive or negative number
make up a new vector that is for example pointing up
y 20 x1 z1ect....
heres some other functions these are kinda old they might help though
these took me forever this is when i did a software zbuffer in java it did like 18 fps so i scraped it but it had lighting and stuff
public static final void CalculateUnitLengthA(double ax,double ay,double az,double bx,double by,double bz)
{
double difx = bx - ax;
double dify = by - ay;
double difz = bz - az;
distance = Math.sqrt(difx * difx + dify * dify + difz *difz);
ulx = difx / distance ;
uly = dify / distance ;
ulz = difz / distance ;
}
public static final double getDotProduct(double Ax,double Ay,double Az,double Bx,double By,double Bz)
{
return (Ax*Bx)+(Ay*By)+(Az*Bz);
}
public boolean isWithinBoundrys(double ax,double ay,double az,double bx,double by,double bz,double cx,double cy,double cz,double x,double y,double z)
{
double np =0;
boolean iswithin = true;
FindUnitNormal( (int)ax,(int)ay,(int)az,(int)bx,(int)by,(int)bz,(int)cx,(int)cy,(int)cz );
CalculateUnitLengthA((int)ax , (int)ay , (int)az , (int) x , (int) y , (int) z);
double ux = GetUnitLengthX();
double uy = GetUnitLengthY();
double uz = GetUnitLengthZ();
np = getDotProduct(nmx,nmy,nmz,ux,uy,uz);// ok this should return a negitive or positive value determineing inside or outside
if(np < 0){iswithin = false;}
return iswithin;
}
public static final double findThetaABeringToB( double rx,double ry,double rz,double lax,double lay,double laz,double lbx,double lby,double lbz )
{
double dfx = lbx - lax; // this is a non unit length 3d vector from point a to bship a to ship b
double dfy = lby - lay;
double dfz = lbz - laz;
findUnitLengthOfVector(dfx,dfy,dfz);
double blx = GetUnitLengthX();
double bly = GetUnitLengthY();
double blz = GetUnitLengthZ();
reset(special);
transform_Special( rx, ry, rz, 0, 0, 0,1.0); // world is thought of as puting that into your world
mult_Vector_By_Special( 300,2,2 );
double nx = (getx() );
double ny = (gety() );
double nz = (getz() );
findUnitLengthOfVector(nx,ny,nz);
double theta = getDotProduct( ulx,uly,ulz,blx,bly,blz );
return theta;
}
// this just rotates a right faceing point
public static final void rotatePoint(double rx,double ry,double rz){
reset(special);
transform_Special( rx, ry, rz, 0, 0, 0,1.0); // world is thought of as puting that into your world
mult_Vector_By_Special( 300,2,2 );
double nx = (getx() );
double ny = (gety() );
double nz = (getz() );
findUnitLengthOfVector(nx,ny,nz);
}
// this was a original to prevent nan errors this finds the normal of a plane from 3 vectors xyz
// it is used to calculate a normal for a triangle ie.. a polygon and can be used on fairly big ones
// since i hope i have yanked out the nan errors that are possible thru use of this **** huge algorithim
// dont laugh until you get one of these nans and it takes you a week to figure out how to get rid of it
public static final void FindUnitNormal( double xa,double ya,double za,
double xb,double yb,double zb,
double xc,double yc,double zc)
{
int normalpointnumber =0;
double Ax = (xb - xa);double Ay = (yb - ya);double Az = (zb - za);
double Bx = (xc - xb);double By = (yc - yb);double Bz = (zc - zb);
double nx = (Ay * Bz) - (By * Az);
double ny = (Az * Bx) - (Bz * Ax);
double nz = (Ax * By) - (Bx * Ay);
double Combinedsquare = (nx*nx)+(ny*ny)+(nz*nz);
if( Combinedsquare == 0){Combinedsquare =1;}// saftey
double sqrtofnewpoint = Math.sqrt(Combinedsquare);
double multiplerrorval = 1; // 1 = no errors this is to compensate for NaN errors do not remove
double normalcoef = 1.0 / sqrtofnewpoint; // if this line is errored it means that sqrtofnewpoint is probably to big a number low probabability this will ever happen
if(Combinedsquare == 0){System.out.println("ERROR Unchecked the combined square is 0 probably all nans or rather too big a number ");}
if(sqrtofnewpoint == 0){System.out.println("ERROR squareroot of newpoint is 0 ");}//nvr gonna happen er wait it can so the fix is above
if(Double.isNaN(sqrtofnewpoint)){ System.out.println("ERROR the square is NAN do alternate routine ");};//error handle msg
// handle inherent possible error of nan value
while(Double.isNaN(sqrtofnewpoint) == true){// handle a possible NaN error ackk this took 3 days to figure out were this bug was
multiplerrorval += 1;
if(Ax != 0){Ax = (double)((double)(Ax / multiplerrorval)); }
if(Ay != 0){Ay = (double)((double)(Ay / multiplerrorval)); }
if(Ay != 0){Az = (double)((double)(Az / multiplerrorval)); }
if(Bx != 0){Bx = (double)((double)(Bx / multiplerrorval)); }
if(By != 0){By = (double)((double)(By / multiplerrorval)); }
if(By != 0){Bz = (double)((double)(Bz / multiplerrorval)); }
nx = (Ay * Bz) - (By * Az);
ny = (Az * Bx) - (Bz * Ax);
nz = (Ax * By) - (Bx * Ay);
Combinedsquare = (nx*nx)+(ny*ny)+(nz*nz);
sqrtofnewpoint = Math.sqrt(Combinedsquare);
normalcoef = 1 / sqrtofnewpoint;
}// eofNaN error Prevention lol :) arggg
nmx = (double)( ((double)(nx) * normalcoef ) );
nmy = (double)( ((double)(ny) * normalcoef ) );
nmz = (double)( ((double)(nz) * normalcoef ) );
}
i misread your post what you need is super simple
if you store all the points on the floor as xy
and you have a center point of a ball
and you know the radius of the ball then
let the center of the balls xy position be ( bx by ) and the balls radius center to outer point of ballbe r
and let floor[] xy= fx[],fy[]
then its super simple
fx - bx = differencex
fy - by = differencey
// now you need absolute values if i rember right so
if (differencex < 0 ){differencex = differencex * -1;}
if (differencey < 0 ){differencey = differencey * -1;}
now you have the absolute difference in distance xy from the floor to the ball
so your almost done you need the real distance to the floor point so you do the old
pathagorean theorumsquareroot of (a^2 + b^2)
distance = math.sqrt(x * x + y * y);
this is the distance of a line to the point on the floor you have checked against
now since you made it absolute already all you do is
if( distance < r){ then the ball has contacted a point on the surface }
if your floor is a array of points then put this whole thing in a loop and loop thru your points
if any points make contact set a boolean to true
further more if you still have the x and y coordinates in thier negative differences
then original_differencex / distance * -1 = the opposite direction to bounce in or the negative sin
in a decimal
you can find the cosine the same way you can use that to bounce away from whatever you hit
Thanx a lot for both your answers lightwavex.
As shmoove pointed out though, this collision detection has to be carried out in J2ME...!!! That means I can't use any floating point numbers or square roots or this kind of stuff... (tough luck) Actually your second answer could be made even more simple if your initial assumption (having all the floor points in an array) was true. In fact what I'm asking is for a way to accomplish exactly that. I need to find a way to find and store all these points.
Initially the floor is represented by only a few points and is then drawn by drawing lines between these points. What I'm looking an answer to is how can I get all the points that lie in between the initial points before drawing the screen. Once this is done I can then just compare the coordinations of the center of the ball to the Y coordinations of the counterpart X point on the floor. I really need to know the Y coordinates for every single X point on the floor then...
I know it's tough because of the restricted capabilities of J2ME, but I really need to do this! :/ Please give any ideas on either how to find all the in between points or other possible representations of the floor that would solve this problem.
Thanx in advance,
AF
yikes with no decimals thats tough
you might want to look into a form of breshamns line draw to manually calculate all those points on each line yourself im not sure i remember this just right but i think you can do that with the original breshamns
like so
assume two points x1 y1and x2 y2 say 10,1020,12 a sort of diagnal line
now the difference between these points is 10 on the x line
so youll want to set up a loop of the xdifference length
difx = x2- x1 ;
dify = y2- y1 ;
// now as we go left we subtract the diff y from x but we will put x into a errorterm instead of useing it directly
errortermx = difx;
// first though we set a
int yplot = y1 ;to the yheight of were were starting from in this case x1,y1 so
for(int n = 0;n < difx;n++){
errorterm -= dify;
while(errorterm < 0){
yplot++;
errorterm += difx;
}
// record the yplot or height as x is incrementing towards its other point
}
thier you go no decimals
Maybe something like this might work. I'm not sure about my vector math, so take this with a grain of salt...
A few tricks to doing integer-only are scaling (= fixed point arithmetic), and avoiding sqrt() by calculating the square of the distance instead of the distance. If your ball radius is 7, compare the "squared scaled distance" with 7 * 7 * SCALE * SCALE.
Assumption: your lines are well behaved -- add checks if you have vertical or zero-length lines. Also I'll assume your coordinates never get big enough to cause integer overflow even when squared and scaled (n * n * 64 * 64 < MAXINT for all possible coordinates in your program).
You'll need to add a check for the ball-below-ground case if that can happen; use the slope ("k") and fixed point math to get the line's y coordinate (ground height) at the x position of the ball.
public class distance
{
/****************
*
* Floating point version
*
*/
static double distanceSquared(double x0, double y0, double x1, double y1)
{
return (x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0);
}
static double distance(int px, int py, int x0, int y0, int x1, int y1)
{
double k =
(double) ((px - x0) * (x1 - x0) +
(py - y0) * (y1 - y0)) /
(double) distanceSquared(x0, y0, x1, y1);
// Outside line segment?
if (k < 0 || k > 1)
return 1000;
// (ix,iy) is the intersection point
double ix = x0 + k * (x1 - x0);
double iy = y0 + k * (y1 - y0);
double d2 = distanceSquared(px, py, ix, iy);
return Math.sqrt(d2);
}
/****************
*
* Integer version
*
*/
static final int SCALE = 64;
static int distanceSquared(int x0, int y0, int x1, int y1)
{
return (x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0);
}
static int distanceSquaredScaled(int px, int py, int x0, int y0, int x1, int y1)
{
int k =
((px - x0) * (x1 - x0) +
(py - y0) * (y1 - y0)) * SCALE /
distanceSquared(x0, y0, x1, y1);
// Outside line segment?
if (k < 0)
return SCALE * 1000;
if (k > SCALE)
return SCALE * 1000;
// (ix,iy) is the intersection point in scaled values
int ix = x0 * SCALE + k * (x1 - x0);
int iy = y0 * SCALE + k * (y1 - y0);
return distanceSquared(px * SCALE, py * SCALE, ix, iy);
}
public static void main(String args[])
{
int px = Integer.parseInt(args[0]);
int py = Integer.parseInt(args[1]);
int x0 = Integer.parseInt(args[2]);
int y0 = Integer.parseInt(args[3]);
int x1 = Integer.parseInt(args[4]);
int y1 = Integer.parseInt(args[5]);
System.out.println("1: " + distance(px, py, x0, y0, x1, y1));
int d2 = distanceSquaredScaled(px, py, x0, y0, x1, y1);
System.out.println("2: " + d2);
System.out.println("3: " + Math.sqrt((double) d2) / SCALE);
}
}
re: No doubles/floats/etctry MathFP (see link above).
mlka at 2007-7-15 21:51:26 >
i dont think he ever came back to the post
anyways what he needed to do was put in a few points on the bottom of the screen like a floor
then from them make a array the size of the screen width from left to right
that represented the floor at every point
the breshamns algorithim would do this very quickly it doesnt have any multiplys or divides
and requires no floats or doubles just addition and subtraction of integers
so its a extremely fast algorithim in the loop. in addition to that its prolly only about 12 lines long
then he could use mathFP to do the distance calculation.
if he ever reposts that hes still haveing trouble ill write it out for him its really easy to do.
I agree ... when drawing the line, you need to check the coordinate and check it if it is within the circle boundary (use sqrt(xDistance^2 + yDistance^2)...
To calculate sqrt, you may need this simple function so it can work on J2ME ...
final static int[] SQRT = new int[] {
0,1,3,7,13,21,31,43,57,73,91,111,133,157,183,211,241,273,
307,343,381,421,463,507,553,601,651,703,757,813,871,931,993
};
static int sqrt(int val) {
if (val<1) return 0;
if (val==1) return 1;
if (val>992) return 32;
for (int i=0; i<SQRT.length; i++)
if (SQRT>val) return i-1;
return 32;
}
To warn you, it is slow, and stupid and is limited to sqrt(992) only .. but hey .. if you need bigger number, do increase the range of SQRT your self ..
You should know how to generate SQRT array if you read my code.. If you don't, shame on you ... ;-) ..
rgds,
Alex
I am reading the posts... I don't want to sound rude for not answering, my apologies. lightwavex, I think your second answer (with errortermx) does the job. Is this the breshamns algorithm? I take it you meant to write errortermx in all three points but u use 'errortermx' & 'errorterm' interchangeably. I also think you need to recalculate 'difx' within the for loop as you travel to the right, right? Would u please have a look in what you posted in your previous message and make sure there are no typos?
Thanx a lot ppl.
sorry if that was a bit confuseing i just typed it out on the spot heres one i typed out and tested just now
even thier might be a bug but i just about got the correct output which i pasted at the bottom
this is a full explination of what is happening hope this helps i was really bored so i wrote this all out
its not a perfect breshamns algorithm it doesnt address the need for continuity in the plots going up
if you wanted a simple line draw instead this is exactly what you require. if you wanted to make this
a line draw algorithim then you would put a drawpixel inside each of the while loops but you dont need to do that.
// breshamns example
// if we had decimals we would just do the following to find the slope
// distance = sqrt( difx*difx + dify*dify ); beringx = difx/distance; beringy = dify/distance;
// we cant do the above division in that way gives us a decimal so we must look at this for a second
// what are we doing by saying dify/distance were saying how many times does disance go into difx
// what we do with the breshamns is nearly the same but we now say
// how many smaller values y does it take before we have a value equal to or greater than x
// we loop to find out but what we are looping thru is each point from left to right
// everytime the errorterm of dify excedes the difx we know we must plot just 1 higher
// the amount we loop by is the difx in your case.
// ok set up all the variables well need first
// for example your array and the screen width or window whatever
// is 100 lets say
int[] floors_Y_position = new int[51]; // heres your array representing the floor height from one side of the screen to the other
// above could be bigger if you intend your app to be scrollable
// lets say this is in your method and that method takes x1 y1 x2 y2
// now if your screen goes from left to right in other words 0,0 is top left and 100,100 is bottom right
int x1 =1 , y1 = 10 ;// bottom left point
int x2 = 50 , y2 =5 ;// middle right of the screen
// ok the first thing we do is get the difference of these depending on which way you subtract
// is important you can make it work either way but you must set your initial marker to the
// set of coordinates you subtract with like so
// the below marks were you start ploting from on the screen.
int plotposx = x1;
int plotposy = y1;
// well get back to the above in a second
// now we are commited to useing x1 y1 as the subtractor
int difx = x2 - x1;// and 100 - 1 =99
int dify = y2 - y1;// so 50 - 100 =-50
// now the difference x is the total distance from left to right
// and the difference y is the total distance from top to bottom think in slopes now
// we set (thiers different ways to do this i preffer to add but you can just as well subtract y from xterm )
int termY = dify;// (this should really start at 0) we make this seperate because we need the dify value to remain unchanged
// so remember error termY initially has the same value as dify and you can think of it as that
// now how do we use this well we know that the line moves across the screen one pixel at a time so
// if we looped like so for(int n = x1;n < x1 + difx ;n++){ drawadot(n,50); } we would get a straight line
// across the screen the same length as the line we wish to draw what we need to do is find when we
// have to move up as we traverse across the line. This is were are errorterm comes in
// for obvious reasons we absolutely need difx to be a absolute
// in case you plot this from right to left
int ABSdifx =0;if(difx < 0){ABSdifx = difx * -1;}else{ABSdifx = difx;}// change sign if need be
// step across from left to right
for( int traversalx = 0; traversalx < ABSdifx ; traversalx++ ){
// now as we traverse x we add to termY the difference of Y
// (!note)might want this after you set floors position
termY += dify;
// this is not adding to were we plot yetwe are figureing that out below
// now if termY is larger than difx then we know that it is time to move are point down on the Y line
// because are screen coordinates go from top to bottom
// and oppositely if its below the negative difx its time to move it up on the screen
while(termY < -ABSdifx){
// if we have entered this loop it means are errorterm is telling us its time to move up
termY = 0; // degrade are errorterm
plotposy --;// are plot should go upwards on the screen
}
while(termY > ABSdifx){// coulda made this a if but its best to do it in a while
termY = 0; // degrade are errorterm
plotposy ++; // are plot should go downwards on the screen
}
floors_Y_position[plotposx] = plotposy; // now you can compare your balls position to any point on the floor some or all at once
//DrawPixel(plotposx,plotposy,250,250,250);
System.out.println("x "+plotposx+" y "+plotposy);
plotposx ++;
}
x 1 y 10
x 2 y 10
x 3 y 10
x 4 y 10
x 5 y 10
x 6 y 10
x 7 y 10
x 8 y 10
x 9 y 9
x 10 y 9
x 11 y 9
x 12 y 9
x 13 y 9
x 14 y 9
x 15 y 9
x 16 y 9
x 17 y 9
x 18 y 9
x 19 y 8
x 20 y 8
x 21 y 8
ect....
oh i almost forgot
put that code in a method like so
findHeight(int x1,int y1,int x2,int y2){
// the code
}
then if you have a buncha points just draw between them one after the other
findHeight(px1,py1,px2,py2);
findHeight(px2,py2,px3,py3);
findHeight(px3,py3,px4,py4);
findHeight(px4,py4,px5,py5);
if you make the array outside the method thisll fill it with the proper values
were px and py are the points of your floor that you are drawing lines between on the floor into your array
Thanx a lot for your time and all. I'm sure this will do the job perfectly OK.cheers,AF
