All I want to do is simple (?) 2D bounding-radius collision detection. So far, what I have written works, but is slow with large numbers of intersecting objects... but it is as follows (written in python, by the way): One master "Game" class, contains the list of "GameObject" objects in a variable called scene. Every object has a function called "Think" which is the function used to update position, do motion calculation, collision detection, and set up the next frame of animation if applicable. These are all called in a loop "for each object in game.scene". In each object's Think() function, it searches for collisions in a loop that (once again) iterates "for each object in game.scene". It check to make sure it is not checking collision with itself, and then checks by what I call a "RadiusOverlap". This function is as follows: Check for collisions between self, and objects in game.scene

    def CollisionScan(self):
        for obj in self.game.scene:
            if obj != self and obj.collides and not obj.collisionScanned:
                if self.collide:
                    if obj.type in self.collide:
                        obj.CheckCollision(self)
                else:
                    obj.CheckCollision(self)
        self.collisionScanned = True

Check for an overlap:

    def CheckCollision(self, obj):
        info = self.RadiusOverlap(obj)
        if info[0] <= 0:
            self.Collide(obj, info)

(Collide() simply stores the collision information in a list) Support functions:

    def RadiusOverlap(self, obj):
        return [self.DistanceTo(obj) - obj.asset.radius - self.asset.radius, self.AngleToO(obj)]

RadiusOverlap() returns the distance between to objects taking into account bounding circles. If the first item in the return list is negative, there is an intersection. And the relevant support functions:

    def DistanceTo(self, obj):
        return math.sqrt((obj.x - self.x)**2 + (obj.y - self.y)**2)

    def AngleToO(self, obj):
        return self.AngleToP(obj.x, obj.y)

    def AngleToP(self, x, y):
        return math.atan2(x - self.x, y - self.y)%(math.pi*2)

(by the way, the ** operator is an exponent). RadiusOverlap returns the distance between objects taking into account radius, and also returns the angle to the object (for motion collision repsonse stuff that's not implemented yet). Currently, if two objects are found to intersect, the object, overlap, and angle is stored in a list for later processing. In the Think function, each item in the collision list is iterated through, each object is moved apart by the RadiusOverlap as stored previously. My problem is that this setup is very s-l-o-w. Is that obvious to anyone? How can I make it better?? Thanks.

A few things right away that might speed things up.

0. Instead of looping through every object and checking obj.collides, have a separate list containing only pointers (or handles, indices, references, whatever) to those objects which can collide. That saves you looping over objects which cannot collide.

And, if you have, say, 10 objects, make sure you don't check if you check that 1 collides with 2 through 10, take into account that you only have to check that 2 collides with 3 through 10 (you already checked 1 vs. 2) and so on, so that when you get to 10 in the outer loop, you don't need to check anything, as 1-9 have already checked vs. 10. (in other words make sure you aren't comparing everything twice.) Probably you already have that covered.

1. Don't do the sqrt. instead, compare against the square of the distance.

Don't call atan() and do all that calculation stuff every time.

Instead, you can probably have a 2d array with the indices encoding (an approximation of) the x/y distances between the colliding objects, and the value(s) in that array being the pre-calculated results you need, either the angle, or perhaps some even more derivative value if it turns out you're always doing the same thing with the angle. For instance, maybe you always use the angle to calculate x/y component vectors to impart some momentum to bounce the objects -- maybe you precalculate those vectors instead of just the angle.

Edit: also, use a profiler, and find where the bottlenecks are, and change one thing at a time, and profile to make sure your changes actually improve things. Sometimes these days caching precalculated values won't give the payoff it gave in the old days. I wouldn't expect that atan2 was particularly fast though.