[Haskell-cafe] Testing a collision detection system

[Joachim Durchholz]

> So the idea is to use an existing collision detection library to
> generate (a lot of) test cases from random data.

I think that won't solve your problem. You wouldn't test that your 
collision library works, you'd test that your collision library is 
bug-for-bug-compatible with whatever other collision library you're 
using as your gold standard.

You'd probably be better off by writing a small collision detector that 
uses just the raw data. Optimized not for speed but for easy inspectability.

Then apply that algorithm to the test cases.
If the objects are pixels, AND the bitmaps and check whether the result 
has 1 bits or not.
If the objects are vector art, apply a collision algorithm; I dimly 
recall there was a really simple and easy-to-validate one in one of 
Robert Sedgewick's "Algorithms" books.


To generate the test cases, that's easier for vector than for bitmap - 
you have sets of points and can move/rotate the two shapes so that you 
get each permutation of line endpoints.
Depending on the complexity of your shapes, this may or may not be feasible.

You can compute the convex hull (again, pretty easy if you go by 
Sedgewick) and check that if convex hulls don't intersect, your 
algorithm does not intersect; that's going to cut down on test cases 
that you don't need to check.


Yet another approach to test case writing: Look at each decision point 
in the intersection algorithm, then take a step back and find out what 
that means, geometrically, and write (or generate) test cases for both 
branches. IOW generate your test cases towards 100% coverage.

QuickCheck may help, too.
If you find it does not detect relevant test cases, consider 
restructuring your code so that the decisionmaking is simplified, and/or 
separated out from the nitty-gritty details of actual checking. Maybe 
separate it out into a "strategy layer" and an "execution layer", where 
strategy decides how to test and execution does the actual test (I can't 
be clearer because I don't know the kind of shapes you are testing).
The goal would be to separate the logic, because that's going to 
simplify testing tremendously. It may even make the code so 
understandable that you don't even need to write tests, because the code 
is self-evident - well, that's probably just an ideal that you can come 
nearer but never fully achieve, but it's a guideline to consider 
whenever you make decisions about how you structure your code.
Refactoring in this way may amount to a full rewrite. If may also reduce 
your testing effort; it's difficult to assess whether it's going to be a 
net win.

Regards,
Jo