Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (565) Games in Android Showcase (152) games submitted by our members Games in WIP (607) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
 Home Help Search Login Register
Pages: [1]
 ignore  |  Print
 Fast Collision Detection  (Read 4171 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: 367
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.

 Games published by our own members! Check 'em out!
Riven
« League of Dukes »

« JGO Overlord »

Medals: 948
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: 367
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!

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

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
« League of Dukes »

« JGO Overlord »

Medals: 948
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.

 Games published by our own members! Check 'em out!
Roquen
 « 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

You cannot reply to this message, because it is very, very old.

 Riven (11 views) 2015-04-01 18:27:05 ags1 (27 views) 2015-03-31 10:55:12 theagentd (13 views) 2015-03-27 23:08:20 wxwsk8er (54 views) 2015-03-20 15:39:46 Fairy Tailz (48 views) 2015-03-15 21:52:20 Olo (29 views) 2015-03-13 17:51:59 Olo (33 views) 2015-03-13 17:50:51 Olo (40 views) 2015-03-13 17:50:16 Olo (44 views) 2015-03-13 17:47:07 ClaasJG (61 views) 2015-03-10 11:36:42
 BurntPizza 21x LiquidNitrogen 21x KevinWorkman 18x EgonOlsen 17x theagentd 16x basil_ 16x Roquen 15x Varkas 12x wessles 11x 65K 11x Riven 9x Rayvolution 9x phu004 8x SHC 8x princec 8x Ashedragon 8x
 How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27
 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