Original Post
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.
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.
