Divide the world into square bins of width 256. For each ball, put it in its appropriate bin. Then for each bin, check for collisions where either both balls are in the bin, or one ball is in the bin, and the other ball is in an adjacent bin.

Implement the detect collisions algorithm described above.

Your new code must still find all the same collisions found by the old code (any pair of balls for which colliding returns true). To check that you are detecting the same collisions, run your code and the original code with the same parameters, and make sure that they detect the same number of collisions.

In your documentation, do not assume that the reader has read this problem set. The old code is provided below.

Using your improved code, after 1000 timesteps with 200 balls, how many collisions did you get? How many simulation steps per second did you run? How many simulation steps per second could you run with the original code and the same number of balls?

Link to the old code (Not the whole thing is important): https://pastebin.com/We9hgekG