I created a dynamic QuadTree and I wanted some feedback. (.net & on github)

[ggggggggggggggg]

Sorry if this isn't the right place to post this. I wasn't sure if "project" meant a full game or a literal meaning of the word.

Hi! After working on it for a few days I think I have a bug free dynamic QuadTree.

Github link: https://github.com/asusralis/QuadTree-for-SFML.NET

I would love suggestions to speed up its performance. I recently just made the remove method faster by having each object keep a list of references to all nodes its contained in. That made dynamic objects preform a lot better.

Also, this is my first Github project so I'm not sure if I set it up correctly. =/

[Ungod]

I just took a quick look and it seems like you're just storing items in leaves which usually means that you store them more then once in different nodes. Is that right?

While whether this is good or not depends on the usage of the tree, I personally found that solution not so satisfying when dealing with high numbers of items. What I did instead is storing items in the deepest inner node (on path from root to leaf) that totally contains the entity. This would be a clear assignment and its ensured that each item is exactly once in the tree.

Not a very profound comment, but you may want to think about it.

[Mörkö]

I don't understand why the extra step is necessary:

private bool IsMaxDepth
{
     get
     {
          if (CurrentDepth == MaxDepth)
               return true;
          else
               return false;
     }
}

Why not just?

return CurrentDepth == MaxDepth

[ggggggggggggggg]

I'm not sure if you can respond to comments so I'm going to use @.

@Ungod

Why is that not satisfying when working with higher objects?

@Mörkö

Yep, you're right! I changed it. Thanks.

[Ungod]

Why is that not satisfying when working with higher objects?

The tree requires more space, because you store every item in multiple nodes. That results in higher RAM usage and longer operation-times (like retrieve) on the tree at all.

Additionally I had the problem following problem: Lets say I have a rect and I want to do a usual operation like retrieve objects from the tree that may collide with that rect. So you have something like a list that you fill with objects from the appropriate nodes.
The problem I see now with your approach is that you have to check whether an object is already in that list or not since they can occur in multiple nodes.

[ggggggggggggggg]

The objects in the QuadTree are just references, no? There no actual data stored in the QuadTree. It's all a reference to your objects that are stored in your main gameobject list. So I'm not sure why that would be so bad on memory. I guess I could just have the QuadTree store a reference to the IQuadTreeItem interface, not the object itself. Do you think that would be actually worth it, though? And if I did that I would still have to have a reference of the gameobejct inside the interface... So doesn't that defeat the purpose of the original fix?

Why is that not satisfying when working with higher objects?

The problem I see now with your approach is that you have to check whether an object is already in that list or not since they can occur in multiple nodes.

You have to store an object multiple times if the object is on the edge of the node it is contained in. That's why I check for intersecting instead of contains. If an object is in more than one node then each node that the object intersects must check collision for that object. Because if that object is in  another node then it might be colliding with the objects in the other node.