Re: [pygame] PROPOSAL: Faster Collision Checking: Ordering Spritesto Boost spritecollide Speed (Please Comment!)

[Pete Shinners <pete@shinners.org>]

Gerrit Holl wrote:
> I have a proposal regarding the spritecollide function. I have written
> it down, comments would be very much appreciated. I hope you can check
> it for errors, but if it's fined out enough it may be worthy to be
> incorporated into the pygame distribution.
i think once you get into the massive amounts of objects you are 
carrying, it's not a big surprise something more efficient might be needed.

it sounds like there may be simpler strategies than the ones you are 
looking for. i think what would help your game out the most would be to 
break the game area down into "rooms", basically any sized rectangular 
area. then when you do the collision test, just find out what room the 
object is in, and you only test for collisions in that room.

even moving objects should work pretty well since the sprite Groups were 
designed to efficiently add and remove members. objects that are on the 
edges of rooms would just go in both rooms (or all 4 rooms if they are 
on the corner)

since you probably want different reactions for each type of object, you 
may want to keep a list of room groups for each type of object. the 
"size" of each room is pretty arbitrary, you'll probably want to play 
with it and find the best size for speed. i'd start with 300x300 areas 
which nicely fits into a 10x10 grid for your game area.

further optimizations might move you towards quadrees instead of a plain 
grid, but i can't imagine that level of organization would be necessary, 
or really even help much?


--
"if they keep silent, the very stones will cry out"
pete*shinners.org

____________________________________
pygame mailing list
pygame-users@seul.org
http://pygame.seul.org