Maximize the number of PyGame sprites, with collision detection

Question

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,........ 
 touch= pygame.sprite.spritecollide(box, boxs,False) 
 if (len(touch))<2:# i do this because (touch) will always return that the box touch it self
 # but when its touch more then one then i know it touch other box so it will not move 
 # and i feel that there is much faster way to do this check then my way :( 
 box.rect.move_ip(0,1)
 boxs.update()
 dirty=boxs.draw(screen)
 pygame.display.update(dirty)
 clock.tick(60)
 end = time.time() 
 print (end-start)
#the best until time totally turn to 0.02xxxx = 260 sprite

So what else I could do to have more then 260 moving and colliding boxes at 60 fps without lag?

Answer 1

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]
   

• مهند عبد الجليل: thank you for your answer but i am still very beginner in programming and python and its the first time for me to hear about Rtree i just downloaded the module few moments ago but i didn't found any one in YouTube explaining the module :(
• مهند عبد الجليل: so if you could pleas give me any example code i could start using to learn the rtree through it ? and thanks you for your answer it was useful to know about the rtree :)
• Gareth Rees: @مهندعبدالجليل: see updated answer.

Answer 2

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)