title: What technique should be used to prune 2d collision checks?
body: <p>From the outset, collision detection feels like it is an O(n^2) problem.  </p>
  
  <p>You have a bunch of objects and you need to check if each object is colliding with any of the other objects.  However, I know that it is wildly ineffecient to check each object against all the other objects.  Why do a relatively expensive collision check between two balls if they aren't even close to eachother?</p>
  
  <p>Here is example of my simple program I'm working on:</p>
  
  <p><img src="https://i.stack.imgur.com/H7T2o.jpg" alt="alt text"></p>
  
  <p>If you have 1000 balls then if you went with the naive collision detection you would have 1000^2 collection checks (a million)!  This collision checking has quickly become the bottleneck in my application.  I <em>need</em> to implement some broad phase pruning.</p>
  
  <p>What techniques should be used to prune collision checks when working with 2d - circular objects?  I've read about QuadTrees, BSP, spatial hashing, etc but it is difficult to sort out what method is most appropriate to this use case.</p>
  
  <p>Does anyone have any knowledge about what might work best?</p>