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