sys/src/games/life.c

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