Collision detection: Neighbour checking

This method allows us to only check objects that are in the approximate same area as each other. It can be achieved by checking which neighbourhood of our game a given two objects are in, and then only performing the more CPU intensive collision detection if there is a realistic chance that a collision could occur.

Suppose we have 10 objects that each need to be checked against each other, then we need to perform 10 squared (100) collision checks. If we do neighbour checking first, we can significantly reduce this number. In the very hypothetical situation in the diagram, we would only need to do an absolute maximum of 11 collision checks, instead of 100, for our 10 objects, if we first check to see if objects share the same sector.

Implementing this in code can be as simple as having a sector member variable for each game object, then looping through the list of objects and just checking when they are in the same sector.

Whichever method(s) of collision detection your game uses it is almost always worth doing the neighbor checking of some sort. Sometimes, if your collision detection method is quite intensive, it can be worth performing a less intensive(and probably less precise) collision detection method and when that less intensive method detects a collision, perform more intensive version.

For example in the Crossing number algorithm tutorial we use rectangle intersection as a preliminary check.