CSE509 Project Report
Spacewar Game
Venu Karumuru
Paul E. McKenney
Project Proposal
Abstract
We propose to develop a Spacewar game. This game will include a Sun in the middle of the screen that provides gravity and at least two mobile player-controlled spaceships that can fire missiles and drop mines. The object of the game is to destroy the other player’s spaceship. Additional features will be added depending on the desires and talents of other members of the project. See below for possible additional features.
This project has three objects: (1) compare the time required to develop this Java program with that required to develop a very similar program in PDP-12 assembler, (2) demonstrate students’ ability to design and program an object-oriented simulation, and (3) produce a fun game.
Basic Project Details
The basic project consists of the following:
Each ship can in addition fire its rocket to accelerate, and can rotate itself either clockwise or counter-clockwise.
A player wins when his ship is the sole surviving ship.
The development time, accuracy, and execution speed of this program will be compared to that of a similar PDP-12 program written in 1977 (~150 man-hours from a pair of students, 3,000 lines of assembler, crude simulation of gravity (significant orbital precession due to round-off error), and sub-reflex (10-20 Hz) update rate). This PDP-12 program was in turn inspired by a similar program developed at MIT.
Proposed Extensions to Basic Project
Actual extensions will be selected based on the desires and capabilities of other team members. Some possibilities include:
See the implementation section for a list of the extensions that were actually implemented.
Example Project Work Breakdown
This is just an example—design time (e.g., CRC exercise) would be needed to determine the classes and methods, and implementation could then be distributed among the group members.
Language
The language chosen for this project is Java.
Project Implementation
Features Implemented
All of the features listed in the proposal for the basic game were implemented. The one concession to modern persistent display technology was the placement (launching) of mines sufficiently far from the ship to allow the mines to be immediately armed. In contrast, in the PDP-12 implementation, the non-persistent monochrome display allowed a yet-to-be-armed mine to be spotted easily even when displayed right on top of the ship.
We also implemented the following features beyond the basic game:
The object-oriented nature of our implementation made these flavors of gravity easy to implement.
User Interface
The blue ship is controlled by the mouse, and the green ship is controlled by the keyboard. The mouse may be used on a grid of nine buttons, arranged as follows:
The keyboard presents the same controls on the numeric keypad (if "Num Lock" is enabled!), using the same pattern so that the numbers map to the functions as follows:
Appearance
The game looks as follows when the full five mines and one missile per ship are in flight.
The sun is in the center of the screen. The tiny white dots are stars. The pale green box is the edge of the universe, off which objects bounce. The small blue and green circles with crosses are mines. The small blue and green circles with flames coming from them are missiles. The large blue and green circles each with the single short line from center to edge are the ships. The lines denote engines, and if the ships’ engines were on, there would be flames emanating from the lines, similar to the flames emanating from the two missiles.
Design
UML Diagrams
Object Overview
Universe Class and Collaborators
SpaceObject and ControlledObject
Helper Classes and Interfaces
Patterns Used
The Universe class is an example of a mediator. All in-flight SpaceObjects’ gravitational and collision interactions are managed by Universe, and SpaceObjects are in general unaware of each other’s position, velocity, state, and existence. There are two exceptions to the lack of awareness of existence: SpaceShips track how many of their SpaceMissiles and SpaceMines are still extant in order to determine whether the player may legally launch another SpaceMissile or SpaceMine. Note that Universe is not a Singleton. As every Star Trek fan knows, limiting your game to a single Universe is just plain shortsighted.
The SpaceGraphics class is an example of a decorator. This class delegates graphics operations to the underlying AWT Graphics object after making the coordinate transformations needed to move from a physics-friendly right-hand-rule coordinate system based on the centers of objects to the increasing-Y-downwards upper-left-corner coordinate system implemented by AWT.
The SpaceObject class serves as a template for the SpaceSun, SpaceShip, SpaceMissile, and SpaceMine classes.
The SpaceObjectRegistry class serves as an abstract factory. New SpaceSuns, SpaceShips, SpaceMissiles, and SpaceMines may be created by sending the SpaceObjectRegistry a message containing the string "sun", "ship", "missile", and "mine", respectively. The SpaceObjectRegistry class is also a singleton: its constructor is private, and all of its methods and instance variables are declared static.
The SpaceObjectListIterator serves as an iterator. This object reduces the number of explicit cast operations required, and supports "all pairs only once" scanning by allowing a iterator to start after a particular object. This simplifies scanning SpaceObject lists when computing gravity or checking for collisions.
Implementation Strategy
Overview
We used a "spiral" implementation methodology. Paul implemented from the display in towards the model, while Venu implemented from the keyboard and mouse in towards the model. We integrated our two components once per week. This approach allows incremental testing with very low scaffolding-creation overhead. Each component was tested as it was created; using previously constructed and tested components as test scaffolding.
Venu used the title bars of the input components to display text messages, thereby verifying that input components were providing the correct response to user input. Paul used hard-coded placement of SpaceObjects with Java statements to verify that the display and the model components were working correctly.
Between these functional tests were interspersed the unplanned, but surprisingly useful, random testing efforts of Melissa, Sarah, and Aaron, Paul’s three children.
Implementation Sequence
Testing Orbital Dynamics
We did specific tests for precession and for delta-V at perihelion and apohelion. The precession and delta-V tests are covered in the following subsections.
Precession
In theory, orbits should be perfect ellipses, parabolas, and hyperbolas. However, calculation errors cause the simulated orbits to deviate from their theoretical forms. There are two major sources of error: (1) roundoff error and (2) integration error.
Although roundoff error was the major contribution to error in the PDP-12 implementation, it is negligible in the Java implementation due to Java’s 64-bit IEEE floating point arithmetic.
However, integration error is significant, especially on highly elliptical orbits. The following diagram helps illustrate integration error:
This diagram shows a blue object in a clockwise elliptical orbit around the sun. We simulated motion using Eulerian integration, which means that we compute the force at a time t1, compute the resulting acceleration, change in velocity, and new position at time t2. However, the force will be changing continuously as the object moves from t1 to t2, and will be changing especially quickly when the object is passing close to the sun in an elliptical orbit. The diagram shows the force of gravity pulling the object upwards and to the right at t1. Eulerian integration uses this same force vector for the entire path from t1 to t2, with about 700 of error in direction of the force at point t2. This error results in precession. Highly elliptical orbits precess about 2 degrees per minute.
Delta-V at Perihelion and Apohelion
If an object is given an impulse (short burst of acceleration) at perihelion, this will cause the apohelion to move, but will not affect the perihelion. This is shown in the following diagram: an impulse in the direction of motion at perihelion causes the object to move from the inner orbit to the outer orbit. (A subsequent identical impulse at perihelion against the direction of motion would cause the object to revert back to the inner orbit.
Similarly, an impulse at apohelion will affect the perihelion, but not the apohelion.
Tests on our SpaceWar game showed that our simulation of gravity closely obeyed this law of motion.
Comparision to PDP-12 Implementation
Source Code Size
The 3312-line Java implementation was surprisingly large compared to the 4001-line PDP-12 implementation. The Java implementation breaks down as follows:
Java Implementation |
|
Lines of Code |
Class |
15 |
ControlledObject.java |
30 |
Gravity.java |
66 |
GravityInverseNewtonian.java |
71 |
GravityNewtonian.java |
53 |
GravityTerrestrial.java |
103 |
MetricSpace.java |
235 |
MetricSpaceEuclideanBounce.java |
690 |
RemoteControl.java |
12 |
SpaceBackground.java |
47 |
SpaceBackgroundStars.java |
61 |
SpaceGraphics.java |
190 |
SpaceGraphicsFlipCenter.java |
67 |
SpaceMine.java |
81 |
SpaceMissile.java |
569 |
SpaceObject.java |
82 |
SpaceObjectListIterator.java |
104 |
SpaceObjectRegistry.java |
45 |
SpacePoint.java |
196 |
SpaceShip.java |
68 |
SpaceSun.java |
187 |
StartUp.java |
340 |
Universe.java |
3312 |
total |
Of these, GravityInverseNewtonian.java, GravityTerrestrial.java, SpaceBackGround.java, and SpaceBackgroundStars.java implement functionality not present in the PDP-12 implementation. Leaving these classes out of the total leaves 3134 lines.
The PDP-12 implementation breaks down as follows:
PDP-12 Implementation |
|
Lines of Code |
Purpose |
29 |
data tables (header comment) |
71 |
distance tables (radii in various states) |
79 |
squares table |
180 |
sin/cos tables |
47 |
explosion image sequence pointers |
1408 |
bit-vector tables for images of objects |
15 |
program linkage control |
37 |
code (header comment) |
7 |
linkage control |
8 |
PDP-8-mode interrupt entry |
38 |
"function" argument-passing area |
16 |
LINC-12-mode interrupt entry |
100 |
global variables |
80 |
interrupt handler |
28 |
interrupt variables and jump table |
57 |
initialization code |
14 |
main calculation loop |
38 |
variables and jump table |
115 |
read input from switch registers |
55 |
update explosion |
108 |
acceleration, launch, missile explosion |
45 |
release mines |
296 |
gravity and movement |
83 |
arm mines |
341 |
check for collisions |
265 |
invoke display code for all objects |
153 |
mine-array utility functions |
17 |
return to OS |
67 |
display code |
53 |
reciprocal |
11 |
square |
61 |
square root |
62 |
sin/cos and r*sin/r*cos |
17 |
trailer comment |
4001 |
total |
The PDP-12 had a legendary reputation for code density, and this example certainly supports the legend. This is especially true when you consider that much of the PDP-12 implementation’s code is provided by Java library classes and by the operating system on which Java runs. When the PDP-12 code implementing arithmetic and interrupts are excluded from consideration, only 3368 lines remain, which is very close to the size of the Java implementation. But it is when the 1408 lines of bit-vector tables are excluded that the true code density of the PDP-12 becomes apparent: only 1960 lines of PDP-12 assembly were required to implement the control, input, and output code, compared to over 3000 lines of Java.
Development and Maintenance Costs
The Java code was much easier to write and debug than was the PDP-12 assembler. Only about 50 hours of time were consumed by the Java implementation, compared to at least 150 hours for the PDP-12 assembly implementation. This is in part because the code required to compute movement had to be written very carefully in order to get the most out of the 12-bit precision available on this machine. Paul McKenney would like to believe that his 23 additional years of experience also helped to reduce the Java implementation’s development.
In addition, the Java implementation is much easier to modify. Of the features in the Java implementation beyond the basic game, the following would have required major changes to the PDP-12 implementation:
Performance
Acolytes of Moore’s law may be surprised to learn that the PDP-12 implementation is about twice as fast as the Java implementation. The hardware and software performance tradeoffs are as follows:
Performance Aspect |
PDP-12 |
Java |
Java/PDP-12 Ratio |
CPU MHz |
0.625 |
166 |
266 |
Memory Access MHz |
0.625 |
7 |
11 |
Memory |
6KB (4KW) |
64MB |
10,667 |
However, the PDP-12 implementation was written in tightly-coded assembly language, while the Java version compiled to interpreted byte codes. Therefore, the calculation time-step was 100ms in the Java implementation, compared to 50ms in the PDP-12 implementation. We added speed blur to the Java implementation to preserve the illusion of motion despite the slow update rate.
Acolytes of Moore’s law might point out that present-day hardware (1GHz processors as opposed to the 166MHz Pentium on which the Java measurements were taken) should allow the Java implementation to easily outperform the PDP-12 implementation.
Accuracy
The PDP-12 implementation used 12-bit arithmetic, which resulted in significant roundoff error. This roundoff error caused even mildly elliptical orbits to precess and decay quickly enough to be visible to the naked eye. In contrast, the Java implementation uses 64-bit IEEE floating point. Although there is some precession due to the simple use of Euler’s method to evaluate the gravitational equations, it is necessary to mark the point on the screen to see the precession. An extremely elliptical orbit precesses about 2 degrees per minute in the Java implementation, which is a great improvement over the 10-degrees-per-second precession of the PDP-12 implementation.
Playability
The PDP-12 version’s controls were a switch register that was directly sensed by the CPU. This made for very tight controls that allowed players to get predictable results with sequences of switch manipulations.
The Java version’s controls (mouse and keyboard) are quite sloppy by comparison. The mouse is especially bad, since it requires the player to shift his eyes from the display. Both mouse and keyboard suffer from the software overhead exacted by the OS and by Java. Although slowing the game down to 10Hz from the PDP-12’s 20Hz helps, further improvement would likely require that control input ramp up, rather than being the current step function. Such ramping would allow players to reliably give the ships delicate nudges, while still permitting full power over longer time periods.
Complexity of Programming Environment
A comprehensive quick reference for the PDP-12 environment filled 11 sides of 8.5x11 paper. In contrast, the same level of detail on the Java language environment fills no fewer than 648 pages, without covering either AWT or Swing. Of course, Java’s documentation complexity is the inevitable price paid for a higher-level language. Even "small" languages like Smalltalk or Lisp require large quantities of documentation to cover their extensive libraries.
Overall Suitability
The PDP-12 implementation was a reasonably impressive game for its day. The Java version did attract Paul’s kids’ attention, however, after about an hour of play, they were thoroughly bored with it. They then went back to their Nintendo and Windows games, which have very complex graphics and story lines. So even though software productivity appears to have increased roughly three-fold over the past 23 years, the demand for software functionality and complexity has increased by orders of magnitude.
The "software crisis" thus appears to be due to growing demand rather than to constant productivity.
Lessons Learned
Summary and Conclusions
We produced a game that surpassed the 1977 PDP-12 version, with roughly one-third the programming effort, with orders of magnitude more simulation accuracy, and with much greater flexibility. Although speed suffered on the 166 MHz Pentium system on which the measurements were taken, it is reasonable to assume that the currently available 1GHz CPUs would easily outperform the PDP-12. However, the growing demand for software features and complexity seems to have far outstripped the productivity gains enabled by modern software tools.