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
 Shapes and collision detection with them  (Read 7995 times) 0 Members and 1 Guest are viewing this topic.
Kova

Senior Devvie

 « Posted 2006-04-22 22:33:24 »

Hello.
So far I used simple x and y based formulas to calculate collision detection between 2 players. Today I wanted to get rid of that (improve it) and I added eclipse around every player and circle around ball using Ellipse2D.Float. When I was done I though collision part would be piece of cake since I just need to check if 2 Shapes intersect, but to my suprise there aren't any methodes to do that  Why?? Only thing I saw is checking if there's some Point2D or a Rectangle intersections... Why not between two Shapes? Can someone explain / say a hint to me how precise collision is done if not this way? Thank you.
oNyx

JGO Coder

Medals: 2

pixels! :x

 « Reply #1 - Posted 2006-04-23 00:01:54 »

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27 `public class Sphere{   public float x;   public float y;   public float r;   Sphere(){      this.x=0;      this.y=0;      this.r=0;   }   Sphere(float x, float y, float r){      this.x=x;      this.y=y;      this.r=r;   }   public void translate(float x, float y){      this.x+=x;      this.y+=y;   }   public void setLocation(float x, float y){      this.x=x;      this.y=y;   }   public boolean intersects(Sphere s){      return (r+s.r)*(r+s.r)>(x-s.x)*(x-s.x)+(y-s.y)*(y-s.y);   }[...]}`

Its easy enough (and damn fast). Ellipses look complicated tho... I also think that I never heard that someone used ellipses for collision detection in a game.

Kova

Senior Devvie

 « Reply #2 - Posted 2006-04-23 12:24:47 »

Ellipse better covers my player since it's a topographic view (from above) and you can only see (except details) head and 2 shoulders.
Ellipses aren't more or less complicated since there's a math formula for them also. For circle it's (x-j)^2 + (y-k)^2 = r^2 where (j,k) are coordinates of center of circle and r is radius. For oval it's the same, just test for less then equal instead of just equal. Equation for ellipse is x^2/a^2 + y^2/b^2 = 1 .

btw. your class Sphere is named incorrect, sphere is 3 dimensional object (like cube). You should name it Oval or something. Also formula just test for "is less then", you should test for equal also to check if oval's borders (circle) intersect.

Anyway thank you very much for this, I never though about implementing my ellipse.

Edit: my bad call, it will have to be ovals anyway... I rotate players and I can't rotate ellipse
oNyx

JGO Coder

Medals: 2

pixels! :x

 « Reply #3 - Posted 2006-04-23 18:28:11 »

>For circle it's (x-j)^2 + (y-k)^2 = r^2 where (j,k) are coordinates of center of circle and r is radius.

That formula is wrong. There is only one r on the right side.

And that ellipse vs ellipse condition thingy also doesnt look right, but I googled something up...

http://mathforum.org/library/drmath/view/66877.html

(As I guessed... its more complicated)

>your class Sphere is named incorrect

I dont really care. I cant be arsed to use different terms for 2d and 3d or write things like Plane2D or Plane3D.

>Also formula just test for "is less then", you should test for equal also to check if oval's borders (circle) intersect.

It doesnt really make a difference (because its a highly unlikely special case), but I disagree anyways. If they are only "touching" (=infinifite small distance) they arent intersecting and there is no collision.

CommanderKeith
 « Reply #4 - Posted 2006-04-24 02:54:41 »

I had the same problem, the J2D shape classes are really deficient.  Not only is there no Shape.intersects(Shape) method, you can't even extend the GeneralPath etc  classes to make your own (they're final).  To get at the underlying points you need to create new objects all the time (GeneralPathIterators, the actual float coords are locked up in private/protected fields) which causes massive GC problems.

Using bounding circles is good but to test for actual intersections I made my own Polygon class that tests for bounding circle intersection and if that's true, tests each line on each line of the other Polygon.  It works very fast, maybe u should consider the same thing.

Keith

dishmoth
 « Reply #5 - Posted 2006-04-24 09:24:29 »

You can always use the Area class (java.awt.geom.Area) instead of the Shape class.  That provides an intersect() function (the overlap between two Area objects), and you can construct Area objects directly from Shape objects if you want to.

If you're worried about the overhead of creating lots of new objects, then do a coarse collision check using bounding boxes or bounding circles first, and if a collision looks possible then do a finer check by creating and intersecting two Area objects.

CommanderKeith
 « Reply #6 - Posted 2006-04-24 10:41:15 »

Thatis something of a work-around, but Area's instance method public void intersect(Area rhs) doesn't return a boolean , it modifies 'this' Area >> not ideal.

When I had this problem the custom Polygon class seemed the best way to go.  If you implement Shape you can do Graphics2D.draw(theShape).  It is backed by an array of Point2D.Floats.  The only draw back I've found is that by having methods like translate and rotate which modify the actual points, rounding errors skew the shapes slightly (the way around this would be to use AffineTransforms, but that looked a little tricky)

Keith

g666

Junior Devvie

 « Reply #7 - Posted 2006-04-24 10:58:55 »

>For circle it's (x-j)^2 + (y-k)^2 = r^2 where (j,k) are coordinates of center of circle and r is radius.

That formula is wrong. There is only one r on the right side.

er no its not. n^2 means n to the power of 2.

Anyway, how about using multiple spheres for collision? Then they can be rotated cheaply and simply.

desperately seeking sanity
oNyx

JGO Coder

Medals: 2

pixels! :x

 « Reply #8 - Posted 2006-04-24 12:32:14 »

a²+b²=c²

You need the sum of the radii squared... squaring one of em wont do the trick.

Kova

Senior Devvie

 « Reply #9 - Posted 2006-04-24 12:54:43 »

don't know what you meant with your last post, but formulas I wrote are fine....

About ellipses, yes they are complicated but it depens what do you mean by that really... as I understood it comes to quintic (?) (4) equasion, which has formula for solving and computer can solve it in a blink, so I don't think it's complicated in that term. If it was for million calculations instead of my few it would matter. Only thing is I don't know if there are formulas when sphere is rotated around it's center.

Quote from: oNyx
It doesnt really make a difference (because its a highly unlikely special case), but I disagree anyways. If they are only "touching" (=infinifite small distance) they arent intersecting and there is no collision.

You're right it wont matter, but they aren't just touching, their borders are intersecting (one over another) and I like to be precise whenever I can.

I gave up on multiple ovals becouse as my player rotates I would, assuming I'm using 3 ovals for detection on single player,  need to move right and left oval up / down for them to stay on player shoulders. Oval in center won't matter since it's at player's head and always in center. I didn't quite get your polligons CommanderKeith, I'll think about it and maybe I'll implement them when I figure them out.
oNyx

JGO Coder

Medals: 2

pixels! :x

 « Reply #10 - Posted 2006-04-24 14:10:38 »

>You're right it wont matter, but they aren't just touching, their borders are intersecting (one over another) and I
>like to be precise whenever I can.

Uhm... no. They are just "touching". You can zoom in for all eternity but you would never see an intersection. (If the floating point numbers were that accurate heh)

Say you have one at 0/0 with a radius of 2 and one at 4/0 and also with a radius of 2. They arent intersecting at all. Its like putting two images next to each other... like this two smilies (they have a radius of 7.5 the distance from the centers is 15):

They arent intersecting, are they?

Keep in mind that the borders of a circle are infinifitely thin. Its zero... really. Its just a boundary and stuff is either inside or not. If you use some image to represent the circle all pixels should be within that border. Eg for a circle with a radius of 20 your image would be 40x40 pixels. This is real precision.

If its still hard to grasp... imagine there are two pixels next to each other... they dont intersect, do they? Or two rectangles next to each other... there is no intersection. They are only next to each other no matter how closely you look.

And this is why I check if the squared distance is smaller than the squared sum of the radii.

Kova

Senior Devvie

 « Reply #11 - Posted 2006-04-24 15:18:13 »

ok let's use (0,0) and (4,0) with radius 2 as you suggested. Let's test if they both pass through same point (2,0).

from formula (x-x0)^2 + (y-y0)^2 = r^2

for (0,0) circle:
(2-0)^2 + (0-0)^2 = 2^2
4=4  ..... => passes through (2,0)

for (4,0) circle:
(2-4)^2 + (0-0)^2 = 2^2
4=4 ...... => passes through (2,0)

=> both circles pass exactly through (2,0), no matter how small they are they will pass through same point (you can think of point as infinately small also), therefore they must intersect in (2,0).

your smiley example isn't good couse coords for drawing are moved when drawing next one...
g666

Junior Devvie

 « Reply #12 - Posted 2006-04-24 19:03:49 »

ok let's use (0,0) and (4,0) with radius 2 as you suggested. Let's test if they both pass through same point (2,0).

from formula (x-x0)^2 + (y-y0)^2 = r^2

for (0,0) circle:
(2-0)^2 + (0-0)^2 = 2^2
4=4  ..... => passes through (2,0)

for (4,0) circle:
(2-4)^2 + (0-0)^2 = 2^2
4=4 ...... => passes through (2,0)

=> both circles pass exactly through (2,0), no matter how small they are they will pass through same point (you can think of point as infinately small also), therefore they must intersect in (2,0).

your smiley example isn't good couse coords for drawing are moved when drawing next one...

but: the cirlce eqn doesnt state that any values satisfiying it are in the cirlce, it states that they lie on the edge, so the point (2, 0) lies on the edge of both circles which doesnt prove that they intesect.

desperately seeking sanity
Kova

Senior Devvie

 « Reply #13 - Posted 2006-04-24 20:02:18 »

how do you mean that dosen't prove it both lines pass through same point, that's intersection. Intersection is by definition set with elements common from set A and set B, but not just from A or just from B. It's lik && logical operator, both conditions must be satisfied. Sorry for my english, but I don't know mathematical terms very well.

Junior Devvie

Java games rock!

 « Reply #14 - Posted 2006-04-25 03:58:23 »

It's just a matter of whether you are talking about open or closed sets. It's a triviality.
oNyx

JGO Coder

Medals: 2

pixels! :x

 « Reply #15 - Posted 2006-04-25 08:45:00 »

There is no point in circle A which is also contained in circle B. Therefore there is no intersection.

And the smilie example was just fine. By your definition they are intersecting, but they arent.

Kova

Senior Devvie

 « Reply #16 - Posted 2006-04-25 12:43:03 »

I agree with Larsen that it's matter of open or close sets, but I clearly said radius of circle was 2 (natural number, integer ...not near 2) so it's including set.

There is no point in circle A which is also contained in circle B. Therefore there is no intersection.

And the smilie example was just fine. By your definition they are intersecting, but they arent.

What is your comment to my post earlier where I have proven that they have a point (2,0) together? It's small but it's there.
The problem here is that I'm thinking of precise mathematics, while you about computer implemantation. Smileys won't intersect couse there's no smaller unit then pixel and therefore you can't precisely determine the center. Anyway both of us are right, it's just perspective, no reason to discuss futher.
Thank you all for helping with collision theory.
oNyx

JGO Coder

Medals: 2

pixels! :x

 « Reply #17 - Posted 2006-04-25 13:15:42 »

The one on the left goes to the left side of the barrier and the one on the right goes to the right side of the barrier. If you do a boolean and-operation with these two circles you end up with nothing, because they dont intersect.

What you have proven is that the point 2/0 lies on the edge of both circles.

Its like pixel boundaries. If two rects are next to each other they arent intersecting, but if you use your logic they do. Like a 10 px line goes from 0-9... a total of 10 pixels starting at pixle 0's left side (or pixel -1's right side) and ending at pixel 9's right side (or pixel 10's left side). Using something different for circles is just inconsistent. If you fail to see that... well, thats your problem not mine.

Kova

Senior Devvie

 « Reply #18 - Posted 2006-04-25 22:49:45 »

well i still say they intersect, another example:
set of numbers [1..5] and [5..10] ... their intersection is 5, you can't say it's not 5 and that  it's close to border... it's 5. Analogly circle from x axis [-2..2] and circle [2..6] intersect in x coords 2.
Anon666

Junior Devvie

aka Abuse/AbU5e/TehJumpingJawa

 « Reply #19 - Posted 2006-04-25 23:21:42 »

By that logic, a shape with an area of zero can still intersect another shape.

While it is a perfectly valid system, that would work, there is no disputing it is unconventional.
As typically a shape that has an area of zero cannot contain, or intersect any another shape.
oNyx

JGO Coder

Medals: 2

pixels! :x

 « Reply #20 - Posted 2006-04-25 23:28:31 »

@Kova

Ok. A circle with a radius of 10. How big would your image be? 20x20 pixels?

If you put two of those next to each other they arent intersecting, are they?

Kova

Senior Devvie

 « Reply #21 - Posted 2006-04-26 01:07:42 »

as I said before both of us are right yes they do not intersect in terms of pixels, but also where's the center of that circle? you can't say it's between 10th and 11th pixel since there's no such thing if you stick to the story 2 smileys aren't intersecting.
I must say the things we're talking about are quite abstract and fictional, so it's all about perspective. I enjoyed the discussion never the less, a brain teaser
Kommi

Junior Devvie

All opinions will be lined up and shot!

 « Reply #22 - Posted 2006-05-01 18:12:09 »

Humm seems like a good place for my question. Lets say i wanted to do collision detection of a 2d polygon vs a rectangle (think Baldur's Gate if that means anything to anyone). What would be the best way of implementing that? do I declare my own polygon and then check to see if my rectangle intersects it anywhere? Or should I write my own based on techniques such as "decompisition through triangle coverings" <-- googled a paper about that, dont know what it is yet.

Kommi
sloppyjoe

Junior Newbie

 « Reply #23 - Posted 2006-05-06 05:09:29 »

http://www.gamedev.net/community/forums/topic.asp?topic_id=251638