BentMaze 1.1: Collide and slide
Man, I totally jinxed myself when I predicted that hooking up my RoundLine collision detection / sliding code to my XNA maze game wouldn't be painful. It was. But after a lot of hours of debugging, I've got it working well enough to call done and usable, though not perfect.
The main problem arises because collision management is all about that exact threshold where an equation changes state, i.e., the moment at which we go from being just outside the wall to just inside the wall. If different parts of the code express insideness/outsideness slightly differently (different algorithms, different coordinate systems, etc.), things that are mathematically equivalent actually give different results due to floating-point rounding error. For instance, I could call my FindFirstIntersection() routine to get the parametric "t" value at which the disc exactly intersects the wall, then call my distance-to-line function and discover that moving to "t" would put me just slightly (like, 0.000000162 units) inside the wall. So the next time I try to move away from the wall, my FindFirstIntersection might return a tiny "t" number, indicating that I'm tapping on the wall's edge from the inside, and thus can't move away.
I first tried to accommodate this by adding little tolerance fudge factors to a bunch of my equations. If you're within 0.00001 of the line, you can probably consider yourself exactly in contact with it, right? But this approach just shifted the breaking point around, and lead to endless random tweaking of these tolerances. And you still need to treat exact contact with the wall carefully. If you are "in contact" and trying to move closer to the wall, you need to set t=0 to stop further motion. If you are moving away from the wall, you need to not do this or else you'll be stuck to the wall forever.
I decided to avoid tolerances as much as possible and instead use a single uniform collision test as a backup to verify the results from all other tests and calculations. The collision test I chose was that the distance squared from the disc to the line, as measured by one piece of code, absolutely must be greater than or equal to zero. Usually, this test would agree with my other results. But in the cases where the other tests were telling me to go to a point that would penetrate the line (according to my standard test), I would instead do a binary search between a known-good (non-penetrating) value and the known-bad (penetrating) value until I had a point that was very close to the line, but still passed my standard test. Eww -- my original vision of a clean, near-constant-time algorithm was suddenly very messy and variable in terms of execution time. There's still an upper bound -- I never iterate more than 10 times -- but it's frustrating because my whole objective with using algebra to compute these intersection points was to avoid the need to stab around with various values until finding an answer that was "close enough." However, I don't think a completely iterative solution would be sufficient. There's always going to be a need for some higher-level analysis. A straight binary search for collision is dangerous because t=0 might not intersect the line, t=1 might not intersect the line, and even t=0.5 might not intersect the line, but there is still some "t" value at which the disc does intersect the line, so some mathematical analysis of the situation is necessary. I couldn't find many useful resources on this topic on the Web, so it's hard to know how near or far my solution is to being optimal.
But enough gloominess. What I've got works pretty well. If you collide with the rounded end of a line, you roll around it in a natural way. If you move into a corner of two walls, you snug right up into that corner and don't wobble around until you change direction. You can slide happily along the wall's edge. And I haven't yet found a case where the disc misses a collision. If you zoom way out so you can see most of the maze, the disc moves much faster in world-space units, yet it never fails to bang up against any walls in its way.
That was more than enough collision code for me. I'm ready to get back to coding up some whizzy graphics.
-Mike