# Quadtrees + Collision Detection

This topic is 4283 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I've got a quadtree add / removing working but now I don't get how to effectively move objects / check for collisions with other objects. To Add: Does it fit into the current node (start at the root): - Yes: return check on all of my children. - No: Add it here. To Remove: Every object has a pointer to it's node, then I just remove it from the list and re-add it from the tree. This is how I update the object's position in the tree. Add / Remove seems to work just fine. Now I need to iterate through all the objects for their collision checks but I don't get why it's any faster. Let's say Object A is in the root node's list (it's right in the centre of the map). Now let's say Object B is in the root node's northwest node's list.
     |
-   |
|B|  |
- -----
|   |
---| A |-----
|   |
---
|
|
|

(hope this turned out)

Object A could very well be touching Object B, but if I'm only looking at Object A's node's object list, I'm never going to see Object B cuz its in one of its children. So for every object, you gotta find every node that that object could be touching (if you're in the root, that's every other single node). There's no way that's more efficient then just looping through every object after you do all the calculations and stuff to figure out what nodes this node could be touching. I gotta be missing something fundamental here cuz this just doesn't make sense. Please help :(

##### Share on other sites
Typicall in quad-trees your nodes contain EITHER child nodes OR object lists. I believe a node containing child nodes is a 'branch' and a node containing objects is a 'leaf'.

And you don't just check the object list for the node your Object A is in, because as I think you were hinting at, objects can straddle multiple nodes.

When I want to know how many objects are potential collision candidates I'll start with the bounding sphere for that object. I pass that into the root node of my quad tree. Each quadtree node has its own sphere (remember sphere-sphere checks are very cheap to do) and I move down the list with some simple logic. If a quad-tree sphere was entirely inside the object's sphere (ie, large object w/small quadtree nodes) then ALL the children of that node are potential candidates (you could choose to optimize out further checks down the tree, but I tend not to).

If the node's sphere just intersects the object's sphere, or the object's sphere is inside the node's sphere (assuming you make that kind of distinction) then further testing is necessary. At that point I'll do a sphere-box check (still pretty cheap if you're using AABB) since the sphere checks produce more positives than needed, especially when your tree nodes are more rectangular than square.

Same rules apply on that level, if it intersects then all the children are analyzed, and that is where the recursion comes in. Hope I explained that well.

##### Share on other sites
Does it fit into the current node (start at the root)

You may be missing part of how quadtrees work. Every point should fit in the root node.

##### Share on other sites
ItsDoh, I think your description of a quadtree is a bit off. There are quadtree implementations that contain object lists in nodes besides the leaves. In fact I'm having trouble thinking of any case where it would make sense to store object lists only in leaf nodes (edit: this makes sense when the quadtree is being used to store points). Using bounding spheres is entirely optional and not necessarily faster because it will cause false negatives for intersection tests and possibly false positives for containment tests depending on the shapes of the objects.

The reason why quadtrees can speed up collision tests is that for N objects there are N*(N-1)/2 pairs to check for collisions. In most situations the objects will be scattered over the game world and will therefore be in entirely different parts of the quadtree. Instead of checking every pair for intersections you only need to check the pairs that are in intersecting nodes in the tree.

For a small number of objects it isn't worth it because it is much faster to check all N*(N-1)/2 pairs. For a large number of objects scattered over the landscape using a quadtree or other spacial partitioning scheme is indispensible. If you have 1000 objects then that's nearly half a million pairs to check for collisions. Spatial partitioning schemes can reduce that number greatly. Even if there are 999 enemies to check for collisions with one player, it can still be faster to use the quadtree than to perform 999 checks.

There's a version of quadtrees called "loose quadtrees" where objects of a certain size are always placed in the same level of the tree regardless of their position. This can be useful for dynamic objects since you can avoid having to determine what level the object should be placed on and it eliminates "hot spots" like the center of the quadtree. (edit: is there actually a difference between "loose quadtrees" and hierarchal grids? the more I think about it, the more I think they're the same thing)

[Edited by - Vorpy on January 28, 2007 7:03:06 PM]

##### Share on other sites
Quote:
 Original post by Vorpy(edit: is there actually a difference between "loose quadtrees" and hierarchal grids? the more I think about it, the more I think they're the same thing)
They're different in as much as one is a tree and the other is a number of grids. A tree has a root and a hierarchical grid does not. Trees are frequently pointer-based whereas grids are not. However, if you linearize the loose octree/quadtree and chop off the root (only retaining the last k levels) then you basically end up with something that's a hierarchical grid. It is reasonable to pose the question: at which point during this "optimization" does the loose octree/quadtree turn into a hierarchical grid and cease to be a loose octree/quadtree? I think the only sensible answer is the counter-question: how long is a piece of string?

##### Share on other sites
Vorpy, I'm aware you can maintain lists at each level, but going back to the original problem he seemed to be thinking there was no reason to check beyond the root node, or he didn't realize the root node encompassed the entire region, I'm not sure which.

And I thought I'd explained that bounding spheres were only as first-stage intersection test, you should of course then continue with more accurate to the geometry tests if the sphere-sphere checks come out true.

1. 1
Rutin
31
2. 2
3. 3
4. 4
5. 5

• 13
• 53
• 11
• 10
• 14
• ### Forum Statistics

• Total Topics
632967
• Total Posts
3009553
• ### Who's Online (See full list)

There are no registered users currently online

×