Sign in to follow this  

Associating an external 2d grid environment to a quadtree

This topic is 3728 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

Hi everyone, I'm making a grid-based 2D game, and I wanted to use a Quadtree (Warnock tree) for collision detection. I'm having some problems with my QuadTree, however. My main issue is that I'm having difficulty coming up with a generic solution to associate my grid cells to quad tree nodes. I've already read the the articles here on GD.net and a few forum posts (they were helpful) but I'm still stuck. In my project, I have a 2D array, which represents my 2D grid: #define DEFAULT_MAP_SIZE 8 MapCell Grid[DEFAULT_MAP_SIZE][DEFAULT_MAP_SIZE]; I have a QuadTree, which is made up of QuadTreeNodes: struct QuadTreeNode { QuadTreeNode children[4]; bool bHasChildren; vector<MapCell*> mapCellList; } class QuadTree { QuadTree(int level); QuadTreeNode* parent; } At the highest level (level = 0), there is only one quadtreenode which has 4 children... at the next level (level = 1), there are 4 quadtreenodes (each of which have 4 children), at the next (level=2), there are 16 quadtree nodes, etc. At the lowest level there are DEFAULT_MAP_SIZE*DEFAULT_MAP_SIZE (64) quadtreenodes. I've successfully generated my QuadTree (I did a pre,post, and in-order traversal to verify this), but I'm having trouble coming up with a generic solution to populate mapCellList: // pass in a 2d map cell grid to associate with the quadtree void QuadTree::AssociateWithMapCells(MapCell** grid) { ? ? ? ? } I'm thinking along the lines of a recursive solution for AssociateMapCells(), but I'm not sure how it would go. Can someone lead me into the right direction?

Share this post


Link to post
Share on other sites
To do it recursively, you'd pass in one MapCell at a time, and the call would recursively delegate to the appropriate child. Honestly, though, a quadtree here seems like overkill. What functionality do you need from your spatial culling structure which the grid spatial culling structure does not provide? It's sure great at collision detection when objects don't each occupy many grid cells.

Share this post


Link to post
Share on other sites
Thanks, that makes sense.

Though, the main issue I seem to be having is, given a 2D index of a MapCell (say, 1,1) -- how do I determine which quadrant it belongs to?

Share this post


Link to post
Share on other sites
Ah, yes, that's a fundamental key part I missed!

So I determine the min and max "bounding box" of each quadtree node, and then with that I can associate the proper MapCells.

Thanks!

Share this post


Link to post
Share on other sites

This topic is 3728 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this