Slim's Geek Gazette

[Slim]

I've become consumed by some pretty nerdy interests this last few weeks and I thought I'd have a thread to document them here. Comments and discussion are welcome of course, also please do feel free to start your own.

Now then. Star Trek. One of the very first computer games, written back in the days when computers were not a thing even in the workplace with very few exceptions, and definitely not at home. They were things the size of fridges kept in server rooms attended by men in white coats and accessed by green screen terminals. A university might have one, or a large business.

Star Trek was written by a high school student who had access to a minicomputer at the University of California, Irvine. It was actually written to use a teletype, not a screen. It's a fairly simple game of strategy.

Ten years later there were a few versions of it for the first microcomputers. I first played it on a Commodore Pet in 1983. Then I decided to write my own BBC Micro version in 1984. Honestly this was one of the most absorbing and fun things I've ever done. I'd worked out in my head how it must work, using an 8x8 array for the "galaxy" and another one for the local "quadrant".

I still have that program on a floppy disk in the garage in theory but I don't have a BBC Micro now and the floppy is most likely unreadable by now.

In 2002 though I decided I'd write a version in C, to run in a terminal. This was less sophisticated than the BBC BASIC version I'd written, but pretty true to the spirit of the original game. A screenshot is shown below. Again this was huge fun to do, though it didn't take long.

Highslide Image Viewer

Sixteen years later in 2018, I decided I'd write another terminal version, this time in BASH, a language intended mainly for admin tasks - orchestrating backups, that sort of thing. But there are utilities for moving the cursor to defined points on the screen, so in principle, animations are possible. Photon torpedoes tracking across the screen, the Enterprise moving across the quadrant. Unfortunately I got bored with it and abandoned it before it was finished.

Once or twice after I retired, I looked at the code with a view to finishing it off, and gave up pretty much immediately. I mostly couldn't fathom it. Then a few weeks ago I had an idea - perhaps ChatGPT could explain to me what my code did, what I intended by this or that function, what was the point of this variable - and so on. It could!

So with the help of AI - both ChatGPT and Gemini - I worked out what my code was doing, and I thought I'd spend a couple of days finishing it off. Once again though I got absolutely engrossed in it. I completely got my head round it. I didn't merely finish it off, I refined it and optimised the fuck out of it. I haven't used AI to write any of it, but I did get it to review snippets of code occasionally. Actually, and this might sound odd, one of the more valuable aspects of doing a coding job like this alongside an AI is the moral support and encouragement it provides. I'm not kidding. There is a genuine psychological benefit to having an AI partner in a coding task.

Highslide Image Viewer

It's been nerd heaven.

[Thenop]

It's been nerd heaven.

Without the afterlife connotation of course.

[The Picnic Wasp]

Weird feeling to recognise and understand all the words yet not have clue what's going on.

[Slim]

Fun fact - although the game was very playable on a BBC Micro - it mostly waits for player input - some of the calculations and logic would run probably a couple of thousand times faster on the BASH version I wrote, on a modern PC.

This is due to:

• Dramatic differences in the clock speed of the CPU - a modern CPU runs about 2000 times faster than the BBC's 6502.
• 64 bit versus 8 bit CPU architecture.
• RAM speed (modern DDR5 RAM is almost 1000 times faster than my old BBC Micro's "warm memory chip" and modern CPUs have on-chip memory caches that are much quicker even than that.

OK I just got ChatGPT to estimate this, it reckons 5,000 times faster. But my 2002 C program, once compiled into a binary, would run more than 18,000,000 times faster on a 2025 PC for the internal calculations. That's largely because compiled programs run much faster than interpreted code.

Highslide Image Viewer

[Nick]

I have distant memories of playing this at the friends of my parents. The husband had a job "with computers" and in a spare room in his house had a monitor and all I can think of now is something that resembled a tower system, although it was the first time I had seen anything like it, huge floppy discs were inserted and StarTrek was loaded. It was quite simply the best thing I had ever seen, vaguely remember selecting photon missiles or similar and spending hours with my brother playing it.

As few years later the husband was knocking off Atari cartridges on green circuit boards that were cut to fit into the Atari console, at the time the games were very expensive but we had the luxury of playing them all as they were copied, I have no idea how he was doing this, great times.

[Slim]

Just googled this - a modern, mid-range desktop or laptop CPU can do 20 billion scalar instructions per second - a scalar instruction being in effect a simple machine code instruction.

So the time taken for a CPU to run a single basic instruction is the time it takes light to travel about 1.5cm.

[Slim]

I think I'm nearly done with my Star Trek updates. I only intended to finish it and get it working but I've implemented loads of optimisations just for the hell of it. A game like this that spends 99% of its time waiting for player input doesn't need optimising really, it's just a boatload of fun to do it.

Most notably I've changed the data structures for quadrants to use sparse arrays rather than filling the "empty space" positions with zeroes. I've buffered the various status scan screens so that they're cached into a variable before being displayed in one go. And I've coded early exits from some of the looped logic.

This morning I've put in place a function that works out the maximum distance you can travel on the 64x64 grid that is the playing space, a bit like a chess board. The function that asks for the distance you want to travel now won't accept a number greater than this. This has allowed me to remove the logic that tests if you attempt to leave the "galaxy" or not (previously you'd get a "warp engines shut down at edge of galaxy" message).

Even better - let's say you want to move 23 places to the right - instead of stepping through each of the places in a loop, as soon as you leave the current quadrant (where I check for collisions with stars) the code can break out of the loop and just jump you there. So you only loop a small number of times. Admittedly you'll never notice the difference, it happens in less than 50 microseconds either way.

So my code is probably more efficient and light on resources than the original 1971 game that ran on an ancient Sigma 7, despite running on a system with a CPU that's hundreds of thousands times faster and has about 250,000 times more memory.

A computational job that took about a second on my Linux PC would take about 18 hours on that old 1971 computer the size of a fridge.

Highslide Image Viewer

[Slim]

I still haven't finished off this implementation of Star Trek. I've made a few optimisations and enhancements this last few days.

Most recently I've pondered, and fixed, the following problem. There are four possible ways for the game to end:

• All Klingons destroyed (player wins)
• Player resigns (loses)
• Enterprise destroyed (player loses)
• Enterprise "stranded" (player loses)

That fourth one is what happens when the Enterprise runs out of energy. It's possible to transfer energy to and from the shields. But if shields and energy are both 0 the player can't navigate anywhere (because energy is "fuel"), so it must be an end-of-game situation.

So what's the problem? Well - the total energy store (energy + shields) is depleted in the following ways: navigation, using phasers or taking damage from incoming Klingon fire.

The basic flow of the game is as follows: the player issues a command (long range scan, phasers, torpedo, navigate, whatever) then if the Enterprise is in a quadrant occupied by Klingons, each of them fires, resulting in the shield energy being depleted. If it goes below 0, the Enterprise is destroyed.

But here's a wrinkle: what if the Enterprise has energy 0, and incoming Klingon fire decrements the shields exactly to 0? It's highly unlikely, but a remote possibility. In that event, the game would end with the "stranded" condition; the Enterprise dead in space, all enery reserves depleted. That's OK, but to me it seems a bit odd in the middle of a combat situation.

So I decided that the "klingon response" phase of the game would never leave the Enterprise with exactly 0 energy reserves. I've decided to do this as follows: if the last Klingon phaser volley leaves the Enterprise on zero reserves, then the first Klingon to fire has another go. Obviously it would be a bit strange just to do this in this one, rare circumstance - so I decided that it would happen randomly, occasionally in any event. And to balance it out, I decided that I'd have one of the Klingons decline to fire, very occasionally.

So the logic of the "Klingon response" phase is now as follows:

The program rolls a virtual ten-sided dice.

• If the dice throw is a 1 (in other words this happens 1 time out of 10), then the last Klingon to open fire withholds fire instead - but ONLY if the Enterprise total energy is not 0 (because we'd be causing the very problem we're trying to fix).
• If the dice throw is a 2 (also 1 time in 10 of course), OR if the Enterprise total energy is 0 - then the first Klingon to fire fires again - provided its attack would not leave the Enterprise on 0 energy reserves.

This way, the game can't end with the Enterprise stranded in a Klingon-occupied quadrant. You'll always get finished off by a Klingon.

The nice thing about this is that irrespective of the Enterprise's energy situation, the random element makes the game a bit more unpredictable and interesting. I decided to shuffle the Klingons before they open fire, so that the withholding or repeating Klingon is not the same every time.

[Slim]

Numerical Methods is a term to describe techniques for solving mathematical problems using algorithmic methods - in other words the sort of maths a computer can chew on. On the first year of my degree course there was a module covering this rather dry discipline.

I remember being quite intimidated by it at first, in fact I remember sitting at the back of a lecture theatre and being overcome by a sense of dismay during the first lecture. I had to pass the module, or I wouldn't get onto the second year. However I did manage to get a handle on the topic, fortunately. It wasn't as hard as the scary-looking equations scrawled on a whiteboard made it appear.

I can only remember two methods that we were taught, and then very vaguely. One was for deriving an equation from x,y points on a curve. But the one that stands out in my mind, albeit paradoxically I forgot the actual method years ago, is Gaussian Elimination.

Until recently I'd forgotten what it was for. However, driven by a later life nostalgic initiative to revisit my youth - I decided to relearn it. I got Gemini to teach me. It's actually not that hard.

So: the idea is to solve a "system of equations". Let's say you're given:

2x + 3y = 7
4x + 5y = 13

Your mission, should you choose to accept it, is to find out the values of x and y. So to do this, we create a simple matrix:

2 3 7
4 5 13

Firstly, we find a "multiplier" that we can use to get the coefficient of x the same in both equations. In this case it's 4 / 2 = 2.

So we multiply the first equation by the multiplier (2), and we get:

4x + 6y = 14
4x + 5y = 13

From this form, you subtract the bottom equation. And you get:

0x + 1y = 1

.. or put more simply:

y = 1

From this point, it's a simple matter to find the value of x, from any of the equations. Let's take the first one:

2x + 3y = 7
2x + 3 = 7
2x = 7 - 3
x = ( 7 - 3 ) / 2 = 2.

If your eyes glazed over reading this then you'll understand how I felt back in September 1985. But if you had to wrap your head round it, you'd find that it's easier than it looks.

However: although I understood the method exactly, I was slow at it. So when the first year exams rolled round in June 1986, I decided I'd enlist some help in the form of my trusty Casio fx4000p programmable calculator, which I still have. I painstakingly wrote on paper, then keyed in, a program to perform the elimination. The program stepped through each problem, showing the intermediate steps, the "working". I just had to enter the values, button-push through the steps, discreetly write them on the exam paper while glancing at the calculator.

You weren't actually supposed to take programmable calculators into an exam, of course. But I hadn't keyed notes into it or anything - just a program to perform calculations using a method I already understood very well. It made very light work of the Gaussian Elimination questions on the exam. And the great thing about a 4000p was that to your average middle-aged exam invigilator in 1986, it didn't look like a programmable, it just looked like a regular scientific calculator.

I insist that I was not, in spirit, cheating. In fact: since the purpose of that course was to learn methods that could be applied to code, I maintain that I had actually gone a bit further than any of the other students on the course. I'd actually coded one.

The actual "language" used by Casio programmables at that time is very basic - it more or less just mirrors the keystrokes that you'd type if you were doing the calculations by hand, with some crude flow control and memory handling thrown in.

Unfortunately I deleted the program from the calculator many years ago. My next project is to reacquaint myself with the language, and code another Gaussian Eliminator.

[Thenop]

Gaussian Eliminator, that's a fantastic album title.

I know the Gaussian terminology only from audio compression, which makes sense considering what you wrote. Not that I amm usning it in any way, it's just a term I have come across. It's sort of a normalization process but it's based around the principle of finding the 'average' rather than 'squashing' the audio as normal AGCs (audio gain compreccors) would do. Radio stations use AGC as you probably know.

[Slim]

My fx4000p.

Highslide Image Viewer

It's 40 years old, I bought it in September 1985 I think. But it looks like it could have been designed and manufactured this year. And that's because - like sharks and ants, calculators reached an evolutionary plateau long ago, and stayed there. As soon as they were sufficiently slim and power efficient and had decent LCD displays, they'd arrived.

The main difference is not one of function or form, but how cheap they are to manufacture. The chips inside them don't even run that much faster, because they don't need to (and if they did they'd eat the batteries more quickly).

I remember my dad bringing a calculator home from work in the '70s. It was a heavy mains-powered thing with big clunky keys and a nixie tube display (a sort of precursor to LED). 

[Slim]

One of my other calculators. I bought this one not long before the fx4000p.  Scientific, but not programmable. These were made for Texas Instruments by Toshiba, interestingly. Solar powered, very handy.

Highslide Image Viewer

[Slim]

And my Casio fx-451. Again, solar powered and again, like the other two, purchased in the late summer / early autumn of 1985 after I'd just started my degree course.

Scientific calculators were not really cheap then. I don't remember if I bought this one before or after the TI and I can't imagine how I'd have justified it to myself.

This one does have an annoying feature - the wallet flap with all the scientific functions doesn't stay flat when you open it, as you can see. I used to hold it down with the corner of a book or a folder. Also I'm not really a fan of the touch keys although they do work OK.

Highslide Image Viewer

[Thenop]

I had one of these in school, I loved it. Sadly, it's in the same place as all my other things from that time went: a black hole.

Highslide Image Viewer

[Slim]

I spent hours yesterday engrossed in my Star Trek code. I had the idea of caching long range scan, short range scan and galaxy map displays - so that if the player invokes one of them and nothing's changed, the program just displays the cache from the last time it was generated.

The program just tests to see if the string variable with all the display data exists, and if it does - it uses that. When something happens that invalidates the data - like for example the Enterprise moving from one quadrant to another - the program just unsets the variable, to mark the data as stale.

There's no practical point in doing this whatever, because the code that generates the displays runs in a very few microseconds. I just get a kick out of making the code as efficient as inhumanly possible. It's a really a very diverting exercise.

Today's plan is to cache the quadrant data.

So: in the old Star Trek game you have 64 quadrants, each quadrant is a 64-element array in reality. What happens is that a quadrant is created dynamically, with stars, and (optionally) a base and a set of klingons, each time you enter it. Obviously on the hardware of the 1970s, this saved memory.

So: you enter a quadrant, you see the stars in a certain position, you leave it, you enter the same quadrant again, the stars (and Klingons if present) are in different places. That's fine, it's true to the spirit of the old game.

But: I'd like to organise the game so that when you enter a quadrant for the first time, it gets created. But then it gets saved, so when you come back, the stars (and Klingons if present) are all in the same place.

What a quadrant actually is, in code terms, is a sparse array of integers, indexed from 0-63. If there's a star at 0,5 say, then quad[5] will be a 1.

Ideally, what you'd want for this would be a sparse array (the galaxy) of sparse arrays (the quadrants). But BASH, the language this is written in, doesn't do arrays of arrays. So I've got to fake it, probably using strings.

Importantly, I want to retain the data structure I already have for the galaxy, and indeed for the quadrants because boatloads of code in the program already use it. I just need somewhere to store it, where I can reread it, instead of creating it anew each time. But the array of integers representing the quad will be exactly the same design.

Highslide Image Viewer

Here's one thought I had. So let's say the player visits the 32nd quadrant in the galaxy array. Let's say it has stars at positions 10,32 and 48 and Klingons at 16 and 60. So it will be a sparse array with 5 elements. As they are put in place by the function that populates the quadrant, the function also creates quadsave[32], previously unset. Stars are represented by the integer 1, Klingons by 2. So maybe quadsave[32] will be "10 32 48 : 16 60". Or maybe "10:1 32:1 48:1 16:2 60:2".

I just need a format that's efficient and that can be read easily by the code. And modified easily, because as the game progresses, Klingons get removed from the quadrants.

I could even have separate arrays for stars, starbases and Klingons. Will have a think. The hard part is doing set subtraction to remove Klingons.