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,
>and
>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 http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/
