biglife 1.1 README ============================================================================== Copyright (c) 1997-2001 Kurt A. Stephens and Ion, Inc., All Rights Reserved. http://www.acm.org/~stephensk Kurt A. Stephens and Ion, Inc. MAKE NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, OR NON-INFRINGEMENT. Kurt A. Stephens and Ion, Inc. SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. $Id: COPYRIGHT,v 1.3 2001/04/03 18:37:16 stephens Exp $ ============================================================================== biglife 1.1 README ============================================================================== $Id: README,v 1.3 1999/11/14 04:02:19 stephensk Exp $ Biglife Copyright 1998, 1999, Kurt A. Stephens http://www.acm.org/~stephensk The biglife library implements Conway's "Game-of-Life" using sparse bitmap arrays. It achieves its speed by unrolling the four nested loops of a naive implementation into 9 different types of bitwise operations and by not processing empty areas. A naive implementations can be used for validation of the fast routines. Currently supported displays are: ANSI terminals (vt100) and GTK+ libraries. Each life_array object is a hash table containing 8x8 bitmaps (life_chunk) indexed by chunk position. Each life_chunk has a chunk coordinate (x,y). Each coordinate element is a short and the hash of the position is a unsigned long concatenation of the coordinate. This allows an effective board size of 524288/524288 (memory permitting). Empty life_chunks, chunks with no live cells are not stored in the life_array, except when determining chunks adjacent to live chunks. Live chunks have at least one live cell. The storage overhead is 8 bytes for the 4 bytes of position and 4 bytes of linked list. This is %50 overhead over a full bit array representation. If we moved up to 16x16 bit chunks (64 bytes) the overhead would be %17.5 but there might be some very sparse chunks due to "gliders" going off to infinity. Iteration algorithm: 1. For each live chunk (C) 2. Find chunks neighboring C (CS[3][3]) 3. Create a new empty chunk (NC) 4. For each cell in chunk C (S) 5. Compute the number of neighbor cells of cell S. 6. Compute the corresponding cell in NC based on the number of neighbor cells for S. 7. For all neighbororing chunks created by step 2, 8. Do steps 3-6. 9. Filter out all dead chunks. A state table (life_trans_table[]) is used to map the 9 cell states into a new center cell state. The index into life_trans_table is the following bits: +---+---+---+ | | | | | 0 | 1 | 2 | | | | | +---+-V-+---+ | | | | | 3 > 4 < 5 | | | | | +---+-^-+---+ | | | | | 6 | 7 | 8 | | | | | +---+---+---+ Bit 4 is the center cell, all other cells are represented by other bits. The state of a cell and all neighbors is represented in 9 bits. For each cell in the life chunk, create a index into the state table from the neighboring cells. This is done using bitwise operations for speed. The display algorithm: 1. Choose a viewport in the chunks. 2. Clear the window. 3. Iterate through the chunks in the window without allocating dead chunks and blit each. Incremental display: TO BE IMPLEMENTED: Toggle the update bit in the chunk if its different from a last chunk. Only draw chunks that have changed as long as the viewport is the same. Commands: Please type '?-RETURN' at the command prompt for a description of each command. ============================================================================== ============================================================================== NAME biglife VERSION 1.1 CATEGORY Games DESC A Game-of-Life program that uses sparse, hashed block, bit matrices to allow Life boards up to any size. CONTAINS_PKGS biglife REQUIRES_OTHERS ansi_terminal DATE 2001/06/02 10:29:47 README /home/stephens/public_html/research/pub/biglife1.1.txt ARCHIVE /home/stephens/public_html/research/pub/biglife1.1.tgz NAME biglife VERSION 1.1 CATEGORY Games DESC A Game-of-Life program that uses sparse, hashed block, bit matrices to allow Life boards up to any size. SRC_DIR /home/stephens/ion/src/biglife CVSLOG CVSLOG MAKE make MAKE_CLEAN clean veryclean OPTIONAL_OTHERS gtk gdk glib RCS_ID $Id: PKG,v 1.6 1999/11/14 04:02:19 stephensk Exp $ README README REQUIRES_OTHERS ansi_terminal REQUIRES_PKGS OTHER ansi_terminal ============================================================================== biglife 1.1 CHANGES ============================================================================== ============================================================================== biglife 1.1 Table of Contents ============================================================================== biglife1.1: total 7 drwxr-xr-x 3 stephens stepheng 1024 Jun 2 05:32 . drwxr-xr-x 3 stephens stepheng 1024 Jun 2 05:32 .. -rw-r--r-- 1 stephens stepheng 100 Jun 2 05:32 CHANGES -rw-r--r-- 1 stephens stepheng 601 Jun 2 05:32 COPYRIGHT -rw-r--r-- 1 stephens stepheng 781 Jun 2 05:32 README -rw-r--r-- 1 stephens stepheng 109 Jun 2 05:32 TOC drwxr-xr-x 3 stephens stepheng 1024 Jun 2 05:32 src biglife1.1/src: total 4 drwxr-xr-x 3 stephens stepheng 1024 Jun 2 05:32 . drwxr-xr-x 3 stephens stepheng 1024 Jun 2 05:32 .. -rw-r--r-- 1 stephens stepheng 390 Jun 2 05:32 GUM_BUILD_ROOT drwxr-xr-x 4 stephens stepheng 1024 Jun 2 05:32 biglife biglife1.1/src/biglife: total 88 drwxr-xr-x 4 stephens stepheng 1024 Jun 2 05:32 . drwxr-xr-x 3 stephens stepheng 1024 Jun 2 05:32 .. drwxr-xr-x 2 stephens stepheng 1024 Feb 2 21:29 CVS -rw-r--r-- 1 stephens stepheng 1036 Nov 13 1999 Makefile -rw-r--r-- 1 stephens stepheng 294 Nov 13 1999 PKG -rw-r--r-- 1 stephens stepheng 2829 Nov 13 1999 README -rw-r--r-- 1 stephens stepheng 40837 Dec 26 1999 biglife.c -rw-r--r-- 1 stephens stepheng 164 Oct 13 1999 biglife.gdb -rw-r--r-- 1 stephens stepheng 5835 Nov 13 1999 biglife.h -rw-r--r-- 1 stephens stepheng 73 Feb 19 1999 biglife.in -rw-r--r-- 1 stephens stepheng 3283 Nov 13 1999 blgtk.c -rw-r--r-- 1 stephens stepheng 4906 Nov 13 1999 blterm.c -rw-r--r-- 1 stephens stepheng 13113 Nov 13 1999 gtklife.c -rw-r--r-- 1 stephens stepheng 1180 Dec 26 1999 gtklife.h drwxr-xr-x 4 stephens stepheng 1024 Feb 2 21:29 lib -rw-r--r-- 1 stephens stepheng 388 Nov 5 1999 life.c -rw-r--r-- 1 stephens stepheng 1796 Dec 26 1999 term.c -rw-r--r-- 1 stephens stepheng 569 Nov 13 1999 term.h biglife1.1/src/biglife/CVS: total 5 drwxr-xr-x 2 stephens stepheng 1024 Feb 2 21:29 . drwxr-xr-x 4 stephens stepheng 1024 Jun 2 05:32 .. -rw-r--r-- 1 stephens stepheng 580 Feb 2 21:29 Entries -rw-r--r-- 1 stephens stepheng 21 Feb 2 21:29 Repository -rw-r--r-- 1 stephens stepheng 28 Feb 2 21:29 Root biglife1.1/src/biglife/lib: total 4 drwxr-xr-x 4 stephens stepheng 1024 Feb 2 21:29 . drwxr-xr-x 4 stephens stepheng 1024 Jun 2 05:32 .. drwxr-xr-x 2 stephens stepheng 1024 Feb 2 21:29 CVS drwxr-xr-x 3 stephens stepheng 1024 Feb 2 21:29 biglife biglife1.1/src/biglife/lib/CVS: total 5 drwxr-xr-x 2 stephens stepheng 1024 Feb 2 21:29 . drwxr-xr-x 4 stephens stepheng 1024 Feb 2 21:29 .. -rw-r--r-- 1 stephens stepheng 14 Feb 2 21:29 Entries -rw-r--r-- 1 stephens stepheng 25 Feb 2 21:29 Repository -rw-r--r-- 1 stephens stepheng 28 Feb 2 21:29 Root biglife1.1/src/biglife/lib/biglife: total 62 drwxr-xr-x 3 stephens stepheng 1024 Feb 2 21:29 . drwxr-xr-x 4 stephens stepheng 1024 Feb 2 21:29 .. drwxr-xr-x 2 stephens stepheng 1024 Feb 2 21:29 CVS -rw-r--r-- 1 stephens stepheng 67 Oct 13 1999 acorn -rw-r--r-- 1 stephens stepheng 39 Oct 13 1999 bakery -rw-r--r-- 1 stephens stepheng 96 Oct 13 1999 barberpole -rw-r--r-- 1 stephens stepheng 20 Oct 13 1999 barge -rw-r--r-- 1 stephens stepheng 30 Oct 13 1999 beacon -rw-r--r-- 1 stephens stepheng 17 Oct 13 1999 beehive -rw-r--r-- 1 stephens stepheng 257 Oct 13 1999 bhepto -rw-r--r-- 1 stephens stepheng 51 Oct 13 1999 biboat -rw-r--r-- 1 stephens stepheng 53 Oct 13 1999 bigs -rw-r--r-- 1 stephens stepheng 64 Oct 13 1999 biloaf -rw-r--r-- 1 stephens stepheng 65 Oct 13 1999 bipond -rw-r--r-- 1 stephens stepheng 18 Oct 13 1999 blinker -rw-r--r-- 1 stephens stepheng 23 Oct 13 1999 block -rw-r--r-- 1 stephens stepheng 15 Oct 13 1999 boat -rw-r--r-- 1 stephens stepheng 28 Oct 13 1999 canoe -rw-r--r-- 1 stephens stepheng 33 Oct 13 1999 century -rw-r--r-- 1 stephens stepheng 29 Oct 13 1999 clock -rw-r--r-- 1 stephens stepheng 112 Oct 13 1999 clock2 -rw-r--r-- 1 stephens stepheng 30 Oct 13 1999 eater -rw-r--r-- 1 stephens stepheng 33 Oct 13 1999 fleet -rw-r--r-- 1 stephens stepheng 62 Oct 13 1999 flipflop -rw-r--r-- 1 stephens stepheng 192 Oct 13 1999 flotilla -rw-r--r-- 1 stephens stepheng 114 Oct 13 1999 flyingmachine -rw-r--r-- 1 stephens stepheng 430 Oct 13 1999 flyingmachineb -rw-r--r-- 1 stephens stepheng 114 Oct 13 1999 flyingmachinex -rw-r--r-- 1 stephens stepheng 103 Oct 13 1999 galaxy -rw-r--r-- 1 stephens stepheng 38 Oct 13 1999 glider -rw-r--r-- 1 stephens stepheng 1131 Oct 13 1999 glidergun -rw-r--r-- 1 stephens stepheng 34 Oct 13 1999 hat -rw-r--r-- 1 stephens stepheng 46 Oct 13 1999 herschel -rw-r--r-- 1 stephens stepheng 64 Oct 13 1999 hexadec -rw-r--r-- 1 stephens stepheng 30 Oct 13 1999 honeyfarm -rw-r--r-- 1 stephens stepheng 46 Oct 13 1999 interchange -rw-r--r-- 1 stephens stepheng 20 Oct 13 1999 loaf -rw-r--r-- 1 stephens stepheng 24 Oct 13 1999 mango -rw-r--r-- 1 stephens stepheng 876 Oct 13 1999 p15 -rw-r--r-- 1 stephens stepheng 53 Oct 13 1999 paperclip -rw-r--r-- 1 stephens stepheng 84 Oct 13 1999 pentadec -rw-r--r-- 1 stephens stepheng 37 Oct 13 1999 pihepto -rw-r--r-- 1 stephens stepheng 22 Oct 13 1999 pond -rw-r--r-- 1 stephens stepheng 161 Oct 13 1999 puffer -rw-r--r-- 1 stephens stepheng 26 Oct 13 1999 pulsar -rw-r--r-- 1 stephens stepheng 33 Oct 13 1999 rpent -rw-r--r-- 1 stephens stepheng 22 Oct 13 1999 shillelagh -rw-r--r-- 1 stephens stepheng 26 Oct 13 1999 ship -rw-r--r-- 1 stephens stepheng 52 Oct 13 1999 shiptie -rw-r--r-- 1 stephens stepheng 125 Oct 13 1999 shuttle -rw-r--r-- 1 stephens stepheng 14 Oct 13 1999 snake -rw-r--r-- 1 stephens stepheng 1424 Oct 13 1999 spacerake -rw-r--r-- 1 stephens stepheng 74 Oct 13 1999 spaceship -rw-r--r-- 1 stephens stepheng 80 Oct 13 1999 spaceshiph -rw-r--r-- 1 stephens stepheng 75 Oct 13 1999 spaceshipm -rw-r--r-- 1 stephens stepheng 63 Oct 13 1999 switchengine -rw-r--r-- 1 stephens stepheng 23 Oct 13 1999 toad -rw-r--r-- 1 stephens stepheng 30 Oct 13 1999 ttetro -rw-r--r-- 1 stephens stepheng 14 Oct 13 1999 tub -rw-r--r-- 1 stephens stepheng 59 Oct 13 1999 tumbler biglife1.1/src/biglife/lib/biglife/CVS: total 7 drwxr-xr-x 2 stephens stepheng 1024 Feb 2 21:29 . drwxr-xr-x 3 stephens stepheng 1024 Feb 2 21:29 .. -rw-r--r-- 1 stephens stepheng 2275 Feb 2 21:29 Entries -rw-r--r-- 1 stephens stepheng 33 Feb 2 21:29 Repository -rw-r--r-- 1 stephens stepheng 28 Feb 2 21:29 Root ==============================================================================