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

[Richard Jones <richardjones@optushome.com.au>]

On Sun, 9 Mar 2003 06:14 am, Gerrit Holl wrote:
> Pete Shinners schreef op zaterdag  8 maart om 19:22:14 +0000:
> > 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!

Pete dropped a "t" - he meant quadtrees.

Quadtrees gather the sprites spread your 2D playing area into four equal 
squares that cover the playing area. Further split each of those four areas 
into a further four areas each, sorting the objects inside into its 
appropriate leaf. Once you hit some boundary condition (typically either 
number of branches in the tree _or_ number of sprites in a leaf) you stop. 
You may then query the tree to quickly find any interesting sprites given a 
point in the playing area.

I can see that it might be useful to offer an implementation of the quadtree 
structure in pygame - possibly as an integrated part of the sprite group 
handling? 


   Richard

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