Java-Gaming.org    
Featured games (91)
games approved by the League of Dukes
Games in Showcase (577)
games submitted by our members
Games in WIP (498)
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  
  Polygon collision detection  (Read 4897 times)
0 Members and 1 Guest are viewing this topic.
Offline weston

Junior Member





« Posted 2004-08-21 08: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");
}
Offline pepe

Junior Member




Nothing unreal exists


« Reply #1 - Posted 2004-08-21 09: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).

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

JGO Coder


Medals: 1


http://t-machine.org


« Reply #2 - Posted 2004-08-21 10: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...
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline pepe

Junior Member




Nothing unreal exists


« Reply #3 - Posted 2004-08-21 12: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...

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

JGO Coder


Medals: 1


http://t-machine.org


« Reply #4 - Posted 2004-08-21 13: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...
Offline Orangy Tang

JGO Kernel


Medals: 51
Projects: 11


Monkey for a head


« Reply #5 - Posted 2004-08-21 13: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. Angry

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline weston

Junior Member





« Reply #6 - Posted 2004-08-21 20: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");
}
Offline oNyx

JGO Coder


Medals: 1


pixels! :x


« Reply #7 - Posted 2004-08-21 21: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++

弾幕 ☆ @mahonnaiseblog
Offline weston

Junior Member





« Reply #8 - Posted 2004-08-21 21: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  Wink 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");
}
Offline weston

Junior Member





« Reply #9 - Posted 2004-08-21 21: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");
}
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline weston

Junior Member





« Reply #10 - Posted 2004-08-22 03: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");
}
Offline Malohkan

Senior Member




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


« Reply #11 - Posted 2004-08-22 05: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?

Admin and Game Developer at
GameLizard.com
Play Rimscape!    |    Play Conquer!
Offline weston

Junior Member





« Reply #12 - Posted 2004-08-22 05: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");
}
Offline pepe

Junior Member




Nothing unreal exists


« Reply #13 - Posted 2004-08-22 08: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 ]

Home page: http://frederic.barachant.com
------------------------------------------------------
GoSub: java2D gamechmark http://frederic.barachant.com/GoSub/GoSub.jnlp
Offline weston

Junior Member





« Reply #14 - Posted 2004-08-22 09: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");
}
Offline weston

Junior Member





« Reply #15 - Posted 2004-08-22 09: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");
}
Offline Abuse

JGO Coder


Medals: 10


falling into the abyss of reality


« Reply #16 - Posted 2004-08-22 15: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 frame
transforms[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 position
Area carArea = baseArea.createTransformedArea(transforms[i]);

// iterate over all the cars, checking for collision
for(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
     ...
   }
}
}



Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Offline kevglass

JGO Kernel


Medals: 85
Projects: 25


Coder, Trainee Pixel Artist, Game Reviewer


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

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

Kev

Offline weston

Junior Member





« Reply #18 - Posted 2004-08-22 19: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");
}
Offline weston

Junior Member





« Reply #19 - Posted 2004-09-06 22: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");
}
Offline pepe

Junior Member




Nothing unreal exists


« Reply #20 - Posted 2004-09-07 05: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)

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

Junior Member




... Boing ...


« Reply #21 - Posted 2004-09-07 09: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
Offline weston

Junior Member





« Reply #22 - Posted 2004-09-14 19: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");
}
Offline weston

Junior Member





« Reply #23 - Posted 2004-09-14 19:12:04 »

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

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

Senior Member




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


« Reply #24 - Posted 2004-09-14 21: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?

Admin and Game Developer at
GameLizard.com
Play Rimscape!    |    Play Conquer!
Offline crystalsquid

Junior Member




... Boing ...


« Reply #25 - Posted 2004-09-16 08: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
Offline weston

Junior Member





« Reply #26 - Posted 2004-09-17 02:23:39 »

Thanks for clarifying that, it is now much more useful for to me  Smiley 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 Smiley

for(int i = 1; i > 0; i++)
{
System.out.println(i+" cups of java downed");
}
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.

xsi3rr4x (23 views)
2014-04-15 18:08:23

BurntPizza (18 views)
2014-04-15 03:46:01

UprightPath (32 views)
2014-04-14 17:39:50

UprightPath (16 views)
2014-04-14 17:35:47

Porlus (32 views)
2014-04-14 15:48:38

tom_mai78101 (58 views)
2014-04-10 04:04:31

BurntPizza (116 views)
2014-04-08 23:06:04

tom_mai78101 (216 views)
2014-04-05 13:34:39

trollwarrior1 (183 views)
2014-04-04 12:06:45

CJLetsGame (190 views)
2014-04-01 02:16:10
List of Learning Resources
by Longarmx
2014-04-08 03:14:44

Good Examples
by matheus23
2014-04-05 13:51:37

Good Examples
by Grunnt
2014-04-03 15:48:46

Good Examples
by Grunnt
2014-04-03 15:48:37

Good Examples
by matheus23
2014-04-01 18:40:51

Good Examples
by matheus23
2014-04-01 18:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:22:30

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:05:20
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!