[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: [pygame] [Announce] Python bindings for the bitmask collision detection library

Hi,

for other peoples interest we have committed these changes to svn.  We
also made it use the old faster code for the default rect collision.
So it shouldn't change how fast current games go.

There's still some more changes coming though.
The main one being:
- implementing bitmask collision functions.

Which brought us on to a conversation about collision response.  As
the new mask module has the ability to return the direction of the
collisions.  So it'd be nice to make use of that functionality from
within the sprite module.

pygame.sprite already has a limited collision response mechanism.  It
allows the 'killing' of sprites upon collision.  With the dokill
arguments to groupcollide, and spritecollide functions, and the kill()
method of sprites.


However there are three types of collision+response we want:
1. - just collision detection.
2. - collision detection where the sprites are removed apon detection.
3. - collision detection where the direction is calculated and passed
to the sprites to work out.

Pygame already does 1., and 2.  However 3 is useful.


3. - collision detection where the direction is calculated and passed
to the sprites to work out.

Number 3, can is pretty generic (the goal of the sprite module).  So
people can implement their behaviour quite easily.  It will allow
people to ask all different questions in the behaviour of the
collision response functions that require a direction:
- did the mario character jump on the head of the creature?
- what direction should they bounce away from each other?


We worked out one way which we could do this to the sprite module so
that the current api can remain, and that we can add it in such a way
that directions are not calculated if they are not needed.

It is important _not_ to calculate the directions if not needed because:
- it is faster not calculating direction. (we don't want to slow down
existing games that don't use it).
- it is easier to implement just collision for custom collision
functions.  (so people can just implement new forms of collision
detection, without being forced to implement the collision direction).


There would be these changed functions:

The current collision functions:
def groupcollide(groupa, groupb, dokilla, dokillb, collided = None):
def spritecollideany(sprite, group, collided = None):
def spritecollide(sprite, group, dokill, collided = None):

The new collision functions:
def groupcollide(groupa, groupb, dokilla, dokillb, collided = None,
collided_direction = None):
def spritecollideany(sprite, group, collided = None, collided_direction = None):
def spritecollide(sprite, group, dokill, collided = None,
collided_direction = None):


The new argument is collided_direction. None means do not calculate
the direction.  Otherwise it should be a collision direction function.

The collision direction functions would be:
def collide_rect_direction( left, right ):
def collide_circle_direction( left, right ):
def collide_mask_direction( left, right ):

Each would of these collide_*_direction functions would return False
if there is no collision, or a vector direction if there was a
collision.


New Sprite method:

As well as a kill method, the Sprite class will gain a new collided() method.
   def kill(self):
   def collided(self, asprite, direction):

Where 'asprite' is the sprite collided with, and the 'direction' is
the direction of the collision.


So to implement sprite behaviour on a collision - you could place it
in the collided method.


So that's the idea of how to implement generic collision response
within the pygame sprite module.

What do you reckon?


On 5/9/07, John Krukoff <helot@xxxxxxxxxxx> wrote: 
René Dudfield wrote:
> It's in pygame now.
>
> There's still a few things I need to do.
>
> - make constructor which takes a surface.
> - a 'make_surface' method in C.  should take a threshold for alpha.
> - complete the documentation (now in src/mask.doc)
> - complete the unittests (test/test/mask_test.py)
> - make set_at and get_at raise IndexError when wrong index is given.
> - double check the reference counting.
> - integrate Mask into examples/testsprite.py
>
>
> JKrukoff has an idea about how to change the sprite classes so they
> can be extended to use different types of collision detection.  He's
> going to write a proposal to the mailing list about it later.

Right, so as discussed in IRC, I have a simple proposal for extending the
sprite module collision detection routines to be able to handle arbitrary
types of collisions instead of only rect collisions. I propose adding a
callback parameter to spritecollide, groupcollide, and spritecollideany
which will be a function which evaluates two sprites for a collision,
returning a boolean result.

The default value for this parameter would be a function that uses
colliderect to evaluate the two sprites, giving clean backwards
compatibility with existing code.

I've had to write my own collision routines in order to support mixing
bounding boxes and bounding circles, but this method would allow for such
tests to be plugged into the existing API. This functionality currently
seems urgent, as we now need an optional way to use bitmask based
collisions. As long as it has to be extended, why not do so in a generic
way?

The attached file contains a sample implementation (sans documentation or
optimization work) which should illustrate the method. It also contains
basic collision functions for rect collisions, scaled rect collisions, and
circle collisions.

This method also lends itself to doing tests in stages, where a less
accurate and faster collision test is used first, and then the results are
used for a second pass with a more accurate (and slower) collision test.

Ex.
>>> import pygame.sprite as sprite
>>> a, b = pygame.sprite.Sprite( ), pygame.sprite.Sprite( )
>>> a.rect = pygame.rect.Rect( 0, 0, 10, 10 )
>>> b.rect = pygame.rect.Rect( 5, 5, 10, 10 )
>>> sprite.spritecollide( a, [ b ], False )
[<Sprite sprite(in 0 groups)>]
>>> sprite.spritecollide( a, [ b ], False, sprite.collide_rect )
[<Sprite sprite(in 0 groups)>]
>>> sprite.spritecollide( a, [ b ], False, sprite.collide_circle )
[<Sprite sprite(in 0 groups)>]

Admittedly, this doesn't solve the issue of how to generate masks for
bitmask collisions (though that can be worked around in the collision
function much as radius calculations are in collide_circle), but then the
default implementation doesn't provide a rect either. This is, I think, a
change in spirit with the current sprite implementation of an extensible
container.

There are some performance considerations, as this adds a couple of lookups
and a function call to each test, but honestly, if you're worried about
performance you aren't using the default collision functions anyway.

---------
John Krukoff
helot@xxxxxxxxxxx