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.
(https://i.ibb.co/zV79MX7n/Star-Trek-text-game.png)
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.
(https://i.ibb.co/CpVCW1HK/trekscrn.png)
It's been nerd heaven.
Quote from: Slim on August 07, 2025, 01:53:07 PMIt's been nerd heaven.
Without the afterlife connotation of course.
Weird feeling to recognise and understand all the words yet not have clue what's going on.
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.
(https://i.ibb.co/HTzn0g9d/CvsBASIC.png)
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.
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.
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.
(https://i.ibb.co/h1s0W5X7/sigmaseven.jpg)
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.
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.
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.
My fx4000p.
(https://i.ibb.co/wsy7BQB/fx-4000p.jpg)
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).
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.
(https://i.ibb.co/hJzgB2zW/ti30slr.webp)
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.
(https://i.ibb.co/Y7sSVKKt/fx451.webp)
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.
(https://i.ibb.co/4Zmv8rt3/TI-30-Galaxy.jpg)
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.
(https://i.ibb.co/xSCc7Dgh/trekimage.png)
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.
Quote from: Slim on August 28, 2025, 11:43:24 AMBut: 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.
So having looked into this, I realised that there's a flaw in this idea. In the existing design, after the Enterprise arrives in a quadrant, the quadrant is populated "around" it. In other words other objects are never placed in the same location.
But if we cache the positions rather than rebuilding them around the Enterprise, the ship could land on top of a star or Klingon.
I still think it's worth doing, but - we'll have to perform a search for the next free position. Very worst case, the next seven positions are occupied and the odds against that are billions to one.
So I did that, works nicely. Surprisingly complicated to do, but it's a bit like building a working model from parts you've made yourself, really rewarding.
Will try to come up with some more meaningful enhancements, maybe uncloaking Romulans or something.
I love the amount of geekiness that oozes through this thread.
I myself find it perfectly normal to refer to Romulans, Vulcans or the Glory of the Empire. Fortunately so does my wife, but I do see people making a face when I wandere in less than geek territory every now and then. Not that I care. I am way past that point.
Anyway, sounds like a fun project you are doing.
Quote from: Slim on August 21, 2025, 12:48:27 PMThe 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.
So I've prototyped a Gaussian Eliminator program in awk, which is a language most oftne used for manipulating text. My first instinct would have been to do this in BASH, for familiarity. But BASH only does integer arithmetic natively. So this is what I came up with, in awk:
#!/usr/bin/awk -f
function get(prompt, var) {
printf "%s ", prompt
getline var < "-"
return var
}
BEGIN {
A = get("X1")
B = get("Y1")
C = get("K1")
D = get("X2")
E = get("Y2")
F = get("K2")
M = A / D
print "M:"
printf M
du=get("")
E = M * E
F = M * F
printf A
du=get("")
printf E
du=get("")
printf F
du=get("")
E = B - E
F = C - F
printf E
du=get("")
printf F
du=get("")
Y = F / E
printf "Y="
du=get("")
printf Y
du=get("")
B = B * Y
printf A
du=get("")
printf B
du=get("")
printf C
du=get("")
C = C - B
printf A
du=get("")
printf C
du=get("")
X = C / A
printf "X="
du=get("")
printf X
du=get("")
}It's intentionally very minimal and crude, to mirror a calculator program. Those 'du=get("")' lines are just to pause until a key is pressed, like a calculator can be made to do.
For the problem:
2x+y=7
3x−2y=7
.. the transcript looks like this:
X1 3
Y1 2
K1 7
X2 2
Y2 1
K2 7
M:
1.5
3
1.5
10.5
0.5
-3.5
Y=
-7
3
-14
7
3
21
X=
7
I think that's pretty close to what my old Casio program would have done in 1986.
Next - convert to Casio code and key in to my calculator!
So, I did that. The Casio program is:
?→A:?→B:?→C:?→D:?→E:?→F:A÷D→M:"M="◢M◢E×M→E:F×M→F:A◢E◢F◢B-E→E:C-F→F:E◢F◢F÷E→Y:"Y="◢Y◢B×Y→B:A◢B◢C◢C-B→C:A◢C◢C÷A→X:"X="◢X◢
And it works! I'm sure it's not exactly the same code I keyed in to the calculator in the summer of 1986, but it does pretty much the same thing.
If you're curious, the ◢ means pause until the user presses a key (allows you to read what it's just written to the single line display) and the : is a delimiter between commands.
I'm going to start a thread called "Matt's Greek Gazette" so you techies might get an empathetic idea of how this one appears to me. :)
Quote from: Matt2112 on September 01, 2025, 12:16:22 PMI'm going to start a thread called "Matt's Greek Gazette" so you techies might get an empathetic idea of how this one appears to me. :)
So that'll be a thread on run down buildings with philosophical tag lines then?
I'm seriously considering doing a Greek GCSE so it could be a journal of my progress through that... ;)
(Sorry to go off-topic).
I decided to rewire my Star Trek program. I just thought of a cleverer way to organise and manipulate the quadrant data. But it was in a complete and working state, so I've kept the existing code as "version 1". My fear of course is that I'll introduce a bug, get bored with it while it's broken, and end up getting an AI to tell me how it works again, years from now. As long as I have a working version, this mission that I embarked on a few weeks ago is complete.
I should admit that the change I'm making makes zero difference to the experience of using the program. But because it's an ancient game from the days when every byte was precious I'm indulging an extreme efficiency philosophy. More in keeping with the spirit of the original idea, back in 1971. It comes partly from learning to code on a ZX-81, a system with roughly seventeen million times less memory than my present Desktop computer has. Without doubt it did make me a very economical programmer.
More than anything, I just find it fascinating to do, like a very complicated puzzle.
So I did that. Changed the way it handles its data. Introduced some clever caching for short range scan displays, and nifty buffering for screen writes. I went to bed last night at about 0130, shortly after I had the idea, with a contented smile on my face as I closed my eyes, thinking "that'll keep me occupied for a few days!"
Nope, all done by about 1500.
I still have a few vague ideas on how to extend it though. Maybe introduce Romulans. I could even have the Romulans and the Klingons attacking each other. Or wormholes.
Spent most of the day setting up my new PC. Using it now, but still a lot to do. But I've hooked the old one up to an old monitor and keyboard so I can do the changeover gradually. Very happy. Big, robust case, the cabling inside is very tidy and it's much quieter than the last one - it's actually a bit eerie here in my mancave with the old one turned off.
For fun I ran some benchmarks to compare performance with my last desktop computer and a micro-pc (minako) which I use as a backup server.
(https://i.ibb.co/G4FPPFs1/benchmarks.png)
The new box (pop-os,named after the Linux version) is quite a bit faster than the last one (glower) and about ten times faster than the micro-pc for a CPU intensive job. The disk write test, involving writing 512MB of junk data to local disk, shows the NVMe storage on the new box to be about twice the speed as the NVMe on the old one, and about five times quicker than the SSD on the micro-pc.
But the graphics card is the most dramatic upgrade. Will try some local AI image generation later.
For perspective, that disk test that took less than half a second on the new PC would have taken about 25 minutes on the workstation I had on my desk in the early '90s, except that it didn't have enough disk space to accommodate 512MB.
I picked up one of my old computer mags, from August 1990. There's an article on voice processing, which of course was in its infancy then. "Algorithms today can capture speech using bit rates from a few hundred bits per second to a few hundreds of thousands of bits per second", it says. Fascinating. A few hundred bits per second would have sounded extremely crude.
It also states that an A4 page of information (in voice format) would take up "500,000 bytes", which would roughly be 32kbps. Then it says "this is clearly too much". And "voice systems tent to sample at a rate of between 6000 and 10000 samples per second".
These days it's trivial to store hours of voice audio at much higher sample / bitrates of course.
Just dug my old netbook out because I wanted to run the same benchmarks from the post before last. These are the actual tests:
jg@aspire:~$ time dd if=/dev/zero of=testfile bs=1M count=512 oflag=direct status=none
real 0m9.435s
user 0m0.009s
sys 0m0.411s
jg@aspire:~$ time head -c 100M </dev/urandom | sha256sum >/dev/null
real 0m3.569s
user 0m1.138s
sys 0m1.202s
jg@aspire:~$
My new desktop PC (much higher spec and 10 years younger):
jg@pop-os:~$ time dd if=/dev/zero of=testfile bs=1M count=512 oflag=direct status=none
real 0m0.312s
user 0m0.000s
sys 0m0.067s
jg@pop-os:~$ time head -c 100M </dev/urandom | sha256sum >/dev/null
real 0m0.287s
user 0m0.272s
sys 0m0.224s
Many times faster. The CPU test runs in less than 0.3 secs, compared to 3.6. The disk test: 0.3 secs compared to 9.5.
Still working on my Star Trek implementation which I have named Bash Trek, after the programming language I've used.
The following graphic shows the Enterprise in a quadrant with four stars. At the moment, I place the stars randomly. But there's a problem with this strategy, a potential flaw. It's possible, though improbable, that the Enterprise could arrive in a corner position, in the corner quadrant with three stars in the immediately adjacent positions. A sort of "three star hug". Were this to happen, a sort of stalemate would occur in which no move is possible.
(https://i.ibb.co/svjjTrh6/starfield.png)
The odds of this happening in any given quadrant are 1 in 2480 and it's only a problem if the Enterprise is in the corner. Nonetheless I see that as significant - it's in "it'll happen one day" territory. So I'm going to change the way I place the stars.
At the moment what I do is shuffle the numbers 0-63 and pick the first four (or fewer) for the stars.
So what I'm going to do instead is place each star, check that it isn't adjacent to any previously placed star and if it is, add repeatedly add 3 to its position (the index into the array of positions) until it isn't. Because 3 is coprime with 64, steps of 3 would visit every position eventually. Actually all odd numbers are coprime with 64, because it's a power of 2.
So no two stars will occupy adjacent positions which I think will be nicer aesthetically. And the configuration above in which two stars are next to each other diagonally will not be possible.
The test for non-adjacency is simple: if the absolute value of the difference in the two index values is 1,7,8 or 9 then the two stars may be adjacent. If not, they can't be. This is where the index for the top-left position is 0 and the bottom right is 63.
My
Star Trek project is pretty much finished now. Perhaps I'll do it again in a different language one day. So I've been thinking of what to do for my next coding project, and I had the idea of implementing a version of Conway's "Game of Life", again in BASH, and again in a terminal. Again this is something that was common on the microcomputers of the early '80s, and again something I once wrote in BBC BASIC.
Life is a "cellular automaton". It uses a two-dimensional grid of cells. Each cell is alive (or "on") or dead (or "off"). You start with a simple pattern of live cells and watch the pattern grow, as though organically, according to simple rules:
- A live cell with fewer than two live neighbours dies
- A live cell with more than three neighbours dies
- A dead cell with exactly three live neighbours springs to life
- A live cell with two or three live neighbours remains alive
Much more info here (https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life).
I thought this would take me a week or two, but I had the whole thing done and dusted in a day yesterday. What I'm particularly pleased about is that I was able to incorporate mouse control - in the phase of the program where you set cells alive for the initial pattern, you click on a square on the grid to toggle on/off.
I may optimise it a bit.
There's a very good online version here: https://playgameoflife.com/
It's quite a fascinating toy. Some patterns repeat, some fizzle out to a completely dead grid, some give out pretty patterns for 30 or 40 generations then get stuck.
This is my own version. Captured the screen output and uploaded it to YouTube.
Well, I squeezed a bit more fun out of Life.
I rewrote the function that counts the number of neighbours a cell has. It uses two loops like this:
for lx in -1 0 1 ; do
for ly in -1 0 1 ; do
So that lx and ly are added to x and y to get the x and y co-ordinates of each neighbour. The problem with this is that you don't want to count the actual cell you're checking, but the loops pass through it.
Previously I was checking the x and y co-ords before adding each cell to the sum of live neighbours. But it struck me that an easier way would be just to subtract the contents of the centre cell from the sum. So that's what I do now.
The other change I made is this: it's possible for a sequence of patterns to repeat forever. I decided I'd add some code to detect a repeating cycle, and exit if (or when, I think it's inevitable eventually even if it's just a blank grid) this occurs.
To do this I need to record each frame (generation) somehow. The most practical way to do this would be to use an external hashing utility like cksum. But I'm not trying to be practical here, so I thought it would be fun to come up with a way to do it in pure BASH. So what I do is consider each row of blocks as a 40-digit binary number, convert it to a 10-digit hexadecimal number then store the 40 10-digit numbers concatenated as a string in a list.
Then - each generation, as the new 400-character string is created, it's compared against existing items in the list. If it's there, then the program must be caught in a loop and it exits.
Each new generation is a pure function of the previous generation, so if any generation is repeated, it must be part of an infinite cycle.
I wouldn't have been able to do this in my old BBC BASIC version even if I'd thought of it, because the list of (if you will) "signature strings" could overwhelm the memory. If I stored 80 strings, I'd be using up about 32K of RAM. Nothing on a modern PC of course.
I last wrote a program to convert between number bases in about 1986 so it's been a nostalgic exercise.
I did a bit of research, with the help of ChatGPT, into cycle detection. It turns out there's a very smart way to do this: Floyd's Tortoise and Hare (https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare)algorithm.
So in this context, what you do is: for each generation, run two steps of a "ghost" generation in parallel. You display the main generation (the "tortoise") steps as normal, while the ghost generation (the "hare") races ahead. At some point, when the sequence starts to repeat, they will meet on the same frame. When that happens: bingo, you've detected a repeating cycle.
The disadvantage of this approach is that you have to run a generation step three times for each "main" (or "tortoise") generation. But the advantage is that you only have to store two signatures - the most recent of each - and compare them. You don't get a huge, growing list of signatures and the comparison is much simpler.
Nice little coding exercise. Life is good.
As a quick diversion I thought I'd arrange a little demo of the difference in speed in an interpreted language versus a compiled language.
I wrote a quick program to calculate the 27th term of the Fibonacci series (this was something I had as an exercise in first year Comp Sci, it's interesting because it can be done recursively). This is the BASH version:
#!/bin/bash
function fib () {
if (( $1 < 3 )); then
echo 1
else
p1=$(( $1 - 1 ))
p2=$(( $1 - 2 ))
a=$(fib $p1)
b=$(fib $p2)
r=$(( $a + $b ))
echo $r
fi
}
fib 27
exit 0
The Pascal version, compiled to a binary (same method, exactly the same algorithm):
program FibonacciRecursive;
function Fib(n: Integer): Integer;
begin
if n <= 2 then
Fib := 1
else
Fib := Fib(n - 1) + Fib(n - 2);
end;
var
n: Integer;
begin
n := 27;
writeln('Fib(', n, ') = ', Fib(n));
end.
Pascal did it in 0.005 seconds, BASH in 6 minutes, 0.4 seconds.
Quote from: Slim on October 14, 2025, 12:29:47 PMI did a bit of research, with the help of ChatGPT, into cycle detection. It turns out there's a very smart way to do this: Floyd's Tortoise and Hare (https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare)algorithm.
There's an even better way to do this, Brent's Algorithm (https://en.wikipedia.org/wiki/Cycle_detection#Brent's_algorithm).
This is more efficient because you're only running the generations in one stream. You store a checkpoint signature at intervals increasing by powers of two (so 1, 3, 7, 15 etc) and compare every subsequent signature to it. When you get a match, you've detected a cycle.
Why powers of two are used I'm not sure, I don't quite understand the maths. The downside is that it won't necessarily detect that the sequence is in a loop as quickly. But it does work, and it was easy to code.
I made four more changes to the Life program. Firstly, I enabled mouse dragging to switch on live cells in the editor - much easier than clicking for some shapes, although that still works as well of course. A bit like painting shapes into the grid.
Secondly, I implemented Brent's Algorithm as described above.
Thirdly, because it can take a while for the Brent algorithm to determine when the system has gone into a loop, I've also set it to detect when the last-but-one pattern was the same - because the most common repeated cycle is STATE A - STATE B - STATE A, or STATE A - STATE A.
Checking the signature from two generations previously detects this instantly, at the cost of storing one extra signature.
Fourthly, I added a compression routine to the signature store. Because blank rows are common, the pattern 00000000 will turn up often in the hex signature. So I substitute a Z for this. Since consecutive blank rows are also common, I could also check for (maybe) four consecutive Zs and substitute a Y (or something) for them on a second pass. But there's little point really. The BASH interpreter can store and compare very long strings very easily on a modern computer.
Need to think of another little project now. Or maybe I'll rewrite this one in C or Pascal.
I don't use the ethernet NIC on my main desktop so I've used it to set up a network between it and my micro server - just a cable plugged in at both ends. You used to need a crossover cable to connect two computers directly, because both NICs expected to transmit and receive on different wire pairs. Now the interface detects the link pulse and swaps its transmit / receive pins if necessary. Handy.
So I've set up the micro server as an NFS server so I can back up to a USB drive plugged in to it. I was doing this using rsync over ssh previously, but (because there's no encryption overhead) NFS is much quicker.
I've been using NFS since 1990 (at work of course). Back then it was NFS2 - pretty horrible to set up and work with, with a whole constellation of different ports being used. NFS4 uses a single port, so much less bother. So much more coherent as well, stateful, stable and quicker.
I gave in to a nagging dissatisfaction with the way I was distributing Klingons throughout the galaxy in my Star Trek program, which I'm calling Bash Trek. The way it worked was this: I picked a number of quadrants to have Klingons, a random number between 5 and 7. Then in each I added a random number of Klingons, between 1 and 4.
That was OK, but the total number of Klingons was too variable. Potentially (although highly unlikely) you could have 7 x sets of 4 Klingons, or (equally unlikely) just 5 in total.
So I decided there would always be 16 Klingons. I populate two quadrants with 4 Klingons each. Then I just keep adding a random number of them, between 1 & 4, to a new quadrant - until there are 12 or more of them. Then I top up one more quadrant to bring the total to 16. Much better outcome and the logic is a bit simpler as well. There's a still a variable number of quadrants with Klingons in but I don't predetermine the number.
So finally, I've decided that Bash Trek is complete and I've uploaded it with documentation to GitHub here: https://github.com/StarShovel/bash-trek
Not saying there won't be a version 1.01 at some point, or even a 1.1 but for now I'm happy with it.
Twenty-five years ago I owned a Sega Dreamcast. For those who don't remember it, Wikipedia describes it as the "first sixth generation era games console". I'd describe it as being better than a PS1, but not as good as a PS2.
There was one game in particular, a flight sim, that I particularly liked called Deadly Skies. Well - it turns out that there's a very good, free Dreamcast emulator for Linux called Redream and the games can be downloaded easily for free. So I've bought myself a USB games controller from Amazon for about £21. Took about 15 minutes to set up. Works nicely! I couldn't find a cheat code for Deadly Skies to unlock all the levels, so I went through the first four missions last night. Fun!
(https://i.ibb.co/nqjm9NDr/deadly-skies.jpg)
There's one mission in particular that I'm looking forward to, set over a city. You have to down incoming cruise missiles (if I'm remembering correctly) before they hit a particular tall building.
(https://i.ibb.co/Kzs2WC84/sddefault.jpg)
I'll be looking into setting up a PS2 or PS1 emulator as well.
Quote from: Slim on October 13, 2025, 10:54:02 AMMy Star Trek project is pretty much finished now. Perhaps I'll do it again in a different language one day. So I've been thinking of what to do for my next coding project, and I had the idea of implementing a version of Conway's "Game of Life", again in BASH, and again in a terminal. Again this is something that was common on the microcomputers of the early '80s, and again something I once wrote in BBC BASIC.
Life is a "cellular automaton". It uses a two-dimensional grid of cells. Each cell is alive (or "on") or dead (or "off"). You start with a simple pattern of live cells and watch the pattern grow, as though organically, according to simple rules:
- A live cell with fewer than two live neighbours dies
- A live cell with more than three neighbours dies
- A dead cell with exactly three live neighbours springs to life
- A live cell with two or three live neighbours remains alive
Much more info here (https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life).
Life got a mention on
University Challenge this evening.
I've created Bash Trek II, a mouse-controlled version of Bash Trek. I started this as an experiment but actually it does work pretty well. Spent hours on it yesterday and today.
(https://i.ibb.co/9mfpNdfN/st2.png)
So the blue row is a list of clickable commands and you enter the values using yellow buttons.
Still need to document it and set up a repo on github.
I changed the design of the above, to this:
(https://i.ibb.co/R4zscK5w/srs.png)
The trouble with the first design, although I liked the little "enter" button is that it involves too much clicking around, too much mouse movement.
In this first design, a right click on a number button would subtract, a left click would add and you left-click on the return button to confirm.
In the second - hopefully more ergonomic design - you left-click separate + and - buttons, then you right-click to confirm.
So it's more a Human / Computer Interaction (HCI) problem than a logical one.
I studied HCI as a final year module 36 years ago. Can't remember much about it except that one of the topics we covered was hypertext. A method of organising and presenting digital text in interconnected chunks that users can navigate by following links. In 1988 it was used in documentation systems, digital training manuals, interactive textbooks.
Our lecturer, a lovely idiosyncratic and endearingly scruffy Welshman called Phil Barker was an expert in the field. He told us that the number of invitations he was getting to speak about it at conferences and presentations was increasing dramatically. It was going to be huge, he told us.
And he wasn't wrong. A few months later Tim Berners-Lee wrote a paper in which he proposed an information management system delivered over the Internet (which already existed) using hypertext. And later that year, the Web was born.
Just as a counterpoint to that prescient nugget delivered by my HCI lecturer, I had another lecturer who, a couple of years earlier, told us that using windows, icons and mouse pointers to interact with computers was a passing fad.
I've finally, I think, finished the mouse-driven version of
Bash Trek and instead of
Bash Trek II I'm calling it
Bash Trek: TNG. I've put it on Github at: https://github.com/StarShovel/bash-trek-tng
I'll post the README here:
Bash Trek: TNG(https://i.ibb.co/5hjgjbtH/bashtrektng.png)
This is an adaptation of
Bash Trek, an implementation of the old terminal game Star Trek. This implementation replaces the typed command interface with a mouse-driven UI and includes some cosmetic refinements.
Requirements- Bash >= 4.3
- A UTF-8–capable, ANSI / VT100-compatible terminal emulator with xterm-style mouse reporting (eg GNOME Terminal, Konsole, Tilix)
- tput - for terminal control / colours
- sleep - for timing and animation
NotesPlease see the
Bash Trek documentation for notes on the basic game design / gameplay mechanics / instructions, as well as comments on the history and inspiration. This document is intended mainly to outline the new command interface mechanics.
InstallationDownload the script directly:
wget https://github.com/StarShovel/bash-trek-tng/raw/main/bash-trek-tng.shchmod +x bash-trek-tng.shAlternatively, clone the full repository:
git clone https://github.com/StarShovel/bash-trek-tng.gitcd bash-trek-tngUsageRun the game from the command line:
./bash-trek-tng.shIt's intended to run on a terminal with a dark background.
IMPORTANT: start the game in a terminal with dimensions 64x22 minimum. Most terminal emulators have a default of 80x24, and that will work nicely. Resizing while the script is running will break the game spectacularly.
InstructionsBash Trek is a turn-based strategy game. The object is to destroy all of the Klingons in the galaxy by finding them, then engaging them with phaser and torpedo fire.
The following commands are available to the player:
NAV - navigate (move) the Enterprise in a specified direction, by a specified number of places (warp)
PHA - use a specified quantity of the ship's energy to fire phasers. Any / all Klingons in the local quadrant will suffer shield damage and may be destroyed.
TOR - fire a photon torpedo in a specified direction. If the torpedo collides with a Klingon, it will be destroyed
SHI - adjust energy allocated to shields, to the specified figure
SRS - display short range scan - showing positions of objects in the local quadrant
LRS - long range scan - information on adjacent quadrants will be displayed and stored in the ship's map data
MAP - display galactic map data
RES - resign command and accept mission failure
The purpose of each is described in the original Bash Trek documentation; please refer to that where not obvious.
Command InterfaceBash Trek: TNG uses a clickable command bar to invoke each of the above commands:
(https://i.ibb.co/C5cN42Wm/cmd01.png)
.. left click on the required command to invoke it.
The NAV and TOR commands require a direction to be entered. To enable this, a pointer arrow is displayed at the Enterprise position on the Short Range Scan grid:
(https://i.ibb.co/nM5s2gtZ/nav01.png)
Left click anywhere to the left of the yellow pointer to click the pointer anti-clockwise one position.
Left-click to the right for clockwise.
Right-click to confirm the vector (direction). You can also left-click on the yellow pointer to confirm.
The
PHA,
NAV and
SHI commands require values to be entered (for phaser energy, distance and shield strength, respectively). Again this is done solely by mouse control. The interface is shown below.
(https://i.ibb.co/MDVp3rHz/nav03.png)
The buttons to the right of the display allow the input field to be modified by the values shown with a left click.
In the above example the player has entered 8, therefore the +16 and -16 buttons are greyed out (since the permitted value range is 0-21).
The player can left-click the 0 to reset the input field to 0, or left-click the maximum value shown (here 21) to enter the maximum value.
The input field can be incremented or decremented by 1 by using the scrollwheel (forward and backward respectively). The interface doesn't permit out-of-range values to be entered.
The input button states (active / greyed out) are updated with each button click.
The values assigned to the buttons are different, depending on the function. For navigation as above, +/- 8 and 16. For phaser energy, +/- 50 and 200. For shield strength, +/- 30 and 150.
Submit the input value with a right-click.
A Brief Note on Scrollwheel EventsOn X11, GTK apps, including some terminal emulators (gnome-terminal for example), ignore the first scrollwheel event after the mouse pointer enters the window. This is intentional behaviour and there's nothing a Bash script can do to override it. In practice this is only a minor irritation, but you can defeat it by using xterm, rxvt or another non-GTK terminal emulator.
ScreenshotsIn addition to the command interface, minor cosmetic changes have been implemented, in particular to the Long Range Scan display. Additional screen captures are shown below.
(https://i.ibb.co/JFx0g9cM/lrs01.png)
(https://i.ibb.co/XkNV5Nc8/com01.png)
Mission DeadlineYou must complete your mission to eradicate the Klingon presence in the galaxy by stardate 1314.1.
Game ConclusionThe game ends with one of five possible outcomes:
Mission SuccessMission Failure- Player resigns
- Enterprise destroyed
- Failure to complete mission by specified stardate
- Energy supply (including shields) completely depleted
LicenseBash Trek: TNG is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
This program is distributed without any warranty; without even the implied warranty of merchantability or fitness for a particular purpose.
See the LICENSE file for details.
I've been itching to start another coding project for a while. I thought of creating a Bash version of Monopoly. Human versus computer. I did a bit of design, and thinking about the data structures. Then I decided not to. Too many complications with the cards, the different place types (station, utility, card, go to jail etc). It would just end up being annoying and the visual representation using terminal fonts would never work very well.
Then I had this thought: Mastermind! Readers of a certain age will be familiar with the old plastic pegs / codebreaking game from the '70s.
(https://i.ibb.co/LzxMjCzF/mastermindbox.jpg)
So I started coding it last night, and so far it looks like this:
(https://i.ibb.co/21dkP3D5/mm.png)
I've got the input mechanics (press B to place a blue peg, Y to place a yellow pag and so on, backspace to pull the last one out again). It doesn't do any checking or feedback yet (will appear on the right hand side).
The green bar represents the flap that the secret code is hidden behind in the physical game. It looks a bit rubbish, I may have a rethink about that.
I asked ChatGPT to create the artwork - in a 70s-retro style, using an oriental cutie and the bearded middle-aged man like the original. It's embarrassingly far more sophisticated than the actual program, even though it took about 30 seconds.
(https://i.ibb.co/VYyqLLSK/mmcrop.avif)
A bit less than 24 hours after I started, I think this is finished ..
(https://i.ibb.co/Vc2Xrv4H/mmfin.png)
The ✘ is a "no pegs" feedback, it just gives the player a confirmation that the row has been entered and he/she is onto the next one. The top row is the secret code, it appears at the end of the game - either when the player runs out of goes, or gets it right.
Quite happy with that, didn't take very long though. Suppose I'll write some brief documentation and put it on GitHub.
I've discovered that there was a "deluxe" edition that used five-peg codes (rather than four), twelve goes (rather than ten) and eight colours to choose from (rather than six).
So I can get a bit more fun out of this project by including a "deluxe" mode - the script should be easy to modify so that the various numbers are variables rather than static. The extra colours will be orange and purple (orange and brown in the original, but they look a bit similar on a terminal and of course the B for Brown is already used by Blue. For this reason I'm using N for Noir to enter a black peg).
So the program will be run by
$ mastermind.sh -d
To invoke deluxe mode.
So, I did that. Nice exercise, but didn't take long.
(https://i.ibb.co/Cs4rzdNn/mmd.png)
Wrote up some documentation, put it on GitHub:
https://github.com/StarShovel/bash-mastermind
I also added a "minimal mode". Three peg codes, four colours, eight goes. Very quick mod.
(https://i.ibb.co/jv9WBPBw/minim.png)
A bit of spreadsheet fun this morning. I've set up a sheet with waypoints on my favourite long distance bike ride to the edge of Norfolk and back.
(https://i.ibb.co/84fY14YJ/waypointsskm.png)
So the first column is the waypoint name, the second is the distance from the previous waypoint, the third is the cumulative distance (so that, for example, Pode Hole is 107.98 km from home) and the last column is the time of day I'm due to arrive there, based on overall progress of 16 km / hour. The start time (03:00 here) is entered manually.
The third and fourth columns are calculated from the second. The nice thing about doing it in a spreadsheet is that if you have to plan a detour into the route due to roadworks, you just have to adjust a figure in the second column and the rest will recalculate. You can also do "what if" based on different start times, of course.
Next I need to get the spreadsheet to extrapolate the waypoints, distances and times for the way back.
It's nice to have your entire bike ride history in Strava and to be able to look through your old tracks, but the user interface is a bit cumbersome - especially if you have a lot of activities in your history.
Fortunately - Strava allows you to download all of your activity history in a big old zip file. So I thought I'd do that, and organise them as a sort of local database on my own PC.
So I downloaded them. The Strava servers just keep whatever you upload unsurprisingly, so I found that I had track files in a number of different formats - mostly GPX, but also FIT, TCX and BIN. File outputs from different devices. My first job then was to convert them to the same format, for a uniform dataset. I decided to convert them to GPX, firstly because it's closest to a standard and secondly because GPX files can be inspected in a text editor.
There's a free Linux command line tool that converts GPS tracks between different formats so I knocked up a quick script to convert the TCX, FIT and BIN files to GPX. That left me with about 1500 GPX files.
The plan is to organise them into folders by month, and perhaps by year as well.
The programming language Python has some nifty functions for interrogating GPX files so I'll use that. It's years since I coded in Python so I'll get ChatGPT to help.
Should keep me off the streets for a bit.
So: my idea is to to set the files up into different folder "views", so for example I might have a folder for each month since 2015, I might have folders representing rough ride distances and so on, using the data encoded in the GPX files. I can do this without duplicating the data around, using hard links.
Python has some nifty add-ons for the GPX format but it's years since I coded in that language and I'm not familiar with its GPX facilities. So that's where ChatGPT comes in. Could you please knock me up a utility to examine a GPX file and determine whether it contains a waypoint east of a particular longitude? I asked. Handy for finding longer rides that go into Lincolnshire. Two seconds later:
#!/usr/bin/env python3
import sys
import xml.etree.ElementTree as ET
if len(sys.argv) != 3:
print("Usage: gpx_east_of.py <longitude_threshold> <file.gpx>")
sys.exit(2)
threshold = float(sys.argv[1])
path = sys.argv[2]
try:
root = ET.parse(path).getroot()
except Exception:
sys.exit(1)
for el in root.iter():
if isinstance(el.tag, str) and el.tag.endswith(("trkpt", "rtept", "wpt")):
lon = el.attrib.get("lon")
if lon is not None and float(lon) > threshold:
sys.exit(0)
sys.exit(1)
Tested it, worked first time. Then I thought of a refinement, so I asked it for a Python utility that would determine whether a ride had passed through a particular point on the map. Every GPX waypoint has a latitude and longitude parameter, represented as a floating point number like this:
<trkpt lat="52.674767850" lon="-1.435571909">
I decided on a tolerance of 100 metres. GPS tracking devices are considerably more accurate than that, but they only record at intervals. 100m is more than good enough for this purpose anyway. Again, took a couple of seconds:
#!/usr/bin/env python3
import sys
import xml.etree.ElementTree as ET
if len(sys.argv) != 4:
print("Usage: gpx_near_30m.py <target_lat> <target_lon> <file.gpx>")
sys.exit(2)
target_lat = float(sys.argv[1])
target_lon = float(sys.argv[2])
path = sys.argv[3]
lat_tol = 0.0009
lon_tol = 0.0015
try:
root = ET.parse(path).getroot()
except Exception:
sys.exit(1)
for el in root.iter():
if isinstance(el.tag, str) and el.tag.endswith(("trkpt", "rtept", "wpt")):
lat = el.attrib.get("lat")
lon = el.attrib.get("lon")
if lat is not None and lon is not None:
lat = float(lat)
lon = float(lon)
if (abs(lat - target_lat) <= lat_tol and
abs(lon - target_lon) <= lon_tol):
sys.exit(0)
sys.exit(1)
You can see the 100m tolerance assigned as lat_tol and lon_tol. Longitude tolerance is actually a little bit more complicated than this, because the precise figure representing 100m differs depending on latitude. But for anywhere in England, that 0.0015 value will be close enough.
I decided, for my next coding project, to create a Bash, terminal version of the old game Battleships (https://en.wikipedia.org/wiki/Battleship_(game)), originally played using pencil and paper, occasionally sold as a plastic or wooden board game, but realised as a computer game in the late '70s.
It's basically grid-based so similar to Star Trek in some respects. But it involves some complex problem-solving, so it should keep me occupied for a few weeks.
So I've now written the function that populates a 10x10 grid with "ships" - One 5 squares in length, one length 4, two length 3, one length 2.
The algorithm I came up with is as follows:
For each ship:
Pick a square at random. Pick a direction at random (up, right, down, left).
Try to fit the ship in that direction from the starting square.
If it won't go (goes out of bounds or collides with another ship), try the next direction.
If all four directions are exhausted, add 9 to the square's "address" in the grid and try again (this loops round, I use modular arithmetic).
Because 9 is coprime with 100 then (as any fule kno) you're bound to visit all of the available squares eventually.
I tested this by populating a grid 400,000 times and there was never a situation in which a ship couldn't be fitted so I'm happy that it must necessarily always work.
I suspect that most programmers wouldn't use this method. A decent way to do it would be: pick a square at random and a direction at random. Attempt to fit the ship. Doesn't fit? pick another random square and direction; repeat until all ships are fitted. Nice and simple and that would work but I just have a dislike of "do random till it works" methods.
At the moment the output looks like this. Very crude; this is just a diagnostic output to demonstrate that it works.
. . . 5 . . . . . .
. . . 5 . . . . . .
. . . 5 . 4 . . . .
. . . 5 . 4 . . . .
. . . 5 . 4 . . . .
. . . . . 4 23 23 23 2
. 13 . . . . . . . 2
. 13 . . . . . . . .
. 13 . . . . . . . .
. . . . . . . . . .
Note that I'm using 23 and 13 for the 3-length ships, to distinguish them from each other. Using these numbers I can derive the length of the vessel using modulus 10. I could use a separate array for the lengths. Arguably that would be more elegant. But having learned to code on a ZX81 I'm stingy with memory.
The board will look something like this during play, although this is a mock-up. The ⬜ are where the player (or computer) has missed. The coloured squares are the player's ships. The ⬛⬛ is a dead ship, the 🔥🔥🔥 is a ship with three hits.
🟦🟦🟦🟦🟦🟦🟦🟦🟦🟦
🟦🟦🟦🟦🟦🟦🟦🟦🟦🟦
🟦🟦🟦🟦🟦🟦🟦🟦🟦🟦
🟦🟦🟦🟦⬜🟦🟦🟦🟦🟦
🟦🟦🟦🟦🟦🔥🔥🔥🟦🟦
🟦🟦⬜🟦🟦🟦🟦🟦🟦🟦
🟦🟦🟦🟦🟦🟦🟦🟦🟦🟦
🟦🟦🟦🟦⬜🟦⬛⬛🟦🟦
🟦🟦🟦🟦🟦🟦🟦🟦🟦🟦
🟦🟦🟦🟦🟦🟦🟦🟦🟦🟦
🟪🟪🟪🟪🟪🟦🟦🟦🟦🟦
🟦🟦🟦🟦🟦🟦🟦🟦⬜🟦
🟦🟦⬜🟦🟦🟦🟨🟦🟦🟦
🟦🟦🟦🟦🟦🟦🟨🟦🟦🟦
🟦🟦🟧🟧🟧🟦🟨🟦🟩🟦
🟦🟦🟦🟦🟦🟦🟨🟦🟩🟦
🟦🟦🟦⬜🟦🟦🟦🟦🟦🟦
🟦🟦🟦🟦🟦🟧🟧🟧🟦🟦
🟦🟦🟦🟦🟦🟦🟦🟦🟦🟦
🟦🟦🟦🟦🟦🟦🟦🟦🟦🟦
I spent hours on this yesterday, it went very well and I have a working prototype.
🟦🟦⬜🟦🟦🟦🟦🟦🟦🟦
🟦🟦🟦🟦⬜🟦🟦🟦🟦🟦
🟦🟦🟦🟦🟦🟦⬜🟦🟦🟦
🟦🟦🟦⬜🟦🟦🟦🟦⬜🟦
🟦🟦🟦⬛🟦🟦🟦🟦🟦🟦
🟦🟦🟦⬛🟦🟦🟦🟦🟦🟦
🟦🟦⬜⬛⬜⬜🟦⬜🟦🟦
🟦🟦🟦⬛🟦🟦🟦🟦🟦⬜
🟦🟦🟦🟦🟦🟦🟦⬜🟦🟦
🟦🟦🟦🟦⬜⬛⬛⬛🟦🟦
🟦⬜🟦🟦🟦🟩🟦⬜🟦🟦
🟦🟦🟦🟦🟦🟩⬜🟦🟦🟦
🟦🟦🟦⬜🟦🟩🟪🟪🟪🟪
🟦🟦🟦⬜🟦🟩🟦🟦🟦🟦
⬜🟦🟦⬜🟦🟩🟦⬜🟦🟦
🟦🟦🟦🟦🟦🟦🟦🟦⬜🟦
🟧🟧🟧🟦🟦🟦⬜🟦🟦⬜
🟦🟦🟨🟦🟦🟦🟦🟦⬜🟦
🟦⬜🟨🟦🟦🟦🟦⬜🟦🟦
🟦⬜🟦⬜⬜🟦⬜🟦🟦🟦
At the moment the computer just takes random potshots on its turn, it just finds a square it hasn't already tried and takes aim.
What I need to do is to introduce a sort of crude AI in which, after it hits a ship, it will take shots at adjacent squares, horizontally or vertically until it's sunk the player's ship, then go back to opportunistic hunting.
I think I'll also have a rule that the code can't place ships that touch each other, except diagonally. I also need a counter for ships sunk so it can work out when someone's won, although that's trivial.
I've written it in Bash so I'm calling it ..
(https://i.ibb.co/yBxMkMGY/bash-ships.avif)
I modified the code so that it only places ships that don't touch horizontally or vertically - and that actually makes the computer opponent logic much simpler, because if you have two hits in adjacent squares, they must be part of the same ship. This has been really absorbing to do. Got a feeling the whole thing will be complete in a few days.
So I need some sort of AI spectrum for the computer's logic. Obviously the player has to work it out for him/herself. There will be:
- just random hunting
- hit a ship, no idea of orientation or extent - shoot adjacent squares until I get a hit
- hit two squares, now I know the orientation - shoot an unhit square that's adjacent in the same orientation to a hit square until I register a "sunk". Then back to 1.
That 3rd idea makes it relatively simple I think - it doesn't have to work out "I've gone as far as I can to the right, now to move left". It just has to aim for unhit, adjacent squares on the same vertical or horizontal.
Quote from: Slim on April 12, 2026, 12:14:19 PMI've written it in Bash so I'm calling it ..
(https://i.ibb.co/yBxMkMGY/bash-ships.avif)
Liking the image especially seeing the playing field in the binoculars lenses.
Fingers are still a bit of an AI miss thoigh. Also: he has a pipe sticking out of his jaw?
(And I'd almost go as far as suggesting to do a play on the ships positioning with the SH in both words you have for the name)
I hadn't noticed that detail about the pipe! The watch looks off as well. I'll get it to have another go.
I spent ages on the code today, at times wanting to tear my hair out (but it's not long enough to get hold of).
I've settled on this idea for the "AI mode" for the computer:
Start off in "hunt" mode.
If you hit a ship, set to "find next" mode - go through the orthogonally adjacent squares until you hit a ship square. Then set the AI mode to "linefind".
In "linefind" mode the computer will walk along the line of hit squares until it finds a square that has not been tried, that's adjacent to a hit square. Then it will shoot at it (might be empty water, might be another part of the ship). It continues in this mode until the ship is sunk, then it returns to "hunt" mode.
Coded it up (was a bit painful to do). It works.
There is another possible improvement I can make. In "hunt" mode it can make stupid choices. It can shoot at a square that cannot possibly be part of a surviving ship. I'll look into fixing that.
I have, mainly, fixed that. It occurred to me that a simple expedient to prevent the computer from aiming at squares adjacent to ships that it's sunk is simply to silently mark them as already attempted. So I did that.
The computer player could still aim at squares in a set that doesn't have space for a remaining ship. I could potentially fix that. But I don't think it's worth it.
Still to do: allow the player to "redo" the player grid with a right-click and organise the win / lose counting / logic.
Quote from: Slim on April 09, 2026, 12:06:24 PMI decided, for my next coding project, to create a Bash, terminal version of the old game Battleships (https://en.wikipedia.org/wiki/Battleship_(game)), originally played using pencil and paper, occasionally sold as a plastic or wooden board game, but realised as a computer game in the late '70s.
It's basically grid-based so similar to Star Trek in some respects. But it involves some complex problem-solving, so it should keep me occupied for a few weeks.
Just finished this. Optimised the code, added some frame buffering, added a high score function and a shot counter, added the win / lose logic, added a "rearrange the fleet" function (right-click).
That was very absorbing but took less than two weeks. Need to think of something else now!
Also I need to document this one and post it up on GitHub.
(https://i.ibb.co/fdnhfft8/bash-ships.avif)
Uploaded to GitHub: https://github.com/StarShovel/bash-ships
I did think of including a "wide mode" version that would use a 10x12 grid, or even 10x14. But some of the code assumes single digit x&y co-ordinates and I'd have to have a proper rewrite. I don't think it's worth it.
Shared the URL on Reddit and got a reply asking me if I'd consider a human vs human version for players logged into the same machine!
Would need to devise a protocol for the two processes to synchronise, maybe using a named pipe. Each running instance would be the authority for its own fleet and return "hit", "miss", or "sunk", the latter including the co-ordinates for the whole ship.
For my next project I'm going to do something that's superficially simple: noughts & crosses.
The board will look like this (a mockup, I haven't started coding yet)
(https://i.ibb.co/RkwqZQVX/0x.png)
This uses a method called Minimax (https://en.wikipedia.org/wiki/Minimax) which I vaguely remember learning during my AI course. The basic idea is that the program recursively plays out every possible move, assuming both sides will make the best move each time.
For a 3x3 board this is not expensive, the program can explore all the possibilities very quickly and it will actually be impossible to beat; the best you can hope for is a draw.
For a 4x4 board, if you can imagine such a thing, the program would take years to explore the possible outcomes for the first few moves.
If the same strategy was adopted for chess, the "game tree" as it's known would take trillions of trillions of trillions times the age of the universe to bottom out.
I've got the algorithm done now. I had to learn the Minimax algorithm during the AI module of my degree course in 1988 or 1989, but apart from the basic idea I'd forgotten it. So I've more or less relearned it today.
As I mentioned in my last post, the computer can't actually lose if I implement it properly. But ..
your move 5
computer move: 0
your move 3
computer move: 1
your move 4
YOU WIN
Each square is represented by a number, 0-8. The mouse control and terminal graphics are not implemented yet. More importantly, clearly there was a bug.
Fortunately I tracked it down - there was a variable in a function that should have been local, that was global. The computer is unbeatable now, as it should be.
Interestingly: the computer takes about 10 seconds to make the first move. It has to examine thousands (40,320 worst case) of possible future versions of the board. But subsequent responses are much quicker - with only 6 empty places left, the very worst case is 720 boards.
So: I had an idea. There are only 9 possible human first moves of course, so instead of calculating the first response, just use a lookup table. I'll use the script in its current form to see what it does for each. Then I'll just put them in a table, hard-coded into the script.
There's no random element, the computer's move will be the same every time for the same first human move.
I've got the mouse control and the graphics sorted now.
(https://i.ibb.co/fVDgfC6N/oops.png)
What I also did was this: if the computer AI finds more than one move leading to a win, it picks one at random. Just to make it a bit less predictable.
This gives rise to the following behaviour. If it knows it can't be beaten, sometimes it will decline to play the winning move. In the above example, instead of placing its next ⭕ to complete the middle row (and win), it placed it in the middle of the bottom row.
It still can't lose. It doesn't cost anything from the computer's point of view; it's not "wrong". But it seems odd. Almost like the computer's trolling you.
It turns out that the minimax method, in its raw form, is in a way very inefficient - in that it will analyse the same board multiple times, even in the same move - because there are sometimes several different ways to arrive at it.
When it is evaluating the "game tree" for a particular sequence of moves, it will recursively look possibly thousands of moves into the future to score the board. Then when it backs up and evaluates the branch for an alternative sequence, it forgets the scores for boards it's seen before. It will blindly re-calculate the entire future tree again.
There's an easy fix for this though, which I implemented yesterday. I set up an associative array as a cache. So when the board scoring routine assesses a score for a board embodying a particular potential move, it saves the score for that board. A board is represented as a simple string of digits with 0 for an empty space, 1 for the human's mark (an X) and 9 for the computer's mark (a 0). Like 191999011, for example.
Because the game is actually pretty boring - the best the human can do is draw - I also set up an optional "compromised" mode, in which the computer AI is only allowed to descend two levels of recursion to analyse a board. In practice this allows the human to win occasionally.
It may be that the caching defeats the first computer move delay, and I don't need to set up a lookup for its first move. Will test that.
In fact - it does, so I've stripped out the code that works out if it's the computers first go and selects a first move, and that's made the code a lot more compact.
This is something I find fascinating - I've done some diagnostics with updates to a log file, and the cache never gets updated after the computer's first move. That's because the first time the Minimax algorithm runs, it explores every single legal combination of moves that can happen from that moment until the end of the game. After that, the cache is complete.
Well, it's finished now. Will document it and publish it on Github.
(https://i.ibb.co/tkhQjcV/bashcover.avif)
Love the price which must seem so alien, even to someone in their fifties. That makes me shudder.
I don't miss all that pounds and shillings nonsense, but I certainly do remember it.
Blows my mind that a "ten bob note" was what we now call 50p.
(https://i.ibb.co/CK8Ykfgv/tenbob.avif)
Quote from: Slim on May 29, 2026, 01:29:35 PMI don't miss all that pounds and shillings nonsense, but I certainly do remember it.
Blows my mind that a "ten bob note" was what we now call 50p.
(https://i.ibb.co/CK8Ykfgv/tenbob.avif)
These were such a wonderful sight when opening birthday cards. Around 1974 our family visited the Isle of Man. I was really surprised to find they used 50 pence notes.
Finished the noughts & crosses game a couple of weeks ago, uploaded to GitHub now https://github.com/StarShovel/bash-noughts