Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (777) Games in Android Showcase (231) games submitted by our members Games in WIP (856) 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 8531 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: 508
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: 1357
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: 508
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: 1357
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: 518

 « 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

 hadezbladez (288 views) 2018-11-16 13:46:03 hadezbladez (157 views) 2018-11-16 13:41:33 hadezbladez (289 views) 2018-11-16 13:35:35 hadezbladez (70 views) 2018-11-16 13:32:03 EgonOlsen (2133 views) 2018-06-10 19:43:48 EgonOlsen (2151 views) 2018-06-10 19:43:44 EgonOlsen (1363 views) 2018-06-10 19:43:20 DesertCoockie (1966 views) 2018-05-13 18:23:11 nelsongames (1599 views) 2018-04-24 18:15:36 nelsongames (2247 views) 2018-04-24 18:14:32
 KaiHH 15x LiquidNitrogen 14x Spasi 13x orange451 13x bullen 9x 65K 9x NuclearPixels 7x polinc 7x Zemlaynin 7x VaTTeRGeR 5x hadezbladez 3x ral0r2 3x CommanderKeith 2x SHC 2x berzas 1x Riven 1x
 Deployment and Packagingby mudlee2018-08-22 18:09:50Java Gaming Resourcesby gouessej2018-08-22 08:19:41Deployment and Packagingby gouessej2018-08-22 08:04:08Deployment and Packagingby gouessej2018-08-22 08:03:45Deployment and Packagingby philfrei2018-08-20 02:33:38Deployment and Packagingby philfrei2018-08-20 02:29:55Deployment and Packagingby philfrei2018-08-19 23:56:20Deployment and Packagingby philfrei2018-08-19 23:54:46
 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