Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (527)
Games in Android Showcase (127)
games submitted by our members
Games in WIP (594)
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  
  Awesome collision detection algorithem  (Read 4204 times)
0 Members and 1 Guest are viewing this topic.
Offline CyanPrime
« Posted 2010-11-24 04:10:03 »

Should thought I'd share this with you all, enjoy!

1  
2  
3  
4  
5  
6  
7  
8  
9  
public void moveUp(Vector<Thing> things){
         y += speed;
         
         for(int i = 0; i < things.size(); i++){
            if(new Rectangle((int) x, (int) y, width, height).intersects(new Rectangle((int) things.get(i).x, (int) things.get(i).y, things.get(i).width, things.get(i).height))){
               y += (things.get(i).y + things.get(i).height) - y;
            }
         }
      }

 
Okay, so first you move. than you check if you're hitting anything by using Rectangle.intersects(Rectangle r), than if you are you change your y to right in front of the thing by saying your movement variable (x or y) is +/- the length inside your items line is in the collided item.
Offline appel

JGO Wizard


Medals: 51
Projects: 4


I always win!


« Reply #1 - Posted 2010-11-24 08:44:48 »

I'm sorry, it's early morning here... it's a joke right?  Roll Eyes

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline kappa
« League of Dukes »

JGO Kernel


Medals: 78
Projects: 15


★★★★★


« Reply #2 - Posted 2010-11-24 09:37:30 »

Not really a tutorial is it? better place for such things is the shared code section. Secondly it doesn't look very generic or usable by others without lots of changes to it.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Matzon

JGO Knight


Medals: 19
Projects: 1


I'm gonna wring your pants!


« Reply #3 - Posted 2010-11-24 09:41:19 »

and performs *really* badly - two new's per iteration - gc hell

Offline princec

« JGO Spiffy Duke »


Medals: 425
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #4 - Posted 2010-11-24 09:55:00 »

Might be ok in JDK7 though Wink

Cas Smiley

Offline OverKill

Junior Devvie




Java games rock!


« Reply #5 - Posted 2010-11-24 10:30:41 »

1. The first new Rectangle is redundant from what I can see. You can create it once and just reuse it.
2. things.get(i) -> why not just get it once and reuse that reference? Saves the getting part.
3. Why do the things not already have the Rectangles instead of creating new ones each iteration?
Offline princec

« JGO Spiffy Duke »


Medals: 425
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #6 - Posted 2010-11-24 10:36:25 »

And while we're pulling it to bits - why use Vector instead of List?
And why call List.size() every loop iteration?

Cas Smiley

Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 834
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #7 - Posted 2010-11-24 10:39:08 »

Moved to 'shared code' as that's what it is!


I think this line is pretty redundant:
1  
y += (things.get(i).y + things.get(i).height) - y;


As you can do the same thing with:
1  
y = things.get(i).y + things.get(i).height;

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline kappa
« League of Dukes »

JGO Kernel


Medals: 78
Projects: 15


★★★★★


« Reply #8 - Posted 2010-11-24 10:44:59 »

also using all those List.get(i)'s is a bad idea, since it'll search the list for them every time the get() method is called, better to just get() the object once at the beginning of the method/loop.
Offline ryanm

Senior Devvie


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #9 - Posted 2010-11-24 11:05:44 »

also using all those List.get(i)'s is a bad idea, since it'll search the list for them every time the get() method is called, better to just get() the object once at the beginning of the method/loop.
Indexed gets are O(1) for Vectors, no searching involved. But yeah, you should still avoid method call overhead.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline appel

JGO Wizard


Medals: 51
Projects: 4


I always win!


« Reply #10 - Posted 2010-11-24 11:44:38 »

Also, I wouldn't really call this a collision detection algorithm.

You can have collision strategies, e.g. broad/narrow, and you can have collision check algorithms.

Also, Java's own classes have never deliver the desired performance for things like this. Rectangle.intersects might work, but it might be several times slower than a custom collision check method.

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline pjt33
« Reply #11 - Posted 2010-11-24 12:14:02 »

In addition to all the problems already pointed out, moving the object to "fix" a collision at i=X might cause a new collision at i=X-1, but that will never be detected.
Offline kevglass

« JGO Spiffy Duke »


Medals: 210
Projects: 24
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #12 - Posted 2010-11-24 12:15:29 »

Probably time to stop now?

Kev

Offline JL235

JGO Coder


Medals: 10



« Reply #13 - Posted 2010-11-24 14:25:37 »

I'm pretty sure I've used Java's shapes for detecting intersections, and the performance was fine (at least for a little game). I think the issues people have with them are a little overrated. java.awt shape classes might not be Box2D, but they are far from unusable.

My personal gripe is that the collision strategy is just a brute force search. This is very inefficient because it's comparing your object against everything, and if you extend that to all objects then I believe your time complexity becomes: O(n^2). If you solve this issue then you perform less collision checks, and for that reason I personally believe solving this is far more crucial then switching away from java.awt classes.

It needs to be indexed in some way so it either eliminates certain objects very quickly and only performs an intersection check on the likely candidates. One way of achieving the first suggestion is to store your objects in separate lists by class, that way if your checking a Bullet against a Unit then all non-Unit objects are automatically excluded. Then you can divide up space as a grid storing all of the units into separate collections based on what section of space they take up. This ensures my second suggestion from above because you'll only check against objects that are close to you, which you are most likely to be colliding with.

I'm sure people can find flaws with my strategy so I'm not suggesting the above as the best way to handle collisions (and it does skip over some issues) but it was at least a strategy that worked very well for me.

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #14 - Posted 2010-11-24 18:48:09 »

Yup, your algorithm is a lot like what I used in some of the first games I made in high school. It works well and is a good start. As people have pointed out, you can do lots better. One thing that'll be good to get away from immediately is using Rectangle.intersects, as it's so incredibly easy to write your own bounding box collision.

1  
2  
3  
4  
5  
6  
7  
boolean rectangleIntersects(float rect1x, float rect1y, float rect1w, float rect1h, float rect2x, float rect2y, float rect2w, float rect2h)
{
    return (rect1x + rect1w >= rect2x &&
            rect1y + rect1h >= rect2y &&
            rect1x <= rect2x + rect2w &&
            rect1y <= rect2y + rect2h);
}


It's quite easy, just 4 simple statements, and obviously this is quite fast.

My main reason for using AWT Shapes for collision, when I do, is because I can't be arsed to write my own algorithm for that shape. However, the approach is usually slow, and when it's so easy to write rect and circle collisions you might as well do them yourself. If you want to use Shape, you can start with a bounding box collision like above and then use the Shape collision for extra precision (some thing good to do anyway).

See my work:
OTC Software
Offline BoBear2681

JGO Coder


Medals: 19



« Reply #15 - Posted 2010-11-24 19:47:50 »

The actual speed of Rectangle.intersects(Rectangle) isn't actually a bottleneck though, is it?  If you were writing a game with Java2D, you could potentially use a Rectangle to store each entity's location/size.  Then using Rectangle.intersects() to determine collisions would be very fast, right (especially with no allocations)?  In that (admittedly simple) case there'd be no reason to roll your own.
Offline CyanPrime
« Reply #16 - Posted 2010-11-24 19:51:22 »

Yup, your algorithm is a lot like what I used in some of the first games I made in high school. It works well and is a good start. As people have pointed out, you can do lots better. One thing that'll be good to get away from immediately is using Rectangle.intersects, as it's so incredibly easy to write your own bounding box collision.

1  
2  
3  
4  
5  
6  
7  
boolean rectangleIntersects(float rect1x, float rect1y, float rect1w, float rect1h, float rect1x, float rect1y, float rect1w, float rect1h)
{
    return (rect1x + rect1w >= rect2x &&
            rect1y + rect1h >= rect2y &&
            rect1x <= rect2x + rect2w &&
            rect1y <= rect2y + rect2h);
}


It's quite easy, just 4 simple statements, and obviously this is quite fast.

My main reason for using AWT Shapes for collision, when I do, is because I can't be arsed to write my own algorithm for that shape. However, the approach is usually slow, and when it's so easy to write rect and circle collisions you might as well do them yourself. If you want to use Shape, you can start with a bounding box collision like above and then use the Shape collision for extra precision (some thing good to do anyway).
Oh, this one uses floats even. some reason I thought the intersects algorithm was a lot more complex.
Offline fireside

Senior Newbie





« Reply #17 - Posted 2010-11-24 21:38:27 »

Quote
boolean rectangleIntersects(float rect1x, float rect1y, float rect1w, float rect1h, float rect1x, float rect1y, float rect1w, float rect1h)

I copied and saved it because it's so simple and elegant, but it looks like some typo's up there.  There's no rect2.
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #18 - Posted 2010-11-24 21:44:10 »

I copied and saved it because it's so simple and elegant, but it looks like some typo's up there.  There's no rect2.
Thanks, I fixed that. I knew I would have a typo somewhere. Smiley

@BoBear - This is indeed a good point, Rectangle will absolutely not be the bottleneck. Still, I personally try to avoid using as many things from AWT as possible, because they tend to be slow and their implementation can be black-boxed. I work exclusively in OpenGL lately, too, so having AWT objects is kinda weird.

See my work:
OTC Software
Offline JL235

JGO Coder


Medals: 10



« Reply #19 - Posted 2010-11-25 07:32:50 »

The discussion is getting back to the bounds checking, but again I don't think this is ever the bottleneck. If you can avoid performing the check then you do less. It's that simple. So I believe the overall strategy is more important.

With a brute force approach you just won't be able to support having millions upon millions of entities!

Offline OverKill

Junior Devvie




Java games rock!


« Reply #20 - Posted 2010-11-25 08:45:14 »

Personally I have always favoured sphere collision detection above rectangular.
Less calculations and it could also be used as a rough detection first. i.e. make the sphere's diameter as large as your longest side, then if you collide, go for the detailed & calc intensive checks.
Advantage is also a sphere can work in 2d and 3d without much change.

You also have to consider how seldom 'pure' rectangular or sphere collection detections are. Chances are high you might even have to go all the way down to pixel or 3d level detection (forgot the name) to make it 'look right' anyway.

Also when your set of collide-able objects grows, you might also consider using space partitioning patterns, such as BSP, QSP or OSP.
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.

PocketCrafter7 (14 views)
2014-11-28 16:25:35

PocketCrafter7 (9 views)
2014-11-28 16:25:09

PocketCrafter7 (10 views)
2014-11-28 16:24:29

toopeicgaming1999 (76 views)
2014-11-26 15:22:04

toopeicgaming1999 (67 views)
2014-11-26 15:20:36

toopeicgaming1999 (16 views)
2014-11-26 15:20:08

SHC (30 views)
2014-11-25 12:00:59

SHC (28 views)
2014-11-25 11:53:45

Norakomi (32 views)
2014-11-25 11:26:43

Gibbo3771 (28 views)
2014-11-24 19:59:16
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

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
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!