In what way would you present an algorithm to detect collisions between diffrent objects?

Question

While working on a really only-for-fun project I encountered some problem.

There is a 2D world populated with Round Balls, Pointy Triangles and Skinny Lines (and other wildlife too, maybe). They all are subclasses of WorldCreatures. They can move inside this world. When they meet each other, a Collision happens.

The thing I'd like to do is to make a way of detecting Collision between them. Here's what I'm standing on right now:

• For me Ball-Ball is easy, I just calculate their distance from their positions and compare it with the sum of their 'sizes'.
• Collision between Ball and edge of the world is simple too - I just check the distance from it, which, in Cartesian coordinates, is simple.
• More generic problems are - how to detect a collision between Line (starting and ending at some points) or other objects I could have there? Distance between a line and a point can be calculated easily too, but what I'd like is to have

Some kind of generic way to say if Obcject A collides with Object B. The code as it is now looks somewhat like:

class WorldCreature:
    def detectCollision(self, otherObject):
        # do something 
        if collision:
            self.onCollision(otherObject)
            otherObject.onCollision(self)
class Ball(WorldCreature):
    # someing here
class Line(WorldCreature):
    # someing here

Now, the collision detection mechanizm should depend on what objects can collide. So will the effect.

Should I just keep a list of all the objects in memory and loop through all them in every single step? Or, is there some better way to improve the performance of this task?

Answer 1

Use a quadtree. They're used to eliminate large regions that you know are outside a collision radius, plus they let you quickly search for the closest point.

As far as actual collision detection goes, since you're only using convex objects, take a look at Metanet Software's tutorial on the separating axis theorem. In their flagship game, they actually use a grid to find all the objects to check for collision against, but it shouldn't be too hard to use a quadtree instead.

(I remember reading an article on quadtrees that used circles in a grid to illustrate how you can find the points within a radius. I can't seem to find it though.)

Answer 2

The answer to this depends on a number of factors, such as how many objects there are, how many are moving vs. non-moving, how fast they move, etc. I think that the right place to start is by getting the core collision detection and behavior code correct while ignoring the optimizations you might do to prune collision checks, etc.

Once the core code is correct, you can start running experiments to see what will perform well for you. I would recommend some kind of spatial subdivision technique, such as kd-trees (although in 2d, you may as well use quadtrees).

Fundamentally, though, there's probably no single right answer, except what you are able to determine by coding up your game and experimenting with it.

Answer 3

I think Hough Transform should help somehow.

Answer 4

Python. Kinda strange beast for me 8)

I have c++ experience creating games -- so I talk from this point of view.

First of all (you can skip this if you have low number of objects) you need broad-phase collision detection. Already mentioned quadtree is just one possible implementation. Broad-phase is needed to find pairs of possibly colliding objects.

Then goes the narrow phase -- when pairs are checked.

I used the following scheme (note -- this was created with primitives in mind, if you need polyhedra collisions -- just use GJK and spheres, plus rays,segments):

Everything that needs collisions have CollisionObject which handles transform and store CollisionPrimitive (box, sphere etc)

Each CollisionPrimitive has type_id -- when you write A_B_CheckIntersection -- the first object always have lower type_id

For each Pair in the list that you get from broad phase -- you swap objects if needed and index an array where pointers to specific collision functions are stored. Sure -- for that you should have them have identical interfaces (c++) but it is easy 8)

As for specific collision routines: visit http://realtimerendering.com/intersections.html It is good place to start