Quick and Dirty Collision Detection

Just a quick note regarding collision detection.

In bullet hell shooters, or any sort of plausible physics-based game, you're going to be doing collision detection.  The naive way of doing this is doing circle-circle (or sphere-sphere) distance detection for each object onscreen colliding with each other object.

This works fine for small numbers of objects.  Where you are going to start running into performance problems with this sort of game is going to be in collision detection, if you want all objects to be collidable with all other objects. 

So for 1000 objects onscreen, you'd be looking at ~1 million collision calculations per tick. In my experience, "naive" collision detection starts running into problems at around 300 objects.

The reason for this is because collisions are exponential.  For each new object, it has to be collided with all other objects in the system. 

So then you get into different sorts of ways to whittle down the collision number, including "binning" or dividing the screen up into N squares, ideally somewhat larger than the individual object's collision box. However, even if you just divide it up into quadrants, that will usually work just fine for any type of sane collision algorithm. There are edge conditions on the borders of the boxes but they are just not noticeable.

Here's a really simple way of binning. Give each object a quadrant, zero through three. When the object moves, its screen quadrant gets updated. On collision check, check first if the two objects' screen quadrants are the same. If not, don't bother doing the collision check. In one way, this seems inefficient because you're only cutting the problem up in four. If you use more bins, you will be able to push more collisions, but then the binning code gets a fair bit more complicated. The advantage the quadrants have is that you have fine-grained collisions the vast majority of the time.

There is going to be a point where this no longer matters, when we can collide eg. 1680x1024 pixels against each other in real time, using the naive approach.  That seems impossible-- a million squared distance calculations-- but it's not a moving target so eventually the doubling rate of computer speed will surpass it.  If we ever get there.


Obviously, in the shot from Geometry Wars below, they're not colliding the particles (sparks) with anything.  But they could.  If they were doing a naive collision, action like this would be unplayably slow.  But with binning, you could actually do that sort of collision if you wanted to.  Modern computers have huge power, but exponential growth will always bring them to their knees at some point.