Collision Detection algorithm using Line Detection

Question

For a 2D physics sandbox I am working on, I need a way of detecting detecting a collision using lines. This sandbox uses a class called Particle, which has a x and a y (stored as a struct called vector2) and a velocity, which also has a x and y. Previously, to find a collision, I tried to detect if the coordinates + the velocity was where another particle's coordinates + velocity was, and then I divided the velocities by the highest velocity, then checked all the velocities incrementally, to prevent tunneling. However, I could not get this to work, and I had suspicions it would be slow when velocities were very large. I now want an algorithm that detects whether two lines (one point is the coordinates, the other is coordinates + velocity) intersect, then put the particles one space before the collision. Since this algorithm is for a physics sandbox, it has to detect any collision, including, for example, if the two lines will collide but are parallel. For simplicity's sake, I won't post the Particle class code, so feel free to create the function using whatever variables you wish (as long as they're self-explanatory)

Answer 1

I now want an algorithm that detects whether two lines (one point is the coordinates, the other is coordinates + velocity) intersect

If I understood you correctly you want to detect the collision between lines. Two lines intersect if they have a matching pair of x/y coordinates.

For example, if we have line a (y = 0.5x + 1) and line b (y = 0.1x + 3). we get the following four equations:

1. y = 0.5x + 1
2. y = 0.1x + 3
3. x = (y-1) / 0.5
4. x = (y - 3) / 0.1

From that you can check if these equations are true:

y = 0.5x + 1 = 0.1x + 3

x = (y-1) / 0.5 = (y - 3) / 0.1

If they are, you have an intersection, if not (i.e. 4 = 7), you don't.

This will check if two lines intersect, however, what you probably want is to check if two line segments intersect. As far as I am aware, you can't check that in y = mx + b form. You can, however, check it through parametric form:

position = initialPoint + direction * scalar where initialPoint and direction are vectors(in your case, vector2's).

You can do with this equation as I did in the previous example. If you don't know how to do it, it is shown at the top of SIGHT & LIGHT: how to create 2D visibility/shadow effects for your game

After you got the points, you can check to see if the scalar value of the intersection makes sense. I would use the magnitude of your velocity vector.

Finally, if you just want to restore the state if there is a collision, you can simply save it before the move, and if it collides post-move, restore it.