Sign in to follow this  
dotminic

QuadTree for 2D collision detection

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: http://www.youtube.com/watch?v=GFxuI7cBFhQ
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 this post


Link to post
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.

http://www.youtube.com/watch?v=xuPRiI41BBs

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 this post


Link to post
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 this post


Link to post
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).

An example implementation may be found here: http://myriad.cvs.sourceforge.net/viewvc/myriad/Myriad/src/org/myriad/shared/ds/

Hope this helps.

Share this post


Link to post
Share on other sites
Quote:
Original post by dotminic
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.


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 this post


Link to post
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 this post


Link to post
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.
Thanks for the advice guys.

Share this post


Link to post
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 this post


Link to post
Share on other sites
TheOrzo: Yeah I thought about it.

After trying a few different scenarios, I think I'll just go with a basic grid. Quick to code and performs just as good as any other spacial partitioning.
In any case, be it a quadtree, or brute force or something else, I'm getting pretty much the same results. I don't have enough collisions to test that it causes a bottle neck.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this