John H. Conway's Game of Life for the 3k expanded VIC

[Mike]

Oh! See, back in my day we called that an "embiggened screen."

I thought the meaning of "overscan" should have been clear from the context but so be it.

But seriously, it's a good idea, because for the regular Game of Life rules, there's an enormous difference between 22 and 48 cells in width. You need around 40 cells in width (maybe a little less?) for the smallest functioning gun.

The Gosper glider gun (which is the first one found) fits into a 36x9 bounding box. The Simkin glider gun (which is a fairly recent find) fits into a 33x14 box.

Next thing then though is the capability to see the complete evolution of the R-pentomino. That one needs over 1000 generations to stablize, it sends out six gliders and the stable pattern that remains at the end spans 109x52 pixels - not counting some extra space needed during its evolution. That one brings a text mode GOL implementation quickly to its limits.

The R-pentomino is the default example pattern supplied with VIC Life and it is loaded when you press the [L] key.

[chysn]

Next thing then though is the capability to see the complete evolution of the R-pentomino. That one needs over 1000 generations to stablize, it sends out six gliders and the stable pattern that remains at the end spans 109x52 pixels - not counting some extra space needed during its evolution. That one brings a text mode GOL implementation quickly to its limits.

The R-pentomino is the default example pattern supplied with VIC Life and it is loaded when you press the [L] key.

I just watched that pattern through with Minigrafik. One of the things I like about CA is watching those kinds of things unfold. And I also like throwing a single extra cell into the works at some point to see what happens. The tragedy of GoL is that, unlike real life, it's not very fault-tolerant at any level of complexity.

[huffelduff]

Hi there Michael, Chysn

I tune in to Life Wiki somewhat more regularly, and it is astonishing what the GOL community has found/constructed in the last years, like oblique spaceships, unit life cells and universal constructors. The 160x192 resolution of my GOL implementation is just barely sufficient to see the smallest of those newly found patterns running on the VIC-20.

The universal constructor idea is absolutely breathtaking. If self replication can be done in simulation, why not in real life chemically? And then nanobots say hello.

I just wrote this. It seems to work okay, and I'll look for optimizations. But the idea is

Soooooooo instead of carrying on with GOL I used the routine to test some images with chunkygraphics. The results are somewhat as expected. It looks a bit old even for my dated tastes. But then again as you indicated, the purpose you wrote it for was for your new GOL implementation and not Adventure games. I've studied the code and I also wrote my own routine to get a grasp of the decoding involved, although I still have a bug with the chunk delete. I will post my inefficient code when I'm done.

Here's the code for the image draw (just for giggles and howls of laughter). In the attached demo program I used a C64 sprite editor and then stitched the data together. It displays images of 46 x 42 and not 46 x 44. The reason for this is it uses 6 bytes (48 pixels) horizontally and if one multiplies that by 44 rows, one gets 264. Bleh, outside a single byte counter range, but 6 x 42 = 252 which fits nicely. Also means that a 2 x 2 sprite block for design works well.

I had to modify your code slightly. I store X and Y in the beginning of the subroutine and restore both at the end.

Excuse the weirdo syntax style below, I use kick assembler.

Greetings

Code: Select all

sub_chunkyscreen_loader:
		//46 x 42 Chunky graphics screen print
		//unoptomized of course - any less optimized and I could have written this in Turbo Logo
		//Using; kick assembler (kickass) and its syntactic sugar
		//$FB and $FC contain the address of the image data
		ldy #0
		stx var_szcs_loader_bitcount
		stx var_szcs_loader_bytecount
				
!:		sty var_szcs_row
		ldy var_szcs_loader_bytecount		
		lda ($FB),y; sta var_szcs_current_byte
		ldy var_szcs_row
		
!:		lda var_szcs_current_byte; and #%10000000; cmp #128; bne !+; sec; jmp !++
!:		clc
!:		ldx var_szcs_column
		jsr ChunkyPlot
!:		lda var_szcs_current_byte; asl; sta var_szcs_current_byte 
		
		inc var_szcs_column; lda var_szcs_column; cmp #44; beq !+
		inc var_szcs_loader_bitcount; lda var_szcs_loader_bitcount; cmp #8; bne !----
		lda #0
		sta var_szcs_loader_bitcount
		inc	var_szcs_loader_bytecount
		jmp !-----
!:		lda #0
		sta var_szcs_column
		sta var_szcs_loader_bitcount
		inc var_szcs_loader_bytecount
		
		iny; cpy #42; beq !+
		jmp !------
		
!:		rts
var_szcs_loader_bitcount:	.byte	0
var_szcs_loader_bytecount:	.byte	0
var_szcs_current_byte:		.byte	0
var_szcs_column:			.byte	0
var_szcs_row:				.byte	0

[huffelduff]

I also implemented a "lowres" graphics mode in V-Forth

Hi srowe,

I was reading up a bit on Forth and I see its entirely stack based.
Do system stack space limitations cause any problems?
I see Forth can self compile. That's very rare indeed.
Is Forth your language of choice?

Greets

[srowe]

I was reading up a bit on Forth and I see its entirely stack based.
Do system stack space limitations cause any problems?

Having to manipulate parameters on the stack forces you to modularize. You can't juggle more than 4 parameters without spending too much time shuffling them around. You could view this as a limitation but it's actually one of the principles of Forth, break the problem down to manageable chunks. You become accustom to designing words (functions) such that the parameters are in the optimal order for the implementation. Forth expects you to make choices like this rather than making the runtime more complex (and therefore inefficient).

I see Forth can self compile. That's very rare indeed.

That's one of the things that I love about it. It allows you to create domain-specific languages, tuning it to the problem you want to solve rather than making you fit the problem to the language.

Is Forth your language of choice?

Only a hobby really, I had fun creating V-Forth but only limited success in using it for problem-solving. You can't easily tackle situations where, say, you would use a structure/class in another programming language. I did try to implement Game of Life, but it's rather slow (I think the runtime of DO...LOOPs is the problem). Perhaps you can suggest some optimizations?

Code: Select all

22 constant maxx
23 constant maxy

variable journal

create rows
0 ,  maxx ,  maxx 2* ,  maxx 3 * ,  maxx 4 * ,  maxx 5 * ,  maxx 6 * ,  maxx 7 * ,
maxx 8 * ,  maxx 9 * ,  maxx 10 * ,  maxx 11 * ,  maxx 12 * ,  maxx 13 * ,  maxx 14 * ,  maxx 15 * ,
maxx 16 * ,  maxx 17 * ,  maxx 18 * ,  maxx 19 * ,  maxx 20 * ,  maxx 21 * ,  maxx 22 * ,

: getbad   ( x y  --  baddr )
    2*  rows  +  @  +  4096  +  ;

: xplot   ( x y  --  )
    getbad  dup
    c@  128  xor  128  and  32  or  swap  c!  ;

: setup
    147  emit  37888  512  6  fill
    3 2 xplot  3 3 xplot  3 4 xplot  2 4 xplot  1 3 xplot
    19 18 xplot  19 19 xplot  19 20 xplot  20 18 xplot  21 19 xplot
    11 10 xplot  12 10 xplot  13 10 xplot
;

: pixelset?   ( x y  --  0/1 )
    2dup  maxy  u<
    swap  maxx  u<  and  if   ( in range )
	getbad  c@  127  >  1  and
    else  2drop  0
    then  ;

variable ncount

: neighbours   ( x y  --  n )
    0  ncount  !
    over  1-  over  1-  pixelset?  ncount  +!
    over  over  1-  pixelset?  ncount  +!
    over  1+  over  1-  pixelset?  ncount  +!
    over  1-  over  pixelset?  ncount  +!
    over  1+  over  pixelset?  ncount  +!
    over  1-  over  1+  pixelset?  ncount  +!
    over  1+  over  1+  pixelset?  ncount  +!
    1+  pixelset?  ncount  +!
    ncount  @  ;

: apply-journal
    pad
    begin
	dup  journal  @  =  not  while
	    dup  1+  swap  c@   ( get Y )
	    over  1+  rot  c@   ( get X )
	    rot  xplot
    repeat
    drop  ;

: generation
    pad  journal  !
    maxy  0  do
	maxx  0  do
	    i  j  neighbours
	    i  j  pixelset?
	    if  ( cell is alive )
		dup  2  =  swap  3  =  or  not
	    else  ( cell is dead )
		3  =
	    then
	    if  ( invert cell state, add to journal )
		j  journal  @  c!  1  journal  +!
		i  journal  @  c!  1  journal  +!
	    then
	loop
    loop  ;

: life
    setup
    begin
	generation
	apply-journal
    ?terminal  until  ;

[huffelduff]

Having to manipulate parameters on the stack forces you to modularize. ...You become accustom to designing words (functions)

I came accross this book called: Functional Programming in Javascript by Luis Atencio
The book is really about functional orientation perhaps more even than Javascript.
It really impressed me because the 'functional orientation' methodology is I believe the future of code in this here universe.
This is such a bold statement that I have to leave it there.... hanging.... pregnant.

Perhaps you can suggest some optimizations?

I think the master blasters in this field are Michael and chysn.
Michael had one particular optimization that he suggested: "... the 'fine' counting algorithm is only thrown at bitmap bytes that might contain cells in the next generation, and not the whole bitmap."

My own version is currently a brute force slow coach.

I have one particularly nasty optimization that occurred to me that maaaay make your code fast I think.
You're may not like it. Turn your Forth machine (stack machine) into a LISP machine (pointer machine).
In other words, don't calculate anything. Do a pointer lookup with lookup tables.
Every cell is a 3 x 3 grid with the cell under investigation in the middle.
Combinatronics says the amount of combinations that exist is given by the number of variants to the power of the number of cells = k^n = 2 ^ 9 = 512 combinations, therefore with 512 results.
You can actually split it into two tables. Is the cell under investigation on or off to start with? Then just do a single byte lookup on one of the two tables (256 bytes each).

Table 1: Cell under investigation off
256 entries with each 8 bits representing the state of the remaining cells

Table 2: Cell under investigation on
256 entries with each 8 bits representing the state of the remaining cells

Each output lookup is a single byte which has one bit of information which says: For this particular combination on this (input cell on or off) table, the cell under investigation is on or off as a result.

Well that's all I got.

Greetings

p.s I've edited this post about six times. I'm leaving it alone now.

[huffelduff]

Hi there srowe,

It is amazing to me how I can write a response, correct it multiple times, and yet still manage to omit critical information.
So why a pointer lookup instead of a normal lookup?
Three words: Multiple rule sets
Not only will a lookup speed up the code but a pointer lookup will allow for multiple automata rule bases to be implemented easily and make them fast.
So one can have the default and then other multiple experimental types (depending on the amount of machine memory available)
This can also allow for a user automata designer section.
So the Lisp machine only comes into its own when you want multiple rule-sets, but I think that is a very powerful feature.
It will also allow the program to have a cool thing where before the simulation starts the program displays: Preparing rule-set for execution...
(while the program builds the lookup tables)

So why does my version use 3k expansion when I don't even use lookups?
Well I implemented a music tracker engine which I recently wrote and combined it with an fx section.
You can enable the tune on the design page. You can also enable audio fx at the same time.
So I actually used the whole buffalo

Greetings

[chysn]

Perhaps you can suggest some optimizations?

I think the master blasters in this field are Michael and chysn.

Not me. I've only ever done it using a brute-force "onion skin" approach, involving two arrays. In 6502, these arrays would likely be replaced by screen images. But no, I don't treat the far-flung unset cells any different than the ones with lots of action. I don't have any GoLs planned at the moment, but I'd be eager to try out some new approaches.

[srowe]

I think the key flaw with my implementation is computing the neighbours every generation from the screen characters. I'll experiment with storing the neighbour count separately, which will take an acceptable amount of space for 22x23 but won't really work for a 176x160 field.

[Mike]

I toyed around a bit with the OP implementation and came up with this oscillator:



It is composed of a Blocker (period 8) and a Fumarole (period 5). As 5 and 8 are mutually prime (i.e., they have no common divisor other than 1), the resulting period is 40.

Normally suchalike combinations of oscillators to yield higher periods are considered trivial, but this one has a single cell that is only alive in 1 generation and dead in the other 39 ones. Can you spot it?

Cheers,

Michael

[chysn]

It wasn't my first guess, but I found it!

[Mike]

It wasn't my first guess, but I found it!

O.K. then - I will disclose the secret tomorrow.

In the meantime, I transferred the oscillator pattern with my "new" pattern editor to VIC Life:



Here's the resulting DATA file (download) which replaces the original DATA file of VIC Life.

While it is possible to draw the pattern within VIC Life itself, using the big cousin is much more comfortable (especially considering the 4x zoomed display and cursor co-ordinate values in the status window).

[Vic20-Ian]

This was coded for the C64 but I thought it worthy to share here as the cellular automata and music link might be interesting to explore on the Vic20.

The 256 byte source is in the post.

https://hackaday.com/2021/05/19/linus-a ... 256-bytes/

I hope to see some of the interesting work in this thread entered in the Things we want to see / hear development competition.

viewtopic.php?f=1&t=10130

[Mike]

...

O.K. then - I will disclose the secret tomorrow.

With the pattern file DATA loaded into the editor, X=17 and Y=15.

[chysn]

With the pattern file DATA loaded into the editor, X=17 and Y=15.

Yep, that's the way I saw it.

This was coded for the C64 but I thought it worthy to share here as the cellular automata and music link might be interesting to explore on the Vic20.

I've struggled a bit (see my first post on this topic) to find a good way to combine CA with non-visual structures, like music. There are many potential avenues, but few satisfying ones. But I haven't given up.

The demo that you shared uses a shift register. My first exposure to shift register-based generative music came from Tom Whitwell's Turing Machine, a hardware Eurorack synthesizer module. I'm not sure if Tom invented the idea, or simply popularized it in hardware. A year and a half ago, I posted BASIC and ML code (viewtopic.php?f=2&t=9434) demonstrating the technique, which I later used in all of my unexpanded VIC games.

It's another way of generating complexity from a simple set of rules. In this case, you get the chance to generate a credible game soundtrack with a few dozen bytes.

If I were to do another GoL program, the GoL would be a game play element, rather than CA for its own sake. It would be kind of like Forbidden Planet, with a GoL-inspired monster trying to break down a barrier between you and it. You can place cells to disrupt or disperse the monster's life force. Occasionally, the monster will hurl gliders at your wall. It could be fun.