4
\$\begingroup\$

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

Improve this question
\$\endgroup\$
1
  • 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, 2012 at 20:14

2 Answers 2

Reset to default
1
\$\begingroup\$

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);
worldGrid.add(player);
[...]
Enemy& newEnemy=Enemy(bar, bar);
enemies.append(newEnemy);
worldGrid.add(newEnemy);
Improve this answer
\$\endgroup\$
3
  • \$\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, 2012 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, 2012 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, 2012 at 22:45
0
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\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, 2012 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, 2012 at 4:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .