Finding all collisions within 1 group of sprites (efficiently)

Question

I have a method that recieves a Group of sprites. For each sprite, I need to find every other sprite it collides with and call its handle_collision method.

How can I find all the sprites each sprite in the group collides with? Here's my idea for finding all collisions within a group.

@staticmethod
def check_collision_group(most_sprites: pygame.sprite.Group, screen):
    for sprite in most_sprites:
        most_sprites.remove(sprite)
        collided_sprites = pygame.sprite.Group()


        for sprite2 in most_sprites:
            if pygame.sprite.collide_rect(sprite, sprite2):
                collided_sprites.add(sprite2)

       sprite.handle_collision(collided_sprites)

        most_sprites.add(sprite)

However, this is slow. The amount of collisions this had to check astonished me when I printed them out.

A bit of searching and I've found 2 ideas that are probably a lot faster.

1. Making the first sprite a Group and using collidegroup from pygame.sprite library.

2. Only testing the sprites around the sprite you are testing. Idea from https://gamedev.stackexchange.com/questions/45392/how-do-i-detect-multiple-sprite-collisions-when-there-are-10-sprites .

To restate question: What is a fast (but hopefully still relatively simple) way to find every other sprite in the group that each sprite collides with?

Answer 1

To find all collisions between a sprite and everything else in it's group.

def check_collision_group(most_sprites, screen):
    single = pygame.sprite.GroupSingle()
    for sprite in most_sprites:
        most_sprites.remove(sprite)
        single.add(sprite)

        collided_sprites_dict = pygame.sprite.groupcollide(
            single, most_sprites, False, False)


        most_sprites.add(sprite)

Note: It's important to use add on the groupsingle, reassignment will keep adding more and more groups to your system and bog down your game. I am not sure why, but changing it to my groupsingle and adding to it fixed the issue.

The speed of this seems to be relatively fast. To calculate all the collisions in a group of ~50 sprites it took about 1.4 milliseconds. I have not tried method 2, which is only checking collisions based on proximity, but I do not see a reason to, as the speed of groupcollide is rather decent.