I have created a quadtree that I use to sort entities in my game's world. They are designed to have an extra list pointer used for a shortcut during more accurate collision tests later on. When ever an entity is moved it's re-sorted into the quadtree. If it coincides with other quadrants I just place it in the parent/root node of those quadrants instead. The root (e.g. the entire world) node contains a pointer to the entities as do the children. I figured that since the quadtree IS sorting I should take advantage of it. The down side to this is that each child doesn't really know where the list stops as of yet. So a little problem there.

When an entity moves and gets sorted, I check if the current node(quadrant) has any other entities in it. If so, I use the short cut pointer and link it to a semi-global list of quadrants to check for possible collisions. The down side to this is that a quadrant may not have one or more nodes after a full update (i.e. all entities are moved/updated). So then I could be wasting my time with quadrants that only had one entity for example. One idea I had was to update all entities first then the player, but that just avoids the problem for a short time and isn't a complete solution. Any body got any better ideas?

I was also thinking about storing the quadtree as single dimension array in hope to speed things up a little. Instead of using pointers, I use an index. Leaving me with just a simple "i = index" loop. Maybe using an index of -1 to denote a leaf, end or something else special. I had a similar concept for BSP collision detection where each model stores a BSP tree in an array referencing it's geometry. I only see this working if I have a static meshes(i.e. no skinned meshes or anything like that) though.

Using that quadtree I believe I can get some pretty accurate results and decent frame rates. Theres just a few little holes in my logic I'm struggling with. So any help or advice would be greatly appreciated.

No ideas? I guess I'll have to figure it out by my self. Oh well, atleast some people read this. Maybe I'm going about it the wrong way... (the algorithm that it)

I am sorry that you didn't get any help, it happens.

I believe the main reason you haven't received any advice is that your system apparently works and you are worrying about empty quadtree nodes for some reason.

Lastly, and this is meant to be contrsuctive, it is hard to understand your question and explanation when you interchange nodes, quadtrants, entities too easily in your description. While your system may make sense to you, your description lacked clarity to really get where the problem may be occuring.. if there is a problem (empty nodes, means nothing to test against,, not much lost time there).

Yeah, I don't grasp what you are trying to ask here. It seems that you already understand quadtree well, but I'm not exactly sure what you are asking.

Yeah... sorry. I get that all the time where I try to read a description and can't understand it or feel completely lost. So please, bear with me.

Im trying to use a quadtree to aid in collision detection. I have entities(things in the world such as player, enemies, etc.) that are sorted in the quadtree. If a quadrant has more then one entitiy, it flagged and added to a "check for collision" list. Once all entities have been processed I may finally go through that list and check for collisions. Get me? The problem is that one entity may not be in a given quadrant after it had been processed, but the quadrant will still be flaged as such.

In my quadtree, I don't flag nodes/entities in any kind of "check for collision" list. Each node stores an empty/nonempty flag, which is used to test for a "terminate search, no need to descend further" condition.

When I find potentially colliding pairs, I simply start from the quadtree root, and descend through all nodes in the quadtree, collecting the potentially colliding pairs as I go. The search stops at each node (and goes back up to visit another unvisited branch in the tree) that was flagged empty.

I was also decribing a possible solution using arrays. My quadtree is fixed in size and depth. 2048x1024x512x256 or something like that. All the nodes add up to 256 i think. My solution was to have an array of 256 elements(bytes or somthing more) and memset it every time I run the loop. The quadtree is also stored in an array, maybe the same one, didn't thoroughly think this one out yet. When an entitiy updates its position, I *could* use an old tile/grid-based technique to find the tile(in this case, quadrant) the entitiy is in. I then go to the corresponding element in my array and add 1. If its value is geater then 1 it will be flagged and added it to the list for possible collisions.....

Wait a minute... I don't have to do any of this. All I have to do is that same thing I've been doing. I get it now. The list of quadrants to check can simply be a double linked list. After processing all the entities, there will still be a list of quadrants to check. But I was worried that this information may be incorrect, but it won't It won't be, because I can simple insert or remove the "said" quadrant onto this list at anytime. Its just an additional check after processing and entitiy if a quadrant is crowded or not. It wouldn't even matter if an entity left a quadrant, just as long as I remove it from that stack as it leaves. Kinda like COM's refference count. I dud its!

Actually, I've decided to abandon quadtrees and use a SAP(Sweep and Prune) method. Sadly, most articles I've read the authors were more indent on showing off their intellects and technical jargon then actually conveying meaningful information. Then again I could just be over thinking it.

With out a full understanding of SAP, I broke it down into two parts: sort and query. From what I've read so far both are done together. I sort pairs of end points(starting and ending) in a list(from least to greatest?) for each given axis. After that I'm lost on how the information is used to detect collisions. I understand that some maybe overlapping, but how to detect, is what I'm uncertain with. Am I suppose to just loop through the array using a simple AABB routine on each element? That doesn't sound right nor does it sound any better then brute force. So there must be something I'm not quite understanding and the tutorials I've seen so far aren't explaining it clearly enough. At least not for me...

Any takers?

grid registration
simple, fast and easy
I feel you are getting lost in old gamedev or academic articles
They are often a colossal waste of time written by people drinking too much coffee - ignore them and use common sense
KISS
Remember the best software engineers barely type any code ... and get awesome results

(edit)
hierarchical indexes (quadtrees/octrees) are really only used by beginners, they are a "rite of passage" for newbie game developers
just check for recent forum posts about them from pro developers ...

just because something is hierarchical doesn't mean it is "magic" and is going to work well

here is one example (of many) of hierarchical systems being dumped:
http://www.slideshare.net/DICEStudio/culling-the-battlefield-data-oriented-design-in-practice

and my unimpressive blog post showing one way of performing grid registration http://skytiger.wordpress.com/2011/01/30/spatial-index-using-3d-grid-registration/