Kova


«
Posted
20060423 00: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


«
Reply #1  Posted
20060423 02: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)>(xs.x)*(xs.x)+(ys.y)*(ys.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


«
Reply #2  Posted
20060423 14: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 (xj)^2 + (yk)^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




Games published by our own members! Check 'em out!


oNyx


«
Reply #3  Posted
20060423 20:28:11 » 

>For circle it's (xj)^2 + (yk)^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
20060424 04: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
20060424 11: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
20060424 12:41:15 » 

Thatis something of a workaround, 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


«
Reply #7  Posted
20060424 12:58:55 » 

>For circle it's (xj)^2 + (yk)^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


«
Reply #8  Posted
20060424 14:32:14 » 

a²+b²=c²
You need the sum of the radii squared... squaring one of em wont do the trick.




Kova


«
Reply #9  Posted
20060424 14: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. 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.




Games published by our own members! Check 'em out!


oNyx


«
Reply #10  Posted
20060424 16: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


«
Reply #11  Posted
20060424 17: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 (xx0)^2 + (yy0)^2 = r^2
for (0,0) circle: (20)^2 + (00)^2 = 2^2 4=4 ..... => passes through (2,0)
for (4,0) circle: (24)^2 + (00)^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


«
Reply #12  Posted
20060424 21: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 (xx0)^2 + (yy0)^2 = r^2
for (0,0) circle: (20)^2 + (00)^2 = 2^2 4=4 ..... => passes through (2,0)
for (4,0) circle: (24)^2 + (00)^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


«
Reply #13  Posted
20060424 22: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.




Ask_Hjorth_Larsen
Junior Member
Java games rock!


«
Reply #14  Posted
20060425 05:58:23 » 

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




oNyx


«
Reply #15  Posted
20060425 10: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


«
Reply #16  Posted
20060425 14: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


«
Reply #17  Posted
20060425 15: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 andoperation 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 09... 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


«
Reply #18  Posted
20060426 00: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 Member
aka Abuse/AbU5e/TehJumpingJawa


«
Reply #19  Posted
20060426 01: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


«
Reply #20  Posted
20060426 01: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


«
Reply #21  Posted
20060426 03: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 Member
All opinions will be lined up and shot!


«
Reply #22  Posted
20060501 20: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
20060506 07:09:29 » 





