Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (499)
Games in Android Showcase (118)
games submitted by our members
Games in WIP (567)
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  
  Shapes and collision detection with them  (Read 4298 times)
0 Members and 1 Guest are viewing this topic.
Offline Kova

Senior Member





« 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  Cry 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.
Offline 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.

弾幕 ☆ @mahonnaiseblog
Offline Kova

Senior Member





« 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 Sad
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline 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.

弾幕 ☆ @mahonnaiseblog
Offline 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

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

Offline 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

Offline g666

Junior Member





« 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
Offline 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.

弾幕 ☆ @mahonnaiseblog
Offline Kova

Senior Member





« 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.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline 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):
SmileySmiley

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.

弾幕 ☆ @mahonnaiseblog
Offline Kova

Senior Member





« 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...
Offline g666

Junior Member





« 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
Offline Kova

Senior Member





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

how do you mean that dosen't prove it Huh 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.
Offline Ask_Hjorth_Larsen

Junior Member




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

弾幕 ☆ @mahonnaiseblog
Offline Kova

Senior Member





« 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.
Offline 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.

弾幕 ☆ @mahonnaiseblog
Offline Kova

Senior Member





« 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.
Offline Anon666

Junior Member




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.
Offline 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?

弾幕 ☆ @mahonnaiseblog
Offline Kova

Senior Member





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

as I said before both of us are right Smiley 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  Wink
Offline Kommi

Junior Member




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

Junior Newbie





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

This thread

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

links to a zip file

http://uk.geocities.com/olivier_rebellion/Polycolly.zip

which contains a tutorial and sample code (c/c++).

A lot of useful info in there imo
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.

Pippogeek (36 views)
2014-09-24 16:13:29

Pippogeek (29 views)
2014-09-24 16:12:22

Pippogeek (18 views)
2014-09-24 16:12:06

Grunnt (41 views)
2014-09-23 14:38:19

radar3301 (24 views)
2014-09-21 23:33:17

BurntPizza (60 views)
2014-09-21 02:42:18

BurntPizza (30 views)
2014-09-21 01:30:30

moogie (35 views)
2014-09-21 00:26:15

UprightPath (49 views)
2014-09-20 20:14:06

BurntPizza (52 views)
2014-09-19 03:14:18
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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!