# QuadTree for 2D collision detection

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

## Recommended Posts

Hi,

I'm currently working on a 2D shoot them up type of game, and I'm using a quad tree for my collision detections. I wrote a working quad tree that correctly pushes my actors into the nodes/leaves they belong to in the tree. However I've got a few problems. Firstly, how do I actually use my quadtree to select against which other objects an object should test collisions ? I'm unsure about how this is done. Which brings up a second question. Say I have an object in node that is not a neighbor of another node, but that the object is large enough that it spans a few node, how can I check for an actual collision, since I'm guessing the tree might consider it's not close enough to collide with objects in a "far away" node ? Should objects that don't completely fit in a node be kept in the parent node ?

This is the type of game I am making:

Most of the objects are of different sizes and moving arround.

I've read a good number of blogs/articles about quadtrees but most just explain how to build a tree which is not really what I'm looking for. Any help/info is welcome.

Thanks.

##### Share on other sites
If an object overlaps a node, you should put it in that particular node. Which means an object may belong to multiple nodes.

You can do broad-phase collisions using quadtrees and do an aabb or sat for narrow phase one.

However, quadtrees or even any broadphase collision is kind of an overkill for a shmup.
A brute force aabb or sat should do the job well even for shmups with thousands of bullets.

My game here is made on the Nintendo DS and guess what I use? Brute force AABBs and SAT.

If you really want good optimization in these types of games then use SAT or "sweep and prune" your AABBs.

[Edited by - relsoft on December 14, 2010 6:01:48 AM]

##### Share on other sites
I'll try out the SAT and aabb and see if I need a broad phase or not.

But if however I was using a quad tree, and my spaceship is in a tree quad, how would I recurse my tree to get a list of objects I might have collisions with ?
Plus in that case, I'd probably need to either, as you suggest, add larger objects to more quads, or leave them in the smallest node that contains them.

I'm just unsure about how I can get my list of objects from the tree. It seems a little different from using a quad tree for culling.

##### Share on other sites
For objects that span multiple nodes, you will want to place that object in the parent node.

As for selecting from the QuadTree I use an API like this:
public Set<Entry<T>> getObjects(Rectangle rect, Set<Entry<T>> objects );public Set<Entry<T>> getObjects(Line l, Set<Entry<T>> objects );public Set<Entry<T>> getObjects(Circle circle, Set<Entry<T>> objects );

These functions recurse down the QuadTree asking each node if it intersects with the supplied geometry. Once it intersects, it will ask each Object on the node if it collides with the geometry and if so, add it to the Set of objects to be returned.

For dynamic objects, you will want to pop and push from the QuadTree each frame (if the object is moving of course). A nice trick is to cache the node in which the object is stored in so popping from the QuadTree is O(1).

Hope this helps.

##### Share on other sites
Quote:
 Original post by dotminicI'll try out the SAT and aabb and see if I need a broad phase or not.But if however I was using a quad tree, and my spaceship is in a tree quad, how would I recurse my tree to get a list of objects I might have collisions with ?Plus in that case, I'd probably need to either, as you suggest, add larger objects to more quads, or leave them in the smallest node that contains them.I'm just unsure about how I can get my list of objects from the tree. It seems a little different from using a quad tree for culling.

Actually it is much similar. You recurse from parent to child, when you are in the node the current object resides in, you could test all the objects contained in that particular node for collisions. You however should also check the objects contained in the adjacent nodes.

But really, you're over thinking this problem. I mean R-type is not known to be collision heavy.

##### Share on other sites
Quote:
 Original post by relsoftBut really, you're over thinking this problem. I mean R-type is not known to be collision heavy.

That was sarcasm right?

##### Share on other sites
Not really, It was an advise. I've been making these types of games for years and I haven't really encountered a situation where I needed quadtrees. Even for some of my bullet hell games, brute-force aabb and sat should be more than enough.

##### Share on other sites
After a few test, the Quadtree solution seems a little overkill, there are not enough actors, so I seem to "waiste" time recursing down the tree. The results are only slightly better than brute force aabb.
I'll try out the SAT and see how that works.

##### Share on other sites
dotminic: are your levels very linear in one direction, such as in R-type? If so, you might want to consider a bi-tree instead of a quad-tree. I don't know if that's a technical term or not, but it should make sense; just split up your world in half down the middle, then in quarters, etc. Each node has two children.

##### Share on other sites
Last time I tried this in 2D, I found that brute force AABB culling then SAT with potential pairs outperformed any kind of spatial partioning based on actual profiling but YMMV.

1. 1
2. 2
Rutin
22
3. 3
4. 4
frob
16
5. 5

• 9
• 33
• 13
• 13
• 10
• ### Forum Statistics

• Total Topics
632580
• Total Posts
3007186

×