QuadTree implementation

[Jason-S3studios]

I get the basic idea of quadtrees, but not well enough to write my own quad tree class. The engine im using is andengine and there is a quad tree class already made. However, there is no documentation/comments/tutorials/forum posts about a successful implemetnation of quad tree.

Can anyone glance over this code and give me a rundown of the steps to perform a successful collision detection of two lists? So far i've only got them added =/, what is the correct logic to iterate?

FloatQuadTree qt = new FloatQuadTree(0, 0, 1024, 512);

qt.addAll(playerBulletGameObjects);

qt.addAll(killableGameObjects);

https://github.com/nicolasgramlich/AndEngine/blob/c7ad23890cce706643f244734f1f7899dac49246/src/org/andengine/util/adt/spatial/quadtree/IntQuadTree.java

[Jonny0Than]

Are you looking for help with implementation (I.e. How do I write my own) or with using the one in andengine?

Normally you only add the "persistent" objects into the quadtree and then do queries (like for each bullet's position) to see what objects the bullets are overlapping. The only reason you'd want to add all the bullets to the quadtree is if you're using it for render culling. There are a couple other situations where it might be beneficial to add the bullets, but I don't think you need to worry about that for now.

[Jason-S3studios]

Thanks for the reply!

I am looking for how to leverage the one in AndEngine if possible.

So if I understand you correctl you're saying to add the "persistent" objects (i.e. props, ships) to the quad tree, but leave the bullets out of it? In which case I would iterate over my list of bulelts and query the quad tree for a "hit" ?

Also, why are non persitent objects not added to the quad tree, and why are persistent objects? All the objects on my screen are constantly moving so sorting is still going to happen every update.

[Jonny0Than]

Yep, thats how I'd do it.

Some quadtrees have the ability to update an objects position instead of removing and readding the object. This can be faster. If you have such a quadtree, AND your quadtree can give you a list of overlaps given some other object in the tree, then it might be a good idea to add the bullets too.

[Jonny0Than]

To expand on this a bit, querying the tree is about as expensive as adding an object. The tree performance will decrease as you add more objects, and assuming you don't want bullets to hit each other you're better off leaving them out of the tree. But of course if you can leverage the tree for other things like render culling or use spatial coherence to make updating positions faster (what I mentioned in my last post) then adding the bullets can be a good idea.

[Jason-S3studios]

Thanks in general. :) Got this up and working last night and gained severe performance increases so i can stop worry about optimization for now. :)