Fast Collision Detection

[StumpyStrust]

So anyone know some super speed ways of finding if there is a collision between 2 points? maybe 2 images? pixel perfect collision?

I have a feeling the way I do it is very....bad.  

[ra4king]

Since the points are circular, you only need to do a radius check:

1   2   3   4

int r = point1.radius + point2.radius; if(distanceSquared(point1,point2) <= r*r) {     //collision }

Are your images of arbitrary shape, or just solid rectangles? If they are rectangles, just use the Rectangle.intersects(Rectangle) method. If not, then there is a very detailed pixel perfect collision which you could do.

EDIT: Fixed code, stupid me

[ReBirth]

Still can be done with rectangle. Intersect returns an area, check if some part of the "body" are contained inside that area. Hmm sounds hard.

Games published by our own members! Check 'em out!

[Riven]

Since the points are circular, you only need to do a radius check:

1   2   3

if(distanceSquared(point1,point2) <= point1.radius + point2.radius) {     //collision }

That's just wrong


It's either:

1   2   3

if(distance(point1,point2) <= point1.radius + point2.radius) {     //collision }

Or:

1   2   3   4

r = point1.radius + point2.radius; if(distanceSquared(point1,point2) <= r*r) {     //collision }

[ra4king]

Damnit how I could I forget that

Typing code directly into forum is not good

[StumpyStrust]

So distance between to points is

(x2- x1)^2 + (y2-y1)^2

so if my max distance is 120 and the distance between the two points is 78.

78 < 120 = COLLISION!

No what about say...an image?

Well then you subtract the images width from the dist

distance is 150. max distance is 120
distance - imageWidth = 96 < 120 = COLLISION!

this assumes that the image has the same width and height.

How do you check for a collision with an image that has different height and width?

How do you check for a collision base on pixels?

Fast = better

currently this is what I use

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17

public boolean collision( Vector3f other, float dist )    {             if(this.loc.dist(other) > (dist*dist) )          return false;       else          return true;    } public float dist( Vector3f other )    {          float xd = other.x - this.x;        float yd = other.y - this.y;                return (xd * xd) + (yd * yd);    }

[gbeebe]

If you already know how to tell if 2 images at given coordinates overlap, then scan the overlapping pixels in each image in that box, using Image.GetRGB().  If both overlapping pixels contain a solid color then the images have collided.  You could speed this up by making an array of 1's and 0's for each image prior to playing and checking those for collision.  I haven't done this in Java, but from my experiences in other languages, pixel perfect collision is very costly, especially if you have lots of blank pixels in your image, and many on screen images to check.  There are other shortcuts that that aren't as costly, such as bounding vectors (an array of points that outline your shape).  Do you necessarily need pixel perfect collision?

[Riven]

1   2   3   4   5   6   7

public float dist( Vector3f other )    {          float xd = other.x - this.x;        float yd = other.y - this.y;                return (xd * xd) + (yd * yd);    }

That is a very misleading method name. What you are calculating is the squared distance. Further, you take a Vector3f and ignore the z coordinate.

1   2   3   4   5   6   7   8   9   10   11   12   13

public float dist( Vector3f other )    {       return (float)Math.sqrt(this.distSquared(other));    }    public float distSquared( Vector3f other )    {         float xd = other.x - this.x;       float yd = other.y - this.y;       float zd = other.z - this.z;       return (xd * xd) + (yd * yd) + (zd * zd);    }

[Damocles]

An Idea: For pixelperfect coll-detection you could
make (pre-generate) a collision datatructure (transparent =0, nontransparent = 1), and put a row of 8 pixels into a byte.
..And use this for a bitwise comparrisson of 8 pixels at a time. This should speed up things compared to iterating though
every single pixel.

[StumpyStrust]

I originally made everything in 3D hence the vector3f but for sake of making things less complicated I only posted the 2d aspect. The Vector3f class I use is one I made. That has my own functions and all. The squared distance is required I believe because if you don't use it you lose accuracy.
I suck at math but follow math formulas to a "T" normally which in programming is not always the most efficient.

http://www.purplemath.com/modules/distform.htm

I think it is cheaper to just use the dist squared instead of calling Math.squrt
It so far works well but I don't know if it could be speed up.

And as far as 3D goes I have been using the same thing but with the z cord added in.

I also really like the idea of using bit wise functions to improve speed. Although, pixel perfect collision still would be extremely slow compared to just point to point.   

Games published by our own members! Check 'em out!

[Roquen]

Although losing the sqrt increases accuracy..that's not the point.  It's simply cheaper to compute.  Neither is the accurate way to perform this computation...but this is games, we don't care.

[StumpyStrust]

well...in my case it is very important to have the dist*dist instead of just dist. with out the dist*dist you get negative values which just are not ok.

The Math.squareroot is not necessary but the power of 2 is.

And in games the more realistic you can get them the better. Not saying game play is unimportant but if you can crank out amazing graphics with good game play then just good game play all the better.