Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (753) Games in Android Showcase (228) games submitted by our members Games in WIP (842) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Fast Collision Detection  (Read 8008 times) 0 Members and 1 Guest are viewing this topic.
StumpyStrust
 « Posted 2012-02-21 01:24:12 »

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

JGO Kernel

Medals: 507
Projects: 3
Exp: 5 years

I'm the King!

 « Reply #1 - Posted 2012-02-21 03:04:31 »

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
 « Reply #2 - Posted 2012-02-21 04:11:41 »

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.

Riven

« JGO Overlord »

Medals: 1336
Projects: 4
Exp: 16 years

 « Reply #3 - Posted 2012-02-21 08:43:27 »

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}`

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
ra4king

JGO Kernel

Medals: 507
Projects: 3
Exp: 5 years

I'm the King!

 « Reply #4 - Posted 2012-02-21 12:04:48 »

Damnit how I could I forget that

Typing code directly into forum is not good

StumpyStrust
 « Reply #5 - Posted 2012-02-22 03:40:21 »

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!

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

Senior Devvie

Medals: 5
Projects: 1

 « Reply #6 - Posted 2012-02-22 03:58:09 »

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

« JGO Overlord »

Medals: 1336
Projects: 4
Exp: 16 years

 « Reply #7 - Posted 2012-02-22 11:37:10 »

 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);   }`

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Damocles
 « Reply #8 - Posted 2012-02-22 11:49:20 »

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
 « Reply #9 - Posted 2012-02-22 18:21:59 »

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.

Roquen

JGO Kernel

Medals: 517

 « Reply #10 - Posted 2012-02-22 18:43:32 »

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
 « Reply #11 - Posted 2012-02-22 19:19:17 »

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.

Pages: [1]
 ignore  |  Print

 nelsongames (17 views) 2018-04-24 18:15:36 nelsongames (13 views) 2018-04-24 18:14:32 ivj94 (587 views) 2018-03-24 14:47:39 ivj94 (49 views) 2018-03-24 14:46:31 ivj94 (400 views) 2018-03-24 14:43:53 Solater (64 views) 2018-03-17 05:04:08 nelsongames (110 views) 2018-03-05 17:56:34 Gornova (175 views) 2018-03-02 22:15:33 buddyBro (723 views) 2018-02-28 16:59:18 buddyBro (93 views) 2018-02-28 16:45:17
 KaiHH 13x ByerN 11x Guerra2442 10x SHC 10x NuclearPixels 10x Zemlaynin 10x Damocles 6x VaTTeRGeR 5x orangepascal 4x philfrei 4x ags1 3x Spasi 3x ndnwarrior15 3x mesterh 3x JojoGlick 2x Springrbua 2x
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org