PDP-1 Spacewar! program internals

From: Al Kossow <aek at spies.com> Subject: PDP-1 Spacewar! program internals To: classiccmp at classiccmp.org Date: Tuesday, October 21, 2008, 11:00 AM Here is part of an oral history I recorded with Steve Russel last August which discusses how the Spacewar! program works internally. Exerpt of an oral history of Steve Russell August 2008 CHM Reference Number X4970.2008 (C) 2008 Computer History Museum Russell: Anyway, the PDP-1 arrived, and Marvin Minsky wrote the tripos demonstration, generally called the Minskytron, and there was the famous weekend where the mob of undergraduates transcribed the macro assembler from TX-0 to the PDP-1, because they didn't like FRAP. And then fairly quickly thereafter, they wrote DDT and connected up the macro symbols to DDT. So that was all sort of in place by the middle of the fall of 1961. And the combination of the Minskytron and having DDT with interactive debugging with symbols was very tempting. I don't remember the exact order of things, but I'm pretty sure I started talking up a better demonstration program than the Minskytron, and eventually, Alan Kotok went up to Maynard and collected the sine and cosine routines from DECUS, presented them to me, and said, "Okay, here are the sine and cosine routines; now what's your excuse?" And I discovered I had run out of excuses; I had to actually think. And so I started work and figured out the basic trick of Spacewar! display which is that you only need to calculate a unit vector pointing in the direction of the spaceship. And you can express everything else the spaceship does, and the outline of the spaceship in terms of that unit vector, suitably scaled. So it's basically a lot of addition in the usual program upkeep. Kossow: Do you want to just give an overview, then, of how Spacewar! actually works? Russell: It's one big loop, and the loop is on the displayable objects. And I called them displayable objects, although I didn't know about object orientation or object- oriented programming at the time. Kossow: So you have the sun-- Russell: Colliding objects, not displayable objects. The colliding object is a space ship, there are two of those. And that has a lot of extra data with it. It shares the position and velocity tables with all of the torpedoes and explosions that are running around. So there's just one big loop through the colliding objects, and it looks at all the higher-numbered colliding objects to see if there's a collision, using an octagon because you don't need to calculate the square root of anything, you can do that by work on X difference, Y difference, and X+Y difference-- Kossow: So the bounding box for the collision detection is an octagon? Russell: Yes. So it goes through, it sees if this object is colliding with any higher- numbered object. If it is, it replaces the calculation routines. That's another thing that every colliding object has, is a calculation routine. It replaces the calculation routine with the explosion calculation routine. And then things take care of themselves. Then, after it's decided whether it's an explosion or not, it goes off to the calculation routine. And the calculation routine updates the position, since all colliding objects have velocity; and if it's a spaceship, it worries about reading the controls and updating the other things about the spaceship in deciding whether to launch a torpedo or not. And if a torpedo needs to be launched, it searches up the colliding object table for an empty slot, indicated by having no calculation routine. It searches up the table for an empty slot, puts a torpedo calculation routine there, and the spaceship position plus the suitable increments, so it won't run into its torpedo, and of the velocity of the spaceship plus an increment for the torpedo, and it goes on. When that the main loop gets done, you go off and do some star display and display the sun, and calculate -- and part of the spaceship calculation is to calculate the effect of gravity on the spaceship. Originally, there wasn't any gravity, and I had an interpreter, which interpreted the outline description, and Dan Edwards, sometime in late 1961 or early 1962, looked at that code and decided if he could write a special purpose compiler which would compile precisely the right code, and proceeded to. And there's one compiled outline for each spaceship; each spaceship actually does half of the spaceship outline and then you twiddle the vectors and do the other half. That keeps the display running just as fast as it can. That gives time to calculate the effect of gravity on the two spaceships, but not on the torpedoes. So we decided that they were photon torpedoes not affected by gravity. Kossow: So when the explosion routine starts, it continues calculating motion, so the explosion moves? Russell: Yes. If you see two spaceships collide, if you watch closely, you will see that there are two explosions that continue off in the direction that the two spaceships were going. There is another number in the table for all colliding objects, which is the size. And this is, roughly speaking, proportional to the amount of computing it takes to compute that object. And at the end of the loop, as you go through the main loop, you accumulate the sizes also; and so at the end of the loop, there's fritter away time loop that attempts to keep the frame rate approximately constant. It doesn't do a wonderful job; it's visually adequate, but God help you when you try to take a movie of it. Kossow: One of the complaints with all modern kids trying to play it now is that it's TOO SLOW. Russell: Kids who are used to something like Asteroids seem to think that. But when we do the demos, we get a number of people who seem to be still quite addicted to it with the old, slow version. Now, that was always a complaint; the reason that all the parameters got accumulated in the first page of the listing, which says you can put that first page of the listing of the console, and anyone who wanted to try a different set of parameters could. But the ones that were compiled in or assembled in were the ones that I thought were good. Now it turns out I'm not a representative arcade game player, and so my version of the parameters is slower and gives more opportunity for marksmanship than the arcade version. Kossow: Right, that's the whole thing with gravity and doing the, what's that called, where you whip around the sun? Does it have a name, where you whip around the sun and you shoot? Russell: The closest name is the "CBS maneuver" is what happens when two lazy experts fight each other, which is they both turn at right angles to the sun, and fire for 3.5 or 4 seconds, so they're now in stable orbits, and they know it. And then they turn at each other and start trying to place torpedoes where they think the other one is going to be. And so the trails turn into an eye around the sun, and CBS used that as a logo, so it got called the "CBS maneuver". You can-- one of the spaceships can go the other way around the sun, so that both ships meet on the same side of the sun. But that seems usually to have less chance of winning. Not much less, but somewhat less. Kossow: It's better that you stay on opposite sides, then? Russell: Yes. Kossow: And then at some point, you added hyperspace? Russell: Yes, and we realized that that was going-- I don't remember whether we actually had it. I may have had it for a little while with no limit, but it became very clear that someone who didn't understand could use hyperspace to escape their proper justice forever, and so we added the unreliability of hyperfield generators very quickly. One thing that Asteroids and the arcade versions, the later arcade versions of Spacewar! added, which actually was a big help, especially with their high acceleration rates, was "training mode" where space was actually viscous. So if you got your ship accelerated so that it was going across the screen so fast you couldn't understand what was going on, if you took your hands off, the situation would gradually become understandable. I don't think I would have been persuaded to do that in the original Spacewar! because it was unrealistic. But it definitely made it easier to learn. Kossow: So are there any other favorite anecdotes about Spacewar!, or just the spread of Spacewar!? Russell: Well, the "imitation is the sincerest form of flattery"-- many people saw Spacewar! as, some people ask for copies of the source, and of course we gave them out because we very briefly considered trying to sell Spacewar!. We realized the only possible customer was Digital Equipment, and we also, on a little reflection, that they were too cheap to do it. So we gave it out to anyone who wanted it, and some people got the listing and thought about it, and by reading it-- a lot of people simply saw the game and had a computer that wasn't the PDP-1 but did have a display, and implemented Spacewar! their own way. I suspect most of them figured out the "basic trick", but I'm not sure. Kossow: What "basic trick" were you thinking of? Russell: That you could do everything based on the spaceship unit vector. How are you fixed for the source code for different implementations of Spacewar!? Kossow: We have a few. I don't know if we have the PDP-10 version. We have the 12 version, and I think we have a PDP-7 version. Russell: I think Bob Saunders wrote the PDP-7 version. I think one 6 version simply ran on the PDP-1 simulator. I think there must have been others, but I don't know. Something for some history grad student to pursue. When we were running a demo for the Yelp event, there was one woman who had done Spacewar! in turtle graphics as a high school programming project, which she wasn't too happy with. She seemed to like the demo of the original Spacewar!. Kossow: So turtle graphics running on a micro or something like that? Russell: I didn't quiz her. I didn't have the opportunity to quiz her further. Kossow: So she thought this version was better? Russell: No, she just thought it was nice to see the original. Kossow: So she was in her mid-20s? Russell: 20s or early 30s; probably 20s. The DEC field service story where the DEC production people got into the practice of loading Spacewar! the last thing before PDP-1 shipped, and field service would then unpack it, make sure that nothing horrible had happened, tryed turning on power, and starting Spacewar!. And if it worked, they would call the customer over and say, "See, it works." If it didn't work, then they'd worry about it. In the restoration project, we had a little reflection and we decided that probably if Spacewar! works, just about everything works, as far as machine instructions go. It doesn't guarantee all the I/O gear works, but it does multiply and divides, and just about every instruction. So a lot of people implemented Spacewar! just from knowing that it existed and having seen it maybe once.