Testing a collision detection system

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Testing a collision detection system

mpevnev
As a part of a project, I write a collision detection system. It is in
dire need of testing, but designing and writing tests for all possible
pairs of types of colliding geometry would be a pretty big effort - not
only I would have to calculate the fact of collision manually for
20-something pairs of types of colliding geometry, I would also have to
do so multiple times for each pair, since each pair requires several
test cases.

So the idea is to use an existing collision detection library to
generate (a lot of) test cases from random data. I've found two such
libraries for Haskell - HODE and Bullet. The problem is, Bullet bindings
aren't documented at all, and HODE (which isn't really documented
either, but at least lists available functions) is extremely ugly with
IO all over the place, and manual tracking of objects' lifetimes (at
least that's what I infer from `create :: World -> IO Body` and
`destroyBody :: Body -> IO ()`, because again - no documentation).

So my question is: does anyone know a library I could use? I'll pretty
much settle for whatever.

--
Michail.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Testing a collision detection system

Brody Berg
And you've already ruled out QuickCheck and friends?

On Sun, Jul 29, 2018 at 2:08 AM, <[hidden email]> wrote:
As a part of a project, I write a collision detection system. It is in
dire need of testing, but designing and writing tests for all possible
pairs of types of colliding geometry would be a pretty big effort - not
only I would have to calculate the fact of collision manually for
20-something pairs of types of colliding geometry, I would also have to
do so multiple times for each pair, since each pair requires several
test cases.

So the idea is to use an existing collision detection library to
generate (a lot of) test cases from random data. I've found two such
libraries for Haskell - HODE and Bullet. The problem is, Bullet bindings
aren't documented at all, and HODE (which isn't really documented
either, but at least lists available functions) is extremely ugly with
IO all over the place, and manual tracking of objects' lifetimes (at
least that's what I infer from `create :: World -> IO Body` and
`destroyBody :: Body -> IO ()`, because again - no documentation).

So my question is: does anyone know a library I could use? I'll pretty
much settle for whatever.

--
Michail.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Testing a collision detection system

Ivan Perez
Definitely worth a try.

It seems like a large test space.

My expectation, based on what I've seen when we applied QuickCheck to haskanoid, would be that, with the standard generators, QuickCheck may be good at detecting things that will not normally happen in realistic simulations, but you may have to tune the generators to look for the more interesting cases you want to test, and that'll be similar-ish to writing your own test cases.

But I'd love to be proven wrong! :)

Ivan

On 29 July 2018 at 17:44, Brody Berg <[hidden email]> wrote:
And you've already ruled out QuickCheck and friends?

On Sun, Jul 29, 2018 at 2:08 AM, <[hidden email]> wrote:
As a part of a project, I write a collision detection system. It is in
dire need of testing, but designing and writing tests for all possible
pairs of types of colliding geometry would be a pretty big effort - not
only I would have to calculate the fact of collision manually for
20-something pairs of types of colliding geometry, I would also have to
do so multiple times for each pair, since each pair requires several
test cases.

So the idea is to use an existing collision detection library to
generate (a lot of) test cases from random data. I've found two such
libraries for Haskell - HODE and Bullet. The problem is, Bullet bindings
aren't documented at all, and HODE (which isn't really documented
either, but at least lists available functions) is extremely ugly with
IO all over the place, and manual tracking of objects' lifetimes (at
least that's what I infer from `create :: World -> IO Body` and
`destroyBody :: Body -> IO ()`, because again - no documentation).

So my question is: does anyone know a library I could use? I'll pretty
much settle for whatever.

--
Michail.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Testing a collision detection system

Joachim Durchholz
In reply to this post by mpevnev
> 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
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Testing a collision detection system

mpevnev
In reply to this post by Brody Berg
I've just looked up a QuickCheck tutorial, and it looks positively
amazing. Thank you for showing me a beautiful piece of Haskell.

On Sun, Jul 29, 2018 at 02:44:16PM -0700, Brody Berg wrote:

> And you've already ruled out QuickCheck and friends?
>
> On Sun, Jul 29, 2018 at 2:08 AM, <[hidden email]> wrote:
>
> > As a part of a project, I write a collision detection system. It is in
> > dire need of testing, but designing and writing tests for all possible
> > pairs of types of colliding geometry would be a pretty big effort - not
> > only I would have to calculate the fact of collision manually for
> > 20-something pairs of types of colliding geometry, I would also have to
> > do so multiple times for each pair, since each pair requires several
> > test cases.
> >
> > So the idea is to use an existing collision detection library to
> > generate (a lot of) test cases from random data. I've found two such
> > libraries for Haskell - HODE and Bullet. The problem is, Bullet bindings
> > aren't documented at all, and HODE (which isn't really documented
> > either, but at least lists available functions) is extremely ugly with
> > IO all over the place, and manual tracking of objects' lifetimes (at
> > least that's what I infer from `create :: World -> IO Body` and
> > `destroyBody :: Body -> IO ()`, because again - no documentation).
> >
> > So my question is: does anyone know a library I could use? I'll pretty
> > much settle for whatever.
> >
> > --
> > Michail.
> > _______________________________________________
> > Haskell-Cafe mailing list
> > To (un)subscribe, modify options or view archives go to:
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> > Only members subscribed via the mailman list are allowed to post.

> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.


--
Michail.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.