JeroMiya
2002.09.25, 02:12 AM
I've reached a bit of a problem with collision detection and response. The problem arises from a couple of cases which break my normal method.
- May detect collision between a moving object and two other objects in the same frame.
- There may be a collision that occurs only after another collision in the same frame.
Here's how I attempted to solve this problem:
Assuming that I find all collisions that will occur in my first pass, I could try to calculate collision response in the order that they occur. Unfortunately, some of the collisions that are detected may not actually occur. This is the first case. If an object collides with one object, that might send the object away from a second object that it would have collided with if it weren't for the first object. This leads to the second case. Each collision response results in two new moving object paths that I need to check for collisions. However, I need to "prune" the list of collisions that occur so that for each pass, I only calculate collision response for collisions that actually occur. I can do this like so:
If two collisions are detected for one object, take only the collision that occurs first.
Of the remaining, if an object A collides with an object B, and B collides with an object C, then take only the collision that occurs first.
The remaining collisions should only be collisions that I know will occur. So now I should have a group of objects and their initial paths and a list of collisions between pairs of objects. Because I did those two steps, I should be able to calculate collision response on the list of collisions and come out with a list of new paths, two per collision, which each have a starting time. For each of these, I need to check for collisions again. This results in another list of collisions, which needs to be pruned again and processed again. This process can then repeat until the start times of all paths are either 0 or the time of the next frame. So The following p-code would result:
Do
Detect collisions between each object path
- only check moving objects against other objects
- only check against nearby objects (space partitioning scheme)
- take path start time into account. (for first pass, all will be 0)
- don't check against an object path you've already checked
If two collisions are detected for one object, take only the collision that occurs first
Of the remaining, if an object A collides with an object B, and B collides with an object C, then take only the collision that occurs first
Calculate collision response for all remaining collisions.
Replace original paths for objects which have collided with calculated response paths and the time they occurred.
While( collisions occurred )
Now, worst case scenario, everything is moving. Most of the time everything IS moving, so this optimization isn't always much help. To further reduce the number of collisions checked, I only check for collisions with objects that could possibly be collided with. This can be done in a couple ways. one way is to have a quadtree system, which would work well if you put a maximum value on the speed of each object, so you could predict which nodes you would have to check against. I can create a bounding box around the entire movement of the object, and check if that box overlaps with other objects first.
Further, for each subsequent path, I really only need to recheck object paths that are a result of a collision in the previous pass. That's because any object that didn't collide with anything in the last pass can only collide in this pass with objects that collided in the last pass. This also reduces the complexity. (Remember that checking if A collides with B is the same as checking if B collides with A).
- May detect collision between a moving object and two other objects in the same frame.
- There may be a collision that occurs only after another collision in the same frame.
Here's how I attempted to solve this problem:
Assuming that I find all collisions that will occur in my first pass, I could try to calculate collision response in the order that they occur. Unfortunately, some of the collisions that are detected may not actually occur. This is the first case. If an object collides with one object, that might send the object away from a second object that it would have collided with if it weren't for the first object. This leads to the second case. Each collision response results in two new moving object paths that I need to check for collisions. However, I need to "prune" the list of collisions that occur so that for each pass, I only calculate collision response for collisions that actually occur. I can do this like so:
If two collisions are detected for one object, take only the collision that occurs first.
Of the remaining, if an object A collides with an object B, and B collides with an object C, then take only the collision that occurs first.
The remaining collisions should only be collisions that I know will occur. So now I should have a group of objects and their initial paths and a list of collisions between pairs of objects. Because I did those two steps, I should be able to calculate collision response on the list of collisions and come out with a list of new paths, two per collision, which each have a starting time. For each of these, I need to check for collisions again. This results in another list of collisions, which needs to be pruned again and processed again. This process can then repeat until the start times of all paths are either 0 or the time of the next frame. So The following p-code would result:
Do
Detect collisions between each object path
- only check moving objects against other objects
- only check against nearby objects (space partitioning scheme)
- take path start time into account. (for first pass, all will be 0)
- don't check against an object path you've already checked
If two collisions are detected for one object, take only the collision that occurs first
Of the remaining, if an object A collides with an object B, and B collides with an object C, then take only the collision that occurs first
Calculate collision response for all remaining collisions.
Replace original paths for objects which have collided with calculated response paths and the time they occurred.
While( collisions occurred )
Now, worst case scenario, everything is moving. Most of the time everything IS moving, so this optimization isn't always much help. To further reduce the number of collisions checked, I only check for collisions with objects that could possibly be collided with. This can be done in a couple ways. one way is to have a quadtree system, which would work well if you put a maximum value on the speed of each object, so you could predict which nodes you would have to check against. I can create a bounding box around the entire movement of the object, and check if that box overlaps with other objects first.
Further, for each subsequent path, I really only need to recheck object paths that are a result of a collision in the previous pass. That's because any object that didn't collide with anything in the last pass can only collide in this pass with objects that collided in the last pass. This also reduces the complexity. (Remember that checking if A collides with B is the same as checking if B collides with A).