Collision Detection in Android

Question

2.00/5 (1 vote)

See more:

Hi,

Am to trying to implement pixel perfect collision detection in android. I have came
across some articles about this pixel perfect detection but am unable to implement them practically. Actually what am doing is: taking 2 bitmap's pixels into arrays. And then trying to take pixels in overlap region. But am confused about how to get pixels of that overLap section. Can any one provide some help on this.

Am having 2 image objects which are bounded by rectangles. Those two image objects are animated.I want to change
some state when those two image objects are collided. This is the code am trying.

public static boolean detectCollision(Ball ball,Sprite bat,int currentFrame)
    {
    	try
    	{
    	int left1,left2,top1,top2,right1,right2,bottom1,bottom2;
    	
    	left1=ball.ballLeft;
        top1=ball.ballTop;
        right1=ball.ballRight;
        bottom1=ball.ballBottom;
        left2=bat.batLeft;
        top2=bat.batTop;
        right2=bat.batRight;
        bottom2=bat.batBottom;
        
        if(bottom1<top2)>
        	return false;
        if(right1 < left2)
        	return false;
        if (top1 > bottom2)
            return false;
        if (left1 > right2)
            return false;
        
        int overLap_left,overLap_top,overLap_right,overLap_bottom;
        
        overLap_left=Math.max(left1,left2);
        overLap_top= Math.min(top1, top2);
        overLap_right=Math.max(right1, right2);
        overLap_bottom=Math.min(bottom1, bottom2);
        
        if (overLap_right <= overLap_left || overLap_bottom <= overLap_right) {
    		return false;
    	}

        
        int width,height;
        //Width and Height of the overlapping Section
        width=overLap_right-overLap_left;
        height=overLap_bottom-overLap_top;
        
        
        
        //Copying bitmap pixels to arrays
        
        Bitmap bmp1=((BitmapDrawable) ResourceCollection.ballCollection.get(currentFrame).getCurrent()).getBitmap();
        Bitmap batImage=((BitmapDrawable) ResourceCollection.batCollection.get(0).getCurrent()).getBitmap();
        
        int[] pixels1 = new int[bmp1.getWidth()*bmp1.getHeight()];
        int[] pixels2 = new int[batImage.getWidth()*batImage.getHeight()];
     
        bmp1.getPixels(pixels1, 0, bmp1.getWidth(), 0,0, bmp1.getWidth()-1, bmp1.getHeight()-1);
        batImage.getPixels(pixels2, 0, batImage.getWidth(),0,0, batImage.getWidth()-1, batImage.getHeight()-1);

        
        	for(int X=overLap_left;X<overlap_right;x++)>
        	{
        		for(int Y=overLap_top;Y<overlap_bottom;y++)>
                        {
        		        		
            	       int x;
                       if (X >XandY.X)
                          x = X - XandY.X;
                       else
                          x =  XandY.X - X;

                      int y;
                        if (Y > XandY.Y)
                           y = Y - (int) XandY.Y;
                        else
                           y =  XandY.Y - Y;
        		
                if(x>=bmp1.getWidth() || y>=bmp1.getHeight())
                	return false;
                if(x>=batImage.getWidth() || y>=batImage.getHeight())
                	return false;
                
                
                int a=bmp1.getPixel(x, y);
                int b=batImage.getPixel(x, y); //But these statements are not working as expected (showing collision 
//even if the two images are not collided(not touched each other) visually) 
                
                                
                if (a != 0 && b != 0) // If both colors are not transparent (the alpha channel is not 0), then there is a collision
                {
                    return true;
                }

        		
        	}
        }
        
return false;
    	}
    	catch(Exception ee)
    	{
    		String msg=ee.getMessage();
    		Log.v("Error", ee.getMessage());
    		return false;
    	}

How can i check that the two images are touched each other in the Intersection rectangle(Overlapping region).?

Posted 22-Aug-11 23:05pm

YashwanthBathini

Updated 23-Aug-11 3:36am

v3

Add a Solution

Comments

Sergey Alexandrovich Kryukov 23-Aug-11 8:03am

Please describe what's a collision and the whole problem.
--SA

_Zorro_ 23-Aug-11 8:13am

I thinks he might be talking about this: http://en.wikipedia.org/wiki/Collision_detection

I agree, the question is not clear enough though.

YashwanthBathini 23-Aug-11 9:42am

Am trying to implement this idea for collision detection. Can you share some code regarding these steps.

* Convert two checked objects coordinate into world coordinate
* Get their bounding box, check for intersection
* if intersection occurs, check every pixel from both objects inside the intersection
* if both objects have non-alpha pixels in the same location inside the intersection, then collision is confirmed.

[no name] 23-Aug-11 9:48am

Oh, it's clear enough. He wants to implement sprites with a good collision detection. No simple testing of bounding boxes, circles or polygons. Instead he wants to detect wether one or more pixels of the sprites overlap or not. There are quite a few ways to accomplish this, but none can be explained in just a few sentences and it also depends a little on what he has already.

Sergey Alexandrovich Kryukov 23-Aug-11 10:12am

Sure, I understand. Thank you very much for clarification.
I'm familiar with the problem and agree -- this is not to be explained in brief. Could be a big solid chapter in a big solid book.
I also know all engines use different kinds of simplifications. I've read that in Second Life, if one designs a pitcher with a handle, it would not be possible to shoot an arrow in the hole between the handle and the pitcher body -- it will be a collision. Good collision handling is never easy...
--SA

[no name] 23-Aug-11 14:00pm

Especially in 3D where comparing pixels is no longer an option. The simplest approach are bounding boxes which are simple and fast to test, but inaccurate. Absolutely accurate but slow would be to intersect every polygon of the first object with every polygon of the second. Each intersection would involve finding a solution to a set of equations derived from the planar equations of the polygons. If there is a solution and it is within the bounds of both involved polygons, then we have a collision.

But the most important thing is to sort out quickly which objects need to be tested for collisions and which not. It's still wasteful to simply test all combinations. Sorting graphics objects in (spatial) tree structures has proven itself to be very efficient for this and some other problems as well.

Sergey Alexandrovich Kryukov 23-Aug-11 10:12am

Thank you for a good link. Sure, it looks like it's the thing.
--SA

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

TheyCallMeMrJames · Answer 1 · 2011-08-23T04:14:00

Solution 1

I'll try to be brief, but if you have more questions you can post them ;)

First, before I alter sprite animation indexes, I would usually do the math to compute if a collision would have occurred between frames. This is way faster than loading/rotating/altering sprites and you don't want to have to unroll those changes if you care about framerate.

Once you've got this in place, the first thing to do is to get the intersecting region using createIntersection[^]. This will give you another Rectangle2D with the overlap area.

From there, it's the comparison. It looks like you've got a start on that, so the only thing left to do is simplify how to capture that intersection.

During the comparison, you'll walk over the area contained within the intersection only. Pass the intersection rect into the getpixels method to see the pixels you care about.

Cheers.

Posted 23-Aug-11 4:14am

TheyCallMeMrJames

Comments

[no name] 23-Aug-11 11:27am

This already looks ok, but there is one thing you could for optimization: Instead of intersecting the original bitmaps, you could add a monochrome mask to each sprite. A zero represents an empty pixel, a one a set one. You would only need one bit per pixel (instead of three or four bytes), reducing the effort for the comparison. Also, you could test eight or more pixels at once (depending on wether you check only bytes or larger words) using XOR.

Edit: Let's say you have sprites of 80 x 80 pixels. A monochrome mask would need 10 x 80 = 800 bytes. The sprite (32 bit RGBA) would require 80 x 80 * 4 = 25600 bytes. Quite a difference when you have to intersect and compare them.

TheyCallMeMrJames 23-Aug-11 11:33am

Good point. And remember to create the mask once (up front) for each version of the sprite. Load that into memory when you're starting the app up. This way the detection is supa-fassst.

[no name] 23-Aug-11 11:38am

Thanks. I got my first sprites onto the screen on my first computer in 1978. The resolution was 64 x 32 pixels (monochrome) and the CPU was somewhat weaker than what we are used to today. But once in a while those old things are still very convenient :)

TheyCallMeMrJames 23-Aug-11 12:25pm

Heheh...yeah, I wasn't far behind...started working at the pixel level in 1983. It's amazing to see how far away from the hardware we can be now and yet still concerned about things that are so small. ;)

YashwanthBathini 24-Aug-11 2:23am

Hi,
Upto getting overlapping rectangle coordinates it is okay but when am trying to call getPixel() on that overlapping section method am encountering an exception saying
Coordinates of the pixel are Out of Bounds defined..How can i resolve this?