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.

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]

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.

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.

Quote:Original post by relsoft
But really, you're over thinking this problem. I mean R-type is not known to be collision heavy.

That was sarcasm right?

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.

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.

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.