Quick Tip: Use Quadtrees to Detect Likely Collisions in 2D Space - Tuts+ Game Development Tutorial
A quadtree is a data structure used to divide a 2D region into more manageable parts. It's an extended binary tree, but instead of two child nodes it has four.
Read full article from Quick Tip: Use Quadtrees to Detect Likely Collisions in 2D Space - Tuts+ Game Development Tutorial
A quadtree is a data structure used to divide a 2D region into more manageable parts. It's an extended binary tree, but instead of two child nodes it has four.
When more objects are added to the quadtree, it will eventually split into four subnodes. Each object will then be put into one of these subnodes according to where it lies in the 2D space. Any object that cannot fully fit inside a node’s boundary will be placed in the parent node.
Each subnode can continue subdividing as more objects are added.
As you can see, each node only contains a few objects. We know then that, for instance, the objects in the top-left node cannot be colliding with the objects in the bottom-right node, so we don't need to run an expensive collision detection algorithm between such pairs.
public void insert(Rectangle pRect) { if (nodes[0] != null) { int index = getIndex(pRect); if (index != -1) { nodes[index].insert(pRect); return; } } objects.add(pRect); if (objects.size() > MAX_OBJECTS && level < MAX_LEVELS) { if (nodes[0] == null) { split(); } int i = 0; while (i < objects.size()) { int index = getIndex(objects.get(i)); if (index != -1) { nodes[index].insert(objects.remove(i)); } else { i++; } } } }
The
insert method is where everything comes together. The method first determines whether the node has any child nodes and tries to add the object there. If there are no child nodes or the object doesn’t fit in a child node, it adds the object to the parent node.
Once the object is added, it determines whether the node needs to split by checking if the current number of objects exceeds the max allowed objects. Splitting will cause the node to insert any object that can fit in a child node to be added to the child node; otherwise the object will stay in the parent node.
http://en.wikipedia.org/wiki/QuadtreeRead full article from Quick Tip: Use Quadtrees to Detect Likely Collisions in 2D Space - Tuts+ Game Development Tutorial
