Conway's Game of Life on the Blitter

Blogs & guides and tales of woo by forum members.
keli
Posts: 97
Joined: 22 Aug 2017 13:34

Conway's Game of Life on the Blitter

Post by keli »

I've been playing around with the Blitter recently and created a PoC implementation of Conway's Game of Life that uses the Blitter for the actual grunt work.

I wrote up a blog post about it and posted the source on my website at: https://www.keli.dk/blitter-life/

Why? Because game of life is apparently Turing complete, making the Blitter almost as well (we need to instruct it what to do from the CPU)...
Gunstick
Posts: 61
Joined: 22 Aug 2017 12:42

Re: Conway's Game of Life on the Blitter

Post by Gunstick »

I made a life using "grafics"-operations, but with the CPU. It's nicely fast and small (it fits in a boot sector). I got that idea from someone who did life with blitter on the Amiga. As you also found out, you only need to count to 4. It is a reimplementation of an adder logic chip by using logic operators. This needs 3 planes. The first plane are the bit0 of every pixel counting the neighbors, and second plane is bit1 of all pixel counters. And the 3rd plane is the carry bit of all the counters. If carry set: the cell dies.
Using the CPU, my planes are just registers in the CPU and thus my 'screen' is 1x32 pixels and sliding over the playing area.
https://demozoo.org/productions/167685/

It uses a line based optimization, as it's not doing any operation if there are no pixels on a line. For this an array with empty lines is maintained.
No idea if that method could speed up the blitter-life.
User avatar
DrF
Posts: 640
Joined: 17 Aug 2017 13:18

Re: Conway's Game of Life on the Blitter

Post by DrF »

Very cool :D

"Conway's Game of Life on the Blitter"

Extra Super Cool :D
Gunstick wrote: 02 Nov 2019 00:00 I made a life using "grafics"-operations, but with the CPU. It's nicely fast and small (it fits in a boot sector). I got that idea from someone who did life with blitter on the Amiga.
How much space did you have to work with?
I can't remember the size of the boot sector even after I watched a video on this sort of stuff just last night :lol:
Gunstick
Posts: 61
Joined: 22 Aug 2017 12:42

Re: Conway's Game of Life on the Blitter

Post by Gunstick »

The bootsector is the smallest thing you can have. 512 bytes. Minus several bytes to make it a valid disk and bootable. That leaves you officially with 452 bytes available. But you can squeeze up to 484 bytes if you know exactly what TOS does with that data.

Additional info: I found a more recent version of the source, a comment says it got a speedup from 3min23s to 1min30s by also adding a test if columns can be skipped (not only empty columns are skipped but also those with static populations). Wow, CPU optimizing is cool.
The version I realeased with the ULM93 demo was still taking 2min8s, but the bootsector got erased by a "no virus" program from TSCC, which is the version you seen on youtube. You need to download the MSA from fujiology. https://demozoo.org/productions/78604/ (crashes on 4MB machines, maybe I should fix that).

Here is the pattern taking 1'30"

Code: Select all

        dc.l %00000000000100000000000000000000 ;3530 generations 4'20"
        dc.l %00000000000111111111111111110000 ;v6:3'23"  v7:1'30""
Gunstick
Posts: 61
Joined: 22 Aug 2017 12:42

Re: Conway's Game of Life on the Blitter

Post by Gunstick »

I actually published the fast life as standalone
https://demozoo.org/productions/167685/
But it's only the bootsector, you need a program to write it
So that also exists https://demozoo.org/productions/167683/
keli
Posts: 97
Joined: 22 Aug 2017 13:34

Re: Conway's Game of Life on the Blitter

Post by keli »

Gunstick wrote: 02 Nov 2019 00:00 I made a life using "grafics"-operations, but with the CPU. It's nicely fast and small (it fits in a boot sector). I got that idea from someone who did life with blitter on the Amiga. As you also found out, you only need to count to 4. It is a reimplementation of an adder logic chip by using logic operators. This needs 3 planes. The first plane are the bit0 of every pixel counting the neighbors, and second plane is bit1 of all pixel counters. And the 3rd plane is the carry bit of all the counters. If carry set: the cell dies.
Using the CPU, my planes are just registers in the CPU and thus my 'screen' is 1x32 pixels and sliding over the playing area.
https://demozoo.org/productions/167685/

It uses a line based optimization, as it's not doing any operation if there are no pixels on a line. For this an array with empty lines is maintained.
No idea if that method could speed up the blitter-life.
Ah so by "grafcs"-operations I assume it's using XOR and AND to calculate the sum and carry bit respectively... a little like my arm tattoo ;)

2019-11-08 19.17.25.jpg
2019-11-08 19.17.25.jpg (169.6 KiB) Viewed 6844 times

That could be rather cool, although it would require some additional copying compared to an Amiga implementation. AFAIK the Amiga blitter can combine 2 (or maybe even 3) sources into a single destination, the Atari blitter can only combine a single source with a single destination, overwriting the destination in the process. I'm sure it can be done though.
User avatar
Cyprian
Posts: 573
Joined: 22 Dec 2017 09:16
Location: Warszawa, Poland

Re: Conway's Game of Life on the Blitter

Post by Cyprian »

keli wrote: 08 Nov 2019 18:26 AFAIK the Amiga blitter can combine 2 (or maybe even 3) sources into a single destination, the Atari blitter can only combine a single source with a single destination, overwriting the destination in the process. I'm sure it can be done though.
actually Atari BLiTTER can combine three sources: 1) Source; 2) Halftone Regs; 3) Destination into single destination.
Atari: V4sa TT030 Falcon030 Mega ST Mega STe 1040 STe 520 STm 800XL 65XE Jaguar Lynx I/II 7800 Portfolio / VME: ATW800/2 Mach64 Mach32 ET4000 CrazyDots PAMNet / SM146 SC1435 SM124 / Antonia2 ATSpeedC16 TF536 PAK68/3
Megafile30 Atari1050 DDDHDD XCA12 SF314 / AVGCART SUBCART SidecarTridge ACSI2STM FujiNet LynxMultiCard SkunkBoard CosmosEx SatanDisk UltraSatan USBFloppyDriveEmulator SDrive SIO2PC Eiffel
http://260ste.atari.org
keli
Posts: 97
Joined: 22 Aug 2017 13:34

Re: Conway's Game of Life on the Blitter

Post by keli »

Cyprian wrote: 08 Nov 2019 18:30
keli wrote: 08 Nov 2019 18:26 AFAIK the Amiga blitter can combine 2 (or maybe even 3) sources into a single destination, the Atari blitter can only combine a single source with a single destination, overwriting the destination in the process. I'm sure it can be done though.
actually Atari BLiTTER can combine three sources: 1) Source; 2) Halftone Regs; 3) Destination into single destination.
But that's only 16 words of data. I'm actually using the halftone regs in my implementation as 16 entry look-up tables to perform additions that way. For the half-adder/full-adder way of implementing parlallel sums you need two memory sources, and this is where having the destination be separate from both sources would be useful.

Return to “MEMBER BLOGS”

Who is online

Users browsing this forum: Amazon [bot], ClaudeBot and 7 guests