Conway's Game of Life for Atom, Beeb, Elk?

bbc/electron apps, languages, utils, educational progs, demos + more
litwr
Posts: 245
Joined: Sun Jun 12, 2016 9:44 am
Contact:

Re: Conway's Game of Life for Atom, Beeb, Elk?

Post by litwr »

Wow! List Life is the impossible fantastic for 8-bit world! I have to express my sincere admiration. :)
BTW Xlife-8 runs r-pentamino for 1100 generations during about 70 s (6502 at 1.76 MHz in Commodore+4).
User avatar
hoglet
Posts: 10709
Joined: Sat Oct 13, 2012 7:21 pm
Location: Bristol
Contact:

Re: Conway's Game of Life for Atom, Beeb, Elk?

Post by hoglet »

litwr wrote:Wow! List Life is the impossible fantastic for 8-bit world! I have to express my sincere admiration. :)
BTW Xlife-8 runs r-pentamino for 1100 generations during about 70 s (6502 at 1.76 MHz in Commodore+4).
Thank you for the compliment.

I was looking for a fun program that would really show off the 225MHz 6502 Core in the PiTubeDirect second processor, and Life has always held a great fascination for me (and Ed).

If you scale everything to 3MHz, then you have:
- List Life runs r-Pentomino for 1100 generations in 161s
- Life88 (from Ed's friend) runs r-Pentomino for 1100 generations in 80s
- Xlife-8 runs r-Pentomino for 1100 generations in 41s (estimated)

So I think Xlife-8 is still the fastest per MHz.

One question I had about your Xlife-8 implementation - is the universe limited to the visible screen (e.g. 160x192), or can it be much larger?

Dave
User avatar
jms2
Posts: 3133
Joined: Mon Jan 08, 2007 6:38 am
Location: Derby, UK
Contact:

Re: Conway's Game of Life for Atom, Beeb, Elk?

Post by jms2 »

I've just got ListLife running on the Pi second processor. It's really amazing! :D As you say, it's the ideal way to show off the power of a second processor - graphics produced by computation, rather than by lots of design work.

It occurs to me that it would be helpful to encourage other "Tube authors" by publishing some basic host and parasite routines to pass bytes of data in an efficient way aimed at plotting graphics - in other words, not the official routines, but ones optimised for speed to suit games.
litwr
Posts: 245
Joined: Sun Jun 12, 2016 9:44 am
Contact:

Re: Conway's Game of Life for Atom, Beeb, Elk?

Post by litwr »

> I tried Rabbits (17331 generations) and found that Atom Life incorrectly stabilizes after 4200 generations.

Rabbits occupy about 8000x8000 square after 17331 generations. AtomLife or Xlife-8 can't keep a so big pattern. I've attached two pictures of Rabbits pattern at 17331 generation. They were made by Xlife in the History mode. The first picture shows the center pattern zoomed in 2 times. You may see the initial rabbits location in red. The second picture shows all bounding box. It is zoomed out 16 times. You may see 40 emitted gliders on it.
rabbits-17331.gif
rabbits-17331-16.gif
Xlife results with screen on (6502 @1.12 MHz) is not very fast. It evolves r-pentamino to 1100 generation during about 122 seconds. The previous results were for screen off and a bit unfair. However I had made several tests with listlife and atomlife using B-Em with 4 MHz 2nd processor. They show that r-pentamino with Xlife-8 is about 3.15 times faster than with atomlife and 1.25 faster than with listlife. For the glider run Xlife-8 up to 40 times faster than atomlife and about 15 times faster than listlife. Xlife-8 uses CPU clocked 3.6 times slower.

BTW my favorite breeder is http://www.conwaylife.com/wiki/Metacatacryst. Its evolution is shown by the mentioned above video. I give a link with the exact time mark https://www.youtube.com/watch?v=IunDIzS012c&t=14s for this small but very sparse pattern.

Xlife-8 has a lot of limitations. It is easy to build it to up to 240x240 grid. More width or height will require changes in the user interface because the cursor coordinates are 8 bits. Another limit is the memory size. Xlife-8 uses about 1 byte per a cell. So 240x240 grid requires about 56 KB RAM. Xlife-8 uses static memory allocation. Xlife uses dynamic but this requires a hash-array or B-tree... IMHO it is possible to try to do a hash. It will require to work with heap (something like to free, malloc C-calls). It will make Xlife-8 a bit slower but capable to work with very large patterns like listlife does. It will also require some work with GUI...

Yagol for Amstrad CPC uses the fastest algorithm for 8-bit machines. However it uses video memory to keep cell data and this removes the video output routine completely! This way is impossible for Commodore video. I am not sure about BBC Micro. Yagol changes the palette so that some different pixels get the same colour. Is it possible with BBC Micro to give the same colour for the different pixels in 16 colour (8 colours + flash) mode?
Last edited by litwr on Fri Nov 04, 2016 9:35 am, edited 1 time in total.
User avatar
BigEd
Posts: 4507
Joined: Sun Jan 24, 2010 10:24 am
Location: West Country
Contact:

Re: Conway's Game of Life for Atom, Beeb, Elk?

Post by BigEd »

Interesting! Thanks for the data.

Yes, it's possible to set a BBC palette so that 2 or 4 bit per pixel modes display in just 2 or 4 colours - so it is possible to use screen memory to hold a life board with both present state and invisible previous state. But... the screen addressing is not linear, it scans down each 8-bit character in turn. Also, it's natural to read and write the screen in a single processor Beeb system, but once you have a coprocessor system, it becomes rather more expensive to read and write the screen. Better to have sufficient information local to the second processor, and write to the screen only the changed pixels.
litwr
Posts: 245
Joined: Sun Jun 12, 2016 9:44 am
Contact:

Re: Conway's Game of Life for Atom, Beeb, Elk?

Post by litwr »

Listlife uses video in a way the same as Xlife for X Window. :D
I have a suggestion for Listlife: to use a bigger step for scrolling.
User avatar
BigEd
Posts: 4507
Joined: Sun Jan 24, 2010 10:24 am
Location: West Country
Contact:

Re: Conway's Game of Life for Atom, Beeb, Elk?

Post by BigEd »

With Dave's latest leap forward, we can run the enormous Turing Machine pattern on Jason's Matchbox copro, at 64MHz and with 1MByte of RAM to play in. It's not fast, but it is computing. Here's a video (no soundtrack):
Image

The code for this 6502Life is on Github, now with a much improved user interface. No doubt Dave will be along shortly with a ready-to-download image, with programs to run on your Atom, or your Beeb with copro. At present you won't be able to run the very largest patterns unless you have a Matchbox with the latest firmware. (But we hope that our scheme for banked RAM will become something of a standard for 6502 second processors.)
User avatar
hoglet
Posts: 10709
Joined: Sat Oct 13, 2012 7:21 pm
Location: Bristol
Contact:

Re: Conway's Game of Life for Atom, Beeb, Elk?

Post by hoglet »

BigEd wrote: No doubt Dave will be along shortly with a ready-to-download image, with programs to run on your Atom, or your Beeb with copro.
Thanks Ed for doing another video of this.

Here's the latest version:
ListLife_20161110.zip
(49.03 KiB) Downloaded 97 times
The UI has improved enormously since the last version.

From the README, the keys are:
* Escape key - return to pattern-selection menu.
* Return - run a single generation
* Z - zoom in
* X - zoom out
* Cursor keys - increase or decrease panning speed
* Copy - reset pan speed to zero
* Tab - pan immediately to center of universe
* R - increase the rate (more generations for each screen update) cycling from 1x to 100x in ten steps and back to 1x.
* S - show or hide the user interface
* Space - toggle single-step/pause mode
For most people, the program to run will be *BLIFE.

Dave
User avatar
BigEd
Posts: 4507
Joined: Sun Jan 24, 2010 10:24 am
Location: West Country
Contact:

Re: Conway's Game of Life for Atom, Beeb, Elk?

Post by BigEd »

Bit of an update: we pursued the idea of processing a little 2d patch of cells at each point, instead of a single cell like the original list life, or an 8-cell line like the 1988 effort. And, it turns out to be 50% quicker! We're now using a 4k table to do the central work of figuring out the next generation - we could move up another speed notch if we used a 32k table but that leaves rather less room for the Life patterns.

The code, as ever, is here on github. Find attached a new disk image. I've also posted some notes over on 6502.org.

Edit: I should add, BLIFE42 is the fast one. It's a bit tricky to implement zooming with the new data structure, so there's no zooming at present. Props to Dave for bringing BLIFE42 to life.
Attachments
life-2016-11-22.zip
(53.28 KiB) Downloaded 94 times
User avatar
lurkio
Posts: 3943
Joined: Wed Apr 10, 2013 12:30 am
Location: Doomawangara
Contact:

Re: Conway's Game of Life for Atom, Beeb, Elk?

Post by lurkio »

More as a curiosity than anything else, here's a ROM-based MODE 7 version of Life that I just found on an old 8bs Magazine disc:
:idea:
8BS12.dsd.zip
8-bit Software magazine disc
(110.49 KiB) Downloaded 88 times
User avatar
BigEd
Posts: 4507
Joined: Sun Jan 24, 2010 10:24 am
Location: West Country
Contact:

Re: Conway's Game of Life for Atom, Beeb, Elk?

Post by BigEd »

This is somewhat off-topic but I thought it might be of interest:
Faster LIAR - Life In A Register
It's for 32 bit platforms, so good for ARM based machines perhaps.
Code here, I think.

There are also 32 bit tricks in Isaac Kuo's JavaScript life - see this post in the thread over on 6502.org. I haven't pulled both up to compare them.
Post Reply

Return to “8-bit acorn software: other”