Quadtrees

They work like a BSP-tree (Binary Space Partiton)...but instead of haveing a simple true/false node...quad trees have four and oct trees have eight....basicly they are a way to subdivide space,objects, whatever in an effort to quickly axcess relevent information.

lets say you have a 640 X 480 screen filled with hundreds of various objects...the player has just clicked on one...so how do you find which one?

you can use a quad-tree...

lets say that mouse clicked on pixel location X=34, Y=56...you start at the root of the tree...a quad tree "slices" space into four equal parts...basicly given a certain area (640 X 480 screen) the center point is used to generate each node...in this case we test the mouse X and Y values aganist the center point of the node (320 and 240 respectively)...we find that the mouse is in 1 of the four sub areas...so we follow the node to another and check it against it''s test value...in this case we are now in a area 320 X 240 in size and are checking against half those values (160 X 120)....basicly we keep checking and following the nodes until one of two things happen:
1) the new sub area we enter into is a null pointer...indicateing that nothing is in this area
2)...or the pointer indicates a object, wall, whatever...this doesn''t meen the mouse clicked on it exactly...just that within the given sub-area this is the only object that is present...so you still need to check the mouse location with the indicated object...but its the only relevant object that needs to be tested

they work by eliminateing as many objects as quickly as is possable....if, in the above example, all objects were distributed evenly across the screen space...the first check removed 3/4s of the possable objects that the mouse clicked on.

I hope this helps (it''s overly simplified)... they arn''t all that complicated...only seem that way