Maximize the number of PyGame sprites, with collision detection

A quick suggestion. If you look at the implementation of spritecollide, you'll see that it iterates over all the sprites in the group to see if the rectangles overlap. This means that the loop:

for box in boxs:
    # ...
    touch = pygame.sprite.spritecollide(box, boxs, False)

takes time proportional to the square of the number of boxes.

What I would try instead would be to insert the boxes into a spatial index which can find intersections efficiently. For example, put them in an R-tree using the Rtree package, and then call the intersection method. Or put their centres in a kd-tree using scipy.spatial.KDTree and then call the query_pairs method, passing the size of the largest box as the search radius.

Responses to comments

1. There are ways to update spatial indexes as objects move (typically in games objects don't move very far in a frame, so updates tend to be local). But the simplest thing to do is to rebuild the spatial index each frame — this has cost \$\Theta(n\log n)\$ which is an improvement on the \$\Theta(n^2)\$ approach of comparing all pairs of objects.

2. Here's an example using scipy.spatial.KDTree. Using this data structure requires three steps. First, take your list of sprites and build a tree containing their centres:

   from scipy.spatial import KDTree
   tree = KDTree([sprite.rect.center for sprite in sprites])
   

   Second, query the tree for candidate collisions, using an appropriate search distance (in this case the diameter of the largest sprite):

   from math import hypot
   distance = max(hypot(*sprite.rect.size) for sprite in sprites)
   collisions = tree.query_pairs(distance)
   

   Third, not all of the candidates are actually colliding (because we have only queried the distance between their centres), so check to see which ones are real:

   for i, j in collisions:
       if sprite[i].rect.colliderect(sprite[j].rect):
           # handle collision between sprite[i] and sprite[j]
   

Not sure how much of a performance increase you can get out this (I'm on a virtual machine right now, not exactly the best), but if you know that:

• Your sprites will always be squares (more precisely: that they'll have a square-shaped colliding box)
• Your sprites will always move only vertically

Then you can exploit these two assumptions by keeping sorted lists of x coordinates and y coordinates and do a binary search to find the closest box. If that box is not colliding, you know that no other box is.

Here is some sample code (I adapted some code from here ), but keep in mind that this is just an example, you should implement it correctly with an OO design if that's what you chose (and I'm curious to know what, if any, kind of improvement you're getting):

import pygame
from pygame.locals import*
import time
import bisect

BOX_SIZE_X = 40
BOX_SIZE_Y = 40

def closest_search(data, val):
    highIndex = len(data)-1
    lowIndex = 0
    while highIndex > lowIndex:
            index = (highIndex + lowIndex) / 2
            sub = data[index]
            if data[lowIndex] == val:
                    return data[lowIndex]
            elif sub == val:
                    return data[index]
            elif data[highIndex] == val:
                    return data[highIndex]
            elif sub > val:
                    if highIndex == index:
                            return data[sorted([highIndex, lowIndex])[0]]
                    highIndex = index
            else:
                    if lowIndex == index:
                            return data[sorted([highIndex, lowIndex])[0]]
                    lowIndex = index
    return data[sorted([highIndex, lowIndex])[0]]

def is_colliding(x, y):
    global sorted_x, sorted_y

    inside_x = False
    inside_y = False
    if len(sorted_x) > 0:
        closest_x = closest_search(sorted_x, event.pos[0])
        if abs(closest_x - box.rect.x) < BOX_SIZE_X:
            inside_x = True
        closest_y = closest_search(sorted_y, box.rect.y)
        if abs(closest_y - box.rect.y) < BOX_SIZE_Y:
            inside_y = True
    if (inside_x and inside_y):
        return True
    return False

screen=pygame.display.set_mode((1250,720))

class Box(pygame.sprite.DirtySprite):
    def __init__(self,posx,posy):
        pygame.sprite.DirtySprite.__init__(self)
        self.image= pygame.Surface ([BOX_SIZE_X, BOX_SIZE_X]).convert_alpha()
        self.image.fill((250,0,0))
        self.rect=self.image.get_rect()
        self.rect.center=(posx,posy) 

    def update (self):
        self.dirty=1 

pygame.init()

clock=pygame.time.Clock()
boxs=pygame.sprite.LayeredDirty()

sorted_x = []
sorted_y = []

while True :
    start = time.time()
    screen.fill((0,0,0))
    for event in pygame.event.get():
        if event.type==pygame.QUIT :
            pygame.quit()
            quit()
        if event.type== pygame.MOUSEBUTTONDOWN and event.button == 1:
            box=Box(event.pos[0],event.pos[1])
            if not is_colliding(box.rect.x, box.rect.y):
                boxs.add(box)
                bisect.insort_left(sorted_x, box.rect.x)
        elif event.type== pygame.MOUSEBUTTONDOWN and event.button == 3:
            pass
        elif event.type==KEYDOWN:
            if event.key==K_SPACE:
                boxs.empty()
                sorted_x = []
    sorted_y = []
    for box in boxs : 
        if box.rect.y<650 :
            touch= pygame.sprite.spritecollide(box, boxs,False) 
            if (len(touch))<2:
                box.rect.move_ip(0,1)
            bisect.insort_left(sorted_y, box.rect.y)


    boxs.update()
    dirty=boxs.draw(screen)
    pygame.display.update(dirty)
    clock.tick(60)
    end = time.time() 
    print (end-start)