apps/plugins/rocklife.c

   1 /***************************************************************************
   2  *             __________               __   ___.
   3  *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
   4  *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
   5  *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
   6  *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
   7  *                     \/            \/     \/    \/            \/
   8  * $Id$
   9  *
  10  * Copyright (C) 2007 Matthias Wientapper
  11  *
  12  * This program is free software; you can redistribute it and/or
  13  * modify it under the terms of the GNU General Public License
  14  * as published by the Free Software Foundation; either version 2
  15  * of the License, or (at your option) any later version.
  16  *
  17  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  18  * KIND, either express or implied.
  19  *
  20  ****************************************************************************/
  21
  22 /*
  23  * This is an implementatino of Conway's Game of Life
  24  *
  25  * from http://en.wikipedia.org/wiki/Conway's_Game_of_Life:
  26  *
  27  * Rules
  28  *
  29  * The universe of the Game of Life is an infinite two-dimensional
  30  * orthogonal grid of square cells, each of which is in one of two
  31  * possible states, live or dead. Every cell interacts with its eight
  32  * neighbours, which are the cells that are directly horizontally,
  33  * vertically, or diagonally adjacent. At each step in time, the
  34  * following transitions occur:
  35  *
  36  * 1. Any live cell with fewer than two live neighbours dies, as if by
  37  *    loneliness.
  38  *
  39  * 2. Any live cell with more than three live neighbours dies, as if
  40  *    by overcrowding.
  41  *
  42  * 3. Any live cell with two or three live neighbours lives,
  43  *    unchanged, to the next generation.
  44  *
  45  * 4. Any dead cell with exactly three live neighbours comes to life.
  46  *
  47  * The initial pattern constitutes the first generation of the
  48  * system. The second generation is created by applying the above
  49  * rules simultaneously to every cell in the first generation --
  50  * births and deaths happen simultaneously, and the discrete moment at
  51  * which this happens is sometimes called a tick. (In other words,
  52  * each generation is based entirely on the one before.) The rules
  53  * continue to be applied repeatedly to create further generations.
  54  *
  55  *
  56  *
  57  * TODO:
  58  *       - nicer colours for pixels with respect to age
  59  *       - editor for start patterns
  60  *       - probably tons of speed-up opportunities
  61  */
  62
  63 #include "plugin.h"
  64 #include "lib/pluginlib_actions.h"
  65 #include "lib/helper.h"
  66
  67
  68
  69 #define ROCKLIFE_PLAY_PAUSE PLA_SELECT
  70 #define ROCKLIFE_INIT       PLA_DOWN
  71 #define ROCKLIFE_NEXT       PLA_RIGHT
  72 #define ROCKLIFE_NEXT_REP   PLA_RIGHT_REPEAT
  73 #define ROCKLIFE_QUIT       PLA_CANCEL
  74 #define ROCKLIFE_STATUS     PLA_LEFT
  75
  76 #define PATTERN_RANDOM     0
  77 #define PATTERN_GROWTH_1   1
  78 #define PATTERN_GROWTH_2   2
  79 #define PATTERN_ACORN      3
  80 #define PATTERN_GLIDER_GUN 4
  81
  82 const struct button_mapping *plugin_contexts[]
  83 = {pla_main_ctx};
  84
  85 #define GRID_W LCD_WIDTH
  86 #define GRID_H LCD_HEIGHT
  87
  88 unsigned char grid_a[GRID_W][GRID_H];
  89 unsigned char grid_b[GRID_W][GRID_H];
  90 int generation = 0;
  91 int population = 0;
  92 int status_line = 0;
  93
  94
  95 static inline bool is_valid_cell(int x, int y) {
  96     return (x >= 0 && x < GRID_W
  97             && y >= 0 && y < GRID_H);
  98 }
  99
 100 static inline void set_cell_age(int x, int y, unsigned char age, char *pgrid) {
 101     pgrid[x+y*GRID_W] = age;
 102 }
 103
 104 static inline void set_cell(int x, int y, char *pgrid) {
 105     set_cell_age(x, y, 1, pgrid);
 106 }
 107
 108 static inline unsigned char get_cell(int x, int y, char *pgrid) {
 109     if (x < 0)
 110         x += GRID_W;
 111     else if (x >= GRID_W)
 112         x -= GRID_W;
 113
 114     if (y < 0)
 115         y += GRID_H;
 116     else if (y >= GRID_H)
 117         y -= GRID_H;
 118
 119     return pgrid[x+y*GRID_W];
 120 }
 121
 122 /* clear grid */
 123 static void init_grid(char *pgrid){
 124     memset(pgrid, 0, GRID_W * GRID_H);
 125 }
 126
 127 /*fill grid with pattern from file (viewer mode)*/
 128 static bool load_cellfile(const char *file, char *pgrid){
 129     int fd;
 130     fd = rb->open(file, O_RDONLY);
 131     if (fd<0)
 132         return false;
 133
 134     init_grid(pgrid);
 135
 136     char c;
 137     int nc, x, y, xmid, ymid;
 138     bool comment;
 139     x=0;
 140     y=0;
 141     xmid = (GRID_W>>1) - 2;
 142     ymid = (GRID_H>>1) - 2;
 143     comment = false;
 144
 145     while (true) {
 146         nc = rb->read(fd, &c, 1);
 147         if (nc <= 0)
 148             break;
 149
 150         switch(c) {
 151         case '!':
 152             comment = true;
 153         case '.':
 154             if (!comment)
 155                 x++;
 156             break;
 157         case 'O':
 158             if (!comment) {
 159                 if (is_valid_cell(xmid + x, ymid + y))
 160                     set_cell(xmid + x, ymid + y, pgrid);
 161                 x++;
 162             }
 163             break;
 164         case '\n':
 165             y++;
 166             x=0;
 167             comment = false;
 168             break;
 169         default:
 170             break;
 171         }
 172     }
 173     rb->close(fd);
 174     return true;
 175 }
 176
 177 /* fill grid with initial pattern */
 178 static void setup_grid(char *pgrid, int pattern){
 179     int n, max;
 180     int xmid, ymid;
 181
 182     max = GRID_W * GRID_H;
 183
 184     switch(pattern){
 185     case PATTERN_RANDOM:
 186         rb->splash(HZ, "Random");
 187 #if 0 /* two oscilators, debug pattern */
 188         set_cell( 0,  1 , pgrid);
 189         set_cell( 1,  1 , pgrid);
 190         set_cell( 2,  1 , pgrid);
 191
 192         set_cell( 6,  7 , pgrid);
 193         set_cell( 7,  7 , pgrid);
 194         set_cell( 8,  7 , pgrid);
 195 #endif
 196
 197         /* fill screen randomly */
 198         for(n=0; n<(max>>2); n++)
 199             pgrid[rb->rand()%max] = 1;
 200
 201         break;
 202
 203     case PATTERN_GROWTH_1:
 204         rb->splash(HZ, "Growth");
 205         xmid = (GRID_W>>1) - 2;
 206         ymid = (GRID_H>>1) - 2;
 207         set_cell(xmid + 6, ymid + 0 , pgrid);
 208         set_cell(xmid + 4, ymid + 1 , pgrid);
 209         set_cell(xmid + 6, ymid + 1 , pgrid);
 210         set_cell(xmid + 7, ymid + 1 , pgrid);
 211         set_cell(xmid + 4, ymid + 2 , pgrid);
 212         set_cell(xmid + 6, ymid + 2 , pgrid);
 213         set_cell(xmid + 4, ymid + 3 , pgrid);
 214         set_cell(xmid + 2, ymid + 4 , pgrid);
 215         set_cell(xmid + 0, ymid + 5 , pgrid);
 216         set_cell(xmid + 2, ymid + 5 , pgrid);
 217         break;
 218     case PATTERN_ACORN:
 219         rb->splash(HZ, "Acorn");
 220         xmid = (GRID_W>>1) - 3;
 221         ymid = (GRID_H>>1) - 1;
 222         set_cell(xmid + 1, ymid + 0 , pgrid);
 223         set_cell(xmid + 3, ymid + 1 , pgrid);
 224         set_cell(xmid + 0, ymid + 2 , pgrid);
 225         set_cell(xmid + 1, ymid + 2 , pgrid);
 226         set_cell(xmid + 4, ymid + 2 , pgrid);
 227         set_cell(xmid + 5, ymid + 2 , pgrid);
 228         set_cell(xmid + 6, ymid + 2 , pgrid);
 229         break;
 230     case PATTERN_GROWTH_2:
 231         rb->splash(HZ, "Growth 2");
 232         xmid = (GRID_W>>1) - 4;
 233         ymid = (GRID_H>>1) - 1;
 234         set_cell(xmid + 0, ymid + 0 , pgrid);
 235         set_cell(xmid + 1, ymid + 0 , pgrid);
 236         set_cell(xmid + 2, ymid + 0 , pgrid);
 237         set_cell(xmid + 4, ymid + 0 , pgrid);
 238         set_cell(xmid + 0, ymid + 1 , pgrid);
 239         set_cell(xmid + 3, ymid + 2 , pgrid);
 240         set_cell(xmid + 4, ymid + 2 , pgrid);
 241         set_cell(xmid + 1, ymid + 3 , pgrid);
 242         set_cell(xmid + 2, ymid + 3 , pgrid);
 243         set_cell(xmid + 4, ymid + 3 , pgrid);
 244         set_cell(xmid + 0, ymid + 4 , pgrid);
 245         set_cell(xmid + 2, ymid + 4 , pgrid);
 246         set_cell(xmid + 4, ymid + 4 , pgrid);
 247         break;
 248     case PATTERN_GLIDER_GUN:
 249         rb->splash(HZ, "Glider Gun");
 250         set_cell( 24, 0, pgrid);
 251         set_cell( 22, 1, pgrid);
 252         set_cell( 24, 1, pgrid);
 253         set_cell( 12, 2, pgrid);
 254         set_cell( 13, 2, pgrid);
 255         set_cell( 20, 2, pgrid);
 256         set_cell( 21, 2, pgrid);
 257         set_cell( 34, 2, pgrid);
 258         set_cell( 35, 2, pgrid);
 259         set_cell( 11, 3, pgrid);
 260         set_cell( 15, 3, pgrid);
 261         set_cell( 20, 3, pgrid);
 262         set_cell( 21, 3, pgrid);
 263         set_cell( 34, 3, pgrid);
 264         set_cell( 35, 3, pgrid);
 265         set_cell(  0, 4, pgrid);
 266         set_cell(  1, 4, pgrid);
 267         set_cell( 10, 4, pgrid);
 268         set_cell( 16, 4, pgrid);
 269         set_cell( 20, 4, pgrid);
 270         set_cell( 21, 4, pgrid);
 271         set_cell(  0, 5, pgrid);
 272         set_cell(  1, 5, pgrid);
 273         set_cell( 10, 5, pgrid);
 274         set_cell( 14, 5, pgrid);
 275         set_cell( 16, 5, pgrid);
 276         set_cell( 17, 5, pgrid);
 277         set_cell( 22, 5, pgrid);
 278         set_cell( 24, 5, pgrid);
 279         set_cell( 10, 6, pgrid);
 280         set_cell( 16, 6, pgrid);
 281         set_cell( 24, 6, pgrid);
 282         set_cell( 11, 7, pgrid);
 283         set_cell( 15, 7, pgrid);
 284         set_cell( 12, 8, pgrid);
 285         set_cell( 13, 8, pgrid);
 286         break;
 287     }
 288 }
 289
 290 /* display grid */
 291 static void show_grid(char *pgrid){
 292     int x, y;
 293     unsigned char age;
 294
 295     rb->lcd_clear_display();
 296     for(y=0; y<GRID_H; y++){
 297         for(x=0; x<GRID_W; x++){
 298             age = get_cell(x, y, pgrid);
 299             if(age){
 300 #if LCD_DEPTH >= 16
 301                 rb->lcd_set_foreground( LCD_RGBPACK( age, age, age ));
 302 #elif LCD_DEPTH == 2
 303                 rb->lcd_set_foreground(age>>7);
 304 #endif
 305                 rb->lcd_drawpixel(x, y);
 306             }
 307         }
 308     }
 309     if(status_line){
 310 #if LCD_DEPTH > 1
 311         rb->lcd_set_foreground( LCD_BLACK );
 312 #endif
 313         rb->lcd_putsf(0, 0, "g:%d p:%d", generation, population);
 314     }
 315     rb->lcd_update();
 316 }
 317
 318
 319 /* Calculates whether the cell will be alive in the next generation.
 320    n is the array with 9 elements that represent the cell itself and its
 321    neighborhood like this (the cell itself is n[4]):
 322    0 1 2
 323    3 4 5
 324    6 7 8
 325 */
 326 static inline bool check_cell(unsigned char *n)
 327 {
 328     int empty_cells = 0;
 329     int alive_cells;
 330     bool result;
 331
 332     /* count empty neighbour cells */
 333     if(n[0]==0) empty_cells++;
 334     if(n[1]==0) empty_cells++;
 335     if(n[2]==0) empty_cells++;
 336     if(n[3]==0) empty_cells++;
 337     if(n[5]==0) empty_cells++;
 338     if(n[6]==0) empty_cells++;
 339     if(n[7]==0) empty_cells++;
 340     if(n[8]==0) empty_cells++;
 341
 342     /* now we build the number of non-zero neighbours :-P */
 343     alive_cells = 8 - empty_cells;
 344
 345     if (n[4]) {
 346         /* If the cell is alive, it stays alive iff it has 2 or 3 alive neighbours */
 347         result = (alive_cells==2 || alive_cells==3);
 348     }
 349     else {
 350         /* If the cell is dead, it gets alive iff it has 3 alive neighbours */
 351         result = (alive_cells==3);
 352     }
 353
 354     return result;
 355 }
 356
 357 /* Calculate the next generation of cells
 358  *
 359  * The borders of the grid are connected to their opposite sides.
 360  *
 361  * To avoid multiplications while accessing data in the 2-d grid
 362  * (pgrid) we try to re-use previously accessed neighbourhood
 363  * information which is stored in an 3x3 array.
 364  */
 365 static void next_generation(char *pgrid, char *pnext_grid){
 366     int x, y;
 367     bool cell;
 368     unsigned char age;
 369     unsigned char n[9];
 370
 371     rb->memset(n, 0, sizeof(n));
 372
 373     /*
 374      * cell is (4) with 8 neighbours
 375      *
 376      *   0|1|2
 377      *   -----
 378      *   3|4|5
 379      *   -----
 380      *   6|7|8
 381      */
 382
 383     population = 0;
 384
 385     /* go through the grid */
 386     for(y=0; y<GRID_H; y++){
 387         for(x=0; x<GRID_W; x++){
 388             if(y==0 && x==0){
 389                 /* first cell in first row, we have to load all neighbours */
 390                 n[0] = get_cell(x-1, y-1, pgrid);
 391                 n[1] = get_cell(x,   y-1, pgrid);
 392                 n[2] = get_cell(x+1, y-1, pgrid);
 393                 n[3] = get_cell(x-1, y,   pgrid);
 394                 n[4] = get_cell(x,   y,   pgrid);
 395                 n[5] = get_cell(x+1, y,   pgrid);
 396                 n[6] = get_cell(x-1, y+1, pgrid);
 397                 n[7] = get_cell(x,   y+1, pgrid);
 398                 n[8] = get_cell(x+1, y+1, pgrid);
 399             } else {
 400                 if(x==0){
 401                     /* beginning of a row, copy what we know about our predecessor,
 402                        0, 1, 3, 4 are known, 2, 5, 6, 7, 8 have to be loaded
 403                     */
 404                     n[0] = n[4];
 405                     n[1] = n[5];
 406                     n[2] = get_cell(x+1, y-1, pgrid);
 407                     n[3] = n[7];
 408                     n[4] = n[8];
 409                     n[5] = get_cell(x+1, y,   pgrid);
 410                     n[6] = get_cell(x-1, y+1, pgrid);
 411                     n[7] = get_cell(x,   y+1, pgrid);
 412                     n[8] = get_cell(x+1, y+1, pgrid);
 413                 } else {
 414                     /* we are moving right in a row,
 415                      * copy what we know about the neighbours on our left side,
 416                      * 2, 5, 8 have to be loaded
 417                      */
 418                     n[0] = n[1];
 419                     n[1] = n[2];
 420                     n[2] = get_cell(x+1, y-1, pgrid);
 421                     n[3] = n[4];
 422                     n[4] = n[5];
 423                     n[5] = get_cell(x+1, y,   pgrid);
 424                     n[6] = n[7];
 425                     n[7] = n[8];
 426                     n[8] = get_cell(x+1, y+1, pgrid);
 427                 }
 428             }
 429
 430             /* how old is our cell? */
 431             age  = n[4];
 432
 433             /* calculate the cell based on given neighbour information */
 434             cell = check_cell(n);
 435
 436             /* is the actual cell alive? */
 437             if(cell){
 438                 population++;
 439                 /* prevent overflow */
 440                 if(age<252)
 441                     age++;
 442                 set_cell_age(x, y, age, pnext_grid);
 443             }
 444             else
 445                 set_cell_age(x, y, 0, pnext_grid);
 446 #if 0
 447             DEBUGF("x=%d,y=%d\n", x, y);
 448             DEBUGF("cell: %d\n", cell);
 449             DEBUGF("%d %d %d\n", n[0],n[1],n[2]);
 450             DEBUGF("%d %d %d\n", n[3],n[4],n[5]);
 451             DEBUGF("%d %d %d\n", n[6],n[7],n[8]);
 452             DEBUGF("----------------\n");
 453 #endif
 454         }
 455     }
 456     generation++;
 457 }
 458
 459
 460
 461 /**********************************/
 462 /* this is the plugin entry point */
 463 /**********************************/
 464 enum plugin_status plugin_start(const void* parameter)
 465 {
 466     int button = 0;
 467     int quit = 0;
 468     int stop = 0;
 469     int usb = 0;
 470     int pattern = 0;
 471     char *pgrid;
 472     char *pnext_grid;
 473     char *ptemp;
 474     (void)(parameter);
 475
 476     backlight_ignore_timeout();
 477 #if LCD_DEPTH > 1
 478     rb->lcd_set_backdrop(NULL);
 479 #ifdef HAVE_LCD_COLOR
 480     rb->lcd_set_background(LCD_RGBPACK(182, 198, 229)); /* rockbox blue */
 481 #else
 482     rb->lcd_set_background(LCD_DEFAULT_BG);
 483 #endif /* HAVE_LCD_COLOR */
 484 #endif /* LCD_DEPTH > 1 */
 485
 486     /* link pointers to grids */
 487     pgrid      = (char *)grid_a;
 488     pnext_grid = (char *)grid_b;
 489
 490     init_grid(pgrid);
 491
 492     if( parameter == NULL )
 493     {
 494         setup_grid(pgrid, pattern++);
 495     }
 496     else
 497     {
 498         if( load_cellfile(parameter, pgrid) )
 499         {
 500             rb->splashf( 1*HZ, "Cells loaded (%s)", (char *)parameter );
 501         }
 502         else
 503         {
 504             rb->splash( 1*HZ, "File Open Error");
 505             setup_grid(pgrid, pattern++);  /* fall back to stored patterns */
 506         }
 507     }
 508
 509
 510     show_grid(pgrid);
 511
 512     while(!quit) {
 513         button = pluginlib_getaction(TIMEOUT_BLOCK, plugin_contexts, ARRAYLEN(plugin_contexts));
 514         switch(button) {
 515         case ROCKLIFE_NEXT:
 516         case ROCKLIFE_NEXT_REP:
 517             /* calculate next generation */
 518             next_generation(pgrid, pnext_grid);
 519             /* swap buffers, grid is the new generation */
 520             ptemp = pgrid;
 521             pgrid = pnext_grid;
 522             pnext_grid = ptemp;
 523             /* show new generation */
 524             show_grid(pgrid);
 525             break;
 526         case ROCKLIFE_PLAY_PAUSE:
 527             stop = 0;
 528             while(!stop){
 529                 /* calculate next generation */
 530                 next_generation(pgrid, pnext_grid);
 531                 /* swap buffers, grid is the new generation */
 532                 ptemp = pgrid;
 533                 pgrid = pnext_grid;
 534                 pnext_grid = ptemp;
 535                 /* show new generation */
 536                 rb->yield();
 537                 show_grid(pgrid);
 538                 button = pluginlib_getaction(0, plugin_contexts, ARRAYLEN(plugin_contexts));
 539                 switch(button) {
 540                 case ROCKLIFE_PLAY_PAUSE:
 541                 case ROCKLIFE_QUIT:
 542                     stop = 1;
 543                     break;
 544                 default:
 545                     if (rb->default_event_handler(button) == SYS_USB_CONNECTED) {
 546                         stop = 1;
 547                         quit = 1;
 548                         usb = 1;
 549                     }
 550                     break;
 551                 }
 552                 rb->yield();
 553             }
 554             break;
 555         case ROCKLIFE_INIT:
 556             init_grid(pgrid);
 557             setup_grid(pgrid, pattern);
 558             show_grid(pgrid);
 559             pattern++;
 560             pattern%=5;
 561             break;
 562         case ROCKLIFE_STATUS:
 563             status_line = !status_line;
 564             show_grid(pgrid);
 565             break;
 566         case ROCKLIFE_QUIT:
 567             /* quit plugin */
 568             quit = 1;
 569             break;
 570         default:
 571             if (rb->default_event_handler(button) == SYS_USB_CONNECTED) {
 572                 quit = 1;
 573                 usb = 1;
 574             }
 575             break;
 576         }
 577         rb->yield();
 578     }
 579
 580     backlight_use_settings();
 581     return usb? PLUGIN_USB_CONNECTED: PLUGIN_OK;
 582 }