Figure 94. Space Invaders -- a typical interactive real-time game.
In this game, an army of invaders from outer space is approaching the earth. The player must shoot them all down before they reach the surface. Some points are added to the player's score for each invader that is shot down. The player controls a gun, which can be moved horizontally at the bottom of the screen (the surface of the earth) and which can fire vertically. The invaders initially move from left to right. When the right-most invader reaches the right edge of the screen all invaders first move downwards a small distance, then move horizontally again until the left-most invader reaches the left edge, and so on.
spaceF: the space fudget. This is the black background in which all the other objects move around.
gunF: the gun.
torpedoF: the torpedoes fired by the gun.
invaderF: a number of invaders
scoreF, which displays the current score and a high-score.
torpedoFuse timers internally to control the speed of their motion. To coordinate the motion of the invaders, they are controlled by a common timer which is located in a windowless fudget called
tempoF. There is also an abstract fudget called
shoutSP, which broadcasts timer alarms and other input to all invaders.
Section 35.2 illustrates how the fudgets are interconnected. The
information flow is as follows: the space fudget outputs mouse
and keyboard events to
gunF. (This allows the user to place the
mouse pointer anywhere in the window to control the gun.) The
gun responds to these events by starting or stopping its movement, or
by firing a torpedo. When the gun is fired, it outputs its
current position to the torpedo fudget. The torpedo then starts
moving upwards from that position. When it hits something, it
outputs its current position to the invaders. Each invader then
checks if the hit is within the area it occupies on the screen
and, if so, it removes its window and dies.
Figure 95. The processes and their interconnection in the Space-Invaders implementation.
Below, we take a closer look at
invaderF. The other fudgets are
just variations on a theme, so we will not discuss them further.
invaderF maintains an internal state consisting of the
following parts: the current position (a
Point), the current
direction (left or right), if it is time to turn (i.e., move
downward at the next timer alarm, and then change directions).
The invaders speak the following language:
When an invader hears adata InvaderMsg = Tick | Turn | Hit Point | Death (Int,Int)
Tick, it moves one step in the current direction. It also checks if it has reached an edge, in which case it outputs
Turn, which is received by all invaders. When an invader hears a
Turnit remembers that it is time to turn at the next
Tick. When a torpedo has hit something at position
p, all invaders receive
Hit p, and check if p is within their screen area. If so, it outputs
Death n, where n is the identity of the invader. This identity is recorded by
shoutSP, so that it does not have to shout to dead invaders. It is also used to determine how many points to add to the score.
The fact that all objects are implemented as group fudgets means that each object has its own X window. To move an object you move its window. No drawing commands need to be output.
How does the torpedo know if it has hit something? The torpedo
is a window which moves behind all other windows. This means
that it becomes obscured when it hits something. The X server
VisibilityNotify event when this happens. This causes
the torpedo to stop and send its current position to the
invaders. (Nice hack, isn't it? But isn't there a timing problem?
And what if the torpedo is obscured by some other application
window? We leave it to the reader to ponder over this.)
We have measured the CPU time consumption of the Space-Invaders
implementation described above running on a Sparcstation IPX in
a situation where 55 invaders move twice per second, the gun and
the torpedo move every 30ms. The average CPU load was
approximately 60%. 10% of this was consumed by the X server. As
a comparison, the program
xinvaders, a C program implemented
directly on top of Xlib, consumes less than 5% CPU time in a
As usual, programming on a higher abstraction level results in a less efficient solution. Part of the inefficiency comes from the use of Haskell and the Fudget system. The load on the X server comes from the fact that the moving objects are represented as windows. Not surprisingly, moving a window is a more expensive operation than just drawing an image of the same size. But using techniques outlined in the next section, it is possible to rewrite the Fudget program to draw in a single window, like the C program, and still keep the same nice program structure, i.e., one process per moving object.
Above, we compared the efficiency of a high-level implementation (using the Fudget system) of the game with a low-level implementation. It would also be interesting to compare other user interface toolkits, e.g. Motif and Interviews, to the Fudget system.
The CPU time consumption figures above do not say much about
the real-time behaviour of the two implementations. The fact is
that the C program meets the real-time deadlines, but the Fudget
program does not. As a response to a
tempoF, all 55
invaders should move one step. Computing and outputting 55
MoveWindow commands unfortunately takes longer than 30ms,
which means that the
MoveWindow commands for the gun and the
torpedo will be output too late, resulting in a jerky
motion. This problem can be solved in at least two different
ways: manually, by not moving all 55 invaders at the same time
and thus not blocking output from other fudgets for longer than
30ms; automatically (from the point of view of the application
programmer), by introducing parallel evaluation and some kind of
fair, indeterministic merge of the output from different
fudgets. The latter solution is of course the more general one,
and we hope to improve the Fudget system in this direction.
The behaviour of a single fudget is usually implemented as a
sequential program by using the stream-processor operators
To increase the efficiency of our space
invaders implementation, we can instead structure the program as
one fudget whose behaviour is described by some composition of
stream processors. This increases the efficiency in two ways:
fudlogue(Section 22.2.2) will be somewhat cheaper, and that the load on the X server is reduced (since windows will not be moved).
listF(tagged parallel composition) and a separate stream processor
shoutSP. Some overhead can be avoided by using untagged parallel composition of stream processors instead:
Doing the same with processes represented as fudgets would not give you the same efficiency advantage since the low-level streams remain tagged even in untagged parallel compositions. Thus when one process in a parallel composition terminates, some tagging overhead will remain.nullSP -*- sp == sp -*- nullSP == sp
The fact that parallel compositions can reduce to
gives us an opportunity to make use of the sequential
seqSP (Section 16.4) in an
interesting way. Suppose that all that is needed to start a new level
in the game is the creation of a new army of invaders. Then the
behaviour of the game could be programmed in the following way:
When the last invader in the invader army dies, the parallel composition will be reduced toplayGameSP = playLevelSP 1 playLevelSP level = startNewLevelSP level `seqSP` playLevelSP (level+1) startNewLevelSP level = invaderArmySP level invaderArmySP level = ... -- creates a parallel composition of invaders
nullSP, which causes
seqSPto invoke the next level.