通过

Collision and wall sliding on a RoundLine

  • 项目

I think I've got it! After a couple hours of head-scratching and geometry, my XNA code to handle collision between a disc and a RoundLine is looking correct -- at least in my test app. Soon my maze game will be a bit more challenging, since the walls will be impenetrable.

Okay, so there's a lot of colorful lines and dots in that picture -- here's what it all means:

  • The red line is the target line, the one we're testing for collision against
  • The green line is the disc path line (in the screenshot, the start position is highlighted)
  • The red dot is the point at which the path first intersects the target line
  • The gray dot is the point at which the path last intersects the target line (this might be useful someday)
  • The orange line connects the red dot to the closest point on the target line
  • The blue line is the orange line rotated 90 degrees and made unit length
  • The cyan line is the projection of the post-intersection part of the path line onto the blue line.

So, suppose the disc is trying to move along this green path. We let it proceed for the first part of the path. But due to the collision with the red line, we stop the disc at the red dot. But the disc shouldn't just stop dead here -- it feels better to have it slide along the wall. The cyan line shows this sliding path. The disc should end up at the end of the cyan path.

Here's what happens if you graze the tip of the RoundLine:

The green lines I'm using for testing are way longer than are likely to occur in practice, unless the disc is moving really fast from one frame to the next. More typically, the path will be something more like this:

The math turned out to be pretty basic geometry and algebra. My math skills are pretty rusty, so it took some time to figure out, but the result is straightforward and should be reasonably efficient.

I broke the RoundLine intersection problem into three separate subproblems: one for each endpoint, and one for the line part.

To solve the endpoint intersections, I translated the path so the endpoint was at (0, 0). Then I expressed the path parametrically for x and y:

x = p1.X + (p2.X - p1.X) * t

y = p1.Y + (p2.Y - p1.Y) * t

Pythagoras says:

x * x + y * y = dist * dist

And as I learned last time, it's easier to solve for distance-squared than for distance. Remember that in this case, the distance we care about is the sum of the disc's radius and the line's radius. So dist is a constant value, as is dist * dist.

If you substitute the top equations into the bottom one, you end up with a quadratic equation that can be solved for t using the quadratic formula.

To solve the line intersections, I transformed the path so the target line is going from (0, 0) to (1, 0). In this space, y is the distance from the target line, and x can be used to find if the intersection points are between 0 and 1 (meaning, between the RoundLine's endpoints).

So I compute all six possible intersection points, and find the minimum (red dot) and maximum (gray dot) that are still on the disc path (t between 0 and 1).

Next up: determining which lines to test against, and dealing with multiple collisions. I don't foresee a lot of pain there, though. After that I'll plug this code into the maze game, and hopefully the disc's interaction with the walls will feel natural.

-Mike

GraphDemo_1_1.zip

Comments

  • Anonymous
    February 14, 2007
    PingBack from http://www.xnatutorial.com/?p=66

  • Anonymous
    February 25, 2007
    Man, I totally jinxed myself when I predicted that hooking up my RoundLine collision detection / sliding