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

[Gerrit Holl <gerrit@nl.linux.org>]

Pete Shinners schreef op zaterdag  8 maart om 19:22:14 +0000:
> 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.

Indeed. I'm writing a platform game, and although the viewport won't carry
more than 50 objects, the level is much larger (approx. 10 times).

> 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.

Yes... I'll need to think it over, but it sounds like a good idea. 

> 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)

Hmm, maybe you're right. I'd have groups than with associated rectangles
and the viewport rectangle could check collisions with a number of those.
Hmm... hmm... I foresee some problems but not unbridgable to I am
definately going to try it.

> 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.

Well, my game does currently not work with a grid, but that shouldn't be
too much of a problem.

> 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?

Hmm, I'm not sure what you mean by this. I can see 'quadri-' = square,
but then I don't see the difference with a grid; but I can get further
with this advice. Thanks, it's obvious that I don't have experience in
programming games!

yours,
Gerrit.

-- 
Asperger Syndroom - een persoonlijke benadering:
	http://people.nl.linux.org/~gerrit/
Het zijn tijden om je zelf met politiek te bemoeien:
	http://www.sp.nl/
____________________________________
pygame mailing list
pygame-users@seul.org
http://pygame.seul.org