How to improve the speed of a nested for loop for game physics

Question

I'm making a game with python (specifically using pygame to render) where in my physics engine I have a O(n^2) problem. In my Engine object:

def step():

    for obj1 in self.objects:
        for obj2 in self.objects:
            if obj1.XY != obj2.XY: # You can't have the object bounce itself
                obj1,obj2 = Collision(obj1,obj2)

These loops happen every time the game loop runs The nested for loop is really killing the fps when there are 100+ objects (10000 total iterations). I was wondering if there was a faster way to iterate through all possible combinations and apply a function to that pair

Answer 1

The way you fix this is by using smarter data structures, so that your algorithm is no longer quadratic.

Look into space partitioning in general, and quadtrees in particular (https://en.wikipedia.org/wiki/Quadtree) (if you're doing 2D -- the 3D equivalent is the octree: https://en.wikipedia.org/wiki/Octree).