When we first started looking at the Spacewar! source code, one of the first things we tried to identify were the code segments that handled drawing the game state. Thanks to helpful comments in the source, we were quickly able to find the code that rendered the star field, which was covered in the previous post in this series. We also found a section of code that had the tantalizing comment "outlines of spaceship", followed by the two blocks of numbers that you can see in the image to the right. Working out what these numbers meant was the core challenge in understanding how Spacewar! draws its ships.
At first we thought the numbers might be a bitmap encoding of ship sprites, but drawing out what that might look like gave us nothing recognizable. From reading interviews that discussed the techniques that the Spacewar! programmers used we gleaned that the spaceships were actually drawn with vector graphics methods, so our second guess was that the numbers were encodings of vectors. Frustratingly, the simplest interpretation of taking consecutive pairs of numbers to be the x and y coordinates of a series of vectors that were being drawn one after the other again gave us nothing.
A big clue as to what was going on came from a section of the code that was commented as being the "outline compiler". Tracing through this code revealed that it was writing out machine instructions into an empty block of memory past the end of the main program, some of which were display instructions. Next we discovered a separate code section that seemed to be taking the heading of a ship, computing the sine and cosine of the heading, and storing linear combinations of the results in memory. That same memory was then referenced by the code that was being generated by the outline compiler. This was suspiciously like the kind of computation that would need to be done to multiply vectors by a rotation matrix. We'd found the code for rotating the graphics coordinate system!
We found the next piece of the puzzle by tracing the code in the outline compiler using an excel spreadsheet to keep track of variables as the program executes. It turned out that the memory that stored the outline encodings was being consumed in small chunks, and the number that those chunks encoded was being used to jump the program that many instructions ahead. This meant every octal digit in the outline's encoding was specifying a source code section to execute, and each of these code sections caused new instructions to be written into memory, which in turn would later be executed to display the ship on the screen. What these instructions did was update the drawing location, moving it in one of 5 directions relative to the last point drawn, save the current location, or restore the last saved one. By chaining these instructions together the program would trace out the outline of the ship.
With this discovery we had enough information to try reconstructing the outlines of the ships from the encodings by hand. Anxiously, we started sketching the outline of the first ship and were disappointed mid way through to find that it seemed like it mostly just a straight line and that there weren't enough instructions to possibly encode the whole outline of a ship. After reflecting for a moment though, we realized it makes sense that the needle ship would be mostly straight, so that was actually not a problem, but the final realization that made everything fit together was that only half of each ship's outline was being encoded; the programmers must have reflected them to draw the other halves.
Armed with our decoded spaceship outlines we are now reconstructing Spacewar!'s graphics in GAMBIT's Arduino port of the game. For avid Spacewar! fans, you too can reconstruct your own needle and wedge from the encodings in the picture using this decoding: 1 = down, 2 = right, 3 = down and right, 4 = left, 5 = down and left, 6 = save / restore, and 7 = finish!
