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

Re: [pygame] quadtrees

Gerrit Holl wrote:

Has anyone ever implemented quadtrees in Python?
what a coincident. i just stirred up a crude version of a weighted quadtree for irc. i had to run and never even got a change to test it, but the logic should all be ok (hopefully the implementation too)

a quadtree is a recursive type of object that holds 4 children quadtrees. at some point the area of the quadtree gets within a small enough size and it just stores a list of objects in that tree.

at each level of the quadtree it computes the active area of all contained objects. a weighted quadtree will find the average center of that area, but you can also just pick the mathematical center. this is done in both X and Y. so you divide a rectangular area into 4 sections.

then you loop through all the objects the quadtree should contain and pass them into the appropriate quadtree for that area. this whole process then repeats for each of the 4 children.

when you want to find an object that is in a specific position, you can quickly dig through the trees to the node that contains only the objects in the specified area. this makes a quick way to narrow down the list of objects to choose from.

the quadtree isn't so great for moving objects, since you must rebuild the it everytime you want to do some position testing with it. the shallower the tree the faster it will be to build, but the less help it will be for collision tests. deeper trees take longer to build, but offer the most speed benefit.

again, my code here is totally untested up to this point. well, aside from a few poor folks who went ahead and used this from the #pygame irc channel. i realize now it could be optimized by stopping the tree creation when there are no more objects. in fact, now that i think about it, it may raise an exception when an individual section has no objects?

good luck, if anything maybe it will help explain all this better.
http://www.pygame.org/ftp/contrib/quadtree.py

actually, after relooking at the code, much could be done to speed this up. things like not recomputing the bounds at each depth. and including more threshold than just pixel size (like number of objects, depth, etc)