quadtree

[bcvz]

Hello,
I have build a region quadtree class which manages itself, without having to insert objects to it every frame.
This is the first time I build a Quadtree, also my first template class in C++.

It tracks objects bounding rect every frame and update their position in the quadtree.
The quadtree has infinite levels.

Quadtree.h
http://pastebin.com/0LjAHgM7

Qtree.inl
http://pastebin.com/S6vHFCyk

I've tried to make it the fastest possible.
It only updates objects positions, and remove wrecks when a quadtree is marked for removal.

If you want to use this quadtree:
-You simply need a class which has "getBoundingRect()" method which returns a floatrect.
-you insert your objects once, and call "manage()" method every frame

know that the quadtree has probably some bugs, I did not test it to much.

there is no collision system yet, you have to implement it yourself

------------------

My goal is to make the Quadtree 99% self managed, I mean we only insert objects, and update it, then we do not care about it.

When I delete an object, I have also to remove it from the quadtree.
I'd like that the quadtree checks every frame if every of his objects still points to something, if not it removes it automatically.
So we won't have to remove ourselves.
I've heard that we can do this combining shared_ptr and weak_ptr but it seems complex...

your advices are welcome

UPDATE:
-no more template
-It now handles collisions and sends you a collision set

Quadtree.h : http://pastebin.com/R07dXQJK
Quadtree.cpp : http://pastebin.com/hPBCLReD
Boundable.h : http://pastebin.com/1W2fbPP7

And I've made a little demo for testing, you can download it here:
https://www.dropbox.com/s/gtlhyv5xedhywhm/Quadtree.rar

Mouse wheel -> changes the limit of objects in quadtrees
Left mouse button -> Adds one object
E key -> Adds 100 objects
R -> Activates / Deactivates random size objects
X -> Clear the quadtree
C -> Activates / Deactivates collision

the performance is not perfect but it's OK

[Ixrec]

My thoughts:

1)

        /*
        -2 = parent
        -1 = this
         0 = upleft
         1 = upright
         2 = downleft
         3 = downright
         */

This should be an enum, not just a comment.  Then you can replace all the magic numbers in your implementation with meaningfully named constants.


2) I don't think the quadtree should be a template class, because it depends on objects having a getBoundingRect() method.  A better choice would be providing an abstract base class called Boundable or something with a getBoundingRect() method, and having the Quadtree take pointers to Boundables.  That makes it far more explicit what assumptions your Quadtree is making, both to users and to compilers.

I guess if you're using C++11 you could have the user pass a lambda to the Quadtree constructor that tells it how to get the bounding rectangle for whatever class Object happens to be, in which case it makes sense as a template.  But even this requires the user and the Quadtree to agree on a rectangle class for the lambda to return, so I'm not sure it's a net gain.


3)

I'd like that the quadtree checks every frame if every of his objects still points to something, if not it removes it automatically.
So we won't have to remove ourselves.
I've heard that we can do this combining shared_ptr and weak_ptr but it seems complex...

It definitely requires some kind of smart pointer.  Unfortunately, weak_ptr requires a shared_ptr, which would force the user to use shared_ptrs for all their collidable object management, which in many cases is completely unnecessary.  If there is a clean solution to this, I don't know what it is.  Hopefully Nexus or someone else does.


4) The Quadtree constructor takes a Vector2f, a float and a float.  That is very odd.  It would make more sense to take either four floats, or a single FloatRect.


5) Why is isMarkedForRemoval() public?  What would the user do with this?


6) draw() sounds like it's drawing all the Objects in the quadtree.  It should be drawDebugRectangles() or something.


7) The get*Count() functions seem very very strange from an API design perspective.  It might be better to make those private functions and instead have a single public method called count() or size() that calls the appropriate private one.


8) Using "Object" as the template class/typename is confusing, because it looks like the name of an actual abstract base class, not of a parameterized type.  T or TYPE or OBJECT would be clearer.


9) And perhaps the biggest thing...

there is no collision system yet, you have to implement it yourself

With the current public API to this class, I don't see how one could be implemented.  The only querying functions are the get*Count()s and isMarkedForRemoval(), which don't really help with collision detection.

[bcvz]

thanks for your thoughts

1 ) I agree

2 ) Yeah it could give more possibilities as you said. I choosed template class because I thought it would be easier to implement for the user, they would just have to add one method to their drawable object and they could use it.

4, 6, 5, 7, 8 ) you're right

9 ) By "implementing" I meaned, modifying the class (I used the wrong word I guess). You could add a method which iterates through all children an checks collisions between objects and insert them in a set of pair.


(sorry for my english)

[bcvz]

Update:
-I've done most of things you said, now the class is composed of Boundable objects instead of template class.
-It now handles collisions and sends you a collision set

Quadtree.h : http://pastebin.com/R07dXQJK
Quadtree.cpp : http://pastebin.com/hPBCLReD
Boundable.h : http://pastebin.com/1W2fbPP7

And I've made a little demo for testing, you can download it here:
https://www.dropbox.com/s/gtlhyv5xedhywhm/Quadtree.rar

Mouse wheel -> changes the limit of objects in quadtrees
Left mouse button -> Adds one object
E key -> Adds 100 objects
R -> Activates / Deactivates random size objects
X -> Clear the quadtree
C -> Activates / Deactivates collision

the performance is not perfect but it's OK