The next thing I want to add to my XNA maze game is collision detection, so my little orange disc can't go right through the maze walls. There seem to be two alternate general approaches that can be taken regarding collision detection:

  1. After reading the user input, determine whether moving the disc the way that the user requested would cause it to penetrate a wall. If so, alter the disc's path before applying it, so as to not penetrate the wall.
  2. After reading the user input, move the disc the way that the user requested, then determine whether that motion caused it to penetrate a wall. If so, "back up" the motion so it no longer penetrates the wall.

Since using Latin phrases makes everything sound more scientific, these two approaches are termed a priori and a posteriori. The a priori approach seems more clean and straightforward to me, so I'm going to wander down that road and see how things go.

Here is a careful breakdown of the problem I want to solve: We have a disc D, with radius Dr, which is at position Dp0 at time t=0. User input indicates that we are considering moving the disc (with constant velocity) to position Dp1 at time t=1, but a line might be in the way. For any (thick, round) line L, which also has a radius and two endpoints, compute the following:

  1. Will disc D overlap line L at any point, as it moves from Dp0 to Dp1?
  2. If so, at what time t between t=0 and t=1 does the overlap first occur?

This problem has two twists in comparison to the usual point vs. line geometry problems. Firstly, both the disc and line have nonzero thickness, so these have to be accounted for. That is, we aren't looking for the "t" value where the mathematical point intersects the mathematical line, but rather the value where the distance between them first reaches a value equal to the sum of their radii. Secondly, the line is not infinite, but is more correctly a line segment with two endpoints. So the distance from the disc to the line is not a single polynomial equation.

These twists make the problem complex enough mathematically that I was having a hard time getting my head around all the issues, let alone how to compute the solution. There's always the option of using brute force or some sort of binary search to find the first intersection. But it seems that a direct derivation of "t" shouldn't be that hard, and would be much more efficient, so I pressed on.

I decided it was worth taking the time to write a program that would let me interactively explore, and graphically represent, the problem. So I wrote a program that lets me move a disc and its linear path around a target line, and graph "t vs. d" where "t" is the parametric position along the disc's path, and "d" is the distance between the disc and the line. The resulting program was quite helpful. Here's a look:

The red line is the "target line" that we are measuring distance to.  The green line is the path taken by the disc (it's a happy coincidence that a disc, swept along a line, produces a RoundLine).  The orange line shows the shortest distance from the disc to the target line.  By pressing B and moving the right stick, you can arrange the disc's path however you want.  Then you can sweep the disc along its path and see the correlating point on the graph (marked in green).

I wrote a Graph class to handle drawing graphs in a general way. For a while I had grandiose visions of making this class totally general and reusable and bursting with clever features, but in the end I only hooked up some basic functionality, and you have to specify some things (like grid size) manually. What's there is useful, but it would need more work to be a complete and reusable component. Here's a shot of it graphing y = x * sin(x), and that equation's first derivative:

One great feature in C# is delegates, which are similar to function pointers. The graph class takes a "ComputeY" delegate, which it calls to evaluate the Y coordinate for every X value. The really slick thing about delegates is that they can be a class member function which references member variables -- to do this requires in C++ hoop-jumping, but it "just works" in C#. This is a huge help, since my "LineDistance" function needs to access class information about the disc position, target line, and graph mode.

Back to the problem at hand. We are trying to find the "t" value at which the distance first drops below the value which is the sum of the disc's radius and the line's radius. In my program, the target line has radius 0.2, and the disc has radius 0.1, so we're looking for the place where the graph dips below 0.3 (the dark blue gridlines are spaced 0.1 units apart). When the target line's endpoints aren't relevant to the problem, the distance (graphed in white) is a simple linear function of t, so its derivative (graphed in gray) is a constant (well, two constants -- it flips when the disc crosses the target line):

When the endpoint determines the distance, the distance is nonlinear. I thought it was quadratic at first, but it's hyperbolic, which means that even its derivative is nonlinear:

In the most complex case, the distance goes from hyperbolic, to linear, to hyperbolic:

Yuck. But look at what happens when we graph distance-squared, rather than distance:

It becomes quadratic, with a sequence of linear derivatives, regardless of whether the endpoints are involved! The slope of the derivative is the only thing that changes for the various phases of the graph. It looks like it will be easier to compute the value of t at which d-squared first drops below (0.3)-squared.

To someone with better mathematical intuition than me, this all may have been obvious.  But it didn't click for me til I could visualize it and tweak the variables.

You might find this program a useful starting point for creating visualizations for other geometric/mathematical problems. In any case, it's fun to play with. Many people use Java to create similar visualizations -- this site is particularly impressive. Using XNA instead of Java (or MFC, or Mathematica, or Applesoft, or whatever) has pros and cons, but it got the job done for me, and that's the important thing. Oh, and it was fun -- that's important too.

-Mike