Rotational Collsion Detection

Java 2D
#1

I am working on a game in Android and I currently have pixel perfect collision detection working. It first checks bounding boxes and if that returns true then checks the overlap of pixels. All works great except when I rotate my image. The collision detection is still using the old un-rotated 2d pixel array. So my question is how I should go about rotating the indexes of the pixels to match that of the current rotation of the image?

Thanks in advance, I find this subject very interesting to work on!

#2

Ask your self a question do you really need pixel perfect collision detection. Actual device screen is usually so small that its just not worth it. Pixel perfect collision detection is performance is really bad and the gains are usually neglible. Just compose your game objects from primitives: circles, rectangles, maybe even polygons. Then math is lot more robust and more performant.
Also keep in mind that there is ton of difference size screens in Android scene. How you deal with that if your game logic is based on pixels? What happen when you want animated characters? Do collision events based on current animation state and cause jerky movement.

I desing all my game sizes on meters, this is just lot more natural and work perfectly well on every screen size and every scenario. If I decide that I need more accurate graphics and I double all picture sizes that do not cause any changes on logic layer.

#3

I do realize that the collision detection like this is going to hinder the performance a bit. But it only needs to occur if there is a bounding box collision so I really don’t think that it will be that bad. And I have seen many android games that have implemented it and it works/looks great. I currently am not worried about animated sprites at all, that will be next.

Currently my game has some collisions that do not look good at all because it is not pixel perfect. I don’t necessarily need it on all of the images either. Just one because it has a pointy edge with a lot of transparent pixels around it. It is quite obvious when a collision occurs that shouldn’t.

I appreciate your thoughts @pitbuller I need to keep a lot of things in mind when doing this for sure.

#4

How are you rendering the rotated images? In particular:

  1. Are you using anti-aliasing? If so, you’re going to need to define how pixel-perfect collision should work…
  2. Is the angle quantised?
  3. Do you pre-render anything to a back-buffer? If not, is the memory vs performance tradeoff the reason why not?
#5

I am not using any anti-aliasing to do the rendering. When I display an image on screen it is using the Android Bitmap object(which is very similar to the standard Image class when doing Java Graphics). The rendering is done via a Canvas object which in turn is basically the same as the Graphics2D class in standard Java Graphics. I am not doing anything other than calling a draw method on the Bitmap object via the Canvas. I currently have a 2D array of pixels that I retrieved from the Bitmap and what I am looking to do is as the image is rotated, I need to rotate the pixels in the 2D array to match the specific rotation.

I don’t know if this helps at all. What do you mean by “Is the angle quantised?” Thanks! I appreciate your thoughts on this!

#6

Just read pixel, if its opaque add transformation to that coordinate(local texture coordinate) and then check sprite position + transformed pixel against geometry that you want.

Still I disagree the need of pixel perfect collision detection. Pixel perfect collision just means that you divide your object to size*size number of rects and bruteforce all possible collisions. Non naive implementation would use just as many rectangles that are needed for accurate collision detection. Bounding boxes are your friend learn to use them right.
Pixel perfect collision might work good enough for object vs static objects and only when you don’t need collision forces but it’s just not scalable or offers anything that would not be possile with other means.

I personally use Auriel Ribbon’s box2d editor. http://code.google.com/p/box2d-editor/
I take my game object image and draw outlines and rest is magic. I would suggest you to think something similar in future.

#7

@pitbuller I think you have missed the point on your comment. I know what I need for my game. I am using bounding box collision to detect a collision and from there on out I only brute force the overlapping rects created by the bounding boxes until there is a pixel overlap at the same x and y coordinate. I have that fine. I was hoping to get some help to understand how to transform a 2D array by a certain value of degrees. Whether it be an Android solution or not. It is a necessity that I implement this in my game and I need it to be perfect for the game to be played properly. More importantly I am very interested in learning how to do this and also the math behind it.

#8

I allready gave an answer how to do it.

[quote]Just read pixel, if its opaque add transformation to that coordinate(local texture coordinate) and then check sprite position + transformed pixel against geometry that you want.
[/quote]

#9

Oh thanks that really explains it well. Glad I know how to do it now. lol

#10

I have a friend who made a game engine in Delphi and the other day he showed me how he deals with this type of collisions:

On every frame he calculates a “bounding polygon” of the sprite and uses it as a sort of bounding box, checking if it overlaps with other sprites. The result was amazingly precise… You don’t have to make a perfect silouette of the sprite for the sake of performance, but calculating the relevant points that cover the current frame and joining them would be enough. Maybe on Android it’s too much calculation per frame, I don’t know, but you could try that approach.

#11

Rectangles and circles are good enough.