Restructuring a 1K ZX-81 BASIC Game

Introduction

Tony Lyon, a fellow heavily into retro video gaming, tweeted the above image of a listing of a ZX-81 BASIC “Space Invader” (note the singular!) game that fits in 1K. Erico Patricio Monteiro posted it to the Facebook CoCo group, and CoCo users have been looking at it since. I succumbed to temptation, and here we’ll take a shot at restructuring it, ultimately rewriting it in BASIC09.

Step One: Get the Text

First, let’s get this in text format. This photo is of a listing from the days of low-res dot matrix printers, so I may make a mistake. I’ll use lower case, and will use strings of question marks as a first cut for the laser cannon, the ship (again, note the singular), and the like. We can fill in something plausible later. For now I will put a tab between line numbers and lines; this is for human understanding, as far as that is possible in street BASIC^[1].

Step Two: Line Number Exorcism

Street BASIC, like some other early interactive languages of the time (e.g. JOSS and FOCAL), requires a line number on each and every line.  This is evil.

Why? It’s dense camouflage hiding the control flow. Here’s a line of BASIC, with a number. Quick! How many other places in the program end up here? Until you read the entire program, you don’t know. Any other line might branch to it.

So, here’s the program with only the line numbers that are actually used. We’ll insert a blank line before each numbered line.

Hey, the last couple of lines before line 500 are

so they could just as well be the single line

                If s<>1000 then goto 80

eliminating any need for the line number 500. Even better, then you could do all that as

                if s<>1000 then goto 80
                let e$="???"
                let d=d+d
                goto 80

Step Three: INKEY$

We see the common idiom of using inkey$ to get a character indicating the player’s intention, but why three times? Surely

                let k$=inkey$
                if k$="A" then...
etc. would be smaller and faster, and would prevent your keystroke from being read, compared with something other than what you typed, and discarded for the next inkey$ call.

Step Four: Demunging

There are many articles telling you how to mangle street BASIC code into unintelligibility to somewhat compensate for the interpreter’s extreme inefficiency. The sort that stands out here is saving constants in variables to avoid the overhead of the interpreter converting it from human-readable to internal format over and over and over… For even more fun, the code takes advantage of this particular BASIC interpreter setting pi to an approximation of pi, so the first two lines set a to 1 and b to 0. You can’t do that in Color BASIC, where uninitialized variables default to 0.

We will ultimately move to BASIC09, which is definitely not “street BASIC”. In particular, code is converted to an internal form as soon as possible. That internal form

• keeps numerical values in binary representation, so no endless conversion at runtime
• keeps expressions in reverse Polish notation, so no endless parsing at runtime
• accesses variables by offsets, so no endless linear symbol table lookups at runtime

so to make the code more understandable for us humans rather than better for a primitive interpreter, we will get rid of these variables that just hold constants, except for h. (We have plans for h.) When the smoke clears…

Step Four: Looking at Y

Is Y=H? ...How About Now?

There’s a lot of repeated evaluation in those three lines starting with “if y=h”:

Thanks to the line number exorcism, we know nobody will change any of these variables and jump into the middle, so we can just as well rewrite it as

and then put line number 130 back on the start of the inkey$ checking.

Where Y Changes

A couple of lines after line 80, y is set to a random value that surely won’t exceed h, so why is there that test that bounds y to be no more than h? It’s only modified on line 170. Since that’s the only place it can ever exceed h, let’s move that check after line 170.

The Code So Far

Let’s see what we’ve come to.

Colon-ization

Apparently ZX-81 BASIC doesn’t let you run multiple statements together on a line. Color BASIC does, and it even has an ELSE. Let’s sort of switch to Color BASIC (still leaving off unused line numbers for now, and ignoring the PAUSE, which waits a number of “ticks”) and see if things can be made clearer. (And we’ll READ those variables rather than assign them one per line.)

What Do All Those One-Letter Variables Mean?

That’s a good question for any street BASIC program. The final PRINT statement gives away^[2] that s is the score. x and y suggest coordinates in a two-dimensional space, but we need more evidence.

Next clue: the player can move the defensive weapon. The only variable changing depending on inkey$ values is c, and considering the print at statements starting at line 110, I’m guessing the invader is at (y,x) and the defender at (h,c), or perhaps it’s (x, y) and (c, h);  maybe ZX-81 flips the coordinates.  h is set once and doesn’t change, consistent with Space Invaders, where you can only move your defensive weapon left and right. (Further evidence: code comparing  y and h and x and c. It’s a collision check. )

Moving to BASIC09 (Finally!)

Enough one-letter variable names. Time for BASIC09, because it has capabilities this program desperately needs:

• The mostly optional line numbers that we’ve been using post-exorcism. Ultimately we hope to remove them all using BASIC09’s superior flow control statements; we’ll see.
• The ability to use longer variable names at minimal cost. The internal form of the code doesn’t use the names at all, so a BASIC09 procedure has exactly one copy of the name of any variable or parameter in it.
• BASIC09’s TYPE facility, which gives you what in the type biz is called a “product type”. In Algol 68 or C they’re structs;  in Pascal, record types. TYPE lets you gather up the information about something in a single place rather than scattering it across a bunch of seemingly unrelated variables.
• procedures with local variables and parameters.

Let’s start with TYPEs. We are dealing with three kinds of things here:

• The playing field, a rectangular region where things appear and happen.
• The coordinates that specify a location.
• An object that is on the playing field.

which suggest the following types:

We’re wimping out a bit on REGION by assuming the minimum coordinates are zero;  we really should have a min in it as well. One could also argue about dead. Does the invader really die when it goes low enough, and do projectiles or beams die?

Curiously, the original has some constants actually appearing in code rather than being assigned to variables:

• 26, which we place in playingField.max.x
• 21, which we place in playingField.max.y

I guess the overhead of converting them wasn’t considered worth avoiding. Good practice these days considers such constants in code “magic numbers” and recommends giving them names to indicate their meaning. Writing street BASIC? Good luck finding a meaningful one- or two-letter variable name for them. In BASIC09? No problem.

So here’s a map from some of the random single-letter variables to what you’ll see below:

• x in the original program becomes invader.loc.x here
• y in the original program… you guessed it, invader.loc.y
• c is, of course, defender.loc.x
• h is defender.loc.y

TYPEs let you name things consistently, in a way that shows their purpose and what they belong to. In street BASIC, you get to infer that kind of information yourself, unless the author has added comments (but, but… with comments you couldn’t fit it in 1K!) or a separate explanatory text that you hope is kept up to date with the code.

There’s no variable in the original program that corresponds to the dead field in an OBJECT.  So how is that information represented in the street BASIC version? It’s represented by where you are in the code. You test the expression that corresponds to it and conditionally branch. In general, the current line number can thus represent an arbitrary amount of implicit state. Good luck keeping it all straight.

This is just refighting the structured programming wars, which structure long ago won. In 1966, Böhm and Jacopini proved that any program can be cast in a structured form, if you’re willing to put up with some additional variables^[3]. The dead fields are just that. collisionCheck sets them to TRUE if needed, and the main loop checks them. Back in the day, GOTO fans^[4] claimed that setting and testing those added variables was just too inefficient… but I think it’s worth it for clarity. How long does the loop run? Until the defender’s dead.

So here’s an initial cut of… OK, it’s not the initial cut. You’ll see the offsets that appear in BASIC09 listings, so this is code that basic09 actually accepts and can run. Apologies for the funky colors; Code Blocks does nicely for setting source code, but… (I told it it was BASIC, but it got confused with the strings somehow.)

So… we’ve gotten rid of all the line numbers save those on the subroutines. Alas, BASIC09 doesn’t have the TrueBASIC SELECT…CASE that would let us avoid them.

Why the explicit check for an empty string coming back from inkey? Think about it. I claim that SUBSTR(“”, s) will return 1 no matter what string s is. Why? Every character in the empty string can be found, in order, at the beginning of s, because there are no characters in the empty string. Therefore, it gives us a false positive on  the ON…GOSUB.

What have we forgotten?

• Randomizing the random number generator seed.
• Remembering the echo setting for standard input, turning it off, and putting it back to its remembered state at the end.
• Slowing it down enough that I might actually get a positive score.

Those, and picking a decent set of characters to press for left, right and fire, we’ll leave as an exercise to the reader.

If you have the urge to extend it, it’s easy to write something like

DIM defender,invader(10):OBJECT

along with adding a variable to track the current number of invaders, code to increase the number of invaders, and code to iterate over them if you want to make life tougher for the player. (Try that in street BASIC.)