harvey/sys/src/games/life.c

/*
 * This file is part of the UCB release of Plan 9. It is subject to the license
 * terms in the LICENSE file found in the top-level directory of this
 * distribution and at http://akaros.cs.berkeley.edu/files/Plan9License. No
 * part of the UCB release of Plan 9, including this file, may be copied,
 * modified, propagated, or distributed except according to the terms contained
 * in the LICENSE file.
 */

/*
 * 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];
int		delay;

Point	cen;
Image	*box;
int	i0, i1, j0, j1;
int	needresize;

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))), display->white, nil, ZP);
}

void
setrules(char *r)
{
	char *a;

	for (a = action; a != &action[nelem(action)]; *a++ = *r++)
		;
}

static void
g9err(Display *d, char *err)
{
	fprint(2, "%s: %s (%r)\n", argv0, err);
	exits(err);
}

void
usage(void)
{
	fprint(2, "Usage: %s [-3o] [-r rules] file\n", argv0);
	exits("usage");
}

void
idle(void)
{
	int c;

	while (ecanmouse())
		emouse();			/* throw away mouse events */
	while (ecankbd()){
		c = ekbd();
		if (c  == 'q' || c == 0177) /* watch keyboard ones */
			exits(nil);
		if (c >= '1' && c <= '9')
			delay = (c - '0') * 100;
		else if (c == '0')
			delay = 1000;
	}
	if (needresize)
		reshape();
}

void
main(int argc, char *argv[])
{
	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 '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);
	box  = allocimage(display, Rect(0, 0, BX, BX), RGB24, 1, DBlack);
	assert(box != nil);

	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[(int)*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, display->white, 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, display->white, 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();
}