Efficient collision detection

Question

I am using python and pyglet in a 2d game but I have come across a problem in collision detection. My code to check for collision looks like this:

def distance(self,target):
    return math.sqrt((self.x-target.x)**2 + (self.y-target.y)**2)
def check_collision(self):
    for i in list_of_mobs:
        if self.distance(i) < (self.width/2 + i.width/2):
            return True

It checks the distance from each sprite with "target" being another sprite. The thing I am unsure of is "should I be checking for collisions between all the sprites?" I have over 200 mobs (even more I hope in the finished product) and it becomes unplayable when the collisions are checked. Is there someway to only check sprites within a certain distance without losing speed?

EDIT:

I had a read around google and found out that a lot of the speed was spent doing the same collisions. i.e. sprite1 was checked with sprite2 and sprite2 was checked with sprite1. So I made a few changes to the check collision function and it runs quicker now but still less than 20 fps

def check_collision(self):
    global mobs_to_collide
    if mobs_to_collide == []:
        mobs_to_collide = list_of_mobs[:]
    if self in mobs_to_collide:
        mobs_to_collide.remove(self)
    for i in mobs_to_collide:
        if self.distance(i) < (self.width/2 + i.width/2):
            return True

(it may contain some inefficient code/useless stuff. I was playing around with it a bit)

EDIT2:

I decided to use rabbyt as the sprite library. The collisions are fast and easy. I replaced the code above ^^ with:

rabbyt.collisions.collide(mobs_to_collide)

This returns a list of lists (I'm not sure if that's the correct term) with the objects that collided. I'm still working on how to translate that into an "if collided:" type statement but I am making progress. If anyone is in a similar situation, I would reccomend using rabbyt.

Have a google and read about quadtrees and binary space partitioning — Aesthete
They seem quite complex :/ I was thinking maybe a grid might work, though I'm not sure how this would be done — user1237200
@user1237200 if rabbyt is the solution, you should add this as an answer rather than update the question (you can even accept your own answer). — Andy Hayden

Aesthete Aesthete · Accepted Answer · 2012-09-17T10:01:05

A simple way to improve the speed on this, could be to remove the square root operation.

def distancesq(self,target):
  return (self.x-target.x)**2 + (self.y-target.y)**2
def check_collision(self):
  for i in list_of_mobs:
    # Square this distance to compensate
    if self.distancesq(i) < (self.width/2 + i.width/2)**2: 
        return True

Efficient collision detection

2 Answers