I'm trying to use a quadtree for 2D collision detection, but I'm a little stumped on how to implement it. First of all, I'd have a quadtree which contains four subtrees (one representing each quadrant), as well as a collection of objects which don't fit into a single subtree.
When checking an object for collisions in the tree, I would do something like this (thanks to QuadTree for 2D collision detection):
- Check the object for collisions with any objects in the current node.
- For any subtree whose space overlaps the object, recurse.
To find all collisions within a quadtree tree:
- Check each object in the current node against each other object in the current node.
- Check each object in the current node against each subtree.
To insert into a quadtree:
- If the object fits into multiple subtrees, then add it to the current node, and return.
- Otherwise, recurse into whichever subtree contains it.
To update a quadtree:
- Recurse into each subtree.
- If any element in the current node no longer fits completely in the current tree, move it to the parent.
- If any element in the current node fits into a subtree, insert it into the subtree.
Is this alright? Can it be improved?
Your quadtree structure isn't optimal. You're right to store 4 subtrees per node, but actual objects should only be stored inside the leaves, not inner nodes. Therefore the collection holding the actual objects needs to be moved to the leaves.
Let's have a look at the implementation of the operations:
Check if the object intersects the current node. If so, recurse. If you've reached the leaf level, insert the object into the collection.
Execute the exact same steps as if inserting the object, but when you've reached the leaf level delete it from the collection.
Execute the exact same steps as if inserting the object, but when you've reached the leaf level check for collision with all the objects in the collection.
For every object in the quadtree execute the single object collision test.
Delete all objects from the quadtree whose position has been modified and insert them again.
This has several advantages:
Only disatvantage: