sprite-collision: how to ignore transparent colors

[bauerr]

Hi,

I'm just thinking of sprite-sprite-collisons. How can I detected  a "true collision"? I want to ignore the transparent parts of a sprite.
I've been thinking of defining several Rectangles that fit the size of my sprite, but I think this will be to compllicated if we talk about complex spirtes.

So, what would be the best method?

By the way: If possible I'm interested in doing this without additional jar/API

Best regards.

Ralf

[Malohkan]

If you're interested in using any sort of shape (as accurate as you make it) you could use collision detection with polygons via the Area class.  You can see how I do that in the source to my tutorial found here:
http://www.gamelizard.com/JavaGameProgrammingPresentation.htm

[erikd]

You could also first detect an image-image collision (disregarding alpha, just detecting if the images overlap), and if such a collision was detected, compare the overlapping pixels of the parts of the 2 images (sprites) that overlap. If both pixels of a compare are not transparent, you have a collision. This way, you'll have pixel perfect collision detection (which BTW is seldom really needed).
Only in the worst case you'll be comparing all pixels of both sprites, but usually you'll just compare a small part.
An additional optimization might be to do the comparing from the 'inner' pixels of the images to the 'outer' pixels (as the transparent pixels are usually on the 'outer' parts of a sprite).
I hope I'm making sense here.

Games published by our own members! Check 'em out!

[Jeff]

Thats how games have tarditionalyl done it when needed (first do a boundign box or bounding speher and then compare the in intersection points pixel by pixel.)

But as already said its almost never done. usually bouding box or bounding spehere is good enough.

[bauerr]

Thanks.

In the meantime I started with a solution as erikd described it. But I will think about all suggestions.

Ralf

[Jeff]

A side note. if you REALLY need pixel perfect inertscetiion then there is an imetrmediate step between bounding-topes and pixel comaprison that cna speed thinsg up.

its sometimes called a "shadow".  What you do is create a 1 dimensional p[rojection of the 2D object ina bit mask.  At any x location where a  pixel is not transparent on any row of pixels, the mathcing bti is sit on the mask.  If you imagine that the obejct was one bit per pixel, then the mask is the binary OR of all the rows

1   2   3   4   5   6   7   8   9

If this is the object:               XXX    XXX             XXXX   XXXXX             XXX           XXXXX Then the shadow is this:         XXXXX    XXXXXXX

Edit: Damn HTMl wont make it line up straight... ghrr.. well I hope you get the idea
What you do is shit the bitstring over the appropriate amount to match the current overlap of the two objects and then binary AND it together.

If the result is clear (all zeros) then there is noi collision. If it is not clear then you just check the columns for each bit position that is 1 to see if there is really an intersection there.

Obviosuly ist not justa  simpel shift and AND because your going to need a wider bit field then you can fit in a single variable (twice the width of your widest object) but the theory is the same, its jus ta bit fancier code to hanbdle the arbitrarily wide bitfield

[kevglass]

Thats neat! So to paraphrase you build a line of pixels for each sprite by either summing up the pixels in each column or row (which I suppose you can cache). Then do a comparison between the two lines.

Double neat!

Kev

[bauerr]

Two questions:

1. If I check the color of a pixel like that:

 private static void printChannels(int pixel) {

   int alpha = (pixel >> 24) & 0xff;  
   int red   = (pixel >> 16) & 0xff;  
   int green = (pixel >>  8) & 0xff;  
   int blue  = (pixel ) & 0xff;  
   
   if(alpha!=255){
    System.out.println(alpha + "/" + red + "/" + green + "/" + blue);
   }
   
   
  }

Which combination is a transparent  color? I can't find a hint about this :(

2. If I use the suggest of Jeff: How would this work for objects with a great amount of transparent color, e.g. somethin like this:


xxxxxx
xxxxxx
ooxxoo
ooxxoo
ooxxoo
oxxxxo
oxxxxo
ooxxoo
ooxxoo
ooxxoo

If I understand it well, this leads to

xxxxxx

This seems no pixel perfect collision to me?

[kevglass]

Ah, the thing Jeff suggested wasn't for the final check, just another quick check you can perform before performing the pixel for pixel check.

(Completely) Transpent pixels should have an alpha of zero I believe.

Kev

[bauerr]

Thx.

Games published by our own members! Check 'em out!

[K.I.L.E.R]

Why don't you just load the image, create another temporary image, copy the original to the empty temporary image, avoid adding alpha colours?

Then pass the managed image back to your main program.
Whenever you do basic collision it would be pixel perfect.

[Jeff]

Ah, the thing Jeff suggested wasn't for the final check, just another quick check you can perform before performing the pixel for pixel check.

(Completely) Transpent pixels should have an alpha of zero I believe.

Kev

Right,  if you rotuinely fill all the coluns with at least one pixel its not terribly useufl. OTOH if you have a lot of "surrounding whitespace" or columsn of whitespace  in the middle, it can be.

Its just another potential heuristic.

[bauerr]

@K.I.L.E.R

How should this work? My images are still defined with x/y/widht/height and the collision are still detected by overlapping rectangles. So, I still have to check the pixels, don't I?

[K.I.L.E.R]

@K.I.L.E.R

How should this work? My images are still defined with x/y/widht/height and the collision are still detected by overlapping rectangles. So, I still have to check the pixels, don't I?

Yeh, but at least you wont have to check many pixels. It removes a lot of overhead at the expense of load time.

[bauerr]

Finally I got a solution, but I still have to test it properly. I also thinking about adding some of the suggestions above into my programm.
Nevertheless, here's my solution. It is not called for each collison detection only for some cases.
Any comment would be appreciated.



import java.awt.*;
import java.awt.image.*;


public class CollisionDetector {
 
 static Rectangle s1;
 static Rectangle s2;
 static Rectangle inter;
 static int width;
 static int height;
 public static BufferedImage buf1;
 public static BufferedImage buf2;

 public static CollisionDetector single = new CollisionDetector();
 
 public CollisionDetector getDetector(){
   return single;
 }
 
 public static boolean checkPixelCollision(Image a, int ax, int ay, Image b, int bx, int by){
 
   //Rectangles
   //System.out.println("detector");
   //System.out.println("A = " + ax + "/" + ay + "/" + a.getWidth(null) + "/" + a.getHeight(null));
   //System.out.println("B = " + bx + "/" + by + "/" + b.getWidth(null) + "/" + b.getHeight(null));
   
   //initialize Rectangles
   Rectangle rec1 = new Rectangle();
   Rectangle rec2 = new Rectangle();
   inter = new Rectangle();
   
   //set Bounds and get intersection
   rec1.setRect(ax,ay,a.getWidth(null),a.getHeight(null));
   rec2.setRect(bx,by,b.getWidth(null),b.getHeight(null));
   Rectangle.intersect(rec1,rec2,inter);
   
   //Intersection
   //System.out.println("I = " + inter.x + "/" + inter.y + "/" + inter.getWidth() + "/" + inter.getHeight());
   
   //widht and height must be at least 1 Pixel
   width = (int) inter.width;
   height = (int) inter.height;
   
   if(width<1){
     return false;
   }
   
   if(height<1){
     return false;
   }

   //compute sub-images for image 1
   s1 = getSubRec(rec1,inter);

   //widht and height must be at least 1 Pixel
   width = (int) s1.width;
   height = (int) s1.height;
   
   if(width<1){
     return false;
   }
   
   if(height<1){
     return false;
   }
   
   //compute sub-images for image 2
   s2 = getSubRec(rec2,inter);
   
   //widht and height must be at least 1 Pixel
   width = (int) s2.width;
   height = (int) s2.height;
   
   if(width<1){
     return false;
   }
   
   if(height<1){
     return false;
   }
   
   //SubImages
   //System.out.println("S1 = " + s1.x + "/" + s1.y + "/" + s1.width + "/" + s1.height);    
   //System.out.println("S2 = " + s2.x + "/" + s2.y + "/" + s2.width + "/" + s2.height);    

   buf1 = (BufferedImage)a;
   buf2 = (BufferedImage)b;
   
   buf1 = buf1.getSubimage((int)s1.x,(int)s1.y,(int)s1.width,(int)s1.height);
   buf2 = buf2.getSubimage((int)s2.x,(int)s2.y,(int)s2.width,(int)s2.height);
   
   //System.out.println(buf1.getWidth() + "/" + buf2.getWidth());
   //System.out.println(buf1.getHeight() + "/" + buf2.getHeight());
   
   for(int i=0;i<buf1.getWidth();i++){
     for(int n=0;n<buf1.getHeight();n++){

       //System.out.println(i + "/" + n);
       int rgb1 = buf1.getRGB(i,n);
       int rgb2 = buf2.getRGB(i,n);

       
       if(isOpaque(rgb1)&&isOpaque(rgb2)){
         return true;
       }
       
     }
   }
   
   
   
   return false;
 }

 private static boolean isOpaque(int pixel) {

   int alpha = (pixel >> 24) & 0xff;  
   //int red   = (pixel >> 16) & 0xff;  
   //int green = (pixel >>  8) & 0xff;  
   //int blue  = (pixel ) & 0xff;  
   
   //transparent if alpha = 0
   if(alpha==0){
     return false;
   }
   
   return true;
   
 }

 //computing Rectangles for sub-images
 private static Rectangle getSubRec(Rectangle rec1, Rectangle inter) {
   
   //Rechtecke erzeugen
   Rectangle sub = new Rectangle();
   Rectangle source =  rec1;
   Rectangle part  =  inter;
   
   int absoluteX = 0;
   int absoluteY = 0;
   
   //get X - compared to the Rectangle
   if(source.x>part.x){
     sub.x = 0;
     absoluteX = source.x;
   }else{
     sub.x = part.x - source.x;
     absoluteX = part.x;
   }
   
   if(source.y>part.y){
     sub.y = 0;
     absoluteY = source.y;
   }else{
     sub.y = part.y - source.y;
     absoluteY = part.y;
   }
   
   //same handling with y
   if((source.x+source.width)<(part.x+part.width)){
     sub.width = (source.x+source.width)-absoluteX;
   }else{
     sub.width = (part.x+part.width)-absoluteX;
   }

   if((source.y+source.height)<(part.y+part.height)){
     sub.height = (source.y+source.height)-absoluteY;
   }else{
     sub.height = (part.y+part.height)-absoluteY;
   }

   
   return sub;
 }
 

}