If you’ve looked at my air hockey code, you’ll see that I do very simple collision detection; each ball checks itself against the boundaries of the field, the goals, and the player’s cursor. However, there is one thing missing — collision between multiple pucks.

Wikipedia explains:

The obvious approaches to collision detection for multiple objects are very slow. Checking every object against every other object will, of course, work, but is too inefficient to be used when the number of objects is at all large.

Say you run my air hockey code and change the number of pucks to 25. If I were to implement inter-puck collisions, to check each puck against one another, that would take 300 operations (25 choose 2). With 50 pucks, 1225 operations would be needed. The more pucks you have, the more cross checks you’ll have to do and inefficiency will grow.

For a real world example, take online computer games. The majority of games check to make sure your character stays within the boundaries of the game world, but how many games check to make sure you’re not standing on top of another player? It’s not impossible to do, but the extra computing isn’t always worth it.

Advertisements