Slim's Geek Gazette

[Slim]

This is my own version. Captured the screen output and uploaded it to YouTube.

[Slim]

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:

Code Select Expand

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.

[Slim]

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

[Slim]

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:

Code Select Expand

#!/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):

Code Select Expand

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.

[Slim]

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 algorithm.

There's an even better way to do this, 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.

[Slim]

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.

[Slim]

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.

[Slim]

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.

[Slim]

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.

[Slim]

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!

Highslide Image Viewer

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.

Highslide Image Viewer

I'll be looking into setting up a PS2 or PS1 emulator as well.

[Slim]

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.

Life got a mention on University Challenge this evening.

[Slim]

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.

Highslide Image Viewer

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.

[Slim]

I changed the design of the above, to this:

Highslide Image Viewer

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.

[Slim]

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

Highslide Image Viewer

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

Notes

Please 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.

Installation

Download the script directly:

wget https://github.com/StarShovel/bash-trek-tng/raw/main/bash-trek-tng.sh
chmod +x bash-trek-tng.sh

Alternatively, clone the full repository:

git clone https://github.com/StarShovel/bash-trek-tng.git
cd bash-trek-tng


Usage

Run the game from the command line:

./bash-trek-tng.sh

It'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.


Instructions

Bash 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 Interface

Bash Trek: TNG uses a clickable command bar to invoke each of the above commands:

Highslide Image Viewer

.. 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:

Highslide Image Viewer

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.

Highslide Image Viewer

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 Events

On 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.

Screenshots

In 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.

Highslide Image Viewer

Highslide Image Viewer

Mission Deadline

You must complete your mission to eradicate the Klingon presence in the galaxy by stardate 1314.1.


Game Conclusion

The game ends with one of five possible outcomes:

Mission Success

• All Klingons destroyed

Mission Failure

• Player resigns
• Enterprise destroyed
• Failure to complete mission by specified stardate
• Energy supply (including shields) completely depleted

License

Bash 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.

[Slim]

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.

Highslide Image Viewer

So I started coding it last night, and so far it looks like this:

Highslide Image Viewer

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.

Highslide Image Viewer