Re: [stella] And now, for my next trick...

Subject: Re: [stella] And now, for my next trick...
From: Erik Mooney <emooney@xxxxxxxxxxxxxxxx>
Date: Thu, 08 Mar 2001 20:32:52 -0500
On Fri, 9 Mar 2001 01:12:31 +1100, you wrote:

>Thanks for the pointers.  Nobody seems to have considered packing the data
>in RAM.  Considering that MOST of the playfield during a life 'game' is 0
>(the theoretical maximum is 50% used), and that large areas of the playfield
>are usually contiguous 0's... and also that non-zero and alternating
>patterns are typically grouped together...  I figure a simple run-length
>packing (speed essential!) would be feasible.
>All the messages I read seem to assume that 1 bit/pixel is the limit that
>can be achieved.  This is not so!  As a simple example, byte-aligned runs of
>0's only (eight 0's) could be efficiently packed to a single bit, and all
>other data left as-is (plus another bit).  This would be pretty quick to
>unpack, yet save HEAPS of RAM.

I don't get it.  That's a nice compression for the average and best cases,
but the kernel and algorithm have to be able to handle the worst case.
What if a large-scale stable situation develops - all stable patterns (2x2
blocks, 6-cell ovals, etc, 3-in-a-row alternators, etc) separated by empty
gaps 2-4 cells wide?

>I'm still thinking about the feasibility and operation of the kernal, and
>how I can interleave run-length unpacking into the display kernal, in
>particular.  I'm not saying it CAN be done... I just think it might be
>possible :)

Sure you can compress it, but it doesn't save you RAM in worst-case
scenarios, which you have to support.

>> b) Life on Mars.   An implementation of John Conway's life (in at least a
>> 32x32 - or possibly up to 40 x 64 - grid).   All in orangy/red colours,

>Don't forget that you also need to store TWO copies of the grid at all
>times... the current grid, and the next-generation grid. If you just use
>one, the pattern smears in the direction of your update algo, and it doesn't
>work right.

Now here, we can optimize. :)  No cell can affect or be affected by
another nonadjacent cell.  So we can go with as few as 2 rows of common
storage, where after calculating each line N, line N-1 is copied out of
the common (temporary) storage to the main array.  Then line N+1 can be
calculated using the old line N; it makes no use of line N-1.

Archives (includes files) at
Unsub & more at

Current Thread