Basic Collision

General:

Collision is:

• Detected and resolved
• More of a geometry problem than a physics problem
• Much better for a game's performance when as basic and simplistic as possible.
The higher the frame-rate of the physics, the more realistic it can seem.

Basic Detection:

• Basic collision type:

(2d or 3d) circles:

• Check if the distance from the bounding sphere centers (of two objects) is >= the sum of
• Use this equation: distance= sqrt(dx^2+dy^2) <= R1+R2 (slow)
• Or better yet, this version: dx^2+dy^2 <= (R1+R2)^2 (faster since no square root)  • Recommendations:

• Use simple spherical collision as the base of all collision detection,
doing more advanced collision detection once the insides of the spheres have been penetrated.
• Don't check each object against every other object in the game each frame
(more on this further down in the other recommendation sections).
• Problem:
Dealing with movement: With discrete time, you are “teleporting” objects, moving them in a
linear fashion (along a straight-linepath) each frame. You need to take into account when objects
should collide (when they cross paths in a
frame/time step), but it is skipped by the step. This, because the objects went past one another
instead of into one another.
• (One) Solution:
Make sure that objects never “teleport” over one another to avoid the problem altogether.
For example, you could make it such that objects can never move more than double the radius
of their bounding sphere in any given time-step. Where if you capped the speed so that a
bounding sphere could not move more than twice it's radius, for a 0.1 sec. time-step,
you would simply multiply that by the frame rate to determine the max velocity
of the object in terms of your game's distance units. For smaller objects (with smaller bounding
sphere radii) that you want to go fast (e.g.: bullets), you can make the time step smaller.
Of course there is a performance hit, so only do it if you can get away with it in your game.
• (A second) Solution:
Check if the center of one object’s bounding box is intersecting with the rectangular path of
another object over the current frame. The rectangular path of objects should be taken into
account with line segments given the objects position in the last frame to the current one.
This can be stored or reverse computed using the physics involved.
• Problem:
Detecting collision between rectangles of arbitrary size and orientation.
• (One) Solution:
When using boxes, you can just check the normal vectors on all sides (parallelopiped
, six orthogonal planes) in regard to the center point of the line-path that the object
passed through this frame. You can take all the normals (of the cube) and say: if I’m on
the “in”-side of each line as it passes through the planes of the rectangular path. Then
you can detect whether or not you’re inside the box (with respect to a current vertex),
and the objects are colliding.
• Problem: Detecting precise collisions:
• (One) Solution:

You can check if the rectangle made up by the path of an object's bounding sphere has collided
with the rectangular volume of another object's path.
• (Another) Solution:

Could check the line-paths of objects in a frame and not the rectangular path volumes.
Of course, this method is less accurate when it comes to detecting collisions with
the smaller objects.
• Tips:

• Determining if arbitrary boxes have collided is very difficult and not advisable in contrast
to sphere collision.

• Key factors to consider:

• Momentum
• Other rebound effects, variables, and coefficients involved with the physics,
like: momentum coefficient, reverb, coefficient of friction, etc.
• Discrete time steps with linear movement of objects over each frame

• Problem:
After a collision between objects is detected, doesn't the order that objects collisions
are resolved in matter? For example a collision between two objects can get resolved before
a third object that was supposed to be involved with the collision could also be resolved as it
should have been.
• (One) Solution:

If you have the velocities of your game objects capped, so that they can only move a given distance
each frame and the faster objects are updated first (before collision detection/resolution).

• Problem: Can’t let colliding objects be interleaved (occupying some portion of the same space).
• (One) Solution: Figure out where on an object's path (in a frame) it's bounding sphere collides
with the edge of the other object's bounding sphere, then place the object just before it.
That is close enough to "collide" (Have objects close enough to look like it).
• (A second) Solution:
The moment you detect an object collided, move it back half the distance that it traveled, you
either are colliding or not. Continue moving objects back and forward to make them "collide"
at near the exact place and time that they (actually) collided. A binary search is efficient
to achieve this method.
• Tips:

• Use an epsilon value to determine when objects are close enough to be in contact (This is done
mainly for speed purposes but accuracy is also a factor). Think of it like this: How big can
the epsilon value be made and you can get away with it. In 2d you’d want the epsilon value to be
something like one pixel (simple right?). But with 3d you can fudge it more and it may take some
more fine tuning.
• (A third) Solution:
Can reverse compute the positions of both object's bounding spheres when they collided to where
they were before. Then you will have a beginning and end point for the object's path in that
frame. Once you have the paths (as line segments) you can encompas the bounding spheres volume
along that path as a rectangular of size correlating to the bounding sphere/path length and at
an arbitrary orientation.

• Tips:
• Often times phsics engines are made for the general purpose case and as such don't take
advantage of major shortcuts, so they're not as fast as something you could make.

• Could do complex polygon collisions, but they are very hard. Convex polygons are much easier
to do collision for than concave ones. Even if there are concave polygons being used, they
can be broken up into multiple (connected) convex polygons.

• Problem:

With discrete time steps there is a problem with collisions on walls, if something goes fast enough
then it could be ambiguous as to where it will be at the end of the frame in the provided time step.
Note that polygons are planes and can be considered as walls depending on your circumstance.

• (One) Solution:

If something collides with a wall so fast that it appears far away from the wall such that it’s
noticeable. Then the object should be put right next to the wall so that it looks like it collided. • (A second) Solution:

When processing one object at a time, objects can get interleaved within one another. You can sort
each of the objects from the slower to the faster moving ones so that no slow-moving object could
get into a faster moving one. You may want to put a hack into the game to take into account when
objects are colliding and have the same velocity.

• (A third) Solution: Could have a 2d (or even 3d) array, partitioning the world into sections (equating
to cells in the array) where only the objects in each section would be processed for collision with
other objects in that and perhaps subsequent sections.