# 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?

• You should consider profiling your code. That's always the first, crucial step when you have performance issues. You can guess what the bottleneck is; ultimately, it may or may not be the real bottleneck. Jan 9, 2013 at 20:03

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->A2 //Ignored
A2->A3
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.

• As Byte56 said you should check combinations instead of permutations, also consider using itertools for more simple code: for a1, a2 in itertools.combinations(self.agents, 2): Jan 9, 2013 at 19:07
• Thanks @Leftium, I caught that already and fixed it. We can actually get it down to 4,950 by removing self checks. Jan 9, 2013 at 19:13
• @Byte56 I don't quite understand what you meant. The code you posted seems like the java version of saying in python: for a in self.agents: for a2 in self.agents[1:]: test. Which does not speed it up at all.. but I must have misunderstood Jan 10, 2013 at 4:58
• They're not meant to be copy/paste. Just making it clear so you know what to do. It's not the same as what you have. See that the second loop starts at i+1. That means every iteration of the outer loop makes the inner loop get shorter and shorter. Jan 10, 2013 at 5:00
• @Byte56 No I got that it was not meant to copy paste, but the implications of the code was not immediately clear at first, I'm still obviously a novice haha! But now I understand what you meant, and successfully changed my code, thank you so much for your help! Jan 10, 2013 at 7:06

You might want to divide your world into segments/ a grid so that you only check collision for agents that are relevant. Agent A thats on the other side of the screen will NOT collide with B on te opposite side. So why check collision? Google for Spatial partitioning / quadtrees /spatial hashing.

Grid

Also your second forloop should start at a1+1. Because all the previous agents were already checked And need no checking. This also eliminates the need of

if a1 == a2 : continue


Because it starts one index ahead of a1.

Here are some tips, from simple to more complex. All these optimizations can be used together. The more complex optimizations will probably yield greater performance improvements, but add them only if the simple ones are not enough:

• Prune out redundant tests as suggested by Jovan and Byte56. This will roughly half the number of tests, thus doubling performance.
• Eliminate expensive, unneeded calculation. Calculate only the distance^2 between agents, not the distance. Distance requires an expensive square root operation. Then instead of comparing to the sum of the radii, compare to the (sum of the radii)^2 (change 40 to 1600 in your case).
• Reduce the time each test takes even further by using simpler bounding box tests. This will eliminate relatively expensive multiplication operations for simple addition. This might produce "false positive" collisions because squares can overlap corners when circles don't. If you don't like this you can confirm these collisions by testing distance/radii only after the bounding box test says there is a collision.
• Prune out even more collision tests by partitioning agents into groups that you can assume will not collide. Grids are one method. Binary Space Partitions or Quadtrees are more advanced methods.

Collision Detection, Getting the most out of your collision tests by Dave Roberts is a great introductory tutorial on these topics and even introduces a simple axis-sorting method to prune redundant collisions tests that hasn't been mentioned, yet.

• I wouldn't be so sure that bounding box tests are faster than sphere tests. Floating-point multiplies are essentially as fast as additions on virtually any modern hardware, and both are dwarfed by the cost of comparisons - and while the sphere test only does a single compare, the box test generically has to do six or more comparisons to confirm intersection. I would expect bounding-box tests to be substantially slower than bounding-sphere tests. Jan 9, 2013 at 22:22
• Thanks, I read your comments before you deleted them. Not sure why you did, it seemed like useful information. Jan 10, 2013 at 5:15

This looks and works great, as long as the number of agents is below 100

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


That'll do it. You're veering on O(N^2) operation there.

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.

Yup. The general idea is known as Hierarchical Collision Detection.

One basic, popular approach is to use tiles/grid. It's fairly simple to keep track of what tile your agent is on, and check the surrounding tiles for collisions.

Another approach is to group the agents that are close to each other using a bounding primitive. There's several ways to do this, but for best results you should try to minimize the amount of empty space in your bounding object, by calculating what axis your agents are on and fitting the bounding primitive.

Take a look at the Minimum Bounding Rectangle. Object-Oriented Bounding Boxes are also popular.

For big "worlds" it could be a solution to create something like a network of rectangles over the whole "world". (I am not allowed to post an image)

Check if a circle collides with the part of the network from before. If they don't collide, check for all network's parts if the circle collides and save its value in a attribute of the circle. Also update a networks attribute which holds the colliding circles.

For circle-cirlce-collision just check the circles which collide the same part of the network. If the distance between most circles is not too small, this can extremely decrease the time needed for collision.

If you didn't understand my discription for the network or if you need a code example just feel free to ask.