User-agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.3b) Gecko/20030306
Rene Dudfield wrote:
quadtree.py - contains the QuadTree class.
test_quadtree.py - tests for the quadtree class.
rene, stellar work, i'm checking this out now..
i haven't played much with quadtrees. but i can help describe them
pretty well. take your game area space, and divide it into four parts.
for each part of the screen, create a list of all the objects inside
that area. now, divide each of those areas into 4 parts again. these new
parts are "children" of the parent part that contains them. each one of
these can find out which objects are inside them by only looking at the
objects included in its parent. you recursively work your way down until
you usually have a given number of layers.
this whole structure is called a 'quadtree'. meaning each node has 4
children underneath it. you can now effectively find what objects are in
which parts of the screen by going down however deep you need in the
quadtree. the deeper you go, the better the accuracy.
you can also have each node be subdivided a different number of times,
often based on how many objects are inside that area. so if you have no
objects in the topleft corner, you don't subdivide further, but if you
have many in the topright corner, you will subdivide a lot deeper, until
there are only 5 or less objects in each node. note you usually need
some kind of 'minimum space' to stop the subdivisions here also, like
don't split down once you've reached a 1x1 pixel area.
there are multiple schemes of dividing into 4 parts. the simplest and
generic approach is to cut down the middle in each direction. another
one is to find the 'midpoint' in each direction and cut along that. this
gives you a much more balanced tree, but usually means most of your data
won't be moving around.
my description kind of stinks, but usually only the final level of
subdivision stores the geometry it includes. although i guess you could
store it at each level of the tree as well?
just for fun, you can take this into the 3rd dimension, and you have
"octrees". which is really the same thing, but you are dividing a 3
dimensional cube into 8 parts. octree's are really useful for 3d
intersection and more, since there's such a bigger 'volume of space'. i
belive if you use the 'averaged middlepoint' splitting on on actree it
is called a BSP, binary space partition, like quake3 uses. but my
terminology sucks, so please correct me. heh.
the advantage for doing collisions with all this is, you can quickly
discard the cases where there is nothing in the area of your object to
collide with.
in the end, for a map level that's fairly balanced (evenly distributed
walls, monsters, and powerups) i would think a straight grid of of nodes
would work equally well, if not a little better since it is easier to
manage?
phew, anyways, time to play with rene's code. oh, and there was a post
to the list that got bounced. Paul Nilsson recommended using a R+ or R*
tree implementation. which he says causes no problems for moving
objects. (I'm not sure what these are actually)
--
"if they keep silent, the very stones will cry out"
pete*shinners.org
____________________________________
pygame mailing list
pygame-users@seul.org http://pygame.seul.org