Hello, Attached are some quadtree files. quadtree.py - contains the QuadTree class. test_quadtree.py - tests for the quadtree class. I think it works correctly. There are tests for 200 objects being updated at once. Uses 0.07194 % cpu on my duron 850 for 60 fps( or 0.001199 seconds to do one update ). Could do with some more tests, but I can't be bothered at the moment :) It should be possible to create a collide function which uses the quadtree to limit the number of possible collision tests. Every time you update an objects .rect attribute you need to call a_quadtree.update( obj ). Or faster if you call a_quadtree.update_multi( objects ) on all your objects. This doesn't really scale up to 3000 objects moving every frame. For that you'd need to use numeric or c/c++ I think. I tried using psyco for the code, but it only slowed it down. Another option instead of quad trees, sphere trees are supposed to be very quick. What you could do to speed up your code is not update characters which aren't in view. --- Pete Shinners <pete@shinners.org> wrote: > 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? > __________________________________________________ Do You Yahoo!? Everything you'll ever need on one web page from News and Sport to Email and Music Charts http://uk.my.yahoo.com
Attachment:
quadtree.py
Description: quadtree.py
Attachment:
test_quadtree.py
Description: test_quadtree.py