Last week, I talked a bit about how to detect collisions. I didn't go into too much detail, focusing on first order approaches to limit the number of tests we have to do. There are multiple ways of getting increasingly tighter results, such as a hierarchy of bounding volumes. The way it works is you split the body into a series of smaller bounding volumes, such that the whole object is contained within them. Properly built, you can discard half the triangles in a body on each level, until you find the intersection.
But that's beyond the scope of my first attempt. I'm going to be pretending that my bodies are all perfectly round, and handle the crashes accordingly. The result is that the first order check with spherical bounding volumes gives me all the information I need.
After comparing the bodies' distance from each other, I have a list of all the collisions that happened in a given frame. This should be a fairly small list. It's unlikely that in a given frame you'll find many collisions. Still, we don't want to assume we'll only ever find one, or we may find strange results in some cases.
Of course, after going to all this trouble to determine when two objects are getting too close, we actually have to decide what to do about it. This decision has to be informed by the kind of game, and the actors involved. For example, if you detect the collision between a bullet and an object, you'll want to remove the bullet and deal damage to the object. If you are simulating billiard balls, you'll want to have them bounce off of each other. If it's a person walking into a wall, you might just want to move them back so they're not inside the wall any more and stop them.
I'm going to be pretending my 'asteroids' act as billiard balls for now. This means elastic collisions. It won't look very good when the asteroids gain better detail, but by then we can improved the tests in different ways.
Starting with the collision list, we can determine how long ago each crash was. We know the distance between the bodies and their speeds. The difference between the sum of their radii and their actual distance divided by their relative speeds tells us the time since they crashed. We can then back up the simulation to the first crash by reversing the speed of the objects and moving them to the positions they would have been in at the time of the crash.
Once this is done, we calculate the new speeds, using simple collision physics. There's plenty of information on how to do this on the internet, so I won't go into the details. It doesn't really add to the subject in any case, the important thing is that the math gives us new speeds for the objects involved. We now advance the simulation to the time we were at before backing up, and run the collision detection again.
I don't actually use the old list because when we changed the velocities of the objects, we changed things in such a way that we can't be sure that that collision happened. Or it may be that the new velocities caused another collision. The only way to be sure is to run the collision detection again. Since the frames should really be very quick, we shouldn't find too many collisions on a single frame. Objects would have to be very tightly packed for this to be a concern, such as in the opening shot of a billiard game.
Still, this can get expensive. Worse still, the way I'm doing things, adding elements to the scene increases the cost very quickly. We can even determine exactly how much more expensive each additional item is. One object requires no checks. Two objects require one check. Three objects require three checks. Four will require six checks. Five will require ten checks. And in general, n objects will require (n-1)*n/2 checks. This is a quadratic function, and something we don't really want to work with. Having just fifty objects in the scene would require 1,225 checks every frame. Double or triple if we have a few impacts.
There is of course a way about this problem as well, which I'll talk about next week.
No comments:
Post a Comment