Java-Gaming.org Hi !
 Featured games (91) games approved by the League of Dukes Games in Showcase (757) Games in Android Showcase (229) games submitted by our members Games in WIP (844) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Polygon collision detection  (Read 13076 times) 0 Members and 1 Guest are viewing this topic.
weston
 « Posted 2004-08-21 06:44:21 »

I'm writing an asteroids remake with convex polygons used to represent the bounds of ships, asteroids, and bullets for use with collision detection. Each of these objects also has a bounding rectangle that must intersect another object's bounding rectangle before polygon collision detection is done. The asteroids and ship must rotate and so must their bounding polygons/rectangles. I used a bit of trig to rotate the polygons, but I don't believe I will be able to use rotated Rectangle object as I don't have direct access to its x and y points so I can rotate them. To get around this I was thinking of using another Polygon to represent the bounding rectangle instead of a Rectangle object, but from what I hear Polygon collision detection isnt very efficient and I was wondering if using a 4 sided Polygon would be less efficient than a Rectangle for checking intersection. Obviously a rectangle is a polygon in math terms, but I'm not sure the differences between the objects. Also, Rectangle has a method for checking whether it intersects another Rectangle, but I lose this with Polygon and I can only check if one contains any of the points from another. so my questions are:

will using a 4 sided Polgyon object be slower for checking intersectio than a Rectangle object?

how can I use a Polygon for accurate collision detection, the only way I currently see is to go through and check if one Polygon contains any of the points from another polygon, this obviously isn't completely accurate.

what is the best way to get around this issue with the rotating Rectangle bounds, do I need to create the four sided Polygon, or is there some other way this is done?

I'm doubting this, but maybe it would be better to just do pixel detection (check if two opaque pixels overlap from the two objects being checked) after bounding box detection, not sure how I would do this with with jogl...

thanks for any help.

for(int i = 1; i > 0; i++)
System.out.println(i+" cups of java downed");
pepe

Junior Devvie

Nothing unreal exists

 « Reply #1 - Posted 2004-08-21 07:26:55 »

Don't bother.
Use java.awt.Area shapes , transform them using AffineTransforms. It's fast and easy to use. Moreover, you will not need anything else stored to make collisions.
Area to Area collision is fast (i did point in area test, which is enough for your game also, imho).

------------------------------------------------------
GoSub: java2D gamechmark http://frederic.barachant.com/GoSub/GoSub.jnlp
blahblahblahh

JGO Coder

Medals: 1

http://t-machine.org

 « Reply #2 - Posted 2004-08-21 08:58:34 »

That's not true - lots of Area stuff is extremely slow (so slow it'll make you weep).

The trick is to discover which bits are "as fast as anything you could hand-code" and which bits aren't.

But certainly do NOT blindly assume all operations will be fast. In general, point - in - Area tests are fast so long as the area is very simple. Note that if you use CSG to make a complex area then the point tests can get slow.

In fact, if you do more than one or two unions/intersections/etc of areas, then *everything* gets slow (IIRC this is because Sun's implementation stores it's data in a VERY inefficient (for algorithms) way, that I suspect they will eventually change, because it's just not possible to achieve high performance that way).

malloc will be first against the wall when the revolution comes...
pepe

Junior Devvie

Nothing unreal exists

 « Reply #3 - Posted 2004-08-21 10:47:05 »

You are right, and i think i am also.

Under the conditions i wrote, everything is fast.
Now, would CSG be fast enough or not for collision is something i FEEL like it would not be appropriate. i don't see it as the right method for that purpose but YMMV...

------------------------------------------------------
GoSub: java2D gamechmark http://frederic.barachant.com/GoSub/GoSub.jnlp
blahblahblahh

JGO Coder

Medals: 1

http://t-machine.org

 « Reply #4 - Posted 2004-08-21 11:07:07 »

Yeah, sorry, I was trying to say that whilst the conditions you outlined would usually be OK, the rest of Area etc is a dangerous area for performance.

AFAICS CSG ought to be very fast, but I think it isn't because Sun discards the information they could have used to do faster checks (which would have made their algorithms more complex but faster). Can't be sure though - it's a long time since I checked the speed of their algos.

malloc will be first against the wall when the revolution comes...
Orangy Tang

JGO Kernel

Medals: 57
Projects: 11

 « Reply #5 - Posted 2004-08-21 11:22:57 »

I think the CSG stuff splits objects up into scanlines and then does the CSG on each line. While that probably makes for a simple general case algorithm its bloody inefficiant and tends to give those annoying 1 pixel errors.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
weston
 « Reply #6 - Posted 2004-08-21 18:29:23 »

couple more questions. What is CSG?
My polygons are no more than six sided, would it be worth it to give them rectangle shaped Areas and check for a collision with these before checking Area intersection with the Areas shaped like my sprites?

for(int i = 1; i > 0; i++)
System.out.println(i+" cups of java downed");
oNyx

JGO Coder

Medals: 2

pixels! :x

 « Reply #7 - Posted 2004-08-21 19:06:11 »

>What is CSG?

Constructive Solid Geometry. That is... constructing rather complex shapes by combining shapes with logical operators like add, sub, xor...

Here is an (non java) example:
http://people.freenet.de/ki_onyx/logo.htm

>My polygons are no more than six sided[...]

Well, you can use faster algos if the polys are always convex. And if they are rather round you could use bouding circles instead.

edit: sp++

weston
 « Reply #8 - Posted 2004-08-21 19:28:35 »

they are convex, but bounding circles won't work in this case since collision detection should be near perfect in an asteroids game. At least this is what I think since close encounters with asteroids/ships/bullets etc. are part of the game   do you mean the algorithms will work more efficiently or that I can choose a different algorithm that will be more efficient?

for(int i = 1; i > 0; i++)
System.out.println(i+" cups of java downed");
weston
 « Reply #9 - Posted 2004-08-21 19:31:51 »

here is a link, just got it working on webstart:
http://www.cyntaks.com/projects/asteroids/webstart/asteroids.php the green lines show the bounds that are used for collision detection, a collision is found whenever two of the outer bounding boxes intersect because for some reason polygon.contains(x, y) is always returning true... I'm working on switching over to using Areas now though

for(int i = 1; i > 0; i++)
System.out.println(i+" cups of java downed");
weston
 « Reply #10 - Posted 2004-08-22 01:19:19 »

I'm not even using collision detection yet, but just to rotate the Areas that I will use for collision detection its using an extra 10% cpu according to task manager. Not only that but it seems like I'm having to create a objects every time through my gameloop. Here is the code I am using to rotate/translate my Areas:

Rotating/translating my ship:
 1  2  3  4  5  6  7 `public void updateBounds()  {    boundsTransform.setToRotation(Math.toRadians(-rotation), width/2, height);    bounds = originalBounds.createTransformedArea(boundsTransform);    boundsTransform.setToTranslation(x, y);    bounds = bounds.createTransformedArea(boundsTransform);  }`

rotating/translating my asteroids:
 1  2  3  4  5  6  7 `public void updateBounds()  {    boundsTransform.setToRotation(Math.toRadians(rotation), width/2, height/2);    bounds = originalBounds.createTransformedArea(boundsTransform);    boundsTransform.setToTranslation(x, y);    bounds = bounds.createTransformedArea(boundsTransform);  }`

I just want to make sure I'm not doing anything horribly wrong since it seems to be taking the majority of the processing time in my game.

for(int i = 1; i > 0; i++)
System.out.println(i+" cups of java downed");
Malohkan

Senior Devvie

while (true) System.out.println("WOO!!!!");

 « Reply #11 - Posted 2004-08-22 03:05:03 »

 1  2  3  4  5 `trans.setTransform(1, 0, 0, 1, x - width/2, y - height/2);trans.rotate(theta, width/2, height/2);Area a = new Area(rectangleBounds);a.transform(trans);`
That's all I'd do.  Any comments on my way?

GameLizard.com
Play Rimscape!    |    Play Conquer!
weston
 « Reply #12 - Posted 2004-08-22 03:22:38 »

is this meant to be something that could replace the body of my updateBounds() method? if so I don't see how you could use your Area a since it is created within the method body. Other than that I'm not sure if it would work correctly or not since I can't use half of it (creating Area a within the method body based on rectangleBounds).

Some good news, collision detection is working perfect and it didn't require any extra noticeable amount of cpu, its just rotating and translating my Areas...

for(int i = 1; i > 0; i++)
System.out.println(i+" cups of java downed");
pepe

Junior Devvie

Nothing unreal exists

 « Reply #13 - Posted 2004-08-22 06:00:40 »

i don't understand why you need to recreate your bounds each frame.

also, your jnlp does not work.
JNLPException[category: Erreur de téléchargement : Exception: java.io.FileNotFoundException: http://cyntaks.com/projects/asteroids/webstart/externalresources.php : LaunchDesc: null ]

------------------------------------------------------
GoSub: java2D gamechmark http://frederic.barachant.com/GoSub/GoSub.jnlp
weston
 « Reply #14 - Posted 2004-08-22 07:28:37 »

you must have an old jnlp cached or something cause my current jnlp has no reference to externalresources.php (that file doesn't even exist anymore). I was having troubles with webstart but they were fixed earlier today (guess thats yesterday now...) and I've been testing on a few different peoples computers with no troubles.

for(int i = 1; i > 0; i++)
System.out.println(i+" cups of java downed");
weston
 « Reply #15 - Posted 2004-08-22 07:38:19 »

I am recreating the bounds cause what I need each frame is a translated and rotated version of the original area I created. I don't know of another way to do this so its not applying the rotation/translation to the already rotated/translated Area. Heres an example of my problem: The ship needs to be rotated at 45 degrees, and I have this value stored in a variable, but I can't just tell it to rotate 45 degrees each frame or it will just spin. I am probably going about this wrong. maybe instead of changing the value of some theta variable, I could actualy rotate the ship on keypress... I was just trying to use it in the same way I do with a Graphics context in Java2D, g.rotate(theta, width/2, height/2) each time the screen is rendered.

for(int i = 1; i > 0; i++)
System.out.println(i+" cups of java downed");
Abuse

JGO Ninja

Medals: 64

falling into the abyss of reality

 « Reply #16 - Posted 2004-08-22 13:21:36 »

You are going about it the correct way - I am doing something similar in my 4KRacer game.

The smallest (in terms of code size) way of doing it is to create an Area that represents the original untransformed geometry, and, each frame create a new Area that is transformed to the objects location.

 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  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42 `//init - done just once.Area baseArea = new Area(new Rectangle(1, 0, CAR_WIDTH-2,CAR_HEIGHT));...while(running) //game loop{...// in the game loop, iterate over all cars for(int i = 0;i< NUM_PLAYERS;i++){...//create a transform to represent the cars position for this frametransforms[i] = new AffineTransform(carCos,carSin, -carSin,carCos, x-CAR_WIDTH/2*carCos+CAR_HEIGHT/2*carSin,y-CAR_WIDTH/2*carSin-CAR_HEIGHT/2*carCos);//transform the base geometry to the cars positionArea carArea = baseArea.createTransformedArea(transforms[i]);// iterate over all the cars, checking for collisionfor(int n = 0;n< NUM_PLAYERS;n++){   //oldTransforms will be null in the 1st game frame, so null check is needed   if(n==i || oldTransforms[n]==null) continue;    //oldTransforms are the transforms from the previous game frame(or from this game frame if n < i)   Area intersection = baseArea.createTransformedArea(oldTransforms[n]);   //calculate the intersection between the 2 objects bounding Areas   intersection.intersect(carArea);       //if the intersection is not empty, a collision has occured.   if(!intersection.isEmpty())   {      //collision has occured      ...   }}}`

kevglass

« JGO Spiffy Duke »

Medals: 319
Projects: 25
Exp: 22 years

Coder, Trainee Pixel Artist, Game Reviewer

 « Reply #17 - Posted 2004-08-22 13:31:55 »

Yep, thats what I'm doing for Gravity Battle also. Seems to work out quite nicely.

Kev

weston
 « Reply #18 - Posted 2004-08-22 17:07:33 »

Ok, stuff seems to be working pretty well now so thanks for all the help guys.

for(int i = 1; i > 0; i++)
System.out.println(i+" cups of java downed");
weston
 « Reply #19 - Posted 2004-09-06 20:55:19 »

For anyone who is curios I did come up with a way to improve performance (a lot). Its actualy quite simple, I just don't call my updateBounds() method every frame now. I keep a loop counter and only call the method when loopCounter%5 == 0, this has had an unbelievable effect on performance. Before I did this I tried 50 rotating asteroids on screen at a time and it was very slow. I just tried 100 on screen rotating with no slowdown at all. Rotating my collision bounds doesnt even take a noticeable amount of cpu when I have a sane number of asteroids on screen now. It would probably be better to call updateBounds() after a certain period of time instead of every 5 times through the loop, I may switch to this. I should also say that I've switched between both modes (calling updateBounds() every frame and every fifth frame), and there is absolutely no visual difference.

edit: typos

for(int i = 1; i > 0; i++)
System.out.println(i+" cups of java downed");
pepe

Junior Devvie

Nothing unreal exists

 « Reply #20 - Posted 2004-09-07 03:01:29 »

Quote
I am recreating the bounds cause what I need each frame is a translated and rotated version of the original area I created. I don't know of another way to do this so its not applying the rotation/translation to the already rotated/translated Area. Heres an example of my problem: The ship needs to be rotated at 45 degrees, and I have this value stored in a variable, but I can't just tell it to rotate 45 degrees each frame or it will just spin. I am probably going about this wrong. maybe instead of changing the value of some theta variable, I could actualy rotate the ship on keypress... I was just trying to use it in the same way I do with a Graphics context in Java2D, g.rotate(theta, width/2, height/2) each time the screen is rendered.

In GoSub, each of my bounds are transformed back to original rotation each frame using
 1  2  3  4  5  6  7  8 `            try            {// resetting shape to its normal state, so next transform is not added to the current...                  ((java.awt.geom.Area)collisionShape).transform( transform.createInverse() );            }            catch ( java.awt.geom.NoninvertibleTransformException e )            {                  e.printStackTrace();            }`

It also creates an object, but it is immediatly collectable and never gets out of first generation, so is cheap. Your duplicate objects survive for too long to be interesting for Generational GC, which might be your problem, imho.

(in the code, 'transform' is the AffineTransform that is applied to that bound)

------------------------------------------------------
GoSub: java2D gamechmark http://frederic.barachant.com/GoSub/GoSub.jnlp
crystalsquid

Junior Devvie

... Boing ...

 « Reply #21 - Posted 2004-09-07 07:43:01 »

Another optimisation you can try:
Generate a check-circle (sphere in 3D), by simply taking the distance of the furthest poly point from the centre of rotation. On each frame, test if any circles overlap (very simple - just take the distance squared between the centre points, and compare against the sum of the radii squared (this avoids the square root):

 1  2  3  4  5  6 `float dist = (obj1.x - obj2.x)*(obj1.x - obj2.x) + (obj1.y - obj2.y)*(obj1.y - obj2.y);float minDist = (obj1.radius + obj2.radius) * (obj1.radius + obj2.radius);if( dist <= minDist ){// Potential collision - rotate the poly bounds and do the full test...}`

Doing this means you only ever rotate the bounds when they might be needed.

- Dom
weston
 « Reply #22 - Posted 2004-09-14 17:09:16 »

with alot of the shapes I'm using, a circle would not be very good for colllision bounds. Some of the shaps could have 3:1 length to width ratio so this would drop accuracy a bit more than I would like to.

for(int i = 1; i > 0; i++)
System.out.println(i+" cups of java downed");
weston
 « Reply #23 - Posted 2004-09-14 17:12:04 »

pepe: I'll give that a try although performance is good now

for(int i = 1; i > 0; i++)
System.out.println(i+" cups of java downed");
Malohkan

Senior Devvie

while (true) System.out.println("WOO!!!!");

 « Reply #24 - Posted 2004-09-14 19:31:12 »

I only use one AffineTransform object for my whole game.  When I want to use it I use:
 1  2 `trans.setToTransform(scaleX, scaleY, 0, 0, x, y);trans.rotate(radians, centerX, centerY);`
then use it.  Is this bad?

GameLizard.com
Play Rimscape!    |    Play Conquer!
crystalsquid

Junior Devvie

... Boing ...

 « Reply #25 - Posted 2004-09-16 06:57:35 »

Quote
with alot of the shapes I'm using, a circle would not be very good for colllision bounds. Some of the shaps could have 3:1 length to width ratio so this would drop accuracy a bit more than I would like to.

You don't need to use it for the actual test - its a 1st pass rejection test that can very quickly eliminate 99% of cases. If the circle test passes, you then do the full test to see if a collision really occurs.

This is integrated with the rotating bounds like so:
Store the frame count that the rotated bound was calculated.
Use circle tests - if a circle test says a collision may have occured and the last update to the area was >5 frames, then rotate the area. Then do the full collision test as normal.

This sort of technique is well used in professional games - a nested hierarchy of succesively better collision areas. The first one to check is always the sphere/circle test because it is by far the fastest test to do.

- Dom
weston
 « Reply #26 - Posted 2004-09-17 00:23:39 »

Thanks for clarifying that, it is now much more useful for to me   I see what you mean when you said: "Doing this means you only ever rotate the bounds when they might be needed. ", I never thought about it that way, but it makes sense, just rotate the collision bounds once you have found that there is a possible collision. There is still so much that I have to learn

for(int i = 1; i > 0; i++)
System.out.println(i+" cups of java downed");
Pages: [1]
 ignore  |  Print

 EgonOlsen (73 views) 2018-06-10 19:43:48 EgonOlsen (54 views) 2018-06-10 19:43:44 EgonOlsen (73 views) 2018-06-10 19:43:20 DesertCoockie (253 views) 2018-05-13 18:23:11 nelsongames (154 views) 2018-04-24 18:15:36 nelsongames (154 views) 2018-04-24 18:14:32 ivj94 (895 views) 2018-03-24 14:47:39 ivj94 (156 views) 2018-03-24 14:46:31 ivj94 (808 views) 2018-03-24 14:43:53 Solater (172 views) 2018-03-17 05:04:08
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 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