Improve performance of entity to entity collision detection with quad tree

[BSVogler]

Currently entity collision runs in O(n^2) as every entity checks it collision with each other.

With a grid:
Inserting n entities in a grid with m cells: Still n^2 but divided by m.

Using a quad tree should reduce collision search to O(log(n)).
Split cell if it contains >3 elements. Check for collision probably needs to check the surrounding cells. How to obtain them?

http://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space--gamedev-374

http://gamedevelopment.tutsplus.com/tutorials/make-your-game-pop-with-particle-effects-and-quadtrees--gamedev-2138