SFML community forums
Help => General => Topic started by: didii on February 25, 2014, 04:20:30 am
-
I'm currently trying to implement a Quad Tree, the first example I've seen from it gave me the idea a Quad Tree is this:
Divide the playground in fixed equal squares and see in which one an object resides. For a collision check, only the objects in the same square are checked. According to the picture: only the same colored shapes will be checked for collision. If an object resides in multiple squares at once (such as the triangle) collision is checked for all objects in all squares. Optimization is done by correcting the size of the squares.
(http://s18.postimg.org/vkh0kiyxx/Quad_Tree.png)
However, after some more searching I found that it was rather done using a recursive way:
Start with one square and divide it in four equal parts if more than N amount of objects are placed within it. All objects now go to a child square. Every part is again a Quad Tree and thus behaves the same as its parent. The dividing process keeps happening until all objects are placed or a maximum depth has been reached. Optimization is done by correcting the maximum amount of objects and the maximum depth.
So my question: what are the benefits of the one over the other?
These are my thoughts:
Properties of first Quad Tree
- Pro: Indexing a shape on a fixed raster is not an expensive task.
- Con: The number of objects returned from a square is uncertain which results in a less stable performance when a lot of objects are close to each other.
Properties of second Quad Tree
- Pro: When getting all objects which might collide. You are certain about the maximum number of objects it can return resulting a more stable performance.
- Con: However, when the maximum depth was reached, the certainty of the previous pro disappears.
- Con: It would need to recalculate the place of objects every time a square needs to split which means the first couple of objects added will check collision several times with the Quad Tree.
- Con: It constantly has to create and destroy Quad Tree objects for moving objects. And as far as I'm aware, creating and destroying objects is an extensive process.
- Con: When 2 objects are about to collide, chances are higher that it needs to divide right at that moment which is bad for performance and could possibly break the collision if it results in a frame drop.
Where Quad Tree 1 is the obvious winner.
-
Seems you are thinking backwards. You found some data structure (somehow its a habit in many internet-forums to tell everyone to make an octtree/quadtree first), you only half understand it and then you try to find some problem to apply it to, when normally you should have a problem first and then try to find a good solution. This will only complicate your program for no gain if you dont have a huge number of objects.
Calculating some bounding spheres to test against each other is much easier and if its really too slow after completing your game and profiling you can still change it.
-
That might or might not be the case. I'm simply interested in the differences between both quadtrees, regardless of whether I should or should not implement it :)