447 lines
8.5 KiB
C
447 lines
8.5 KiB
C
/*
|
|
* life - john conways's game of life (and variations),
|
|
* sci. am. 223, october 1970, pp. 120—123, or
|
|
* http://en.wikipedia.org/wiki/Conway's_Game_of_Life
|
|
*/
|
|
#include <u.h>
|
|
#include <libc.h>
|
|
#include <bio.h>
|
|
#include <draw.h>
|
|
#include <event.h>
|
|
|
|
enum {
|
|
NLIFE = 256, /* life array size */
|
|
PX = 4, /* cell spacing */
|
|
BX = PX - 1, /* box size */
|
|
NADJUST = NLIFE * NLIFE,
|
|
};
|
|
|
|
/*
|
|
* life[i][j] stores L+2*N, where L is 0 if the cell is dead and 1
|
|
* if alive, and N is the number of the cell's 8-connected neighbours
|
|
* which live.
|
|
* row[i] indicates how many cells are alive in life[i][*].
|
|
* col[j] indicates how many cells are alive in life[*][j].
|
|
* Adjust contains pointers to cells that need to have their neighbour
|
|
* counts adjusted in the second pass of the generation procedure.
|
|
*/
|
|
char life[NLIFE][NLIFE];
|
|
int row[NLIFE];
|
|
int col[NLIFE];
|
|
char action[18]; /* index by cell contents to find action */
|
|
char *adjust[NADJUST];
|
|
|
|
Point cen;
|
|
Image *bg, *box;
|
|
int i0, i1, j0, j1;
|
|
int needresize;
|
|
int reverse;
|
|
|
|
void birth(int, int);
|
|
void centerlife(void);
|
|
void death(int, int);
|
|
int generate(void);
|
|
int interest(int [NLIFE], int);
|
|
void main(int, char *[]);
|
|
int min(int, int);
|
|
void readlife(char *);
|
|
void redraw(void);
|
|
void setrules(char *);
|
|
void window(void);
|
|
|
|
static void reshape(void);
|
|
|
|
static void
|
|
setbox(int i, int j)
|
|
{
|
|
Point loc;
|
|
|
|
loc = Pt(cen.x + j*PX, cen.y + i*PX);
|
|
draw(screen, Rpt(loc, addpt(loc, Pt(BX, BX))), box, nil, ZP);
|
|
}
|
|
|
|
static void
|
|
clrbox(int i, int j)
|
|
{
|
|
Point loc;
|
|
|
|
loc = Pt(cen.x + j*PX, cen.y + i*PX);
|
|
draw(screen, Rpt(loc, addpt(loc, Pt(BX, BX))), bg, nil, ZP);
|
|
}
|
|
|
|
void
|
|
setrules(char *r)
|
|
{
|
|
char *a;
|
|
|
|
for (a = action; a != &action[nelem(action)]; *a++ = *r++)
|
|
;
|
|
}
|
|
|
|
static void
|
|
g9err(Display *, char *err)
|
|
{
|
|
static int entered = 0;
|
|
|
|
fprint(2, "%s: %s (%r)\n", argv0, err);
|
|
exits(err);
|
|
}
|
|
|
|
void
|
|
usage(void)
|
|
{
|
|
fprint(2, "Usage: %s [-3bo] [-d delay] [-r rules] file\n", argv0);
|
|
exits("usage");
|
|
}
|
|
|
|
void
|
|
idle(void)
|
|
{
|
|
int c;
|
|
|
|
while (ecanmouse())
|
|
emouse(); /* throw away mouse events */
|
|
while (ecankbd())
|
|
if ((c = ekbd()) == 'q' || c == 0177) /* watch keyboard ones */
|
|
exits(nil);
|
|
if (needresize)
|
|
reshape();
|
|
}
|
|
|
|
void
|
|
main(int argc, char *argv[])
|
|
{
|
|
int delay = 1000;
|
|
|
|
setrules(".d.d..b..d.d.d.d.d"); /* regular rules */
|
|
ARGBEGIN {
|
|
case '3':
|
|
setrules(".d.d.db.b..d.d.d.d");
|
|
break; /* 34-life */
|
|
case 'b':
|
|
reverse = ~0xff;
|
|
break;
|
|
case 'd':
|
|
delay = atoi(EARGF(usage()));
|
|
if(delay < 0)
|
|
sysfatal("invalid delay: %d", delay);
|
|
break;
|
|
case 'o':
|
|
setrules(".d.d.db.b.b..d.d.d");
|
|
break; /* lineosc? */
|
|
case 'r': /* rules from cmdline */
|
|
setrules(EARGF(usage()));
|
|
break;
|
|
default:
|
|
usage();
|
|
} ARGEND
|
|
if (argc != 1)
|
|
usage();
|
|
|
|
initdraw(g9err, 0, argv0);
|
|
einit(Emouse|Ekeyboard); /* implies rawon() */
|
|
|
|
cen = divpt(subpt(addpt(screen->r.min, screen->r.max),
|
|
Pt(NLIFE * PX, NLIFE * PX)), 2);
|
|
|
|
bg = allocimage(display, Rect(0,0,1,1), screen->chan, 1, DWhite^reverse);
|
|
if(bg == nil)
|
|
sysfatal("allocimage: %r");
|
|
box = allocimage(display, Rect(0,0,BX,BX), screen->chan, 1, DBlack^reverse);
|
|
if(box == nil)
|
|
sysfatal("allocimage: %r");
|
|
|
|
redraw();
|
|
readlife(argv[0]);
|
|
do {
|
|
flushimage(display, 1);
|
|
idle();
|
|
sleep(delay);
|
|
idle();
|
|
} while (generate());
|
|
exits(nil);
|
|
}
|
|
|
|
/*
|
|
* We can only have interest in a given row (or column) if there
|
|
* is something alive in it or in the neighbouring rows (or columns.)
|
|
*/
|
|
int
|
|
interest(int rc[NLIFE], int i)
|
|
{
|
|
return(rc[i-1] != 0 || rc[i] != 0 || rc[i+1] != 0);
|
|
}
|
|
|
|
/*
|
|
* A life generation proceeds in two passes. The first pass identifies
|
|
* cells that have births or deaths. The `alive bit' is updated, as are
|
|
* the screen and the row/col count deltas. Also, a record is made
|
|
* of the cell's address. In the second pass, the neighbours of all changed
|
|
* cells get their neighbour counts updated, and the row/col deltas get
|
|
* merged into the row/col count arrays.
|
|
*
|
|
* The border cells (i==0 || i==NLIFE-1 || j==0 || j==NLIFE-1) are not
|
|
* processed, purely for speed reasons. With a little effort, a wrap-around
|
|
* universe could be implemented.
|
|
*
|
|
* Generate returns 0 if there was no change from the last generation,
|
|
* and 1 if there were changes.
|
|
*/
|
|
#define neighbour(di, dj, op) lp[(di)*NLIFE+(dj)] op= 2
|
|
#define neighbours(op)\
|
|
neighbour(-1, -1, op);\
|
|
neighbour(-1, 0, op);\
|
|
neighbour(-1, 1, op);\
|
|
neighbour( 0, -1, op);\
|
|
neighbour( 0, 1, op);\
|
|
neighbour( 1, -1, op);\
|
|
neighbour( 1, 0, op);\
|
|
neighbour( 1, 1, op)
|
|
|
|
int
|
|
generate(void)
|
|
{
|
|
char *lp;
|
|
char **p, **addp, **delp;
|
|
int i, j, j0 = NLIFE, j1 = -1;
|
|
int drow[NLIFE], dcol[NLIFE];
|
|
|
|
for (j = 1; j != NLIFE - 1; j++) {
|
|
drow[j] = dcol[j] = 0;
|
|
if (interest(col, j)) {
|
|
if (j < j0)
|
|
j0 = j;
|
|
if (j1 < j)
|
|
j1 = j;
|
|
}
|
|
}
|
|
addp = adjust;
|
|
delp = &adjust[NADJUST];
|
|
for (i = 1; i != NLIFE - 1; i++)
|
|
if (interest(row, i)) {
|
|
for (j = j0, lp = &life[i][j0]; j <= j1; j++, lp++)
|
|
switch (action[*lp]) {
|
|
case 'b':
|
|
++*lp;
|
|
++drow[i];
|
|
++dcol[j];
|
|
setbox(i, j);
|
|
*addp++ = lp;
|
|
break;
|
|
case 'd':
|
|
--*lp;
|
|
--drow[i];
|
|
--dcol[j];
|
|
clrbox(i, j);
|
|
*--delp = lp;
|
|
break;
|
|
}
|
|
}
|
|
if (addp == adjust && delp == &adjust[NADJUST])
|
|
return 0;
|
|
if (delp < addp)
|
|
sysfatal("Out of space (delp < addp)");
|
|
p = adjust;
|
|
while (p != addp) {
|
|
lp = *p++;
|
|
neighbours(+);
|
|
}
|
|
p = delp;
|
|
while (p != &adjust[NADJUST]) {
|
|
lp = *p++;
|
|
neighbours(-);
|
|
}
|
|
for (i = 1; i != NLIFE - 1; i++) {
|
|
row[i] += drow[i];
|
|
col[i] += dcol[i];
|
|
}
|
|
if (row[1] || row[NLIFE-2] || col[1] || col[NLIFE-2])
|
|
centerlife();
|
|
return 1;
|
|
}
|
|
|
|
/*
|
|
* Record a birth at (i,j).
|
|
*/
|
|
void
|
|
birth(int i, int j)
|
|
{
|
|
char *lp;
|
|
|
|
if (i < 1 || NLIFE - 1 <= i || j < 1 || NLIFE - 1 <= j ||
|
|
life[i][j] & 1)
|
|
return;
|
|
lp = &life[i][j];
|
|
++*lp;
|
|
++row[i];
|
|
++col[j];
|
|
neighbours(+);
|
|
setbox(i, j);
|
|
}
|
|
|
|
/*
|
|
* Record a death at (i,j)
|
|
*/
|
|
void
|
|
death(int i, int j)
|
|
{
|
|
char *lp;
|
|
|
|
if (i < 1 || NLIFE - 1 <= i || j < 1 || NLIFE - 1 <= j ||
|
|
!(life[i][j] & 1))
|
|
return;
|
|
lp = &life[i][j];
|
|
--*lp;
|
|
--row[i];
|
|
--col[j];
|
|
neighbours(-);
|
|
clrbox(i, j);
|
|
}
|
|
|
|
void
|
|
readlife(char *filename)
|
|
{
|
|
int c, i, j;
|
|
char name[256];
|
|
Biobuf *bp;
|
|
|
|
if ((bp = Bopen(filename, OREAD)) == nil) {
|
|
snprint(name, sizeof name, "/sys/games/lib/life/%s", filename);
|
|
if ((bp = Bopen(name, OREAD)) == nil)
|
|
sysfatal("can't read %s: %r", name);
|
|
}
|
|
draw(screen, screen->r, bg, nil, ZP);
|
|
for (i = 0; i != NLIFE; i++) {
|
|
row[i] = col[i] = 0;
|
|
for (j = 0; j != NLIFE; j++)
|
|
life[i][j] = 0;
|
|
}
|
|
c = 0;
|
|
for (i = 1; i != NLIFE - 1 && c >= 0; i++) {
|
|
j = 1;
|
|
while ((c = Bgetc(bp)) >= 0 && c != '\n')
|
|
if (j != NLIFE - 1)
|
|
switch (c) {
|
|
case '.':
|
|
j++;
|
|
break;
|
|
case 'x':
|
|
birth(i, j);
|
|
j++;
|
|
break;
|
|
}
|
|
}
|
|
Bterm(bp);
|
|
centerlife();
|
|
}
|
|
|
|
int
|
|
min(int a, int b)
|
|
{
|
|
return(a < b ? a : b);
|
|
}
|
|
|
|
void
|
|
centerlife(void)
|
|
{
|
|
int i, j, di, dj, iinc, jinc, t;
|
|
|
|
window();
|
|
di = NLIFE / 2 - (i0 + i1) / 2;
|
|
if (i0 + di < 1)
|
|
di = 1 - i0;
|
|
else if (i1 + di >= NLIFE - 1)
|
|
di = NLIFE - 2 - i1;
|
|
dj = NLIFE / 2 - (j0 + j1) / 2;
|
|
if (j0 + dj < 1)
|
|
dj = 1 - j0;
|
|
else if (j1 + dj >= NLIFE - 1)
|
|
dj = NLIFE - 2 - j1;
|
|
if (di != 0 || dj != 0) {
|
|
if (di > 0) {
|
|
iinc = -1;
|
|
t = i0;
|
|
i0 = i1;
|
|
i1 = t;
|
|
} else
|
|
iinc = 1;
|
|
if (dj > 0) {
|
|
jinc = -1;
|
|
t = j0;
|
|
j0 = j1;
|
|
j1 = t;
|
|
} else
|
|
jinc = 1;
|
|
for (i = i0; i * iinc <= i1 * iinc; i += iinc)
|
|
for (j = j0; j * jinc <= j1 * jinc; j += jinc)
|
|
if (life[i][j] & 1) {
|
|
birth(i + di, j + dj);
|
|
death(i, j);
|
|
}
|
|
}
|
|
}
|
|
|
|
void
|
|
redraw(void)
|
|
{
|
|
int i, j;
|
|
|
|
window();
|
|
draw(screen, screen->r, bg, nil, ZP);
|
|
for (i = i0; i <= i1; i++)
|
|
for (j = j0; j <= j1; j++)
|
|
if (life[i][j] & 1)
|
|
setbox(i, j);
|
|
}
|
|
|
|
void
|
|
window(void)
|
|
{
|
|
for (i0 = 1; i0 != NLIFE - 2 && row[i0] == 0; i0++)
|
|
;
|
|
for (i1 = NLIFE - 2; i1 != i0 && row[i1] == 0; --i1)
|
|
;
|
|
for (j0 = 1; j0 != NLIFE - 2 && col[j0] == 0; j0++)
|
|
;
|
|
for (j1 = NLIFE - 2; j1 != j0 && col[j1] == 0; --j1)
|
|
;
|
|
}
|
|
|
|
static void
|
|
reshape(void)
|
|
{
|
|
// int dy12;
|
|
|
|
// if (needresize) {
|
|
// sqwid = Dx(screen->r) / (1 + bdp->cols + 1);
|
|
// dy12 = Dy(screen->r) / (1 + bdp->rows + 1 + 2);
|
|
// if (sqwid > dy12)
|
|
// sqwid = dy12;
|
|
// recompute(bdp, sqwid);
|
|
// }
|
|
sleep(1000);
|
|
needresize = 0;
|
|
cen = divpt(subpt(addpt(screen->r.min, screen->r.max),
|
|
Pt(NLIFE * PX, NLIFE * PX)), 2);
|
|
redraw();
|
|
flushimage(display, 1);
|
|
}
|
|
|
|
/* called from graphics library */
|
|
void
|
|
eresized(int callgetwin)
|
|
{
|
|
needresize = callgetwin + 1;
|
|
|
|
/* new window? */
|
|
/* was using Refmesg */
|
|
if (needresize > 1 && getwindow(display, Refnone) < 0)
|
|
sysfatal("can't reattach to window: %r");
|
|
|
|
/* destroyed window? */
|
|
if (Dx(screen->r) == 0 || Dy(screen->r) == 0)
|
|
exits("window gone");
|
|
|
|
reshape();
|
|
}
|