python - Collision detection performance problem

Using python and pygame I've built a collision detection system according to the instructions in this YouTube tutorial.

This is updated 40 times per second and controls movement and collision detection between some number of "agents", which are circles, each with a radius of 20:

for a in self.agents:
    dir = a.target - a.pos

    if dir.length >= 3:
        dir.length = 3
        a.pos = a.pos + dir


for a in self.agents:
    for a2 in self.agents:
        if a==a2: continue
        d = a.pos.get_distance(a2.pos)
        if d<40:

            overlap = 40 - d
            dir = a2.pos - a.pos
            dir.length = overlap/2
            a2.pos= a2.pos+dir
            a.pos= a.pos-dir

This looks and works great, as long as the number of agents is below 100. A higher number of agents will cause the pygame frame rate to drop. I left out some code which increases movement speed and pushback for a selected agent, but I don't think it has any consequence for the issue.

How can I make the code more efficient? For instance, would it help to make it so agents only check the distance of other nearby agents, say within a circle 4X the size of the agent, instead checking the complete list in every iteration of the code. Or is it better to change the method all together?

Answer

You're checking each agent against every other agent more than once. For example, consider a simple list of 3 agents, there should only 3 checks, you're checking 9 times, and that gets much worse with larger numbers. At 100 you're checking 10,000 times instead of 5,050.

When you iterate like you're doing, the comparison happens like this:

A1->A1 //Ignored
A1->A2
A1->A3
A2->A1 //Already checked
A2->A2 //Ignored
A2->A3
A3->A1 //Already checked
A3->A2 //Already checked
A3->A3 //Ignored

You need to check against the agents using a for loop. The inner for loop should start just after the agent being checked in the outer for loop.

for (int i = 0; i < agents.size(); i++) {
  for (int j = i+1; j < agents.size(); j++) {
    //Test
  }
}

The number of checks can be calculated by:

1+2+3+4+5+6+...+N-1

Otherwise written as:

(N(N+1)/2)-N

Its a Triangular number minus N (since we're cutting out the tests against self).

You should see significant improvements there, beyond that, spatial partitioning will help reduce the number of checks needed.