# Quad Tree Help - 2d game

## Recommended Posts

Unorthodox    100
I've tried to bold the key points so you can skim this.
[b]
[/b]I working on making a [b]2d, fast paced side-scroller/ platformer.[/b] I'm relatively new to game development and I'm just getting to the collision detection of the game. I've decided to [b]use a quad tree[/b] [b]to reduce the number of collision checks and for drawing the onscreen world[/b](enemies, projectiles and platforms/ground). After a day or two of reading and looking up articles on quad trees I have a basic understanding of how they work and how they can be used but I'm seriously stuck on implementing my own. I've tried looking at sample code but its still hard to tell.

[b]My understanding of a quad tree:[/b]
You have tree nodes each has pointers for its 4 children and parent. If one doesn't have a parent (pointer is NULL) its the root and if it doesn't have children its the lowest level of (leaf/node?).
Each node also has a list of objects that are in its quadrant.
You only check the collision of an object with its current and nearby quadrants.
I also realize that moving and non-moving objects will generally be in 2 different trees

[b]Questions:[/b]
1. What type of list is used for each tree node for the list of game objects?
2. For moving objects how exactly do you update the tree? do you have to go through the list of moving objects and set the tree again?
3. If you have n different trees how do you get to the same node on each tree? (if I'm correct that you use different trees for different types of game objects)
4. How do I decide how far to keep subdividing?
5. I'm assuming everything I want to collision check has to be game object (so it can be in the same list), do I just use simple inheritance to make all enemies, platforms/ground, items and player game objects?

I would really like to understand, write and implement my own Quad Tree or if you suggest a different collision method, then that. I'm not looking for sample code to modify and implement.
[b]For question 5[/b], you can just point me in the right direction if its more complicated. It's a question I was thinking about while typing this.

Thanks.

##### Share on other sites
procgen    108
You seem to understand how a quad tree works perfectly. I doubt a quad tree is going to be necessary for a side-scroller, though. Simply splitting the map into non-recursive sectors is probably enough. You seem to be looking for the strict definition of how a quad tree should be implemented, but it really depends on what you're using the quad tree pattern for.

##### Share on other sites
Unorthodox    100
[quote name='procgen' timestamp='1312745764' post='4845871']
You seem to understand how a quad tree works perfectly. I doubt a quad tree is going to be necessary for a side-scroller, though. Simply splitting the map into non-recursive sectors is probably enough. You seem to be looking for the strict definition of how a quad tree should be implemented, but it really depends on what you're using the quad tree pattern for.
[/quote]

So are you talking about like a grid/tile based collision detection then? One of my questions was how do you up date that grid/list with moving objects? Seems like Updating every item's grid location would be just as fast as collision testing every item, so is there a faster way? or is that some how more efficient?

##### Share on other sites
SriLumpa    198
[quote name='Unorth' timestamp='1312747246' post='4845878']
Seems like Updating every item's grid location would be just as fast as collision testing every item, so is there a faster way? or is that some how more efficient?
[/quote]

You can update only the ones that move. If you have a lot of non-moving objects, that makes a difference.

Also, even if an object moves, it may still stay in the same cell.
And you do the check/reposition only once per object, that's less than testing every object against every other object.