Collision detection for 2D RTS game in C++

Question

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.

Answer 1

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.

Answer 2

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