Awesome collision detection algorithem

Shared Code
#1

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


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.

#2

I’m sorry, it’s early morning here… it’s a joke right? ::slight_smile:

#3

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.

#4

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

#5

Might be ok in JDK7 though :wink:

Cas :slight_smile:

#6
  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?
#7

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

Cas :slight_smile:

#8

Moved to ‘shared code’ as that’s what it is!

I think this line is pretty redundant:

y += (things.get(i).y + things.get(i).height) - y;

As you can do the same thing with:

y = things.get(i).y + things.get(i).height;
#9

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.

#10

Indexed gets are O(1) for Vectors, no searching involved. But yeah, you should still avoid method call overhead.

#11

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.

#12

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.

#13

Probably time to stop now?

Kev

#14

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.

#15

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.


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

#16

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.

#17

Oh, this one uses floats even. some reason I thought the intersects algorithm was a lot more complex.

#18

[quote]boolean rectangleIntersects(float rect1x, float rect1y, float rect1w, float rect1h, float rect1x, float rect1y, float rect1w, float rect1h)
[/quote]
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.

#19

Thanks, I fixed that. I knew I would have a typo somewhere. :slight_smile:

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

#20

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!