**2D**

If the objects all move on 2D plane, your problem is greatly simplified if you just think about the problem as a line intersection problem in 2D.

Each frame, your actors move on the X/Y axis by some amount. Plot a point here and connect it to the last position point. This becomes a line segment which indicates how much the character moved.

To test for collision, you test the newly created line segment against all existing line segments. If there is an intersection, then you have a collision to handle. If there isn’t a collision, you can place the new line segment into the collection of line segments to test against in the future.

Note: This is a dirty O(N^2) solution.

Optimizations:

-If a character is moving in a straight line, ie, the slope between the last line segment and current line segment is unchanged, then you can merge the line segment vertices to create a really long line segment. If you’re travelling in a straight line for 1000 frames, you don’t need 1000 line segments, you just need 1.

-If your game rules allow it, you can delete old line segments to save on space and processing.

**3D**

This gets a bit more tricky because objects move in any direction in 3D space, so the 2D plane solution won’t work. You can still use a similar approach though by using planes with fixed dimensions (or a static mesh object). You’ll have to get the characters “up” direction and orient the plane accordingly, and get the characters change in elevation and rotation. The messy bit comes when the character rotates. If they pitch up or down, there will be gaps and overlaps between the planes. Similarly if they roll. Yaw is seamless. Afterwards, you can apply a plane intersection test to see if there is a collision (though, you may have to write your own depending on if the engine supports it out of the box or not).