Re: [pygame] Pixel perfect collision detection sugestion

[Rene Dudfield <renesd@xxxxxxxxx>]

Hey,

The reason why the numeric one will probably be faster is that it is
all in C.  Python for loops are quite slow.  However if you were using
psyco yours would be quite fast!

We could translate the loop into C though, then it would be really quick :)


My vote is to use your code, but changed to do that loop in C,
abstract the hitmask, and generate the HitMask in C without using
numeric.



Now a note onto why we should abstract your code a little more...

There may be a faster way with bitsets or RLE encoding.  However those
are a bit(HAR HAR) more complicated.  So if we make it a HitMask
object, and have the functions use those, then we can implement the
bitset/rle stuff later.

Bitsets could compare up to 32 pixels at once with a SHIFT+AND, and
RLE could do say 256 pixels at once if they were all empty/full
pixels.  This would be quite useful for lots of images, or very large
sparse images.

So it's worth abstracting the HitMask a little more now, so that we
can upgrade to those later if anyone feels like implementing them
without people needed to change the api.




def _pixelPerfectCollisionDetection(sp1,sp2):
    """ Internal method used for pixel perfect collision detection.
         Returns 1 if the hitmasks collide.
         Would probably replace this function call with just the line
below where
            _pixelPerfectCollisionDetection is used.
    """
    return sp1.hitmask.collide(sp1.rect, sp2.hitmask,  sp2.rect)



# Here is an unfinished HitMask object which will be generated by C code...

class HitMask:
    # generated via a C function rather than array_colorkey.
    #   very similar to:
    #     pygame.surfarray.array_colorkey() or pygame.surfarray.array_alpha()
    #  except don't use numeric.
    #TODO: have to make sure that integers are 32 bits.  otherwise, treat
    #  differently.  Perhaps use SDL functions/constants for this.
    #bitset = array.array('L',range(int(math.ceil(numpixels / 32.))))
    #eight_bits_per_pixel = array.array('B',range(numpixels))
    #rle_encoded = Surface((h,w), 8, RLEACCEL)

    def collide(self, rect1, other_hitmask, rect2):
        """ returns True if collision.
               NOTE: this will be done in C.
        """
        # if they are aligned we can use bitsets... if not... RLE.
        #   otherwise we use the normal one.
        # note: could also use the numeric collision detection code one in here.

        hm1 = self.eight_bits_per_pixel
        hm2 = other_hitmask.eight_bits_per_pixel

        intersect_rect  = rect1.clip(rect2)

        x1 = intersect_rect.x-rect1.x
        y1 = intersect_rect.y-rect1.y
        x2 = intersect_rect.x-rect2.x
        y2 = intersect_rect.y-rect2.y

        for r in range(0,rect.height):
            for c in range(0,rect.width):
                if hm1[c+x1][r+y1] & hm2[c+x2][r+y2]:
                    return 1

        return 1



On 9/9/05, John Eriksson <john@xxxxxxxxxxxx> wrote:
> BTW...even if you do have large images with large areas of intersection you
> probably still would find a hit within the first row wouldn't you? Then the
> nested loop wouldn't cost that much after all.
> 
> Best Regards
> /John
> 
> >
> > hmm, time flies... but seriously, you're already using Numeric anyway,
> > and if you replaced just the part with the nested Python loops with a
> > Numeric function, it would probably be much faster, especially if you
> > ever have large images with large areas of intersection.
> >
> 
>