Conway's Game of Life on the Blitter

Blogs & guides and tales of woo by forum members.
Post Reply
keli
Posts: 95
Joined: Tue Aug 22, 2017 1:34 pm

Conway's Game of Life on the Blitter

Post by keli » Fri Apr 06, 2018 12:05 pm

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: 56
Joined: Tue Aug 22, 2017 12:42 pm

Re: Conway's Game of Life on the Blitter

Post by Gunstick » Sat Nov 02, 2019 12:00 am

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
Moderator
Moderator
Posts: 541
Joined: Thu Aug 17, 2017 1:18 pm

Re: Conway's Game of Life on the Blitter

Post by DrF » Sat Nov 02, 2019 9:00 am

Very cool :D

"Conway's Game of Life on the Blitter"

Extra Super Cool :D
Gunstick wrote:
Sat Nov 02, 2019 12:00 am
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: 56
Joined: Tue Aug 22, 2017 12:42 pm

Re: Conway's Game of Life on the Blitter

Post by Gunstick » Sun Nov 03, 2019 3:22 pm

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: 56
Joined: Tue Aug 22, 2017 12:42 pm

Re: Conway's Game of Life on the Blitter

Post by Gunstick » Tue Nov 05, 2019 7:06 am

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: 95
Joined: Tue Aug 22, 2017 1:34 pm

Re: Conway's Game of Life on the Blitter

Post by keli » Fri Nov 08, 2019 6:26 pm

Gunstick wrote:
Sat Nov 02, 2019 12:00 am
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 187 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.

Cyprian
Posts: 157
Joined: Fri Dec 22, 2017 9:16 am

Re: Conway's Game of Life on the Blitter

Post by Cyprian » Fri Nov 08, 2019 6:30 pm

keli wrote:
Fri Nov 08, 2019 6:26 pm
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.
Lynx II / Jaugar / TT030 / Mega STe / 800 XL / 1040 STe / Falcon030 / 65 XE / 520 STm / SM124 / SC1435
SDrive / PAK68/3 / Lynx Multi Card / LDW Super 2000 / XCA12 / SkunkBoard / CosmosEx / SatanDisk / UltraSatan / USB Floppy Drive Emulator / Eiffel / SIO2PC / Crazy Dots / PAM Net
Hatari / Steem SSE / Aranym / Saint
http://260ste.appspot.com/

keli
Posts: 95
Joined: Tue Aug 22, 2017 1:34 pm

Re: Conway's Game of Life on the Blitter

Post by keli » Fri Nov 08, 2019 7:08 pm

Cyprian wrote:
Fri Nov 08, 2019 6:30 pm
keli wrote:
Fri Nov 08, 2019 6:26 pm
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.

Post Reply

Return to “MEMBER BLOGS”