(Conway's) Life in BASIC

Discussions
1

In collaboration with @EdS I’ve devised a version of Conway’s Game of Life, which will work both on Commodore 8-bits and on the Beeb (BBC Micro). – You’ve just to set the config variable in the very first line appropriately.

Mind that there are two rather suitable online emulators for those machines,
for a PET 2001: Commodore PET 2001
and “JSBeeb” for the BBC Micro: https://bbc.godbolt.org/

On the emulated PET, you may simply drop a BASIC text file onto the emulated screen to import a source file, JSBeeb supports specially crafted data-URLs (as does the PET emulator).

To craft such links, I’ve provided a tool for each of those emulators:
For the PET: PET 2001 Link Console
and for JSBeeb: Beeb Link Console

And now for the script:

10 BB=0 : REM CONFIG, 1=BEEB, 0=COMMODORE
20 IF BB=0 THEN PRINTCHR$(147);CHR$(18);:GOTO 30
25 MODE 7
30 PRINT"  CONWAY'S GAME OF LIFE  "
40 PRINT:PRINT"IN MEMORIAM JOHN H CONWAY"
50 PRINT"26 DEC 1937 - 11 APR 2020":PRINT
60 INPUT"WIDTH, HEIGHT (EG, 8,8)";W,H
70 IF W<4 THEN W=4
80 IF W>39 THEN W=39
90 IF H<4 THEN H=4
100 IF H>24 THEN H=24
110 G=0:A=0:P=0:W=W+1:H=H+1:D1=W+1:D2=W-1:K=0:NG=1:XM=W-1:YM=W*H-W:N=0
120 IF BB=0 THEN 140
130 CS=12:CH=30:CO=79-32:R=1:GOTO150
140 CS=147:CH=19:CO=209-32:R=0
150 PRINT:PRINT"PROBABILITY OF INITIAL POPULATION:":INPUT"(0>P<1)";P
160 IF P<=0 OR P>=1 THEN P=0.5
170 DIM M%(1,W*H+W):PRINTCHR$(CS);
180 FORY=W TOYM STEPW:FORX=1TOXM:M%(0,Y+X)=RND(R)<P:NEXT:NEXT
190 PRINTCHR$(CH);"GEN.:";N
200 FORY=W TOYM STEPW:FORX=1TOXM:PRINTCHR$(32-M%(G,Y+X)*CO);:NEXT:PRINT:NEXT
210 FORY=W TOYM STEPW:FORX=1TOXM:A=Y+X
220 K=M%(G,A-D1)+M%(G,A-W)+M%(G,A-D2)+M%(G,A-1)+M%(G,A+1)
230 K=K+M%(G,A+D2)+M%(G,A+W)+M%(G,A+D1):M%(NG,A)=(K=-3)OR(K=-2 ANDM%(G,A)=-1)
240 NEXT:NEXT:G=NG:NG=1-G:N=N+1:GOTO190

Annotations

Commodore BASIC and BBC BASIC use -1 for true and 0 for false.
Thus, CHR$(32-V*CO) will print either a space (CHR$(32)) or a disk character (CHR$(209)) on Commodore machines, and an “O” on the Beeb, depending on the boolean value in V.

The script uses extra rows and columns at the very edges so that the 3x3 kernel can iterate over the actual data:

00000000
0DDDDDD0
0DDDDDD0
0DDDDDD0
0DDDDDD0
00000000

Variables used:
W, H … width, height
YX, XM … upper boundary for loops
P … threshold for initial population (0 > P < 1)
M%(G, A) … field by generations (0,1) and rows x cols
N … count of generations processed (total iterations)
G … current generation (0,1)
NG … next generation (0,1)
K … sum of living neighboring cells
D1, `D2’ … offsets row + 1 cell, row - 1 cell

Since Commodore BASIC supports arrays only in up to 2 dimensions, we calculate our own indices (offsets) into M%:

K =
M%(G,A-D1) + M%(G,A-W) + M%(G,A-D2) +
M%(G,A- 1) +             M%(G,A+1)  +
M%(G,A+D2) + M%(G,A+W) + M%(G,A+D1)

which is the same as in 3D:

K =
M%(G,Y-1,X-1) + M%(G,Y-1,X) + M%(G,Y-1,X+1) +
M%(G,Y  ,X-1) +               M%(G,Y  ,X+1) +
M%(G,Y+1,X-1) + M%(G,Y+1,X) + M%(G,Y+1,X+1)

Cross-Platform Related:
BP … config flag: 1=Beeb, 0=Commodore BASIC
CS … CHR$() code for clear screen
CH… CHR$() code for cursor home
CO … CHR$() code offset to add to 32 for the character of a living cell
R … parameter for RND() to get a value 0 > v < 1

Ideas:
Can you alter the script so that it wraps?
(Hint, you may have to use modular additions inside the kernel, where there are currently D1, D2, W added or subtracted to the base index A. If you want too keep the script compatible, mind that there is no MOD() function in Commodore BASIC.)

Post your ideas and/or your own versions!

3 Likes
2

Don’t use % variables, unless you intend to compile in Blitz basic or something like that. Otherwise, they’re too slow. Microsoft BASIC always does math by first converting to float, and converting back afterward - even for compares and even for bitwise math.

The only reasons to use % types are to save memory with a large int array, and some bizarre obscure cases … like you have some particular reason to want to avoid lots of explicit int conversions. Or, in my case, I am doing bitmap graphics on the C64 and I need a fast way to clear 8K of RAM all to zeros. Turns out the fastest way to do that in BASIC is to initialize a huge array of % int (I make the array big enough to ensure 8192…16191 get cleared out.) Then, I set the color map to point to 1024…2023 - in other words, the default character screen. Printing CLR HOME thus sets all 1000 screen bytes to 32 - or red-on-black. This sets up a clear HIRES screen in a couple seconds, as opposed to a laborious FOR loop which would take minutes.

But like … that’s the sort of bizarre obscure reason for using % ints which I’m talking about. (Since my C64 is a C128, and it includes graphics commands … no need for that bizarre hack, for me anymore.)

Anyway, I would definitely advise against using AND to implement wraparound torus effects. It would just be too slow. Also, my experience with fiddling with Game Of Life implimentations is that wrap-around is generally NOT desirable. Most of the time, a simple “blank” edge-of-the-world will inoffensively absorb gliders - turning them into squares. As such, any infinite-plane pattern which doesn’t touch the edges will usually work fine. But with wraparound, those gliders will wrap around and collide with the evolving pattern. This will inevitably spoil the pattern.

3

(Moved your comment to this new thread, hope that’s OK!)

I’m quite tempted to try to make the world a torus - it’s imperfect, for sure, but then so is a boundary, so it may be a matter of taste. It seems both options have their adherents.

Any idea if the 2D array is costly?

1 Like
4

Regarding integer variables, while integers are generally slower, M% is used here to save RAM. (Mind that there are just 4K on the very first PET 2001 and 8K may be expected as a standard.)
A subscripted variable (array) uses 5 bytes per subscript for floating point variables and just 2 bytes for integers. Also, logical values happen to be integers as well.

Having tested both, the trade-off for using an integer array here isn’t really noticeable.

Edit: However, we may argue that, while we’re at it, K should be rather K%, as well.

5

I don’t know exactly how costly a 2D array is (in Commodore Microsoft BASIC), but I would never use one unless I had a compelling reason. The processing of the extra index alone would be a performance drag I’d rather avoid by using a raster scanned single dimension array.

Also, for this particular application I’d pack 8 cells per array element - but that’s because BASIC is just so slow and I’m used to writing weird optimized implementations of Game of Life in tight RAM (unexpanded VIC-20 in particular). Floats can store every value between 0 and 2^32-1, so essentially I’ve got 32 bit unsigned int capability. At 4 bits per cell, that’s good enough to store values from 0…15 in each cell. In other words, it’s possible to sum up stuff in parallel, 8 cells at a time. You can sum up values in parallel so instead of 9 sums, you only do 5 sums and one subtraction … only about 6/8 operations per cell. Readout is more complex, though, since you can’t rely upon bitwise math up to 32 bits. It only allows AND up to 32767, so readout is done 3 cells at a time - requiring division by 4096^2 and 4096 to shift by the necessary amounts.

Actually, calculations are done on only 6 cells at a time, rather than 8, because the edges are needed for proper calculations of the neighbor cells.

Anyway, the resulting algorithm is stupidly complex and it’s only worth bothering with if you have a weird fixation on optimizing this sort of thing. I was just really obsessed with getting this stuff to fit in an unexpanded VIC-20 for purposes of an actual game (LifeCommand … which I never got a chance to implement on the VIC-20 due to life happenings, but I did return to the concept to implement it in Javascript.)

1 Like
6

I still have half a mind to apply a couple of ideas to this code. Thanks for writing and sharing it @NoLand. In fact I believe with some mild abuse of convention we can make a single version which works for both Beeb and PET.

7

Regarding arrays: mind that array subscripts are done in machine language and integer math. In MS BASIC, an array variable stores both the subscript length and dimensions as binary values, so determining a subscript is probably faster than looking up a single variable (especially, if there’s just a single array variable defined) and next to certainly faster than using floating point math for computing addresses. In the case of integer vars, a subscript offset may be determined just by a single shift, since the length of a subscript is 2 bytes.

Some details may be found here, <Now Go Bang!> BASIC Variables and Strings - with Commodore

8

It still has to waste time actually reading and converting the second subscript value. And generally it is not necessary to compute addresses using two variables.

In particular, you can do offsets both dimensions at the same time. For example, instead of doing CELL(x+1, y+1), you do CELL(xy+65) (where 65 = 1 + 1*64). So you halve the number of variable lookups, and halve the number of adds.

9

But then, you’d actually duplicate the kernel code, since there’s no way to assign or alias an array in BASIC. Or, otherwise, you’d have to add an array copy, which will be costlier than anything saved by using a single dimensional array.

And, as for alternatives, PEEK and POKE are also rather slow. (I think, PRINTing a character is actually faster than directly POKEing a screen code into video RAM.)

10

I have no idea what you mean by duplicating the kernel code. I’m just talking about using a one dimensional array rather than a two dimensional array.

Think of it this way. If you were accessing screen memory, you could either do it with two position variables (x,y) or by a single position variable (xy). In the former case, x ranges from 0 to 39 while y ranges from 0 to 24. In the latter case, xy ranges from 0 to 999. For most practical purposes, the latter is more efficient.

11

But, for Life, you have to manage two fields at once. One for the old generation, currently displayed, and one for the new one, which you are computing by the kernel/sliding window. And both switch place on each iteration. (As here, where we compute G(1) based on G(0) and then G(0) based on G(1), and so on.)

Edit: You could probably do it by multiplying the array length by 2 and setting up appropriate base addresses. (Like in G0=0 and G1=Width*Height and switching those.) But, for our purpose, readability would suffer quite a bit, since we’re already compressing X and Y dimensions into a single one. However, it may be an optimization worthwhile. Remains to be tested.

12

I think I can see a way not to manage two fields at once…

… but we might all be better off showing code for what we mean, rather than describing it. In other words, let’s not argue. If we can, let’s create.

13

So, here’s a version using a single dimensional array.

10 BB=0 : REM CONFIG, 1=BEEB, 0=COMMODORE
20 IF BB=0 THEN PRINTCHR$(147);CHR$(18);:GOTO 30
25 MODE 7
30 PRINT"  CONWAY'S GAME OF LIFE  "
40 PRINT:PRINT"IN MEMORIAM JOHN H CONWAY"
50 PRINT"26 DEC 1937 - 11 APR 2020":PRINT
60 INPUT"WIDTH, HEIGHT (EG, 8,8)";W,H
70 IF W<4 THEN W=4
80 IF W>39 THEN W=39
90 IF H<4 THEN H=4
100 IF H>24 THEN H=24
110 G=0:A=0:P=0:W=W+1:H=H+1:D1=W+1:D2=W-1:K=0:DG=W*H+W:NG=DG
120 XM=W-1:YM=W*H-W:N=0:IF BB=0 THEN 140
130 CS=12:CH=30:CO=79-32:R=1:GOTO150
140 CS=147:CH=19:CO=209-32:R=0
150 PRINT:PRINT"PROBABILITY OF INITIAL POPULATION:":INPUT"(0>P<1)";P
160 IF P<=0 OR P>=1 THEN P=0.5
170 DIM M%(DG+DG):PRINTCHR$(CS);
180 FORY=W TOYM STEPW:FORX=1TOXM:M%(G+Y+X)=RND(R)<P:NEXT:NEXT
190 PRINTCHR$(CH);"GEN.:";N
200 FORY=W TOYM STEPW:FORX=1TOXM:PRINTCHR$(32-M%(G+Y+X)*CO);:NEXT:PRINT:NEXT
210 FORY=W TOYM STEPW:FORX=1TOXM:A=G+Y+X
220 K=M%(A-D1)+M%(A-W)+M%(A-D2)+M%(A-1)+M%(A+1)+M%(A+D2)+M%(A+W)+M%(A+D1)
230 M%(NG+Y+X)=(K=-3)OR(K=-2 ANDM%(A)=-1)
240 NEXT:NEXT:G=NG:NG=DG-G:N=N+1:GOTO190

(However, the improvement in runtime isn’t impressive, at least on the PET. – I’d say, about 10%.)

14

@IsaacKuo Ah, I see, your comment was moved here by moderation and not a comment on the particular script. Sorry for any irritations.

15

Oh okay - I see why there was a lot of confusions. Sorry, I didn’t really look at your code carefully - I was originally commenting on a different discussion thread, as you noted.

I generally do NOT double-buffer Game Of Life implementations. Besides it consuming precious memory, it’s just not necessary once you do some minor optimizations. I’m so used to not bothering with double buffering, it didn’t even occur to me to think about that.

Basically, the simplest optimization is to keep a running tally of totals rather than restarting calculations from scratch each cell. So, you store three lines of 3 neighbor totals, which is generally much less memory than a full second buffer. By the time you start overwriting cells, you’ve already stored the relevant line’s totals (because they were required to calculate the previous line of cells).

This is always one of the first optimizations I implement, so I never even bother with double buffering. I … simply forgot it was a thing at all, in Game of Life.

2 Likes