karl@zip.UUCP (Karl F. Fox) (10/25/89)
Here's another graphics game for the UNIX PC. Please send me bug reports, bug fixes, interesting new patterns, and suggestions for improvements. Note: This code is designed to be fast, not small. Look: % size /usr/games/life 7432(.text) + 1148(.data) + 518884(.bss) + 0(.lib) = 527464 My apologies if you only have a .5M machine. #!/bin/sh # # This is a SHAR archive. To extract, remove everything # above the #!/bin/sh line and type "sh filename" # if `test ! -s ./README` then echo "Writing ./README" sed 's/^X//' > ./README << '\End\of\File\' XThis is John Horton Conway's game of life for the AT&T UNIX PC. X X XHow to make it: X XType "make". X X XHow to use it: X XJust run it. There are no arguments. Stop it by giving it a SIGINT or XSIGTERM or by typing any key (except a digit) to the display window. XTyping digit n will set the time to sleep between generations to n/10 of Xa second. X XPressing the middle mouse button freezes or resumes animation, and Xpressing the right mouse button kills all the cells. When the left Xmouse button is pressed *down* the cursor changes from a tiny dot X(which, by the way, will disappear completely if places in the far upper Xright corner of the screen) to a life cell, which can be placed on the Xscreen by releasing the button. Depositing the new cell on an old cell Xkills it. X XWhen the arena gets into a stable configuration (all dead, completely Xstatic or a pattern repeating every 63 generations or less), a glider or Xspaceship will be injected to stir up the action. After a few tries at Xthis, the screen will be cleared and a random starting pattern will be Xselected from the file /usr/local/lib/life-patterns. Note that the cell Xarena extends a ways beyond the boundaries of the visible screen, so an Xapparently static configuration may be active off-screen. X XPlease send me any interesting new startup patterns that you discover X(karl@MorningStar.Com or karl@zip.UUCP). X XHave fun! X XP.S. Send me email if you want my xlock driver. X X@(#)README 1.1 \End\of\File\ else echo "Not overwriting ./README" fi if `test ! -s ./Makefile` then echo "Writing ./Makefile" sed 's/^X//' > ./Makefile << '\End\of\File\' X# @(#)Makefile 1.1 X X# X# Makefile for the game of life X# X# karl@MorningStar.Com or karl@zip.UUCP X# X XLDFLAGS = /lib/crt0s.o /lib/shlib.ifile X Xlife: life.o X $(LD) -o $@ life.o $(LDFLAGS) X Xlife.o: life.c lifegame.c X $(CC) $(CFLAGS) -c life.c X Xclean: X rm -f life *.o core Xlint: X lint -p life.c X XREADME: s.README X $(GET) $(GFLAGS) -p s.README > $@ X Xlife.shar: README Makefile life.c lifegame.c X -shar README Makefile life.c lifegame.c > life.shar \End\of\File\ else echo "Not overwriting ./Makefile" fi if `test ! -s ./life.c` then echo "Writing ./life.c" sed 's/^X//' > ./life.c << '\End\of\File\' X/* X * Copyright (c) 1989 Karl F. Fox, all rights reserved X * X * You may use this software for any purpose as long as you include X * this copyright notice. X */ X X# ifndef lint Xstatic char life_sccs_id[] = "@(#)life.c 1.1"; X# endif /* lint */ X X/* X * life.c X * X * John Horton Conway's game of life for the AT&T UNIX PC. X * X * X * How to use it: X * X * X * Just run it. There are no arguments. Stop it by giving it a X * SIGINT or SIGTERM or by typing any key (except a digit) to the X * display window. Typing digit n will set the time to sleep X * between generations to n/10 of a second. X * X * Pressing the middle mouse button freezes or resumes animation, X * and pressing the right mouse button kills all the cells. When X * the left mouse button is pressed *down* the cursor changes from X * a tiny dot (which, by the way, will disappear completely if X * places in the far upper right corner of the screen) to a life X * cell, which can be placed on the screen by releasing the button. X * Depositing the new cell on an old cell kills it. X * X * When the arena gets into a stable configuration (all dead, X * completely static or a pattern repeating every 63 generations or X * less), a glider or spaceship will be injected to stir up the X * action. After a few tries at this, the screen will be cleared X * and a random starting pattern will be selected from the file X * /usr/local/lib/life-patterns. Note that the cell arena extends X * a ways beyond the boundaries of the visible screen, so an X * apparently static configuration may be active off-screen. X * X * Please send me any interesting new startup patterns that you X * discover (karl@MorningStar.Com or karl@zip.UUCP). X * X * Have fun! X */ X X# include <stdio.h> X# include <termio.h> X# include <fcntl.h> X# include <sys/window.h> X# include <sys/font.h> X# include <signal.h> X# include <string.h> X# include <memory.h> X X# define K_OK 0 X# define K_OTHER 1 X# define K_EXIT 2 X X# define ESC '\033' X X/* X * Mouse event string character classes X */ X# define ESCAPE 0 X# define SEMI 1 X# define M 2 X# define O 3 X# define DIGIT 4 X# define DEFAULT 5 X Xint mouse_state = 0, X mouse_x = 0, X mouse_y = 0, X mouse_buttons = 0, X mouse_reason = 0; X Xstruct termio orig_tm; X X# define PATTERN_FILE "/usr/local/lib/life-patterns" X X# define SYSV X X# ifdef SYSV X# define srandom(seed) srand((unsigned)(seed)) X# define random() rand() X# define bcmp(a,b,c) memcmp((char *)(b), (char *)(a), (int)(c)) X# define bzero(a,c) memset((char *)(a), 0, (int)(c)) X# endif /* SYSV */ X Xstatic int width, height, xs, ys, xb, yb, xp, yp; X X# define NROWS 128 X# define NCOLS 256 X X# define XS1 4 X# define YS1 3 X# define NR1 64 X# define NC1 64 X# define XS2 1 X# define YS2 1 X Xextern int open(), close(), read(), write(), ioctl(), rand(), memcmp(), X fprintf(), fcntl(); Xextern void srand(), exit(), perror(); Xextern unsigned sleep(); Xextern long time(); X Xint wd; X Xvoid main() X { X extern void process(); X X if ((wd = open("/dev/window", O_RDWR)) < 0) X { X (void)perror("Can't open '/dev/window'\7"); X (void)exit(1); X } X X process(); X (void)close(wd); X (void)exit(0); X /*NOTREACHED*/ X } X Xvoid terminate() X { X extern void cursor_visible(), mouse_off(), term_reset(); X X static int in_terminate = 0; X X if ( ! in_terminate) X { X ++in_terminate; X cursor_visible(); X mouse_off(); X term_reset(); X (void)close(wd); X (void)exit(1); X } X } X Xvoid cursor_invisible() X { X if (write(wd, "\033[=1C", 5) != 5) X { X (void)perror("Can't set cursor invisibility\7"); X terminate(); X } X } X Xvoid cursor_visible() X { X if (write(wd, "\033[=0C", 5) != 5) X { X (void)perror("Can't restore cursor visibility\7"); X terminate(); X } X } X X# define WIDTH 720 X# define HEIGHT 300 X Xint running = 1, delay = 0; X Xvoid process() X { X extern void mouse_on(), term_cbreak(); X extern int set_window_parameters(); X X if (set_window_parameters(0, 0, WIDTH, HEIGHT, NBORDER) < 0) X return; X X term_cbreak(0, 0); X mouse_on(1, 1, WIDTH, HEIGHT); X (void)signal(SIGTERM, (int (*)())terminate); X (void)signal(SIGINT, (int (*)())terminate); X X cursor_invisible(); X X for (;;) X { X extern void initlife(), draw_life_game(); X extern int life_game_done(); X X initlife(WIDTH, HEIGHT); X X do X { X register int i, n; X char buffer[64]; X X do X { X extern int do_key(); X X if ((n = read(wd, buffer, sizeof buffer)) > 0) X for (i = 0; i < n; ++i) X switch (do_key(buffer[i])) X { X case K_OK: X break; X X case K_OTHER: X case K_EXIT: X terminate(); X } X } X while ( ! running); X X X draw_life_game(); X } X while ( ! life_game_done()); X } X X /*NOTREACHED*/ X } X Xint set_window_parameters(x, y, w, h, uflags) Xregister int x, y, w, h, uflags; X { X struct uwdata uwdata; X struct utdata utdata; X X if (ioctl(wd, WIOCGETD, &uwdata) < 0) X { X (void)perror("Can't perform WIOCGETD\7"); X return (-1); X } X X uwdata.uw_x = x; X uwdata.uw_y = y; X uwdata.uw_width = w; X uwdata.uw_height = h; X uwdata.uw_uflags = uflags; X X if (ioctl(wd, WIOCSETD, &uwdata) < 0) X { X (void)perror("Can't perform WIOCSETD\7"); X return (-1); X } X X (void)strncpy(utdata.ut_text, "life", WTXTLEN); X utdata.ut_num = WTXTUSER; X X if (ioctl(wd, WIOCSETTEXT, &utdata) < 0) X { X (void)perror("Can't perform WIOCSETTEXT\7"); X return (-1); X } X X return (0); X } X Xint window_rastop(srcbase, srcwidth, dstbase, dstwidth, srcx, srcy, dstx, X dsty, bltwidth, bltheight, srcop, dstop, pattern) Xunsigned short *srcbase, srcwidth, *dstbase, dstwidth, srcx, srcy, dstx, X dsty, bltwidth, bltheight, *pattern; Xchar srcop, dstop; X { X struct urdata urdata; X X urdata.ur_srcbase = srcbase; X urdata.ur_srcwidth = srcwidth; X urdata.ur_dstbase = dstbase; X urdata.ur_dstwidth = dstwidth; X urdata.ur_srcx = srcx; X urdata.ur_srcy = srcy; X urdata.ur_dstx = dstx; X urdata.ur_dsty = dsty; X urdata.ur_width = bltwidth; X urdata.ur_height = bltheight; X urdata.ur_srcop = srcop; X urdata.ur_dstop = dstop; X urdata.ur_pattern = pattern; X X if (ioctl(wd, WIOCRASTOP, &urdata) < 0) X { X (void)perror("Can't perform WIOCRASTOP\7"); X return (-1); X } X X return (0); X } X X# define DISPLAY_WIDTH ((WIDTH + 7) / 8) X Xunsigned short display[DISPLAY_WIDTH/2 * HEIGHT]; X Xunsigned short white_pattern[] = X { X 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, X 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF X }; X Xunsigned short black_pattern[] = X { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; X Xvoid draw_rectangle(x, y, xsize, ysize) Xint x, y, xsize, ysize; X { X register unsigned short *s = &display[(y * DISPLAY_WIDTH/2) + (x >> 4)]; X X if (xsize == 3 && ysize == 2) X switch (x & 15) X { X case 0: *s |= 0x0007; s += DISPLAY_WIDTH/2; X *s |= 0x0007; X return; X case 4: *s |= 0x0070; s += DISPLAY_WIDTH/2; X *s |= 0x0070; X return; X case 8: *s |= 0x0700; s += DISPLAY_WIDTH/2; X *s |= 0x0700; X return; X case 12: *s |= 0x7000; s += DISPLAY_WIDTH/2; X *s |= 0x7000; X return; X } X X if (window_rastop(0, 0, display, DISPLAY_WIDTH, 0, 0, (unsigned short)x, X (unsigned short)y, (unsigned short)xsize, (unsigned short)ysize, X SRCPAT, DSTSRC, white_pattern) < 0) X (void)fprintf(stderr, X "window_rastop() failed in draw_rectangle(%d, %d, %d, %d)\n", X x, y, xsize, ysize); X } X Xvoid erase_rectangle(x, y, xsize, ysize) Xint x, y, xsize, ysize; X { X register unsigned short *s = &display[(y * DISPLAY_WIDTH/2) + (x >> 4)]; X X if (xsize == 4 && ysize == 3) X switch (x & 15) X { X case 0: *s &= ~0x000F; s += DISPLAY_WIDTH/2; X *s &= ~0x000F; s += DISPLAY_WIDTH/2; X *s &= ~0x000F; X return; X case 4: *s &= ~0x00F0; s += DISPLAY_WIDTH/2; X *s &= ~0x00F0; s += DISPLAY_WIDTH/2; X *s &= ~0x00F0; X return; X case 8: *s &= ~0x0F00; s += DISPLAY_WIDTH/2; X *s &= ~0x0F00; s += DISPLAY_WIDTH/2; X *s &= ~0x0F00; X return; X case 12: *s &= ~0xF000; s += DISPLAY_WIDTH/2; X *s &= ~0xF000; s += DISPLAY_WIDTH/2; X *s &= ~0xF000; X return; X } X X if (window_rastop(0, 0, display, DISPLAY_WIDTH, 0, 0, (unsigned short)x, X (unsigned short)y, (unsigned short)xsize, (unsigned short)ysize, X SRCPAT, DSTSRC, black_pattern) < 0) X (void)fprintf(stderr, X "window_rastop() failed in erase_rectangle(%d, %d, %d, %d)\n", X x, y, xsize, ysize); X } X Xvoid update_display() X { X if (window_rastop(display, DISPLAY_WIDTH, 0, 0, 0, 0, 0, 0, X (unsigned short)width, (unsigned short)height, X SRCSRC, DSTSRC, 0) < 0) X (void)fprintf(stderr, X "window_rastop() failed in update_display()\n"); X } X X/*ARGSUSED*/ Xstatic int new_color(color) Xint color; X { X return (0); X } X X/*ARGSUSED*/ Xstatic void draw(row, col, age) Xint row, col, age; X { X draw_rectangle(xb + xs * col, yb + ys * row, xp, yp); X } X Xstatic void erase(row, col) Xint row, col; X { X erase_rectangle(xb + xs * col, yb + ys * row, xs, ys); X } X Xvoid initlife(w, h) Xint w, h; X { X extern void init_life_game(); X X int rows, cols; X X width = w; X height = h; X X erase_rectangle(0, 0, width, height); X X xs = XS1; X ys = YS1; X X if (width / xs < NC1 || height / ys < NR1) X { X xs = XS2; X ys = YS2; X } X X cols = width / xs; X rows = height / ys; X X if (xs <= 2 || ys <= 2) X xp = xs, yp = ys; X else if (xs <= 4 || ys <= 4) X xp = xs - 1, yp = ys - 1; X else X xp = xs - 2, yp = ys - 2; X X xb = (width - xs * cols) / 2; X yb = (height - ys * rows) / 2; X X init_life_game(rows, cols, 0); X } X Xvoid term_cbreak(vmin, vtime) Xint vmin, vtime; X { X static int initialized = 0; X struct termio tm; X X if ( ! initialized) X { X if (ioctl(wd, TCGETA, &orig_tm) < 0) X { X perror("Can't get terminal characteristics\7"); X terminate(); X } X X ++initialized; X } X X tm = orig_tm; X X tm.c_cc[VMIN] = vmin; X tm.c_cc[VTIME] = vtime; X tm.c_lflag &= ~(ICANON | ECHO | ECHOE | ECHOK | ECHONL); X X if (ioctl(wd, TCSETA, &tm) < 0) X { X perror("Can't set terminal characteristics\7"); X terminate(); X } X } X Xvoid term_reset() X { X if (ioctl(wd, TCSETA, &orig_tm) < 0) X { X perror("Can't reset terminal characteristics\7"); X terminate(); X } X } X X/* X * Life cell cursor: X * X * *** X * *** X */ Xstruct icon cell_icon = X { X 0, /* ic_flags (ignored) */ X X { /* struct fcdef ic_fc */ X 3, /* fc_hs */ X 2, /* fc_vs */ X -2, /* fc_ha */ X -1, /* fc_va */ X 0, /* fc_hi */ X 0, /* fc_vi */ X 0 /* fc_mr */ X }, X X { /* unsigned short ic_raster[64] */ X 7, X 7 X } X }; X Xstruct icon tiny_icon = X { X 0, /* ic_flags (ignored) */ X X { /* struct fcdef ic_fc */ X 1, /* fc_hs */ X 1, /* fc_vs */ X -1, /* fc_ha */ X -1, /* fc_va */ X 0, /* fc_hi */ X 0, /* fc_vi */ X 0 /* fc_mr */ X }, X X { /* unsigned short ic_raster[64] */ X 1 X } X }; X Xstruct umdata umdata; X Xvoid mouse_cursor(cursor) Xstruct icon *cursor; X { X umdata.um_icon = cursor; X X if (ioctl(wd, WIOCSETMOUSE, &umdata) < 0) X { X perror("Can't set mouse characteristics\7"); X terminate(); X } X } X Xvoid mouse_on(x, y, w, h) Xregister int x, y, w, h; X { X umdata.um_flags = MSUP | MSDOWN; X umdata.um_x = x; X umdata.um_y = y; X umdata.um_w = w; X umdata.um_h = h; X mouse_cursor(&tiny_icon); X } X Xvoid mouse_off() X { X umdata.um_flags = 0; X mouse_cursor((struct icon *)0); X } X X/*ARGSUSED*/ Xint m_null(c) Xchar c; X { X return (K_OK); X } X X/*ARGSUSED*/ Xint m_err(c) Xchar c; X { X mouse_state = 0; X return (K_OTHER); X } X X/*ARGSUSED*/ Xint m_init(c) Xchar c; X { X mouse_x = mouse_y = mouse_buttons = mouse_reason = 0; X mouse_state = 1; X return (K_OK); X } X Xint m_digit(c) Xchar c; X { X term_cbreak( ! running, delay = c - '0'); X mouse_state = 0; X return (K_OK); X } X Xint m_x(c) Xchar c; X { X mouse_x = (mouse_x * 10) + c - '0'; X return (K_OK); X } X Xint m_y(c) Xchar c; X { X mouse_y = (mouse_y * 10) + c - '0'; X return (K_OK); X } X Xint m_buttons(c) Xchar c; X { X mouse_buttons = (mouse_buttons * 10) + c - '0'; X return (K_OK); X } X Xint m_reason(c) Xchar c; X { X mouse_reason = (mouse_reason * 10) + c - '0'; X return (K_OK); X } X Xint m_key(c) Xchar c; X { X switch (c) X { X case 'w': case 'W': /* Exit key or close box selection */ X return (K_EXIT); X X default: X return (K_OTHER); X } X } X X/*ARGSUSED*/ Xint m_2(c) Xchar c; X { X mouse_state = 2; X return (K_OK); X } X X/*ARGSUSED*/ Xint m_3(c) Xchar c; X { X mouse_state = 3; X return (K_OK); X } X X/*ARGSUSED*/ Xint m_4(c) Xchar c; X { X mouse_state = 4; X return (K_OK); X } X X/*ARGSUSED*/ Xint m_5(c) Xchar c; X { X mouse_state = 5; X return (K_OK); X } X X# define LEFT_BUTTON 4 X# define MIDDLE_BUTTON 2 X# define RIGHT_BUTTON 1 X X/*ARGSUSED*/ Xint m_push(c) Xchar c; X { X extern void reversecell(), clear_the_board(); X X static int old_mouse_buttons = 0; X X if (mouse_reason & MSDOWN) X { X if (mouse_buttons & LEFT_BUTTON) X mouse_cursor(&cell_icon); X X if (mouse_buttons & MIDDLE_BUTTON) X { X running = ! running; X term_cbreak( ! running, delay); X } X X if (mouse_buttons & RIGHT_BUTTON) X clear_the_board(); X } X X if (mouse_reason & MSUP) X if (old_mouse_buttons & LEFT_BUTTON) X { X reversecell((mouse_y - yb) / ys, (mouse_x - xb) / xs); X mouse_cursor(&tiny_icon); X } X X old_mouse_buttons = mouse_buttons; X mouse_state = 0; X return (K_OK); X } X Xint (*(mouse_action[][6]))() = X { X/* State ESCAPE SEMI M O DIGIT DEFAULT */ X/* 0 */ { m_init, m_err, m_err, m_err, m_digit, m_err }, X/* 1 */ { m_err, m_2, m_err, m_5, m_x, m_null }, X/* 2 */ { m_err, m_3, m_err, m_err, m_y, m_err }, X/* 3 */ { m_err, m_4, m_err, m_err, m_buttons, m_err }, X/* 4 */ { m_err, m_err, m_push, m_err, m_reason, m_err }, X/* 5 */ { m_err, m_err, m_err, m_err, m_err, m_key }, X }; X Xint do_key(c) Xregister char c; X { X register int class; X register int (*action)(); X X/* # define ECHO_INPUT */ X# ifdef ECHO_INPUT X fprintf(stderr, c == ESC ? "<ESC>" : "%c", c); X# endif /* ECHO_INPUT */ X X switch (c) X { X case ESC: class = ESCAPE; break; X case ';': class = SEMI; break; X case 'M': class = M; break; X case 'O': class = O; break; X case '0': case '1': case '2': case '3': case '4': X case '5': case '6': case '7': case '8': case '9': X class = DIGIT; break; X default: class = DEFAULT; X } X X action = mouse_action[mouse_state][class]; X return ((*action)(c)); X } X X# include "lifegame.c" X Xvoid reversecell(row, col) Xint row, col; X { X register int index; X X row += firstrow; X col += firstcol; X index = row * NCOLS + col; X X /* X * Draw/erase a life cell X */ X if (alive[index]) X death(row, col); X else X birth(row, col); X X update_display(); X } X Xvoid clear_the_board() X { X (void)bzero(neighbors, sizeof(neighbors)); X (void)bzero(alive, sizeof(alive)); X (void)bzero(ages, sizeof(ages)); X (void)bzero(links, sizeof(links)); X head = links; X head -> l_next = 0; X erase_rectangle(0, 0, width, height); X births = deaths = cells = 0; X update_display(); X } \End\of\File\ else echo "Not overwriting ./life.c" fi if `test ! -s ./lifegame.c` then echo "Writing ./lifegame.c" sed 's/^X//' > ./lifegame.c << '\End\of\File\' X/* X * Copyright (c) 1989 Karl F. Fox, all rights reserved X * X * You may use this software for any purpose as long as you include X * this copyright notice. X */ X X# ifndef lint Xstatic char lifegame_sccs_id[] = "@(#)lifegame.c 1.1"; X# endif /* lint */ X X/* X * lifegame.c X * X * Machine-independent (more or less) implementation of John Horton X * Conway's game of life. X * X * X * How to use it: X * X * Include this file (# include "lifegame.c") from a driver program. X * The driver should call init_life_game(rows, cols, color) once and X * then call draw_life_game() followed by life_game_done() until X * the latter returns non-zero. The including file should #define X * NROWS and NCOLS (the maximum size of the cell grid), both of X * which should be powers of two unless you don't mind glacial-speed X * animation. The driver code should supply the following routines: X * X * draw(row, col, color) Display a cell. Color X * is ignored if init_life_game() X * was passed a zero color flag. X * erase(row, col) Erase a cell from the display. X * new_color(color) When using color, return a new X * color if aging cells should X * gradually color-shift. X * update_display() Flush changes to the display. X * X * Also, # define the following if you're not on a BSD system: X * X * # define srandom(seed) srand(seed) X * # define random() rand() X * # define bcmp(a,b,c) memcmp((b),(a),(c)) X * # define bzero(a,c) memset((a),0,(c)) X */ X X# include <stdio.h> X Xstatic int n_patterns, births = 0, deaths = 0, cells = 0, shot_time = 0, X shots = 0, use_color, nrows, ncols, firstrow, firstcol, lastrow, X lastcol; X Xtypedef struct link X { X struct link *l_next; X } link_t; X Xstatic link_t links[NROWS * NCOLS], *head; Xstatic unsigned char neighbors[NROWS * NCOLS], alive[NROWS * NCOLS], X ages[NROWS * NCOLS]; X Xtypedef struct X { X enum X { X c_age, X c_birth, X c_death X } c_op_code; X X union X { X int cu_index; X unsigned short cu_coord[2]; X } c_un; X# define c_index c_un.cu_index X# define c_row c_un.cu_coord[0] X# define c_col c_un.cu_coord[1] X } change_t; X Xstatic change_t changevec[NROWS * NCOLS]; X X# define HISTORY_SIZE 128 X Xstatic short history[HISTORY_SIZE], X *historyp = history, X *history_end = &history[HISTORY_SIZE]; X X# define DRAW(row,col,age) if (row >= firstrow && row <= lastrow \ X && col >= firstcol && col <= lastcol) \ X draw(row - firstrow, col - firstcol, age) X X# define ERASE(row,col) if (row >= firstrow && row <= lastrow \ X && col >= firstcol && col <= lastcol) \ X erase(row - firstrow, col - firstcol) X X# define ENQUEUE(lp) if ((lp) -> l_next == 0) \ X ((lp) -> l_next = head, \ X head = (lp)) X X# define NB_ALIVE(np, lp) if (++*(np) == 3 || *(np) == 4) \ X ENQUEUE(lp) X X# define NB_DEAD(np, lp) if (--*(np) == 3 || *(np) == 1) \ X ENQUEUE(lp) X Xstatic void birth(row, col) Xint row, col; X { X register int index = row * NCOLS + col; X register unsigned char *np; X register link_t *lp; X X alive[index] = 1; X ++cells; X ++births; X ages[index] = 0; X DRAW(row, col, 0); X X np = neighbors + index - NCOLS - 1; lp = links + index - NCOLS - 1; X NB_ALIVE(np, lp); X X ++np; ++lp; X NB_ALIVE(np, lp); X X ++np; ++lp; X NB_ALIVE(np, lp); X X np += NCOLS - 2; lp += NCOLS - 2; X NB_ALIVE(np, lp); X X ENQUEUE(lp + 1); /* This line is only needed for patterns or */ X /* shooting gliders or spaceships */ X X np += 2; lp += 2; X NB_ALIVE(np, lp); X X np += NCOLS - 2; lp += NCOLS - 2; X NB_ALIVE(np, lp); X X ++np; ++lp; X NB_ALIVE(np, lp); X X ++np; ++lp; X NB_ALIVE(np, lp); X } X Xstatic void death(row, col) Xint row, col; X { X register int index = row * NCOLS + col; X register unsigned char *np; X register link_t *lp; X X alive[index] = 0; X --cells; X ++deaths; X ERASE(row, col); X X np = neighbors + index - NCOLS - 1; lp = links + index - NCOLS - 1; X NB_DEAD(np, lp); X X ++np; ++lp; X NB_DEAD(np, lp); X X ++np; ++lp; X NB_DEAD(np, lp); X X np += NCOLS - 2; lp += NCOLS - 2; X NB_DEAD(np, lp); X X ENQUEUE(lp + 1); /* This line is only needed for patterns or */ X /* shooting gliders or spaceships */ X X np += 2; lp += 2; X NB_DEAD(np, lp); X X np += NCOLS - 2; lp += NCOLS - 2; X NB_DEAD(np, lp); X X ++np; ++lp; X NB_DEAD(np, lp); X X ++np; ++lp; X NB_DEAD(np, lp); X } X Xvoid draw_life_game() X { X register link_t *lp = head; X register change_t *cp = changevec, *endp; X X births = deaths = 0; X X while (lp) X { X register int index = lp - links; X register int row = index / NCOLS, col = index % NCOLS; X X link_t *ltmp; X X ltmp = lp; X lp = lp -> l_next; X ltmp -> l_next = 0; X X if (row > 0 && row < NROWS - 1 && col > 0 && col < NCOLS - 1) X switch (neighbors[index]) X { X case 2: /* 2 neighbors -- survives if alive */ X if (alive[index]) X { X register unsigned char *ageptr = ages + index, age; X X if (use_color X && (age = new_color((int)*ageptr)) != *ageptr) X { X *ageptr = age; X DRAW(row, col, (int)age); X cp -> c_op_code = c_age; X cp -> c_index = index; X ++cp; X } X } X X break; X X case 3: /* 3 neighbors -- birth if none yet */ X if (alive[index]) X { X register unsigned char *ageptr = ages + index, age; X X if (use_color X && (age = new_color((int)*ageptr)) != *ageptr) X { X *ageptr = age; X DRAW(row, col, (int)age); X cp -> c_op_code = c_age; X cp -> c_index = index; X ++cp; X } X } X else X { X cp -> c_op_code = c_birth; X cp -> c_row = row; X cp -> c_col = col; X ++cp; X } X X break; X X default: /* anything else -- cell dies */ X if (alive[index]) X { X cp -> c_op_code = c_death; X cp -> c_row = row; X cp -> c_col = col; X ++cp; X } X } X } X X head = links; X head -> l_next = 0; X X for (endp = cp, cp = changevec; cp < endp; ++cp) X switch (cp -> c_op_code) X { X case c_birth: birth((int)cp -> c_row, (int)cp -> c_col); break; X case c_death: death((int)cp -> c_row, (int)cp -> c_col); break; X case c_age: ENQUEUE(links + cp -> c_index); X } X X update_display(); X } X Xstatic void read_pattern(patternp) Xint *patternp; X { X extern int fclose(); X X register FILE *fp; X register int c; X register change_t *cp = changevec; X int pattern = 0, in_comment = 0, in_pattern = 0; X unsigned short row, col; X X if ((fp = fopen(PATTERN_FILE, "r")) == NULL) X { X *patternp = 0; X return; X } X X while ((c = getc(fp)) != EOF) X if (in_comment) X { X if (c == '\n') X in_comment = 0; X } X else X { X if ( ! in_pattern) X switch (c) X { X case '#': ++in_comment; continue; X case '\n': continue; X default: ++in_pattern; row = col = 1; X } X X switch (c) X { X case ' ': X ++col; X break; X X case '\t': X col = ((col + 7) & ~7) + 1; X break; X X case '\n': X col = 1; X ++row; X break; X X case '#': X if (*patternp == pattern) X { X cp -> c_op_code = c_death; X (void)fclose(fp); X return; X } X X in_pattern = 0; X ++in_comment; X ++pattern; X break; X X default: X if (*patternp == pattern) X { X cp -> c_op_code = c_birth; X cp -> c_row = row; X cp -> c_col = col; X ++cp; X } X X ++col; X } X } X X if (in_pattern) X if (*patternp == pattern) X { X cp -> c_op_code = c_death; X (void)fclose(fp); X return; X } X else X ++pattern; X X *patternp = pattern; X (void)fclose(fp); X } X Xstatic void count_patterns() X { X n_patterns = 10000; X read_pattern(&n_patterns); X } X Xvoid init_life_game(rows, cols, color) Xint rows, cols, color; X { X static int first_time = 1; X register change_t *cp; X int row, col, pattern, maxrow, maxcol, minrow, mincol, X row_offset, col_offset; X X nrows = rows; X ncols = cols; X use_color = color; X X if (first_time) X { X srandom(time((long *)0)); X count_patterns(); X first_time = 0; X } X X births = deaths = cells = shot_time = shots = 0; X historyp = history; X X firstrow = (NROWS - nrows) / 2; X firstcol = (NCOLS - ncols) / 2; X lastrow = firstrow + nrows - 1; X lastcol = firstcol + ncols - 1; X X (void)bzero(neighbors, sizeof(neighbors)); X (void)bzero(alive, sizeof(alive)); X (void)bzero(ages, sizeof(ages)); X (void)bzero(links, sizeof(links)); X X head = links; X head -> l_next = 0; X X pattern = random() % n_patterns; X read_pattern(&pattern); X X maxrow = maxcol = 0; X minrow = mincol = 10000; X X for (cp = changevec; cp -> c_op_code == c_birth; ++cp) X { X if (cp -> c_row > maxrow) maxrow = cp -> c_row; X if (cp -> c_col > maxcol) maxcol = cp -> c_col; X if (cp -> c_row < minrow) minrow = cp -> c_row; X if (cp -> c_col < mincol) mincol = cp -> c_col; X } X X row_offset = firstrow + nrows / 2 - minrow - (maxrow - minrow + 1) / 2; X col_offset = firstcol + ncols / 2 - mincol - (maxcol - mincol + 1) / 2; X X for (cp = changevec; cp -> c_op_code == c_birth; ++cp) X { X row = cp -> c_row + row_offset; X col = cp -> c_col + col_offset; X X if (row > 0 && row < NROWS - 1 && col > 0 && col < NCOLS - 1) X birth(row, col); X } X X update_display(); X (void)sleep(1); X } X Xstatic void find_target(rowp, colp) Xint *rowp, *colp; X { X register int row, col; X X for (row = firstrow; row <= lastrow; ++row) X for (col = firstcol; col <= lastcol; ++col) X if (alive[row * NCOLS + col]) X { X *rowp = row; X *colp = col; X X /* X * Don't always just pick the topmost cell. X * Look around a little bit. X */ X if ((random() & 15) == 0) X return; X } X } X Xint life_game_done() X { X int cycle = 0; X X if (cells == 0) X return (1); X X /* X * Quick and dirty way to detect cycles. Sometimes a bit hasty. X */ X *historyp++ = (births << 8) | (deaths & 0xFF); X X /* X * Check for cycles every HISTORY_SIZE generations X */ X if (historyp >= history_end) X { X register unsigned short cycle_size; X X for (cycle_size = 1; X ! cycle && cycle_size < HISTORY_SIZE / 2; X ++cycle_size) X { X register int n_cycles = HISTORY_SIZE / cycle_size, i, no_cycle = 0; X X if (n_cycles > 10) X n_cycles = 10; X X for (i = 2; ! no_cycle && i <= n_cycles; ++i) X if (bcmp(historyp - cycle_size, X historyp - (cycle_size * i), X cycle_size * sizeof *historyp) != 0) X no_cycle = 1; X X if ( ! no_cycle) X cycle = cycle_size; X } X X historyp = history; X } X X if (births == 0 && deaths == 0) X cycle = 1; X X if (shot_time) X --shot_time; X X if (shot_time == 0 && cycle) X { X int row, col; X X if (shots && (random() & 1) == 0) X return (1); X X ++shots; X find_target(&row, &col); X X if (row < 5 X || row > nrows - 5 X || (random() & 15) < 5) X { X X /* X * Shoot a (light, middleweight or heavyweight) spaceship X */ X int ship_size = (random() & 63) / 22; /* ~1/3 */ X X shot_time = 2 * col + 20; X X col = (random() & 3) + firstcol / 2; X row += (random() & 3); X X if (col > NCOLS - 6 - 1) X col = NCOLS - 6 - 1; X X if (row > NROWS - 3 - 1) X row = NROWS - 3 - 1; X X birth(1 + row, 0 + col + ship_size); X X if (ship_size < 2) X birth(0 + row, 1 + col + ship_size); X X if (ship_size < 1) X birth(0 + row, 2 + col + ship_size); X X birth(0 + row, 3 + col); X birth(0 + row, 4 + col); X birth(0 + row, 5 + col); X birth(0 + row, 6 + col); X birth(1 + row, 6 + col); X birth(2 + row, 6 + col); X birth(3 + row, 5 + col); X } X else X { X /* X * Shoot a glider X */ X shot_time = 4 * (col > row ? row : col) + 20; X X if (col > row) X col -= row, row = 0; X else X row -= col, col = 0; X X col += (random() & 3); X row += (random() & 3); X X if (firstrow < firstcol) X col += firstrow / 2, row += firstrow / 2; X else X col += firstcol / 2, row += firstcol / 2; X X if (col > NCOLS - 2 - 1) X col = NCOLS - 2 - 1; X X if (row > NROWS - 2 - 1) X row = NROWS - 2 - 1; X X birth(0 + row, 2 + col); X birth(1 + row, 2 + col); X birth(2 + row, 2 + col); X birth(2 + row, 1 + col); X birth(1 + row, 0 + col); X } X } X X return (0); X } \End\of\File\ else echo "Not overwriting ./lifegame.c" fi echo "Finished archive 1 of 1" exit -- Karl F. Fox, Morning Star Technologies, Inc. karl@MorningStar.COM
eed_wwhh@jhunix.HCF.JHU.EDU (William H Huggins) (01/12/90)
On 25 Oct 89, karl@zip.UUCP (Karl F. Fox) posted Article 446 of unix-pc.sources which presented graphic programs for displaying the outcome of Conway's Game of Life. This fascinating 'Game' and its realization by Fox on the UNIX-PC is more than just an amusement because it casts light on some of the major intellectual questions of the day (e.g. is an embryo a human being?). In a Letter to NATURE, vol 342 14 December 1989, Per Bak, Kan Chen & Michael Creutz of the Dept of Physics, Brookhaven National Laboratory, Upton, NY 11973, USA, report fascinating experiments using the outcome of running the Game of Life as analyzed using the concepts of statistical mechanics to study the long-time and large-scale behaviour of the outcomes. The abstract of the short letter is reproduced below: -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- Self-organized criticality in the 'Game of Life', Nature, vol 342, 14 December 1989, pps 780-781. ABSTRACT: THE 'Game of LIfe' is a cellular automaton, that is a lattice system in which the state of each lattice point is determined by the local rules. It simulates, by means of a simple algorithm, the dynamical evolution of a society of living organisms. Despite its simplicity, the complex dynamics of the game are poorly understood. Previous interest in 'Life' has focused on the generation of complexity in local configurations; indeed, the system has been suggested to mimic aspects of the emergence of complexity in nature [1,2]. Here we adopt a different approach, by using concepts of statistical mechanics to study the system's long-time and large-scale behaviour. We show that local configurations in the 'Game of Life' self-organize into a critical state. Such self-organized criticality provides a general mechanism for the emergence of scale-free structures [3-5], with possible applications to earth-quakes [6,7], cosmology [8], turbulence [9], biology and economics [10]. By contrast to these previous studies, where a local quantity was conserved, 'Life' has no local conservation laws and therefore represents a new type of universiality class for self-organized criticality. This refutes speculations that self-organized criticality is a consequence of local conservation [11], and supports its relevance to the natural phenomena above, as these do not involve any locally conserved quantities. The scaling is universal in the sense that the exponents which characterize correlation functions do not depend on details of the local rules. [1] Berlekamp, E.R., Conway, J.H & Guy, H.K. "Winning Ways for Your Mathematical Plays" vol 2 (Academic, 1982). [2] Gardner, M. Scientif. Am. 223(4), 120-124; (5), 118; (6), 114 (1970). [3] Bak, P., Tang, C. & Wiesenfeld, K. Phys. Rev. Lett. 69, 381-384 (1987) [4] Bak, P. & Tang, C. Phys Today 42, 527 (1989). [5] Kadanoff, L.P., Nagel, S.R., Wu, L. & Zhou, S. Phys. Rev. A39, 6524-6537 (1989). -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- I am indebted to Robert Ballentine, Dept. of Biology, Johns Hopkins University for calling this Letter to my attention, and also for noting its relevance to the remarkable book by Richard Dawkins "The Blind Watchmaker -- Why the evidence of evolution reveals a universe without design", W.W. Norton & Company (1987) paperback $7.95; ISBN 0-393-30448-5 . Norton provides a software program (for Macintoshes) designed to demonstrate the arguments developed in this book which has been acclaimed as perhaps the most influential work on evolution written in this century. W.H. Huggins The Johns Hopkins University eed_wwhh@jhunix.hcf.jhu.edu
alanf@revolver.gatech.edu (Daniel Alan Fleming) (01/16/90)
In article <3934@jhunix.HCF.JHU.EDU> eed_wwhh@jhunix.HCF.JHU.EDU (William H Huggins) writes: >On 25 Oct 89, karl@zip.UUCP (Karl F. Fox) posted Article 446 of >unix-pc.sources which presented graphic programs for displaying the >outcome of Conway's Game of Life. This is one of those posting that everyone hates. I just bought a Unix PC and just reading Unix-pc.sources. Since I enjoy "Life" and don't have a version for my machine, I would be interested in finding out if there is an archive for Unix-pc.sources that I can get this from via ftp or mail. If not, could anyone send me a copy? Anyone with info on AT&T 7300 Unix-pc's that wants to hand out hints on hardware or software please mail... Thank you for you help and patience. ------------------------------------------------------------------------------ computer: | real time: alanf@revolver.gatech.edu - name | Alan Fleming alanf%revolver.gatech.edu@gatech.edu - site | 2515 NE Expressway, Apt. N-2 ...!gatech!alanf@revolver.gatech.edu - UUCP | Atlanta, Ga. 30345 | (404)/634-8014 ------------------------------------------------------------------------------