0
\$\begingroup\$

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)

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.