Python - Checking every item in a list against every other item efficiently

Question

I'm working on a game where each object should check if it is colliding with any other object. I have a single list of all the objects and a function which can determine if two objects are colliding and destroys them. The current method I'm using is very inefficient.

for i in list1:
    for j in list1:
        if collide(i, j):
            i.kill()
            j.kill()

Initially I removed both objects from the list after they were killed, but some collision occurred without detecting so I reverted back to this code. It works, but I'd like something more efficient.

Why not check if an item collides with anything when it moves? — zbys
– zbys, Commented Aug 2, 2018 at 20:18
Are your objects sprites in pygame? If so, there is better collision detection. Please be more specific about the data types and environment you are using. — Rory Daulton
– Rory Daulton, Commented Aug 2, 2018 at 20:28
@zacharybys All objects are always in motion. The game involves a gravity model with asteroids always under gravitational acceleration. — Aeolus
– Aeolus, Commented Aug 2, 2018 at 20:29
@RoryDaulton It is in pygame, however all sprites are circles so the built in rect collision will not work. — Aeolus
– Aeolus, Commented Aug 2, 2018 at 20:31

Jean-François Fabre · Accepted Answer · 2018-08-02 20:37:19Z

1

first this is testing twice too much and also testing if one object collides with itself:

for i in list1:
    for j in list1:
        if collide(i, j):
            i.kill()
            j.kill()

This loops exactly len(list1)**2 times.

a very simple way to divide the number of tests by 2 (and avoiding testing against itself):

for i,obj1 in enumerate(list1):
   for j in range(i+1,len(list1)):
      obj2 = list1[j]
      if collide(obj1,obj2):
         obj1.kill()
         obj2.kill()

It takes advantage of the fact that collide(obj1,obj2) is the same as collide(obj2,obj1).

At this point, you probably want to break out the inner loop since obj1 is now dead. But that depends on what you want to do.

If an accurate collision test is expensive, you could consider a rougher check (distance, rectangle boundary, any quick method), so you can discard items which are too far away from each other without performing the "expensive" test.

edited Aug 2, 2018 at 20:37

answered Aug 2, 2018 at 20:31

Jean-François Fabre♦

141k24 gold badges179 silver badges246 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Aeolus Over a year ago

So this is checking first item against all items, second item against all but first item, third item against all but first two items, and so on?

Jean-François Fabre Over a year ago

yes, exactly. collide(obj1,obj2) is the same as collide(obj2,obj1)

Aeolus Over a year ago

Right, that's why it was so inefficient. Thanks for the help, I'll mark it.

Jean-François Fabre Over a year ago

it has still O(n**2) complexity, but is at least twice as fast.

Aeolus Over a year ago

Is that the fastest possible way to check every item against every item once, or can it get more efficient?

|

Collectives™ on Stack Overflow

Python - Checking every item in a list against every other item efficiently

1 Answer 1

7 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related