How to store game objects in quadtree efficiently

Question

I'm implementing a quadtree structure, for simplifying collision code,. but I'm unsure as to the best practice for doing so. Currently, the quadtree creates subtrees during setup down to a preset maximum depth, then I insert objects into its appropriate tree, for use in pair generation(the actual maths stuff). However, I've heard of other approaches, which only generate subtrees when a certain number of objects are stored. I know my method has a space overhead, but might be computationally faster during update cycles. What would be the best way to handle it?

Answer 1

One approach is to store k elements in each node, starting with one parent node which spans the entire collision space. When inserting element k+1, you subdivide the space and place the new element in the correct quadrant.

Additionally you can use this approach to statically allocate the data structure, assuming you know the maximum number of nodes that will be used, and that there will be some maximum density. This requires a fixed array of nodes and elements to be allocated for the life of the application, but it avoids costly dynamic allocations, which should be a speed gain.