On Programming

I recently implemented "picking" in the publicly available parts of the Doom 3 engine. Picking in 3D games (or applications) means that the mouse cursor position is mapped to the 3D world in such a way that the mouse can be used to "pick" up objects in 3D space. In this post I would like to describe how I used testing in implementing this technique, by first implementing a "spike" solution with visual testing, and then using data from this solution to implement a piece of code that is fully tested without manual intervention. This is an exercise in arriving from an unreliable testing method, that is, looking at the screen, to a reliable one, using data that a machine can process automatically. I briefly touched on the same topic here.

The spike

In "Extreme Programming" the term "Spike Solution" basically means venturing out into the untested waters and "hacking" together a piece of code which roughly does what we want, in order to learn about the problem as well as the solution. So I did exactly that. I found a convenient place to implement my picking code in the update loop of the game. The code would shoot a ray from the mouse curser position into the world, and intersect it with the geometry, providing me with the intersection point (if any). As a visual indication, I would render a sphere of some size at the intersection point. If the mouse cursor appears to be always in the center of the sphere, I assume my code is correct.

After a few iterations over the code, and some grappling with high school trigonometry, I arrive at a satisfactory solution. Visually, everything looks correct, the data in the (occasionally invoked) debugger also looks good. Here is an actual screenshot, with a wireframe sphere indicating the point of intersection on the ceiling, close to the viewer:

Now that I have some code which does roughly what I want, it is time to put it under test. After all, I will get tired of staring at my sphere to test my code for correctness whenever I change it.

The failing test

To put my code under test, I first write a failing test. The code I have written so far essentially calculates the end-point for a ray which will be tested for intersections with the game geometry, the start-point being the location of the viewer. In the game, I am interested in that intersection point, to find out what is in the game world at this point, in order to operate on it in a certain manner. In the test, I am really only interested in the end-point of the ray - if this point is correct, I assume the rest of the operation will be fine. My goal here is to use data that a computer can verify (in my case, a vector consisting of three floating point numbers), as opposed to the visual cues I have gotten so far, which need the human eye to judge (approximate) correctness.

So now, having rid myself of any dependency on the game data, which is expensive and time consuming to load, my test simply has some inputs, and an expected output, and will run completely independent of the game.

My inputs are (for completeness sake):

• The screen coordinates of the mouse cursor
• The horizontal and the vertical field of view
• The view matrix
• The eye point (position of the viewer)

My output is another 3D point, the end-point of the ray which is shot in the view-direction, distorted accordingly using the field of view variables. So, I put the code I have "hacked" into the game into a class, and put this class under test. This test lives in a seperate project from the game project, and is run independently (and cheaply). The first version of my test looks like this:

As you can see, I set up some fantasy data, put it through a function in my new "Pickray" class, which is a copy of my spike code, and check if the result is equivalent to another fantasy 3D point (taking a small epsilon into account). Of course the test fails. This, in the words of Kent Beck, is progress. Because now I know exactly what to do next: I need to make this test pass. How do I make it pass? By feeding it the correct pairs of input data and expected output data. Where do I get this data? Why, by exercising the code that I have put into the game, the code which was visually verified to be correct.

Sampling data

So, back in the game code, I add some lines that print the inputs and the expected outputs I am interested in. Since I am really excited at this point, I don't bother much with formatting. The obvious idea of formatting the output so it becomes correct C++ code ready to be pasted directly into my test eludes me at this point. That's ok though, I remembered it early enough later on. At any rate, an early version of the output code looks like this:

This code dumps the current data whenever I move the mouse (and whenever a certain console variable is set to 1). The high precision in the output is necessary to avoid imprecise results in the test - so the more digits after the comma I can grab, the better. I fire up the game, move the cursor around a bit, and I get a lot of "real world" data to choose from. A few copy and paste operations later, and some reformatting, and the fantasy data in my test is now replaced with one set of this real world data. One version of my first passing test looks like this:

This looks pretty good already: I can get the game to output data which I can use in my test, testing the exact code that the game gives me output samples from. By now I am confident enough to replace the "loose" code in the game with the class I have since put under test. I have moved my tested code already to "production". Always a great feeling.

At this point I am ready to refactor my test for using multiple data samples. I add a little infrastructure in the test, enabling me to add an arbitrary amount of samples for testing. My test now looks something like this:

The class PickrayTester takes care of collecting samples and running the tests. Meanwhile, the code in the game that outputs my samples has been changed to produce correct C++ code, nameley a block of code starting with tester.addSample... which I can directly paste into my test, for every data sample I want, and for as much samples I want.

The final thing I want to do is to remove some of the remaining manual tedium. Also, my test starts looking a bit fat, depending on how many data samples I use. So, approaching the inevitable happy end, I change my sample output code in the game to directly write into a cpp file, which is in the same directory as my test. I call it PickraySamples.cpp. This file now solely contains a list of tester.addSample.. blocks. In my test, I replace the inlined sample data with an #include statement that includes the generated file:

At this point I declare my mission to be accomplished - I can now change my picking code with the safety net of an automated test. Obviously, there is more to picking up 3D objects than just shooting a ray into the world. But the automatically asserted correctness of this integral part is already a nice and solid foundation to build on.

This entry was posted on Monday, August 14th, 2006 at 10:21 and is filed under Doom3, Gaming, Programming, TDD, c++, idsoftware, testing. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.