Sign in to follow this  

I need some help improving my collision detection...

Recommended Posts

enigma_0Z    122
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
            if obj != self and obj.collides and not obj.collisionScanned:
                if self.collide:
                    if obj.type in self.collide:
        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.

Share this post

Link to post
Share on other sites
smcameron    101
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.

Share this post

Link to post
Share on other sites
scottrick49    455

Instead, compare the distance between the objects squared, and the sum of the radii squared.

EDIT: Also, if you are going to have a very large number of objects on the screen, it may be beneficial to break the objects up into different "buckets" based on their location. This way you don't have to compare every object to every other object, just with other objects in the same bucket.

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this