Collision detection performance problem

Question

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 1

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.

Answer 2

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.

I googled some for you:
Quadtrees
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.

Answer 3

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.

Answer 4

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.

Answer 5

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.