Is there a faster algorithm for collision detection?

Question

I'm writing this game on Android where I have a bunch of characters moving around who collide with each other. Everything works fine but when I get passed a certain number of characters on the screen at the same time, the performance of the app gets hit severely. I did my tests and drawing is not causing the low frame rate, it is the algorithm for collision detection, since every time they move they have to check their location to all the other characters. So currently I'm just looping through them all for each character. Is there a way to improve on this? Is there a performance trick to collision detection on a big number of objects that I don't know about?

Answer 1

Yes, there is a technique based on a first broad-phase and second narrow-phase colission detection.

I'll quote some paragraps from: Beginning Android Games, by Mario Zechner.

Broad phase: In this phase we try to figure out which objects can potentially collide. Imagine having 100 objects that could each collide with each other. We’d need to perform 100 * 100 / 2 overlap tests if we chose to naively test each object against each other object. This naive overlap testing approach is of O(n^2) asymptotic complexity, meaning it would take n^2 steps to complete (it actually finished in half that many steps, but the asymptotic complexity leaves out any constants). In a good, non-brute-force broad phase, we try to figure out which pairs of objects are actually in danger of colliding. Other pairs (e .g., two objects that are too far apart for a collision to happen) will not be checked . We can reduce the computational load this way, as narrow-phase testing is usually pretty expensive.

Narrow phase: Once we know which pairs of objects can potentially collide, we test whether they really collide or not by doi ng an overlap test of their bounding shapes.

The broad phase involves dividing the world in large cells, making some sort of grid. Each cell has the exact same size, and the whole world is covered in cells. If two objects are not in the same cell, a narrow phase for those two objects is not needed.

Quote once again:

All we need to do is the following:

• Update all objects in the world based on our physics and controller step.

• Update the position of each bounding shape of each object according to the object’s position. We can of course also include the orientation and scale as well here.

• Figure out which cell or cells each object is contained in based on its bounding shape, and add it to the list of objects contained in those cells.

• Check for collisions, but only between object pairs that can collide (e.g., Goombas don’t collide with other Goombas) and are in the same cell.

This is called a spatial hash grid broad phase, and it is very easy to implement. The first thing we have to define is the size of each cell. This is highly dependent on the scale and units we use for our game’s world.

It also depends on the bounding shape you're using. A simple rectangle or circle around the characters and it's euclidean distance is one simple thing to calculate, but a finer shape (including details as "the head", "the legs" with little additional bounding shapes) will be more a lot more computationally expensive to calculate.