1 /*
2 * life - john conways's game of life (and variations),
3 * sci. am. 223, october 1970, pp. 120—123, or
4 * http://en.wikipedia.org/wiki/Conway's_Game_of_Life
5 */
6 #include <u.h>
7 #include <libc.h>
8 #include <bio.h>
9 #include <draw.h>
10 #include <event.h>
11
12 enum {
13 NLIFE = 256, /* life array size */
14 PX = 4, /* cell spacing */
15 BX = PX - 1, /* box size */
16 NADJUST = NLIFE * NLIFE,
17 };
18
19 /*
20 * life[i][j] stores L+2*N, where L is 0 if the cell is dead and 1
21 * if alive, and N is the number of the cell's 8-connected neighbours
22 * which live.
23 * row[i] indicates how many cells are alive in life[i][*].
24 * col[j] indicates how many cells are alive in life[*][j].
25 * Adjust contains pointers to cells that need to have their neighbour
26 * counts adjusted in the second pass of the generation procedure.
27 */
28 char life[NLIFE][NLIFE];
29 int row[NLIFE];
30 int col[NLIFE];
31 char action[18]; /* index by cell contents to find action */
32 char *adjust[NADJUST];
33 int delay;
34
35 Point cen;
36 Image *box;
37 int i0, i1, j0, j1;
38 int needresize;
39
40 void birth(int, int);
41 void centerlife(void);
42 void death(int, int);
43 int generate(void);
44 int interest(int [NLIFE], int);
45 void main(int, char *[]);
46 int min(int, int);
47 void readlife(char *);
48 void redraw(void);
49 void setrules(char *);
50 void window(void);
51
52 static void reshape(void);
53
54 static void
setbox(int i,int j)55 setbox(int i, int j)
56 {
57 Point loc;
58
59 loc = Pt(cen.x + j*PX, cen.y + i*PX);
60 draw(screen, Rpt(loc, addpt(loc, Pt(BX, BX))), box, nil, ZP);
61 }
62
63 static void
clrbox(int i,int j)64 clrbox(int i, int j)
65 {
66 Point loc;
67
68 loc = Pt(cen.x + j*PX, cen.y + i*PX);
69 draw(screen, Rpt(loc, addpt(loc, Pt(BX, BX))), display->white, nil, ZP);
70 }
71
72 void
setrules(char * r)73 setrules(char *r)
74 {
75 char *a;
76
77 for (a = action; a != &action[nelem(action)]; *a++ = *r++)
78 ;
79 }
80
81 static void
g9err(Display *,char * err)82 g9err(Display *, char *err)
83 {
84 static int entered = 0;
85
86 fprint(2, "%s: %s (%r)\n", argv0, err);
87 exits(err);
88 }
89
90 void
usage(void)91 usage(void)
92 {
93 fprint(2, "Usage: %s [-3o] [-r rules] file\n", argv0);
94 exits("usage");
95 }
96
97 void
idle(void)98 idle(void)
99 {
100 int c;
101
102 while (ecanmouse())
103 emouse(); /* throw away mouse events */
104 while (ecankbd()){
105 c = ekbd();
106 if (c == 'q' || c == 0177) /* watch keyboard ones */
107 exits(nil);
108 if (c >= '1' && c <= '9')
109 delay = (c - '0') * 100;
110 else if (c == '0')
111 delay = 1000;
112 }
113 if (needresize)
114 reshape();
115 }
116
117 void
main(int argc,char * argv[])118 main(int argc, char *argv[])
119 {
120 delay = 1000;
121 setrules(".d.d..b..d.d.d.d.d"); /* regular rules */
122 ARGBEGIN {
123 case '3':
124 setrules(".d.d.db.b..d.d.d.d");
125 break; /* 34-life */
126 case 'o':
127 setrules(".d.d.db.b.b..d.d.d");
128 break; /* lineosc? */
129 case 'r': /* rules from cmdline */
130 setrules(EARGF(usage()));
131 break;
132 default:
133 usage();
134 } ARGEND
135 if (argc != 1)
136 usage();
137
138 initdraw(g9err, 0, argv0);
139 einit(Emouse|Ekeyboard); /* implies rawon() */
140
141 cen = divpt(subpt(addpt(screen->r.min, screen->r.max),
142 Pt(NLIFE * PX, NLIFE * PX)), 2);
143 box = allocimage(display, Rect(0, 0, BX, BX), RGB24, 1, DBlack);
144 assert(box != nil);
145
146 redraw();
147 readlife(argv[0]);
148 do {
149 flushimage(display, 1);
150 idle();
151 sleep(delay);
152 idle();
153 } while (generate());
154 exits(nil);
155 }
156
157 /*
158 * We can only have interest in a given row (or column) if there
159 * is something alive in it or in the neighbouring rows (or columns.)
160 */
161 int
interest(int rc[NLIFE],int i)162 interest(int rc[NLIFE], int i)
163 {
164 return(rc[i-1] != 0 || rc[i] != 0 || rc[i+1] != 0);
165 }
166
167 /*
168 * A life generation proceeds in two passes. The first pass identifies
169 * cells that have births or deaths. The `alive bit' is updated, as are
170 * the screen and the row/col count deltas. Also, a record is made
171 * of the cell's address. In the second pass, the neighbours of all changed
172 * cells get their neighbour counts updated, and the row/col deltas get
173 * merged into the row/col count arrays.
174 *
175 * The border cells (i==0 || i==NLIFE-1 || j==0 || j==NLIFE-1) are not
176 * processed, purely for speed reasons. With a little effort, a wrap-around
177 * universe could be implemented.
178 *
179 * Generate returns 0 if there was no change from the last generation,
180 * and 1 if there were changes.
181 */
182 #define neighbour(di, dj, op) lp[(di)*NLIFE+(dj)] op= 2
183 #define neighbours(op)\
184 neighbour(-1, -1, op);\
185 neighbour(-1, 0, op);\
186 neighbour(-1, 1, op);\
187 neighbour( 0, -1, op);\
188 neighbour( 0, 1, op);\
189 neighbour( 1, -1, op);\
190 neighbour( 1, 0, op);\
191 neighbour( 1, 1, op)
192
193 int
generate(void)194 generate(void)
195 {
196 char *lp;
197 char **p, **addp, **delp;
198 int i, j, j0 = NLIFE, j1 = -1;
199 int drow[NLIFE], dcol[NLIFE];
200
201 for (j = 1; j != NLIFE - 1; j++) {
202 drow[j] = dcol[j] = 0;
203 if (interest(col, j)) {
204 if (j < j0)
205 j0 = j;
206 if (j1 < j)
207 j1 = j;
208 }
209 }
210 addp = adjust;
211 delp = &adjust[NADJUST];
212 for (i = 1; i != NLIFE - 1; i++)
213 if (interest(row, i)) {
214 for (j = j0, lp = &life[i][j0]; j <= j1; j++, lp++)
215 switch (action[*lp]) {
216 case 'b':
217 ++*lp;
218 ++drow[i];
219 ++dcol[j];
220 setbox(i, j);
221 *addp++ = lp;
222 break;
223 case 'd':
224 --*lp;
225 --drow[i];
226 --dcol[j];
227 clrbox(i, j);
228 *--delp = lp;
229 break;
230 }
231 }
232 if (addp == adjust && delp == &adjust[NADJUST])
233 return 0;
234 if (delp < addp)
235 sysfatal("Out of space (delp < addp)");
236 p = adjust;
237 while (p != addp) {
238 lp = *p++;
239 neighbours(+);
240 }
241 p = delp;
242 while (p != &adjust[NADJUST]) {
243 lp = *p++;
244 neighbours(-);
245 }
246 for (i = 1; i != NLIFE - 1; i++) {
247 row[i] += drow[i];
248 col[i] += dcol[i];
249 }
250 if (row[1] || row[NLIFE-2] || col[1] || col[NLIFE-2])
251 centerlife();
252 return 1;
253 }
254
255 /*
256 * Record a birth at (i,j).
257 */
258 void
birth(int i,int j)259 birth(int i, int j)
260 {
261 char *lp;
262
263 if (i < 1 || NLIFE - 1 <= i || j < 1 || NLIFE - 1 <= j ||
264 life[i][j] & 1)
265 return;
266 lp = &life[i][j];
267 ++*lp;
268 ++row[i];
269 ++col[j];
270 neighbours(+);
271 setbox(i, j);
272 }
273
274 /*
275 * Record a death at (i,j)
276 */
277 void
death(int i,int j)278 death(int i, int j)
279 {
280 char *lp;
281
282 if (i < 1 || NLIFE - 1 <= i || j < 1 || NLIFE - 1 <= j ||
283 !(life[i][j] & 1))
284 return;
285 lp = &life[i][j];
286 --*lp;
287 --row[i];
288 --col[j];
289 neighbours(-);
290 clrbox(i, j);
291 }
292
293 void
readlife(char * filename)294 readlife(char *filename)
295 {
296 int c, i, j;
297 char name[256];
298 Biobuf *bp;
299
300 if ((bp = Bopen(filename, OREAD)) == nil) {
301 snprint(name, sizeof name, "/sys/games/lib/life/%s", filename);
302 if ((bp = Bopen(name, OREAD)) == nil)
303 sysfatal("can't read %s: %r", name);
304 }
305 draw(screen, screen->r, display->white, nil, ZP);
306 for (i = 0; i != NLIFE; i++) {
307 row[i] = col[i] = 0;
308 for (j = 0; j != NLIFE; j++)
309 life[i][j] = 0;
310 }
311 c = 0;
312 for (i = 1; i != NLIFE - 1 && c >= 0; i++) {
313 j = 1;
314 while ((c = Bgetc(bp)) >= 0 && c != '\n')
315 if (j != NLIFE - 1)
316 switch (c) {
317 case '.':
318 j++;
319 break;
320 case 'x':
321 birth(i, j);
322 j++;
323 break;
324 }
325 }
326 Bterm(bp);
327 centerlife();
328 }
329
330 int
min(int a,int b)331 min(int a, int b)
332 {
333 return(a < b ? a : b);
334 }
335
336 void
centerlife(void)337 centerlife(void)
338 {
339 int i, j, di, dj, iinc, jinc, t;
340
341 window();
342 di = NLIFE / 2 - (i0 + i1) / 2;
343 if (i0 + di < 1)
344 di = 1 - i0;
345 else if (i1 + di >= NLIFE - 1)
346 di = NLIFE - 2 - i1;
347 dj = NLIFE / 2 - (j0 + j1) / 2;
348 if (j0 + dj < 1)
349 dj = 1 - j0;
350 else if (j1 + dj >= NLIFE - 1)
351 dj = NLIFE - 2 - j1;
352 if (di != 0 || dj != 0) {
353 if (di > 0) {
354 iinc = -1;
355 t = i0;
356 i0 = i1;
357 i1 = t;
358 } else
359 iinc = 1;
360 if (dj > 0) {
361 jinc = -1;
362 t = j0;
363 j0 = j1;
364 j1 = t;
365 } else
366 jinc = 1;
367 for (i = i0; i * iinc <= i1 * iinc; i += iinc)
368 for (j = j0; j * jinc <= j1 * jinc; j += jinc)
369 if (life[i][j] & 1) {
370 birth(i + di, j + dj);
371 death(i, j);
372 }
373 }
374 }
375
376 void
redraw(void)377 redraw(void)
378 {
379 int i, j;
380
381 window();
382 draw(screen, screen->r, display->white, nil, ZP);
383 for (i = i0; i <= i1; i++)
384 for (j = j0; j <= j1; j++)
385 if (life[i][j] & 1)
386 setbox(i, j);
387 }
388
389 void
window(void)390 window(void)
391 {
392 for (i0 = 1; i0 != NLIFE - 2 && row[i0] == 0; i0++)
393 ;
394 for (i1 = NLIFE - 2; i1 != i0 && row[i1] == 0; --i1)
395 ;
396 for (j0 = 1; j0 != NLIFE - 2 && col[j0] == 0; j0++)
397 ;
398 for (j1 = NLIFE - 2; j1 != j0 && col[j1] == 0; --j1)
399 ;
400 }
401
402 static void
reshape(void)403 reshape(void)
404 {
405 // int dy12;
406
407 // if (needresize) {
408 // sqwid = Dx(screen->r) / (1 + bdp->cols + 1);
409 // dy12 = Dy(screen->r) / (1 + bdp->rows + 1 + 2);
410 // if (sqwid > dy12)
411 // sqwid = dy12;
412 // recompute(bdp, sqwid);
413 // }
414 sleep(1000);
415 needresize = 0;
416 cen = divpt(subpt(addpt(screen->r.min, screen->r.max),
417 Pt(NLIFE * PX, NLIFE * PX)), 2);
418 redraw();
419 flushimage(display, 1);
420 }
421
422 /* called from graphics library */
423 void
eresized(int callgetwin)424 eresized(int callgetwin)
425 {
426 needresize = callgetwin + 1;
427
428 /* new window? */
429 /* was using Refmesg */
430 if (needresize > 1 && getwindow(display, Refnone) < 0)
431 sysfatal("can't reattach to window: %r");
432
433 /* destroyed window? */
434 if (Dx(screen->r) == 0 || Dy(screen->r) == 0)
435 exits("window gone");
436
437 reshape();
438 }
439