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)?

  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – 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);
| improve this answer | |
  • \$\begingroup\$ So are you suggesting that I basically clear the tree every frame and fill it just before collision detection? That doesn't seem very efficient to me, but I can see how it would be done. Just have all objects in the world be children of an Object class that has ways to react to collisions that can be overridden in the children. \$\endgroup\$ – Peteyslatts Dec 22 '12 at 21:22
  • \$\begingroup\$ I am not suggesting anything like that, all I am saying that you should have the spatial partitioned data structure in addition of more plain data structures. Repopulating it every frame will be more costly than not using it at all. \$\endgroup\$ – API-Beast Dec 22 '12 at 21:58
  • \$\begingroup\$ Ok, I thought the tree structure was just a more efficient version of the List. So how would I go about passing the position information back and forth? This goes back to my original question: how do I know which object is which so I can pass the correct data to the correct object? \$\endgroup\$ – Peteyslatts Dec 22 '12 at 22:45

Well, BSPs are mainly for rendering but are typically not used today (certainly fine for something that you are making however). Octrees are for spacial partition of the world for objects in game. And yes, you want to put your player into the tree. However, keep a reference to the player specifically if you want to manage them and so that you know where they are. (You can also put the input parsing in the player's AI if you want)

Also, if you can, simplify your design. If you have a game that could be represented in 2D, then only spacially manage 2 directions. Also, using a grid over a tree is typically faster (as it is a simpler design).

| improve this answer | |
  • \$\begingroup\$ See my above comment, because your post made me think of something: if I keep passing in the player every frame, there will be a bunch of copies of the player in the tree. How do I get rid of them? \$\endgroup\$ – Peteyslatts Dec 22 '12 at 21:23
  • \$\begingroup\$ well, your spacial map is generated at the beginning (of every frame if you want or when things are created). You iterate through items in the region, and if they are moved, you adjust their position in the tree/grid \$\endgroup\$ – CobaltHex Dec 23 '12 at 4:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.