35.1 Space Invaders

We start with a brief description of the classical game Space Invaders. Only the most fundamental parts of the game have actually been implemented.

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.

35.2 Structure of the Space-Invaders implementation

In this section we describe an implementation of Space Invaders, where the each object is implemented as a fudget. The objects are:

1. spaceF: the space fudget. This is the black background in which all the other objects move around.
2. gunF: the gun.
3. torpedoF: the torpedoes fired by the gun.
4. invaderF: a number of invaders

There is also scoreF, which displays the current score and a high-score. gunF and torpedoF use 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.

The fudget 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:

data InvaderMsg = Tick | Turn | Hit Point | Death (Int,Int)

When an invader hears a 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 Turn it 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 sends a 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.)

35.3 About the efficiency of the Space-Invaders implementation

One major point of the Fudget system (and of functional programming in general) is to simplify and speed up program development. But it is of course also important that the efficiency of the resulting program is acceptable.

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 similar situation.

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 Tick from 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.

35.4 Replacing fudgets with stream processors for efficiency

Above, we outlined a program structure where each moving object on the screen is represented as fudget with an associated window on the screen. It is of course possible to use fudgets for other kind of simulations where the objects do not correspond to user interface elements.

The behaviour of a single fudget is usually implemented as a sequential program by using the stream-processor operators putSP, getSP and nullSP. 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:

• The communication between stream processors is cheaper (less tagging/untagging).
• The number of windows is reduced. This means that conversions between paths and window identifiers in 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).

In Section 35.2 the input to the invaders is broadcast to all invaders. We implemented this using listF (tagged parallel composition) and a separate stream processor shoutSP. Some overhead can be avoided by using untagged parallel composition of stream processors instead:

-*- :: SP a b -> SP a b -> SP a b

This also makes it easy to write stream processors that dynamically split into two or more parallel processes. One of the processes in a parallel composition can terminate without leaving any overhead behind, since

nullSP -*- sp == sp -*- nullSP == sp

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.

The fact that parallel compositions can reduce to nullSP gives us an opportunity to make use of the sequential composition operator 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:

playGameSP = playLevelSP 1

playLevelSP level = startNewLevelSP level `seqSP` playLevelSP (level+1)

startNewLevelSP level = invaderArmySP level

invaderArmySP level = ... -- creates a parallel composition of invaders

When the last invader in the invader army dies, the parallel composition will be reduced to nullSP, which causes seqSP to invoke the next level.