title: How to subdivide a 2d game world for better collision detection
body: <p>I'm developing a game which features a sizeable square 2d playing area. The gaming area is tileless with bounded sides (no wrapping around). I am trying to figure out how I can best divide up this world to increase the performance of collision detection. Rather than checking each entity for collision with all other entities I want to only check nearby entities for collision and obstacle avoidance.</p>
  
  <p>I have a few special concerns for this game world... </p>
  
  <ul>
  <li><p>I want to be able to be able to use a large number of entities in the game world at once. However, a % of entities won't collide with entities of the same type. For example projectiles won't collide with other projectiles.</p></li>
  <li><p>I want to be able to use a large range of entity sizes. I want there to be a very large size difference between the smallest entities and the largest.</p></li>
  <li><p>There are very few static or non-moving entities in the game world.</p></li>
  </ul>
  
  <p>I'm interested in using something similar to what's described in the answer here: <a href="https://stackoverflow.com/questions/371465/quadtree-vs-red-black-tree-for-a-game-in-c">Quadtree vs Red-Black tree for a game in C++?</a></p>
  
  <p>My concern is how well will a tree subdivision of the world be able to handle large size differences in entities? To divide the world up enough for the smaller entities the larger ones will need to occupy a large number of regions and I'm concerned about how that will affect the performance of the system.</p>
  
  <p>My other major concern is how to properly keep the list of occupied areas up to date. Since there's a lot of moving entities, and some very large ones, it seems like dividing the world up will create a significant amount of overhead for keeping track of which entities occupy which regions.</p>
  
  <p>I'm mostly looking for any good algorithms or ideas that will help reduce the number collision detection and obstacle avoidance calculations.</p>