Jump to content
  • Advertisement
Sign in to follow this  
Unorthodox

Quad Tree Help - 2d game

This topic is 2539 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've tried to bold the key points so you can skim this.

I working on making a 2d, fast paced side-scroller/ platformer. I'm relatively new to game development and I'm just getting to the collision detection of the game. I've decided to use a quad tree to reduce the number of collision checks and for drawing the onscreen world(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.

My understanding of a quad tree:
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

Questions:
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.
For question 5, 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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
Share on other sites

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.


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 this post


Link to post
Share on other sites

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?


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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!