Wednesday, December 23, 2009

Maze Wars SVG version 1.0b2 Released

Maze Wars SVG version 1.0b2 has been released. The closest thing to a functional change is the addition a partial work-around for a Firefox 3.5.x SVG rendering bug that made the eyeball on the game’s first web page render incorrectly. No code changes, other than the deletion of some old, commented-out material. No changes in game play.

Also, the beginnings of a web site for the game can now be found at http://mazewarssvg.sourceforge.net/.

And, last but certainly not least, I’ve had the pleasure of corresponding with Greg Thompson (thanks Bruce), one of the authors of the original Maze War game, and seem to have received his blessing. Nothing said was usable as an endorsement quote (darn it), but the tenor of the correspondence was entirely positive.

Thursday, December 17, 2009

Maze Wars SVG version 1.0b1 Released

Early this morning, Maze Wars SVG version 1.0b1 was released. This retro multi-player first-person shooter had a couple of the inevitable bugs that always seem to be discovered only after a product is announced to the world. But they were exceedingly minor bugs. And they're gone now.

Enjoy.

Wednesday, December 16, 2009

Maze Wars SVG Finally Released

I’ve re-created the classic, multi-player, first-person shooter game “Maze Wars” using modern web technologies (server-side: Java; client-side: XHTML, Javascript, Ajax, and Scalable Vector Graphics). Today, that re-creation has reached beta status, and I believe is ready for general use. It's available on SourceForge, where you can find not only the GPL source, but a pre-built WAR file just waiting to be deployed to your favorite Java web application server. (I’ve only tested it with Tomcat, however.)

Work on this project began sometime around July, 2008, and after going through several periods of dormancy, is finally clean enough and feature complete enough to merit public promotion. It is based on my recollections (and a few graphics files I held onto) of playing a version written for the original Macintosh, sometime around 1987. When the consulting phone wasn’t ringing, it brought productivity to a halt among our office Mac users for several weeks. Legend has it that it had exactly the same effect on a little corporation called Apple Computer.

I’m not talking about the commercial version that eventually appeared (MacroMind “Maze Wars+”). No, this implementation was something else, and earlier. If memory serves, it had the video RAM address of the original 128K Mac hard-coded into it. I remember patching the binary several times in subsequent years to keep it working (video RAM kept moving as Macs gained memory), but eventually Macs changed enough that keeping the game working was beyond mere binary hacking, and the game effectively died. I have no idea who wrote it (let me know if you do), but thanks to whoever was responsible. A lot of people had a lot of fun with it.

(Of course, profound thanks must also go to the creators of the original Maze War game in 1973: Steve Colley, Howard Palmer and Greg Thompson.)

All these years later, I found myself missing the Maze Wars game, and decided that with Scalable Vector Graphics (SVG) resurgent among modern browsers (Safari, Firefox, and now Chrome) I might be able to recreate it for the web. And it looks very much like I’ve succeeded.

You can get some idea of what the original Macintosh game looked like, and how it built its graphics, from the following files (originally in MacPaint format) that were a part of that game.

There were the eyeballs, of course. All the players were represented by eyeballs. As you can see, they were pre-rendered in parts that could be blitted together to form an eyeball at any of the supported sizes (9) and angles (4). If it’s not obvious, the “ball” portion of each eyeball was the same for every view at any given size. It was only the middle portion that changed, which is why there are renderings of the iris and sclera facing head-on, to the left, and to the right, next to each eyeball, and that’s also why the tail, which appears on the eyeballs by default, is carefully drawn such that it stays within that middle portion of the ball – blitting an iris/sclera section onto the eyeball would completely hide the tail. By blitting (or not) a new middle segment onto each ball, any eyeball view could be created very simply. (The four images occupying the right side of the file weren’t visible in the game. They seem to be the doodlings that led the artist to the final renderings on the left side.)

My eyeballs are a bit simpler, omitting the veins in the sclera, for instance, but they’ve gained things the originals didn’t have, like gradient shadings, and individually colored irises. Seen from behind, they retain the pointed tail, because it just wouldn’t have been the same without it, but, because it took me something like three hours to work out the spline curve definitions for drawing the tail, I decided to forgo including any portion of it in the side views.

The game’s screen looked like the top half of this graphic. The first-person maze view was on the left, on the right was the maze map showing the location of yourself and the teleport stations (the circles), and, if memory serves, in the empty space below the first-person maze view was a list of players and, presumably, their scores. The first-person maze view was, like the eyeballs, built by blitting together the pre-rendered elements in the bottom two squares. Wherever a corridor branched-off the one you were looking into, a vertical slice from the right hand square was blitted over the corresponding portion of the left hand square, and—presto!—the uninterrupted walls meeting at a distant vanishing point were now interrupted wherever necessary. No drawing, as such, was required, just a lot of clever blitting together of off-screen bitmaps.

I’ve used a very similar approach in my implementation—not with bitmaps, of course, but with a collection of pre-positioned SVG wall polygons and corridor rectangles which can effortlessly be made visible or invisible by altering their “style.display” properties—because it’s wonderfully simple and effective, and remarkably authentic. It also uncomplicates the implementation in a lot of subtle but important ways, and it even, I realized, creates a rendering bug in one case. I didn’t notice that bug until I’d implemented it myself, but I’m sure it must have been present (though a bit less obvious) in the original version. In practice, I think almost no one will notice it, so I’ll leave it for you to find – or not.

There are, of course, a number of differences between my first-person rendering and the original. For one thing, there’s gradient shading so that everything fades to black by the time it reaches the vanishing point. There’s a hint of color to the floor. Stretches of wall are not featureless; they are interrupted by vertical black lines where corridors would otherwise branch off. (That may enhance the sense of perspective, but I’d’ve preferred not to have those lines. Things just kind of inevitably turned-out that way, and I couldn’t find a good work-around, or an overwhelming reason for being displeased, so the lines remain.) Teleport discs are visible in the first-person view, and they’re a very obvious blue – matched by their representation in the maze map. And, by the way, the sky is black. I’m almost certain that real killer eyeballs only come out at night, so that was a detail that needed fixing.

Other differences: On-screen instructions as you enter the game! A new, random maze for every round of the game. (However, I’ve retained the original 33 X 46 dimensions of the maze. After some experimenting, the original size seemed just right - neither too big, nor too small, for good play.) Problems with clipping long player names due to bugs in the SVG implementations of Safari, Chrome and Firefox. Bonuses for killing campers. And, last (I think), but not least: Bots, so there’ll never be fewer than ten players in the game, even if you can’t get anyone else to play.

The results look something like this, but, being rendered using SVG, they are resolution independent. So, stretch out the game window to fill your screen and everything scales-up immaculately – giant killer eyeballs!

If you’re comfortable deploying Java web applications, and believe in using modern web browsers, give Maze Wars SVG a try, and please have fun.

Monday, December 14, 2009

Geminids, Margaret, You Were Missed

The weather forecast didn't look promising, but, sunset arrived and our skies were still clear, so I threw my meteor photography gear in the truck and headed for the Bamberger Ranch. After a very nice dinner with David and Joanna in front of the fireplace, we headed out to see the meteors. They headed for the area around the observatory, because it was close; I headed out to the windmill near the red pens – my standard location for some time – since I can incorporate the windmill into my photos to good effect. The Milky Way stretched overhead clear and bright as my truck trundled to a halt near the windmill. There followed the usual tedious unloading and setting-up, and the difficult focus adjustment trial-and-error (focusing on infinity doesn't do the trick). Then the skies closed, and the best meteor shower of the year vanished. I waited out in the dark cow pasture as the wind hurtled past, making the night much colder than it claimed to be, and shaking even the truck as it went. Hours later, I gave up, just as the peak should have been happening. The sky had cleared briefly once or twice, but the clouds rushed back just as quickly as they left. All in all, I think saw only 11 meteors over the course of those cold hours. Most of that time, I was lucky to see a star.

Above, my one meteor photo of the night, caught, purely by coincidence, as one of the focus-checking shots. (View it full-size, and look in the lower-left quadrant.)

I'd been looking forward to this shower all year. Margaret Bamberger and I had even made plans to watch it. But it didn't work out. (Oh, holy crap, how it didn't work out....) Now the long wait for next year's showers begins. And as for this year, I'll be glad to be done with it. Good riddance. I'd dance on its goddamn grave, if it were to have one … and if I could dance.

Sunday, December 13, 2009

Geminids Tonight

The peak of the Geminid meteor shower will be tonight, December 13/14. According to NASA’s Fluxtimator, it promises to be a very good show, peaking at a rate of 66.7 meteors per hour in countryside viewing conditions at 12:16 AM CST. Even as early as 9 PM, which is as early as the Fluxtimator will predict, there should be 46.8 meteors per hour. The only problem around here is the weather, which doesn't look very promising.

Tuesday, December 8, 2009

Parallel Number Crunching – Java and C Source Code

As requested, I've made the source code and sample data for my coplanarity scanning example programs available. These are the programs used to produce the timings shown in my previous post, “Parallel Number Crunching – Java vs. C & Grand Central Dispatch.” Feel free to experiment with them as you wish.

Note that both are hard-coded to break out of their processing loops after the first 5,999,600 planes have been checked for coplanarity with the 30,000 sample points provided in the "data/lc-data-30000.bin" file. That seemed to be a reasonable amount of computation for demonstrating the relative performance of the two implementations. If you want to try to complete the full scan of all possible planes, you'll need to remove that hard-coded break – and then you'll need to wait for a very, very long time.

The more complete Java implementation I've been using for my actual number crunching work has features like saving its processing state periodically, so the program can be quit and later resume running from roughly where it left-off. I've pulled those features out of this example code in order to keep the two implementations similar, small and straightforward.

Here’s wishing you a good night, and good coding.

Sunday, December 6, 2009

Parallel Number Crunching – Java vs. C & Grand Central Dispatch

I've been doing some parallel number crunching lately using Java 1.6 (1.6.0_17) on a MacPro (4,1) with a 2.93 GHz quad-core Nehalem processor. This weekend I decided to brush the dust off my C programming skills and re-implement the core of my Java code in C using Apple's Grand Central Dispatch (GCD) technology to see if I could get a dramatic speed boost. The results were both better and worse than expected.

The number crunching in question was the examination of data from a pseudo-random number generator (PRNG). Specifically, the PRNG output was interpreted as 30,000 triplets of 32-bit signed integers. The triplets were treated as points in 3-space, and the number crunching consisted of the search for every point coplanar with every possible plane those points could define. It's been done before, of course, and found weaknesses in PRNGs like multiplicative congruential generators. For my own edification, I wanted to look for the same weaknesses in some other PRNGs. I have yet to complete a single run, however, so those who've done it in the past either used better techniques than my brute-force approach, had more than my 23 GHz to work with, or were very patient. Maybe some even used worse techniques that were faster. I don't know. In any case, I've been giving the brute-force approach a shot.

My implementation identifies coplanarity as discussed in Wolfram MathWorld: by computing the determinant of a 4X4 matrix. If the determinant is zero, the point is coplanar. The determinant computation includes a lot of multiplies that can be precomputed, because the three points that define the plane don't change for each 30,000 point test, and my code (Java and C) dutifully precomputes the lot. [Some future version of the C code may be able to bring the CPU's vector processing unit, or the GPU's resources, to bear on this problem, but I've never tried vector processing, so that's a challenge I'll leave for another time.]

With that out of the way, here are the results for checking all 30,000 points for coplanarity with each of the first 5,999,600 planes. As you'd expect, lower test times are better.

LanguageEnvironmentTime
Java 1.6 (64-bit)Mac OS X command line811 secs.
Java 1.6 (64-bit)IntelliJ IDEA 7.0.5 console814 secs.
C & GCD (64-bit)Mac OS X command line658 secs.
C & GCD (64-bit)Xcode 3.2.1 debugger console657 secs.
C & GCD (64-bit)Xcode 3.2.1 debugger console with GuardMalloc 18 enabled1,814 secs.

More details: The C compiler was the one supplied with the current Xcode tools, GNU gdb 6.3.50-20050815 (Apple version gdb-1346) configured as "x86_64-apple-darwin". The Java runtime version was 1.6.0_17-b04-248-10M3025 and the virtual machine was "Java HotSpot(TM) 64-Bit Server VM" – in other words it was the current version of Java supplied by Apple for Mac OS X 10.6.2.

The results: Running on a quiescent machine, both the Java and C/GCD applications were able to push the CPU utilization to roughly 795% and keep it there at all times (the "Hyper-Threading" feature of the Nehalem cores enabled each of the four cores to act like two, so 800% was the theoretical maximum in this case). In general, Java was 23% slower than C/GCD. Personally, I'd expected Java to either closely approximate or even slightly exceed C/GCD's performance (because the Java just-in-time compiler can optimize and natively compile the code in a manner optimal to the specific hardware it finds itself running on at any given time, whereas the C compiler might make have to make more generalized assumptions), or for C/GCD to beat Java by many times. Neither outcome manifested, though the first was closest to the truth.

I think that the actual results can be interpreted in a couple of ways: (1) "C with GCD is meaningfully faster than Java for this sort of number crunching", or (2) "Java is a reasonable choice for this sort of number crunching." I lean toward the second interpretation, due to two issues. First, the Java code was, in my opinion, much cleaner, clearer and more re-usable than the C code. Second, Java is doing a lot more work for you at the same time it is crunching numbers – helpful work that can affect the reliability of your code, and/or the integrity of its results, like ensuring memory integrity and runtime type-correctness – and that's work that C mostly doesn't do at all, or does very badly, as seen in the case of running the C version of the program with GuardMalloc enabled at the cost of it taking 2.24 times longer to run than the Java program.

Those issues aside, it must be said that, for this comparatively simple program, Apple's Grand Central Dispatch and its extensions to the C language worked very well, and were easy to use. I still find the new syntax difficult, but past experience with closures, and the examples in Apple's documentation, were enough to let me produce the code I needed, in spite of that. Whether the GCD language extensions, or the GCD API, provide as complete a set of services for concurrent programming as the Java language and its "java.util.concurrent" package, I don't know. The general impression I took away from the GCD documentation was that it provides fewer features to aid the development of concurrent software than does Java, but a day's work with GCD isn't sufficient to let me judge.

To conclude: Compared to C, Java's not half bad for number crunching as I'm currently doing it (in fact, it's somewhere between merely 23% bad, and 224% good); and Apple's Grand Central Dispatch is an interesting and useful extension to the C language.