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.
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.
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 b^2 + (y-k)^2 = r^2[/b] 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 
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.
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
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.
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
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.
a²+b²=c²
You need the sum of the radii squared… squaring one of em wont do the trick.
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.
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.
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.
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.
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.
It’s just a matter of whether you are talking about open or closed sets. It’s a triviality.
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.
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.
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.
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.
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.
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.