Broad-phase collision detection methods?

user_117069 0
Viewed 25166

I'm building a 2D physics engine and I want to add broad-phase collision detection, though I only know of 2 or 3 types:

  • Check everything against everything else (O(n^2) complexity)
  • Sweep and Prune (sort and sweep)
  • something about Binary Space Partition (not sure how to do this)

But surely there's more options right? what are they? And can either a basic description of each be provided or links to descriptions?

I've seen this but I'm asking for a list of algorithms available, not the best one for my needs.

In this case, "Broad phase collision detection" is a method used by physics engines to determine which bodies in their simulation are close enough to warrant further investigation and possibly collision resolution.

broad-phase collision-detection physics algorithm
10 Answers

I would like to recommend the introductory reference to game physics from Ian Millington, Game Physics Engine Development. It has a great section on broad phase collision detection with sample code.

user_618420
Related