How do I detect multiple sprite collisions when there are >10 sprites?

Question

I making a small program to animate the astar algorithm. If you look at the image, there are lots of yellow cars moving around. Those can collide at any moment, could be just one or all of them could just stupidly crash into each other.

How do I detect all of those collisions? How do I find out which specific car has crash into which other car?

I understand that pygame has collision function, but it only detects one collision at a time and I'd have to specify which sprites.

Right now I am just trying to iterate through each sprite to see if there is collision:

for car1 in carlist:
    for car2 in carlist:
        collide(car1, car2);

This can't be the proper way to do it, if the car list goes to a huge number, a double loop will be too slow.

Answer 1

There is no 'proper' way, just different approaches that vary from simple-but-slow to complex-but-fast.

You can stick with that method, if your car list is small enough. However, there is a bug in your basic algorithm, as it will compare each pair of cars twice. To fix that, your second loop should start the value of car2 from the position in the list after car1.

Most faster methods of detecting collisions like this use spatial properties of the objects so that the objects can be ordered in such a way that 1 comparison might reject multiple pairings.

Probably the simplest approach using this is to sort the objects along one axis (x or y) and use that knowledge to exit the loop early. eg. Sort cars by x ascending, and when you find a car2 with an x value greater than the right-hand side of the current car1, you know you no longer need to compare it against any more possible car2 objects as they must be even further away.

A more complex approach is to divide the world in 2 dimensions using a grid of squares that are bigger than the objects inside them. You track which grid square each object is in, and conversely which objects are in that grid square. So each object only needs to check for collision against other objects in that square (and maybe the 8 adjacent squares). Technically it's a 'bin' data structure.

Beyond that, there are other ways to partition the world that change as the objects move. A common example is a quadtree which subdivides the space to keep a similar number of objects in each square. Others can be found under the general term of spatial partitioning but as with any data structure, some are optimised for quick lookup while being expensive to add or change data within them.

In your particular case... I would probably just stick with the 2 loops, and upgrade to the coordinate-sorted approach later if necessary.

Answer 2

I see that this is an older question, but I'd like to share my own solution to this problem, as it's part of a recent project of mine and I just cleared out some collision detection that was exactly like yours, more or less. I had two queues of 'good-guys' and 'bad-guys' and every frame I would do this:

#old code!! not great!! :(
for goodguy in goodqueue:
    for badguy in badqueue:
        if goodguy.rect.colliderect(badguy.rect):
            goodguy.got_hit()
            badguy.got_hit()
#i don't recommend this approach!! :(

Even with my simple game, which might have one Player object, 3 - 4 'good guy' Bullets it fired, comparing it against the 3/5/7 bad guys in the badqueue and their Bullets they fire at random intervals… that is a lot of iterations that we don't need!

This is the current state of my project's hit detection: it's a little more code, but it will scale so much better and flat out ignores collisions that aren't happening.

for obj in GAME.allqueue:
    obj.update()
    hit_list = pygame.sprite.spritecollide(obj, GAME.allqueue, False)
    if not hit_list:
        pass
    elif obj in GAME.goodqueue:
        for otherobj in hit_list:
            if otherobj in GAME.badqueue:
                obj.got_hit()
                otherobj.got_hit()

I'll explain what's going on here.

First, the loop calls obj.update(), which does normal game logic-type stuff; moves sprites, determines if they're fired, etc etc.

The next line, hit_list = pygame.sprite.spritecollide(obj, GAME.allqueue, False), tells PyGame to generate a list of all the things that obj is colliding with in GAME.allqueue, which is an instance of pygame.sprite.Group (as I would imagine your carlist is). This is fantastic, because now we just have a list of what's actually colliding with that object.

The next two lines: if not hit_list: pass basically tell the game if the hit_list is empty, don't do anything collision-related and continue on with the game loop. The line if not a_list is a Pythonic idiom which is basically the same as if len(a_list) == 0, or "if this list is empty", or whatever you want to call it. Basically - this is where the game decides if it should even bother with collision detection, or move on to the next important step.

The rest of the code may be a bit situational and not apply to your game/simulation, as my game basically works to avoid 'friendly fire' between both good guys AND bad guys. (It basically makes sure two colliding objects are in separate queues, so only 'good guy meets bad guy' collisions are processed) However -- In your situation, I believe you'd be able to make use of pygame.sprite.spritecollide in a similar fashion.

for car in carlist:  #let's get a list of everything THIS car is colliding with!
    cars_hit_list = pygame.sprite.spritecollide(car, carlist, False) #False tells PyGame NOT to auto-kill the whole list of results!
    if not cars_hit_list:
        pass    #if the cars_hit_list has no length, do nothing!
    else:    #this is assuming you just want all cars to crash…
        for crashedcar in cars_hit_list:
            handle_the_crashes() #whatever you actually do to crash the cars

In my humble opinion -- as long as you're using the pygame.Sprite objects to handle your sprites and the various Groups they belong to, using the list you get back from pygame.sprite.spritecollide will be more satisfying than just iterating over every possible combination of potential collisions to see if they are occurring.