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.