Pixel perfect collision detection

[zparticle]

Well I tried to post the code but the forum software says it is too long so the link is:

http://www.scottshaver2000.com/ImageFunctions.java

[stefanha]

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   38   39   40   41   42   43   44   45   46   47   48   49   50   51   52   53   54   55   56   57   58   59   60   61   62   63   64   65   66   67   68   69   70   71   72   73   74   75   76   77   78   79   80   81   82   83   84   85   86   87   88   89   90   91   92   93   94   95   96   97   98   99   100   101   102   103   104   105   106   107   108   109   110   111   112   113   114   115   116   117   118   119   120   121   122   123   124   125   126   127   128   129   130   131   132   133   134   135   136   137   138   139   140   141   142   143   144   145   146   147   148   149   150   151   152   153   154   155   156   157   158   159   160   161   162   163   164   165   166   167   168   169   170   171   172   173   174   175   176   177   178   179   180   181   182   183   184   185   186   187   188   189   190   191   192   193   194   195   196   197   198   199   200   201   202   203   204   205   206   207   208   209   210   211   212   213   214   215   216   217   218   219   220   221   222   223   224   225   226   227   228   229   230   231   232   233   234   235   236   237

class CollisionMask {       int width, height, maskWidth;       int mask[];       public CollisionMask ( Image image, int width, int height )       {             this ( image, 0, 0, width, height );       }             public CollisionMask ( Image image, int x, int y, int width, int height )       {             this.width = width;             this.height = height;             maskWidth = ( width >> 5 ) + ( ( width % 32 == 0 ) ? 0 : 1 );                         mask = new int[ maskWidth * height ];                         int pixels[] = new int[ width * height ];             PixelGrabber pixelGrabber = new PixelGrabber ( image, x, y, width, height, pixels, 0, width );             try             {                   pixelGrabber.grabPixels ( );             }             catch ( InterruptedException e )             {                   throw new RuntimeException ( "Error grabbing pixels!" );             }                         if ( ( pixelGrabber.getStatus ( ) & ImageObserver.ABORT ) != 0 )             {                   throw new RuntimeException ( "Error grabbing pixels!" );             }                         for ( int i = 0; i < height; i++ )             {                   for ( int j = 0; j < width; j++ )                   {                         if ( ( pixels[ j + ( i * width ) ] & 0xFF000000 ) != 0 )                         {                               mask[ ( j >> 5 ) + ( i * maskWidth ) ] |= 0x80000000 >>> ( j % 32 );                         }                   }             }       }             public boolean collidesWith ( CollisionMask b, int x1, int y1, int x2, int y2 )       {             // Check if the masks even overlap            if ( ( x1 >= x2 + b.width ) || ( x1 + width <= x2 ) ||                    ( y1 >= y2 + b.height ) || ( y1 + height <= y2 ) )             {                   return false;             }                         int ax, ay, bx, by;                         if ( y1 < y2 )             {                   ay = y2 - y1;                   by = 0;             }             else             {                   ay = 0;                   by = y1 - y2;             }                         if ( x1 < x2 )             {                   int dx = x2 - x1;                   int aStart = dx >> 5;                   int shift = dx % 32;                   int aOffset = aStart + ( ay * maskWidth );                   int bOffset = by * b.maskWidth;                                     if ( shift == 0 )      // Masks are aligned, we do not need to shift pixels                  {                                           while ( ( ay < height ) && ( by < b.height ) )                         {                               ax = aStart;                               bx = 0;                                                                                           while ( ( ax < maskWidth ) && ( bx < b.maskWidth ) )                               {                                     if ( ( mask[ aOffset ] & b.mask[ bOffset ] ) != 0 )                                     {                                           return true;                                     }                                                                         aOffset++;                                     bOffset++;                                     ax++;                                     bx++;                               }                               aOffset += maskWidth - ( ax - 1 ) + aStart - 1;                               bOffset += b.maskWidth - ( bx - 1 ) - 1;                               ay++;                               by++;                         }                   }                   else                  // Masks are not aligned, we need to shift pixels                  {                         int invShift = 32 - shift;                                           while ( ( ay < height ) && ( by < b.height ) )                         {                               ax = aStart;                               bx = 0;                                                             while ( bx < b.maskWidth )                               {                                     if ( ax < maskWidth - 1 )                                     {                                           if ( ( ( ( mask[ aOffset ] << shift ) |                                                        ( mask[ aOffset + 1 ] >>> invShift ) ) &                                                    b.mask[ bOffset ] ) != 0 )                                           {                                                 return true;                                           }                                     }                                     else                                     {                                           if ( ( ( mask[ aOffset ] << shift ) & b.mask[ bOffset ] ) != 0 )                                           {                                                 return true;                                           }                                           aOffset++;                                           bOffset++;                                           ax++;                                           bx++;                                           break;                                     }                                                                         aOffset++;                                     bOffset++;                                     ax++;                                     bx++;                               }                                                             aOffset += maskWidth - ( ax - 1 ) + aStart - 1;                               bOffset += b.maskWidth - ( bx - 1 ) - 1;                               ay++;                               by++;                         }                   }             }             else             {                   int dx = x1 - x2;                   int bStart = dx >> 5;                   int shift = dx % 32;                   int aOffset = ay * maskWidth;                   int bOffset = bStart + ( by * b.maskWidth );                                     if ( shift == 0 )      // Masks are aligned, we do not need to shift pixels                  {                         while ( ( ay < height ) && ( by < b.height ) )                         {                               ax = 0;                               bx = bStart;                                                             while ( ( ax < maskWidth ) && ( bx < b.maskWidth ) )                               {                                     if ( ( mask[ aOffset ] & b.mask[ bOffset ] ) != 0 )                                     {                                           return true;                                     }                                                                         aOffset++;                                     bOffset++;                                     ax++;                                     bx++;                               }                                                             aOffset += maskWidth - ( ax - 1 ) - 1;                               bOffset += b.maskWidth - ( bx - 1 ) + bStart - 1;                               ay++;                               by++;                         }                   }                   else                        // Masks are not aligned, we need to shift pixels                  {                         int invShift = 32 - shift;                                           while ( ( ay < height ) && ( by < b.height ) )                         {                               ax = 0;                               bx = bStart;                                                             while ( ax < maskWidth )                               {                                     if ( bx < b.maskWidth - 1 )                                     {                                           if ( ( ( ( b.mask[ bOffset ] << shift ) |                                                        ( b.mask[ bOffset + 1 ] >>> invShift ) ) &                                                    mask[ aOffset ] ) != 0 )                                           {                                                 return true;                                           }                                     }                                     else                                     {                                           if ( ( mask[ aOffset ] & ( b.mask[ bOffset ] << shift ) ) != 0 )                                           {                                                 return true;                                           }                                                                                     aOffset++;                                           bOffset++;                                           ax++;                                           bx++;                                                                                     break;                                     }                                     aOffset++;                                     bOffset++;                                     ax++;                                     bx++;                               }                               aOffset += maskWidth - ( ax - 1 ) - 1;                               bOffset += b.maskWidth - ( bx - 1 ) + bStart - 1;                               ay++;                               by++;                         }                   }             }                     return false;       } }

[stefanha]

I posted my pixel-perfect collision detection routines.  The differences to zparticle's are mainly that I use Java 1.2 and that I keep the mask in a one-dimensional array.

I tried to optimize my code so that only simple operations (+, -, <<, >>>) would be performed in the loops.  I don't need any multiplications to index ints in the collision masks because I keep an offset, which gets incremented appropriately as the loop executes.

I know it's kind of messy, but it is fairly low-level bitmanipulation code.  Also, my optimization strategy was basically just intuition.  I didn't think too much about it, especially in the context of Java.  So if you see some obvious problem/optimization/simplification please tell me.

I tested this code for quite a bit today, so I am fairly confident that there are no bugs.  Again, feel free to prove me wrong.

from, Stefan

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

[FaeLLe]

Well I tried to post the code but the forum software says it is too long so the link is:

http://www.scottshaver2000.com/ImageFunctions.java

Can we request for a version of  your code that uses single images rather than array so it will be easier to understand it please.

Thanx.

[FaeLLe]

Few questions on your code please.

for(int big=0;big<50;big++)

why only traverse the loop till 50 ?

first = com.sun.j3d.utils.timer.J3DTimer.getValue(); //System.currentTimeMillis();

second = com.sun.j3d.utils.timer.J3DTimer.getValue(); //System.currentTimeMillis();

why do you do this even though it is not needed for collision detection ?

Would be nice if you answer please

Thanx.

[zparticle]

Few questions on your code please.

why only traverse the loop till 50 ?

first = com.sun.j3d.utils.timer.J3DTimer.getValue(); //System.currentTimeMillis();

second = com.sun.j3d.utils.timer.J3DTimer.getValue(); //System.currentTimeMillis();

The stuff in the main method was just me testing the functions, it has nothing to do with the actuall collision detection, please ignore it.

[zparticle]

Can we request for a version of  your code that uses single images rather than array so it will be easier to understand it please.

The code already has methods for both single images and arrays of images:

static public int[][][] createPixelMasks(Image[] spriteImages, GraphicsConfiguration gc)

static public int[][] createPixelMask(Image spriteImage, GraphicsConfiguration gc)

And then the actuall collision detection acts on two masks which have to be arrays for the code to work:

public final static boolean maskCollision(int[][] mask1, int x1, int y1, int width1, int height1,
       int[][] mask2, int x2, int y2, int width2, int height2)

basically the masks are simply bits representing each pixel in the images to check for a collision. The bits are on for pixels that can collide and off for pixels that can't.

I should note that this code is based heavy one another persons work, although I can't remember who it was. I think he used to be a member here.