Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (107)
games submitted by our members
Games in WIP (536)
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 3746 times)
0 Members and 1 Guest are viewing this topic.
Offline StumpyStrust
« Posted 2012-02-21 02: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.  Emo

Offline ra4king

JGO Kernel


Medals: 340
Projects: 2
Exp: 5 years


I'm the King!


« Reply #1 - Posted 2012-02-21 04: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 Tongue

Offline ReBirth
« Reply #2 - Posted 2012-02-21 05: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!
Legends of Yore - The Casual Retro Roguelike
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 746
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #3 - Posted 2012-02-21 09: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 Pointing


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
Offline ra4king

JGO Kernel


Medals: 340
Projects: 2
Exp: 5 years


I'm the King!


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

Damnit how I could I forget that Tongue

Typing code directly into forum is not good Grin

Offline StumpyStrust
« Reply #5 - Posted 2012-02-22 04: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);
   }





Offline gbeebe

Senior Member


Medals: 5
Projects: 1



« Reply #6 - Posted 2012-02-22 04: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?
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 746
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #7 - Posted 2012-02-22 12: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
Offline Damocles
« Reply #8 - Posted 2012-02-22 12: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.

Offline StumpyStrust
« Reply #9 - Posted 2012-02-22 19: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!
Legends of Yore - The Casual Retro Roguelike
Online Roquen
« Reply #10 - Posted 2012-02-22 19: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.
Offline StumpyStrust
« Reply #11 - Posted 2012-02-22 20: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.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

CogWheelz (7 views)
2014-07-30 21:08:39

Riven (20 views)
2014-07-29 18:09:19

Riven (13 views)
2014-07-29 18:08:52

Dwinin (12 views)
2014-07-29 10:59:34

E.R. Fleming (32 views)
2014-07-29 03:07:13

E.R. Fleming (12 views)
2014-07-29 03:06:25

pw (42 views)
2014-07-24 01:59:36

Riven (42 views)
2014-07-23 21:16:32

Riven (28 views)
2014-07-23 21:07:15

Riven (29 views)
2014-07-23 20:56:16
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!