Maximize the number of PyGame sprites, with collision detection

I was trying to see what is the highest number of moving and colliding boxes (sprites) I could get in pygame? So that I could start working on game I want, I searched google and I found different people do it as a challenge, trying to get to the highest number of sprites. But none of them use the colliding, they just make a high number of sprites with no for loop inside the main loop.

The highest number I could get before it started to lag was just 260, which is too low for the game I want to start making.

Here is my code:

```
import pygame
from pygame.locals import*
import time
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 ([40,40]).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()
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])
inside=pygame.sprite.spritecollideany(box,boxs )
if not inside :
boxs.add(box)
elif event.type== pygame.MOUSEBUTTONDOWN and event.button == 3:
print (boxs)
elif event.type==KEYDOWN:
if event.key==K_SPACE:
boxs.empty()
for box in boxs :
if box.rect.y<650 :
## touch= pygame.sprite.spritecollideany(box, boxs)
## if touch==box:
##this way above didnt work for me because the box will cross any other box added to the group after it
##for example the box number 3 in the boxs will cross box number 4,5,6,7,8,9,........

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

-
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.

-
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]

StackExchange Code Review Q#159965, answer score: 3