Spatial partitioning

Imagine the Matrix is a real concept, and we are living in a giant physics simulation. Anybody who has dabbled in physics simulations knows that you don’t need many interacting objects to make the simulation chug. The naïve solution is to check every object against every other object leading to an O(n2-n) solution, where you can see in Figure 3.6 that 4 objects have 12 collision checks:

Figure 3.6 – Diagram showing each collision check performed in an inefficient collision detection solution

Improvements can obviously be made to not repeat calculations that have already been made, bringing us down to O(nLog2(n)) where those same four points use only six collision checks. This is better, but there is only so far we can go by checking every object against every other object. We could just not calculate some of them, but that would be like giving some people in our Matrix simulation wall hacks, allowing them to possibly...