Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm currently working on a real time strategy game in C++, and I need to implement a collision detection algorithm. I need to have a very efficient algorithm because this game will be running on mobile devices, and has potential to have many objects on the screen at one time.

I was thinking that a QuadTree might work for this, but then I realized it could be slow since QuadTree's are designed for static objects, and having many objects moving around the Q-Tree might not be optimal.

So I'm wondering what a good algorithm is for detecting collisions? The objects in my game will just have simple axis aligned bounding boxes to check for collisions, so I need a nice spacial indexing system so an object only checks for collisions with objects around it.

share|improve this question
1  
re: "QuadTree's are designed for static objects" No they aren't. A quad tree is exactly what you want for exactly this problem. –  Trevor Powell Feb 2 '13 at 22:44
    
I've read at least 5 sources telling me that QuadTrees are not efficient for moving objects. –  Brad Feb 3 '13 at 5:57
add comment

2 Answers

up vote 7 down vote accepted

Simple spatial hashing will do. Divide your world into equally sized rectangles. Determine the rectangle that the unit is currently in by dividing its position by the rectangles dimensions. Do this for all units, and you will have a list of what units are in which buckets. Then check collisions between units in their buckets and their neighboring buckets.

The performance of this will depend mostly on what size you choose for the bucket, so test out different sizes until your FPS is the highest.

QuadTrees will work, too. In fact, they're closer to the canonical solution for this problem, since in RTS your units will usually not be distributed on the map equally. This is exactly what these dynamic trees are made for. The problem is a QuadTree is a lot more complex than a simple grid, and unless you actually encounter performance difficulties using a simple grid-based solution, you should choose the grid.

share|improve this answer
add comment

If you have AABBs of objects you can use a Recursive Dimensional Clustering algorithm, nicely described in Game Programming Gems, Volume II (by Steve Rabin).

Core idea of a algorithm is to group objects which bounding boxes overlap in one of dimensions and recursively split those groups in means of non-overlapping bounding boxes on other dimensions.

After the process finishes, grouped objects AABBs are colliding, and this may be sufficient considering what you described in question.

I found a nice explanation of this algorithm here

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.