Relminator, OK, is there example code or pseudocode out there for using a K-D Tree to store regions? It seems like a pretty large divergence from the way K-D Trees are presented around the web. Handling dynamic entities that are moving in and out of tree nodes frequently and overlapping multiple nodes is a problem that I don't immediately see the solution to.
Riven, if my question annoys you, you can go somewhere else. Trees are used for collision detection in professional games, this is not a purely academic question, and optimization of such trees is a problem that has been well studied, I just can't find the publications that discuss that optimization. Asking how best to optimize a spatial tree is a perfectly on-topic question for this forum. You don't know the answer and rather than just not comment, you insist that I shouldn't want to know the answer myself.
The quadtree and octree example I posted above has a basic source on how to store data at the nodes. That's also the way how to store data on a kd tree.
Riven's posts are actually good ideas. Your entities are dynamic(moving) every frame. While quadtrees are fast at querying where an entity is, building it in realtime will take a veeeery long time.
His suggestion of using grids for moving entities us the best posted so far.
Btw, building a kd-tree in realtime is also very slow.