# Spatial Partitioning - How do I find the object is in the tree?

I understand the structure of Spatial Partitioning Trees - BSP, Quad and Octal. You just take a space and split it into however many parts specified by your tree - BSP:2, Quad:4, Octal:8. I've written a self managing quad-tree (in Java but this shouldn't matter) before, and I had the same question I'm having now (in XNA).

How, once an object is in the tree, do I find it specifically. ie. I put the player in the tree, he updates ever frame, but unlike the other AI driven/world objects, he needs input, and his health needs to be checked every frame to see if the game is over. How do I get him out, without knowing his exact location.

My solution last time was to just leave the player out of the tree, and when I need to do collision checking, just pass in his coordinates to get the possible collisions, but I feel like this isn't using the tree the way it's supposed to be used.

Right now I'm trying to write a tree for a 3D game this time in XNA. So my second question really is which tree is better? I've heard BSP trees are the standard, but weren't oct trees written for dividing 3D spaces (Same as quad trees are for 2D)?

• what's wrong with keeping a reference of player outside of tree. I mean you are only holding references, put one inside and keep one outside tree. – Ali1S232 Dec 21 '12 at 20:14

Spatial partitioned data structures should only be used for finding out what is in a particular area, they do not replace plain data structures.

SpatialObjectGrid<Entity&> worldGrid;
List<Enemy&> enemies;
[...]
Player& player=Player(blar, blar, blar);
[...]
Enemy& newEnemy=Enemy(bar, bar);
enemies.append(newEnemy);