Posts published by “centaur”

So I'm writing a new sorting function for OIDs. What OIDs are is not important right now ... the important things are that they're strings that hold dot-separated sequences of numbers, like 1.3.6.1 (the Internet OID) and because the sequence of numbers is significant, OIDs cannot be sorted alphabetically (because 1.1 should be followed by 1.2, not by 1.10 as naive alphabetic sorting would imply).

Now, there's a lot to be done to update our software to sort OIDs correctly, but, being trained as an AI programmer, I started by breaking the problem down into its smallest possible parts --- namely, an OID comparison function. And, being a good modern Java programmer, I started with a JUnit unit test which enabled me to check my comparison function.

For those who don't know, JUnit tests are functions in a software module that all start with the word "test", like testLengthOneOIDs or testOIDsVsBlanks. Initially I just had a few handwritten tests - 1 is less than 1.1, which is less than 1.2, which is less than 1.12, which is less than 1.100 but greater than 1.2.1, and so on. These tests are complicated little stanzas of code, and being trained as a good AI programmer, I kept breaking things apart, writing a validateEquality and validateOrdering functions that automatically checked two OIDs for the right ordering. The idea, you see is that once I've written one correct test, I now have a tool to write many more correct tests, and don't have to worry about typos causing failures in later tests.

But still, there were dozens and dozens of cases to test. Then I had a brainflash: rather than writing a whole bunch of tests, one for each pair I wanted to examine, why not write an array with a list of OIDs in the right order (1.1, 1.2, 1.2.1, 1.10, 1.21, 1.30.1, etc) and then write a simple pair of for loops that test each one for the right sequence?

So I did. The outer loop went through every OID in the given list, and the second one went through every OID preceding it in the list to make sure that the comparison worked. That is, for three OIDs, the outer loop would go through items 1, 2 and 3. On the first loop, the inner loop would just go through item 1, but on the second it would go through 1 and 2, and then finally 1, 2, and 3, testing all combinations of OIDs.

SO I wrote that, as well as three or four lists of OIDs. And everything passed with flying colors. So I added that code to my OID utility library, built my sorter exploiting Java's wonderful Collections framework, and sorted the OIDs to call it good. It even ran smoothly at first.

Until I added some new code to do searches. This changed the list of OIDs feeding into my sorting algorithm and --- BOOM! --- Java compains that I'm asking for the fifth item of a four item list. Bad Java juju. What gives?

Well, it's simple. My cute little validateOrdering function should have been called validateLesserThan, because it implicitly assumed that the first OID it was given was lesser and the second OID was greater. However, that test doesn't test all cases of the algorithm --- to do a sort using Java's Collections framework, you need to generate a *numerical* comparision: the compare function is not asking whether a is less than b, true or false, but instead asking for the *sign* of the *difference* --- so that compare of (1,2) is -1, compare of (2,2) is 0, and compare of (2,1) is +1. This is the mathematical signum function.

My test was testing only lesser than and equality --- two branches, not the three branches of the signum. And, sure enough, when I augmented my validateOrdering tester to include a "desired result" parameter so you could specify you wanted lesser-than (-1), equality (0), or greater-than (+1) --- BOOM --- I found an error with my unit tester. When the comparison algorithm checked to see if "1.2.3" was greater than "1", it had an off-by-one error, assuming the second OID had one more element in its list than it actually had. So Java fall down and go boom.

So the POINT? Don't assume. It's a great idea to write unit tests, and an even better idea to make them comprehensive. But when you do so, think carefully about what you're testing --- make sure that you're testing all possible branches of the function at hand, or it may blow up on you later when some new --- possibly entirely unrelated function --- rips the rug of your assumptions out from beneath your feet of clay.

-the Centaur

I don't go to GDC every year just to futz around hunting old books and new games. Well, maybe I do, but another purpose is science --- extracting information about the state of the science of AI and programming from the giant kettle of effort that is the Game Developer's Conference.

There are a lot of big ideas to come out of the conference --- for example, new games require huge quantities of content and thus new methods and tools are needed to help generate that content. Develop Orthogonal, Interoperable Tools is one pattern to deal with this --- build tools whose parts all work with each other cleanly and flexibly so that a small amount of art and content can be composed together rapidly in many combinations to produce a vast number of different results. The Unreal 3 team demonstrated this idea with their game engine, as to a lesser degree the Halo 2 guys did with their AI.

But this pattern goes hand in hand with Reduce The Cycle Time To Zero. I should have already known this --- my co-workers Henry and Emily and my former boss David Cater have been telling me for years that their biggest win was reducing the compile time loop of their development as close to zero as possible, so that they could make a change, instantaneously see the result, and then make the next necessary change as quickly as possible. Reduce Cycle Time To Zero is critical for rapid development of game content --- to be efficient, artists and level designers need to see the results of their work Right Now so they can make changes As Soon As Possible.

This is now writ large in the Unreal 3 engine, which supports dynamic loading of content and dynamic editing of levels in real time. Artists and level designers no longer need recourse to text files; instead you can wander around in the Unreal 3 world and make all your changes in real time. Move a light --- the shadows move real time. Grab a character by the arm --- see him move around like a rag doll. Tweak the parameters of a particle fountain used to generate a special effect --- watch it change in real time, affecting the lights and the players around it. Heck, it's not even just Unreal 3 --- in a recent Game Developer column the author was hacking together his own game by himself and even HE used dynamic content loading.

So. Reduce cycle time. I can do this. What's one of the biggest bottlenecks in my current development environment? Let's see ... the need to write my Blogger blogs online, or to cut and paste out of another text editor. Hm. How can we make that delay go away, so I can blog thoughts as I have them?

Perhaps with an offline blogging client like w.bloggar (or ecto or the client of your choice).

Let's test that theory. Saving and trying to upload NOW.

OK. So it's not perfect --- I found an error and reposted and ended up with two copies of the same blog. But hey --- it's SOMETHING to be able to use a normal-looking text editor and just hit a button to see it fly up to the server.

-the Centaur