[Haskell-cafe] Testing a collision detection system
jo at durchholz.org
Mon Jul 30 06:19:04 UTC 2018
> 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
More information about the Haskell-Cafe