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:

  1. Frame containing playing surface. Objects reaching the edge of the frame bounce.
  2. Sun in center of frame that provides gravity and that destroys ships that venture too close. The sun cannot be destroyed.
  3. Two ships that destroy each other in the following ways:
    1. Firing a missile that is manually detonated. If detonated sufficiently close to a ship, missile, or mine, both the detonating missile and the other object will explode and be destroyed.
    2. Dropping a mine, this automatically detonates as soon as it gets close enough to another ship, missile, or mine. The mine automatically arms itself as soon as it reaches a safe distance from the ship that drops it.
    3. Direct collision.
    4. Exploding close enough to the other ship.

    Each ship can in addition fire its rocket to accelerate, and can rotate itself either clockwise or counter-clockwise.

  4. Missile. Only one of these may be in flight from a given ship at a given time. They are manually fired, and manually detonated. When detonated, they destroy any nearby object (other than the sun). If they hit a ship without being detonated, the missile is silently destroyed—the ships are assumed to automatically disarm/destroy missiles that venture too closely.
  5. Mine. There may be up to ten of these in flight at a given time. They are manually dropped. Once they get far enough from the ship that dropped them, they automatically arm themselves. Once armed, they will detonate upon getting close enough to any object, including the ship that dropped them.
  6. User input. One player will control his/her ship with the keyboard, the other with the mouse. There will be suitable penalties for removing focus from the frame. J
  7. Conceptual "underlying universe" objects mediate physical interactions (gravity, proximity, etc.).

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:

  1. Networked two-player version. Each player would have his or her own screen, keyboard, and mouse.
  2. As above, but allowing for more than two players.
  3. Limited numbers of missiles and mines per ship.
  4. Limited amount of fuel in ships and/or missiles.
  5. Automated scorekeeping.
  6. Change in acceleration based on mass remaining as fuel, missiles, and mines are consumed.
  7. Additional types of weapons, such as short-range lasers/phasers.
  8. Objects "wrap around" rather than bouncing when reaching the edge of the frame.
  9. Objects simply pass out of view when reaching the edge of the frame. "Scroll" the frame to keep the ship in view, and have some sort of indicator for the direction to the sun and to the opposing ships.
  10. Planets that act as "bases", replenishing their ship if it orbits (and destroying the opposing ship(s) if it ventures too close).
  11. Two suns (or more) orbiting each other.

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.

  1. User input and network communication (Controller, more or less).
  2. Display (View).
  3. Physical object interaction, including gravity, collisions, and movement (part of Model).
  4. Physical objects themselves, including creation of additional physical objects (firing missiles, laying mines), thrust, orientation, and mass (the other part of Model).

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:

  1. Multiple suns in mutual orbit. By default, the game comes up with a single sun in the middle of the screen. Although this sun is mobile, its simulated mass is on the order of 1012 times that of the ships. Therefore, for all practical purposes, it is immobile. When the "randomize" button is pressed, the game is restarted with a pair of mutually orbiting suns. Ships and missiles are quite difficult to control in the area between the two suns, but orbits around the outside of both suns are quite stable. The object-oriented nature of our implementation made this feature quite easy to implement.
  2. Suns explode when colliding with other suns (or any other object that has at least 10% of the sun’s mass).
  3. Two additional flavors of gravity:
    1. Negative gravity, such that objects repel rather than attracting.
    2. Normal mutually attracting Newtonian gravity, but in a terrestrial gravity well. The pair of suns will orbit each other, but fall down towards the bottom of the screen, where they bounce. The ships are attracted both to the suns and to the bottom of the screen, and also bounce.

    The object-oriented nature of our implementation made these flavors of gravity easy to implement.

  4. Per-ship limited number of mines in flight at a given time. In contrast, the PDP-12 implementation allowed one player to "starve" the other of mines, simply by keeping all 10 in flight from his ship.
  5. "Sticky" collisions. In the PDP-12 implementation, colliding objects would explode and pass through one another. The Java version features more realistic momentum-conserving sticky collisions. Colliding objects stick together, following the same path as they explode.
  6. Conservation of angular momentum when launching missiles and mines. In contrast, the PDP-12 implementation caused mines and missiles to remain pointing in one direction even when launched from a spinning ship.
  7. Simulated speed blur. The overhead of the Java system forces a relatively low display update rate, particularly when running over X-windows, so that the illusion of movement can be lost when objects are moving quickly. Providing simulated speed blur allows the illusion of movement to be maintained despite low display update rates.
  8. Star field in the background. The cosmetic feature was demanded by the three random testers.
  9. Pale green box marking the boundary off which objects bounce. This boundary was needed because different Java implementations seem to allow differing amounts of margin around the edges of panels and frames. Providing an explicit boundary allowed us to allow 50 pixels of "slop" for differing implementations.

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:

  1. Missile. Launch a missile, but only if this ship does not already have a missile in flight. As soon as a given missile is destroyed, its ship may launch another.
  2. Detonate. Cause the current missile to explode. Does nothing if this ship does not currently have a missile in flight.
  3. Mine. Launch a mine, but only if this ship has fewer than five mines in flight. Just as with missiles, as soon as a mine is destroyed, the ship may launch another in its place.
  4. Left. Start the ship rotating to the left (counter-clockwise).
  5. Stop. Stop the ship’s rotation.
  6. Right. Start the ship rotating to the right (clockwise).
  7. Restart. Restart the game with two ships and a single sun. Use the same type of gravity that was used in the previous game.
  8. Engine. Toggle the engine state, turning it on if it was off and off if it was on.
  9. Randomize. Restart the game with two ships and two suns, randomly selecting gravity from Newtonian (normal free-fall inverse square law), Terrestrial (normal free-fall inverse-square law, but in a strong gravity well), and inverse Newtonian (free-fall inverse square law, but with objects repelling each other rather than attracting each other).

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

  1. SpaceGraphics and SpaceGraphicsFlipCenter. These are closest to the display, and formed the basis for further testing of the model.
  2. RemoteControl version 1. These are closest to user input. Unit testing was accomplished by modifying the frame titles to verify that mouse clicks and keystrokes were indeed being correctly responded to.
  3. Universe, MetricSpace, MetricSpaceEuclideanBounce, Gravity, GravityNewtonian, SpaceObject, SpaceSun, SpaceShip, ControlledObject. These were integrated and tested in a large group due to Paul’s being out of town. They were coded at airports and on board airplanes, and tested upon return. Various tests were run by having the initialization code set up the objects in a known state, for example, one of the ships with its engine on while rotating left, and the other with its engine on without rotating.
  4. RemoteControl version 2. This version used ControlledObject, allowing direct control of the ships. This made it possible to test orbital dynamics.
  5. SpaceMine, SpaceMissile, SpaceObjectRegistry, GravityInverseNewtonian, GravityTerrestrial. The mines and missiles were again placed by the initialization code, since RemoteControl version 2 could not control them. The type of gravity was also selected by the initialization code.
  6. RemoteControl version 3. This version allowed mines and missiles to be launched.
  7. SpaceBackground, SpaceBackgroundStars. This was not planned, but added due to overwhelming demand by Paul’s wife and children. J
  8. RemoteControl version 3. This version allowed the game to be restarted and allowed random selection of types of gravity.

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:

  1. Multiple suns in mutual orbit.
  2. Collisions causing suns to explode.
  3. "Terrestrial" gravity, which simulates the mutual gravitational interactions occurring near the surface of an unbelievably large and massive planet. However, negative gravity was all too easy in the PDP-12 implementation—leaving out a single "CMA IAC" instruction is sufficient, as Paul McKenney and his lab partner saw in an early version.
  4. Sticky collisions.
  5. Conservation of angular momentum.
  6. Simulated speed blur.
  7. Boundary marker. Although it would have been easy to simply add the boundary points to the display list for the Sun, displaying a boundary would have caused a substantial performance impact.
  8. Color. The monochrome display on the PDP-12 was incapable of color.

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

  1. Java is inherently concurrent. Early versions of the Java implementation did not use any synchronization because we (erroneously) believed that concurrency would be an issue only if we explicitly ran multiple Java Threads. Early versions were therefore prone to inexplicable failure on overnight runs on our PCs. The reason behind the failures became apparent as soon as we attempted to run a multi-SpaceObject game on the 32-CPU NUMA-Q system at Paul’s workplace. The game failed in the same inexplicable manner, but within a minute or two. Adding explicit synchronization eliminated the failures. We ran several overnight test runs on both PCs and on the 32-CPU NUMA-Q system. Paul had to grit his teeth and force himself to use a simple code-locking design, going against every instinct built up over ten years of producing highly scalable software. However, this simple locking design was well-suited to this project.
  2. If we were doing this project again, we would probably abstract out a separate "physics state" object from SpaceObject. This would simplify the argument lists of many of the methods in the MetricSpace and Gravity interfaces. It would also make it easier to modify the game to use (for example) general relativity rather than Newtonian physics.
  3. The current implementation of the game has annoying flicker on many platforms. We attempted to reduce flicker by blacking out the previous position of each object, then painting the new position, while disabling repainting of the background color. This was rather complex and difficult to debug. In addition, it was of no help except in cases where the sun was stationary. We therefore ripped out the code, greatly reducing display complexity. If we were doing this again, we would attempt to double-buffer the display into an image object, then display the resulting image in one shot.
  4. Had we refrained from taking the detour in search of a flicker-free display, we would likely have had time to implement a drag-and-drop interface that would allow the players to explicitly set up the game’s initial state. This would also allow the game to be more easily used as a digital orrery for investigating orbital dynamics.
  5. Write once, test everywhere: but only if you are careful to use identical versions of Java. Installation from the same CD does not guarantee the same Java version on different platforms. In particular, the Mac version of CodeWarrior is behind the PC version.
  6. Be sure to appease the Demo Gods (or, if you prefer, be sure to make appropriate allowances for Murphy’s Law):
    1. Freeze your code at least three to four days before the demo. The "simple" changes made at the last minute will invariably destroy your demo.
    2. Never exercise any capability in your demo that you have not thoroughly tested beforehand. If you haven’t tested it, it does not work, no matter how careful and clever you thought you were.
    3. Test your code early in the project on the platform that is to be used in the demo. (We failed to do this, and recovered only by bringing in Paul’s desktop PC at the absolute last minute.)
    4. Rehearse your demo as if you were rehearsing a part in a play:
      1. Time each portion of your performance.
      2. Brutally cut anything that causes you to run overtime.
      3. Allow no less than three minutes for every slide in your presentation.
      4. Allow at least five minutes for questions.
    5. Have backup hardware available. Rehearse setting it up.
    6. Arrive early enough to set up and check out any equipment that you need for your demo.
    7. If you have not already done so, join your local Toastmasters club and work toward your CTM.

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.