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 PLUGIN_HEADER
  68
  69 #define ROCKLIFE_PLAY_PAUSE PLA_FIRE
  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_QUIT
  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 /* not yet implemented */
  81
  82 const struct button_mapping *plugin_contexts[]
  83 = {generic_directions, generic_actions};
  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 char buf[30];
  94
  95
  96 static inline bool is_valid_cell(int x, int y) {
  97     return (x >= 0 && x < GRID_W
  98             && y >= 0 && y < GRID_H);
  99 }
 100
 101 static inline void set_cell_age(int x, int y, unsigned char age, char *pgrid) {
 102     pgrid[x+y*GRID_W] = age;
 103 }
 104
 105 static inline void set_cell(int x, int y, char *pgrid) {
 106     set_cell_age(x, y, 1, pgrid);
 107 }
 108
 109 static inline unsigned char get_cell(int x, int y, char *pgrid) {
 110     if (x < 0)
 111         x += GRID_W;
 112     else if (x >= GRID_W)
 113         x -= GRID_W;
 114
 115     if (y < 0)
 116         y += GRID_H;
 117     else if (y >= GRID_H)
 118         y -= GRID_H;
 119
 120     return pgrid[x+y*GRID_W];
 121 }
 122
 123 /* clear grid */
 124 void init_grid(char *pgrid){
 125     memset(pgrid, 0, GRID_W * GRID_H);
 126 }
 127
 128 /*fill grid with pattern from file (viewer mode)*/
 129 static bool load_cellfile(const char *file, char *pgrid){
 130     int fd;
 131     fd = rb->open(file, O_RDONLY);
 132     if (fd==-1)
 133         return false;
 134
 135     init_grid(pgrid);
 136
 137     char c;
 138     int nc, x, y, xmid, ymid;
 139     x=0;
 140     y=0;
 141     xmid = (GRID_W>>1) - 2;
 142     ymid = (GRID_H>>1) - 2;
 143
 144     while (true) {
 145         nc = read(fd, &c, 1);
 146         if (nc <= 0)
 147             break;
 148
 149         switch(c) {
 150         case '.':
 151             x++;
 152             break;
 153         case 'O':
 154             if (is_valid_cell(xmid + x, ymid + y))
 155                 set_cell(xmid + x, ymid + y, pgrid);
 156             x++;
 157             break;
 158         case '\n':
 159             y++;
 160             x=0;
 161             break;
 162         default:
 163             break;
 164         }
 165     }
 166     rb->close(fd);
 167     return true;
 168 }
 169
 170 /* fill grid with initial pattern */
 171 static void setup_grid(char *pgrid, int pattern){
 172     int n, max;
 173     int xmid, ymid;
 174
 175     max = GRID_W * GRID_H;
 176
 177     switch(pattern){
 178     case PATTERN_RANDOM:
 179         rb->splash(HZ, "Random");
 180 #if 0 /* two oscilators, debug pattern */
 181         set_cell( 0,  1 , pgrid);
 182         set_cell( 1,  1 , pgrid);
 183         set_cell( 2,  1 , pgrid);
 184
 185         set_cell( 6,  7 , pgrid);
 186         set_cell( 7,  7 , pgrid);
 187         set_cell( 8,  7 , pgrid);
 188 #endif
 189
 190         /* fill screen randomly */
 191         for(n=0; n<(max>>2); n++)
 192             pgrid[rb->rand()%max] = 1;
 193
 194         break;
 195
 196     case PATTERN_GROWTH_1:
 197         rb->splash(HZ, "Growth");
 198         xmid = (GRID_W>>1) - 2;
 199         ymid = (GRID_H>>1) - 2;
 200         set_cell(xmid + 6, ymid + 0 , pgrid);
 201         set_cell(xmid + 4, ymid + 1 , pgrid);
 202         set_cell(xmid + 6, ymid + 1 , pgrid);
 203         set_cell(xmid + 7, ymid + 1 , pgrid);
 204         set_cell(xmid + 4, ymid + 2 , pgrid);
 205         set_cell(xmid + 6, ymid + 2 , pgrid);
 206         set_cell(xmid + 4, ymid + 3 , pgrid);
 207         set_cell(xmid + 2, ymid + 4 , pgrid);
 208         set_cell(xmid + 0, ymid + 5 , pgrid);
 209         set_cell(xmid + 2, ymid + 5 , pgrid);
 210         break;
 211     case PATTERN_ACORN:
 212         rb->splash(HZ, "Acorn");
 213         xmid = (GRID_W>>1) - 3;
 214         ymid = (GRID_H>>1) - 1;
 215         set_cell(xmid + 1, ymid + 0 , pgrid);
 216         set_cell(xmid + 3, ymid + 1 , pgrid);
 217         set_cell(xmid + 0, ymid + 2 , pgrid);
 218         set_cell(xmid + 1, ymid + 2 , pgrid);
 219         set_cell(xmid + 4, ymid + 2 , pgrid);
 220         set_cell(xmid + 5, ymid + 2 , pgrid);
 221         set_cell(xmid + 6, ymid + 2 , pgrid);
 222         break;
 223     case PATTERN_GROWTH_2:
 224         rb->splash(HZ, "Growth 2");
 225         xmid = (GRID_W>>1) - 4;
 226         ymid = (GRID_H>>1) - 1;
 227         set_cell(xmid + 0, ymid + 0 , pgrid);
 228         set_cell(xmid + 1, ymid + 0 , pgrid);
 229         set_cell(xmid + 2, ymid + 0 , pgrid);
 230         set_cell(xmid + 4, ymid + 0 , pgrid);
 231         set_cell(xmid + 0, ymid + 1 , pgrid);
 232         set_cell(xmid + 3, ymid + 2 , pgrid);
 233         set_cell(xmid + 4, ymid + 2 , pgrid);
 234         set_cell(xmid + 1, ymid + 3 , pgrid);
 235         set_cell(xmid + 2, ymid + 3 , pgrid);
 236         set_cell(xmid + 4, ymid + 3 , pgrid);
 237         set_cell(xmid + 0, ymid + 4 , pgrid);
 238         set_cell(xmid + 2, ymid + 4 , pgrid);
 239         set_cell(xmid + 4, ymid + 4 , pgrid);
 240         break;
 241     case PATTERN_GLIDER_GUN:
 242         rb->splash(HZ, "Glider Gun");
 243         set_cell( 24, 0, pgrid);
 244         set_cell( 22, 1, pgrid);
 245         set_cell( 24, 1, pgrid);
 246         set_cell( 12, 2, pgrid);
 247         set_cell( 13, 2, pgrid);
 248         set_cell( 20, 2, pgrid);
 249         set_cell( 21, 2, pgrid);
 250         set_cell( 34, 2, pgrid);
 251         set_cell( 35, 2, pgrid);
 252         set_cell( 11, 3, pgrid);
 253         set_cell( 15, 3, pgrid);
 254         set_cell( 20, 3, pgrid);
 255         set_cell( 21, 3, pgrid);
 256         set_cell( 34, 3, pgrid);
 257         set_cell( 35, 3, pgrid);
 258         set_cell(  0, 4, pgrid);
 259         set_cell(  1, 4, pgrid);
 260         set_cell( 10, 4, pgrid);
 261         set_cell( 16, 4, pgrid);
 262         set_cell( 20, 4, pgrid);
 263         set_cell( 21, 4, pgrid);
 264         set_cell(  0, 5, pgrid);
 265         set_cell(  1, 5, pgrid);
 266         set_cell( 10, 5, pgrid);
 267         set_cell( 14, 5, pgrid);
 268         set_cell( 16, 5, pgrid);
 269         set_cell( 17, 5, pgrid);
 270         set_cell( 22, 5, pgrid);
 271         set_cell( 24, 5, pgrid);
 272         set_cell( 10, 6, pgrid);
 273         set_cell( 16, 6, pgrid);
 274         set_cell( 24, 6, pgrid);
 275         set_cell( 11, 7, pgrid);
 276         set_cell( 15, 7, pgrid);
 277         set_cell( 12, 8, pgrid);
 278         set_cell( 13, 8, pgrid);
 279         break;
 280     }
 281 }
 282
 283 /* display grid */
 284 static void show_grid(char *pgrid){
 285     int x, y;
 286     unsigned char age;
 287
 288     rb->lcd_clear_display();
 289     for(y=0; y<GRID_H; y++){
 290         for(x=0; x<GRID_W; x++){
 291             age = get_cell(x, y, pgrid);
 292             if(age){
 293 #if LCD_DEPTH >= 16
 294                 rb->lcd_set_foreground( LCD_RGBPACK( age, age, age ));
 295 #elif LCD_DEPTH == 2
 296                 rb->lcd_set_foreground(age>>7);
 297 #endif
 298                 rb->lcd_drawpixel(x, y);
 299             }
 300         }
 301     }
 302     if(status_line){
 303         rb->snprintf(buf, sizeof(buf), "g:%d p:%d", generation, population);
 304 #if LCD_DEPTH > 1
 305         rb->lcd_set_foreground( LCD_BLACK );
 306 #endif
 307         rb->lcd_puts(0, 0, buf);
 308     }
 309     rb->lcd_update();
 310 }
 311
 312
 313 /* Calculates whether the cell will be alive in the next generation.
 314    n is the array with 9 elements that represent the cell itself and its
 315    neighborhood like this (the cell itself is n[4]):
 316    0 1 2
 317    3 4 5
 318    6 7 8
 319 */
 320 static inline bool check_cell(unsigned char *n)
 321 {
 322     int empty_cells = 0;
 323     int alive_cells;
 324     bool result;
 325
 326     /* count empty neighbour cells */
 327     if(n[0]==0) empty_cells++;
 328     if(n[1]==0) empty_cells++;
 329     if(n[2]==0) empty_cells++;
 330     if(n[3]==0) empty_cells++;
 331     if(n[5]==0) empty_cells++;
 332     if(n[6]==0) empty_cells++;
 333     if(n[7]==0) empty_cells++;
 334     if(n[8]==0) empty_cells++;
 335
 336     /* now we build the number of non-zero neighbours :-P */
 337     alive_cells = 8 - empty_cells;
 338
 339     if (n[4]) {
 340         /* If the cell is alive, it stays alive iff it has 2 or 3 alive neighbours */
 341         result = (alive_cells==2 || alive_cells==3);
 342     }
 343     else {
 344         /* If the cell is dead, it gets alive iff it has 3 alive neighbours */
 345         result = (alive_cells==3);
 346     }
 347
 348     return result;
 349 }
 350
 351 /* Calculate the next generation of cells
 352  *
 353  * The borders of the grid are connected to their opposite sides.
 354  *
 355  * To avoid multiplications while accessing data in the 2-d grid
 356  * (pgrid) we try to re-use previously accessed neighbourhood
 357  * information which is stored in an 3x3 array.
 358  */
 359 static void next_generation(char *pgrid, char *pnext_grid){
 360     int x, y;
 361     bool cell;
 362     unsigned char age;
 363     unsigned char n[9];
 364
 365     rb->memset(n, 0, sizeof(n));
 366
 367     /*
 368      * cell is (4) with 8 neighbours
 369      *
 370      *   0|1|2
 371      *   -----
 372      *   3|4|5
 373      *   -----
 374      *   6|7|8
 375      */
 376
 377     population = 0;
 378
 379     /* go through the grid */
 380     for(y=0; y<GRID_H; y++){
 381         for(x=0; x<GRID_W; x++){
 382             if(y==0 && x==0){
 383                 /* first cell in first row, we have to load all neighbours */
 384                 n[0] = get_cell(x-1, y-1, pgrid);
 385                 n[1] = get_cell(x,   y-1, pgrid);
 386                 n[2] = get_cell(x+1, y-1, pgrid);
 387                 n[3] = get_cell(x-1, y,   pgrid);
 388                 n[4] = get_cell(x,   y,   pgrid);
 389                 n[5] = get_cell(x+1, y,   pgrid);
 390                 n[6] = get_cell(x-1, y+1, pgrid);
 391                 n[7] = get_cell(x,   y+1, pgrid);
 392                 n[8] = get_cell(x+1, y+1, pgrid);
 393             } else {
 394                 if(x==0){
 395                     /* beginning of a row, copy what we know about our predecessor,
 396                        0, 1, 3, 4 are known, 2, 5, 6, 7, 8 have to be loaded
 397                     */
 398                     n[0] = n[4];
 399                     n[1] = n[5];
 400                     n[2] = get_cell(x+1, y-1, pgrid);
 401                     n[3] = n[7];
 402                     n[4] = n[8];
 403                     n[5] = get_cell(x+1, y,   pgrid);
 404                     n[6] = get_cell(x-1, y+1, pgrid);
 405                     n[7] = get_cell(x,   y+1, pgrid);
 406                     n[8] = get_cell(x+1, y+1, pgrid);
 407                 } else {
 408                     /* we are moving right in a row,
 409                      * copy what we know about the neighbours on our left side,
 410                      * 2, 5, 8 have to be loaded
 411                      */
 412                     n[0] = n[1];
 413                     n[1] = n[2];
 414                     n[2] = get_cell(x+1, y-1, pgrid);
 415                     n[3] = n[4];
 416                     n[4] = n[5];
 417                     n[5] = get_cell(x+1, y,   pgrid);
 418                     n[6] = n[7];
 419                     n[7] = n[8];
 420                     n[8] = get_cell(x+1, y+1, pgrid);
 421                 }
 422             }
 423
 424             /* how old is our cell? */
 425             age  = n[4];
 426
 427             /* calculate the cell based on given neighbour information */
 428             cell = check_cell(n);
 429
 430             /* is the actual cell alive? */
 431             if(cell){
 432                 population++;
 433                 /* prevent overflow */
 434                 if(age<252)
 435                     age++;
 436                 set_cell_age(x, y, age, pnext_grid);
 437             }
 438             else
 439                 set_cell_age(x, y, 0, pnext_grid);
 440 #if 0
 441             DEBUGF("x=%d,y=%d\n", x, y);
 442             DEBUGF("cell: %d\n", cell);
 443             DEBUGF("%d %d %d\n", n[0],n[1],n[2]);
 444             DEBUGF("%d %d %d\n", n[3],n[4],n[5]);
 445             DEBUGF("%d %d %d\n", n[6],n[7],n[8]);
 446             DEBUGF("----------------\n");
 447 #endif
 448         }
 449     }
 450     generation++;
 451 }
 452
 453
 454
 455 /**********************************/
 456 /* this is the plugin entry point */
 457 /**********************************/
 458 enum plugin_status plugin_start(const void* parameter)
 459 {
 460     int button = 0;
 461     int quit = 0;
 462     int stop = 0;
 463     int pattern = 0;
 464     char *pgrid;
 465     char *pnext_grid;
 466     char *ptemp;
 467     (void)(parameter);
 468
 469     backlight_force_on(); /* backlight control in lib/helper.c */
 470 #if LCD_DEPTH > 1
 471     rb->lcd_set_backdrop(NULL);
 472 #ifdef HAVE_LCD_COLOR
 473     rb->lcd_set_background(LCD_RGBPACK(182, 198, 229)); /* rockbox blue */
 474 #else
 475     rb->lcd_set_background(LCD_DEFAULT_BG);
 476 #endif /* HAVE_LCD_COLOR */
 477 #endif /* LCD_DEPTH > 1 */
 478
 479     /* link pointers to grids */
 480     pgrid      = (char *)grid_a;
 481     pnext_grid = (char *)grid_b;
 482
 483     init_grid(pgrid);
 484
 485
 486     if( parameter == NULL )
 487     {
 488         setup_grid(pgrid, pattern++);
 489     }
 490     else
 491     {
 492         if( load_cellfile(parameter, pgrid) )
 493         {
 494             rb->splashf( 1*HZ, "Cells loaded (%s)", (char *)parameter );
 495         }
 496         else
 497         {
 498             rb->splash( 1*HZ, "File Open Error");
 499             setup_grid(pgrid, pattern++);  /* fall back to stored patterns */
 500         }
 501     }
 502
 503
 504     show_grid(pgrid);
 505
 506     while(!quit) {
 507         button = pluginlib_getaction(TIMEOUT_BLOCK, plugin_contexts, 2);
 508         switch(button) {
 509         case ROCKLIFE_NEXT:
 510         case ROCKLIFE_NEXT_REP:
 511             /* calculate next generation */
 512             next_generation(pgrid, pnext_grid);
 513             /* swap buffers, grid is the new generation */
 514             ptemp = pgrid;
 515             pgrid = pnext_grid;
 516             pnext_grid = ptemp;
 517             /* show new generation */
 518             show_grid(pgrid);
 519             break;
 520         case ROCKLIFE_PLAY_PAUSE:
 521             stop = 0;
 522             while(!stop){
 523                 /* calculate next generation */
 524                 next_generation(pgrid, pnext_grid);
 525                 /* swap buffers, grid is the new generation */
 526                 ptemp = pgrid;
 527                 pgrid = pnext_grid;
 528                 pnext_grid = ptemp;
 529                 /* show new generation */
 530                 rb->yield();
 531                 show_grid(pgrid);
 532                 button = pluginlib_getaction(0, plugin_contexts, 2);
 533                 switch(button) {
 534                 case ROCKLIFE_PLAY_PAUSE:
 535                 case ROCKLIFE_QUIT:
 536                     stop = 1;
 537                     break;
 538                 default:
 539                     break;
 540                 }
 541                 rb->yield();
 542             }
 543             break;
 544         case ROCKLIFE_INIT:
 545             init_grid(pgrid);
 546             setup_grid(pgrid, pattern);
 547             show_grid(pgrid);
 548             pattern++;
 549             pattern%=5;
 550             break;
 551         case ROCKLIFE_STATUS:
 552             status_line = !status_line;
 553             show_grid(pgrid);
 554             break;
 555         case ROCKLIFE_QUIT:
 556             /* quit plugin */
 557             quit=true;
 558             return PLUGIN_OK;
 559             break;
 560         default:
 561             if (rb->default_event_handler(button) == SYS_USB_CONNECTED) {
 562                 return PLUGIN_USB_CONNECTED;
 563             }
 564             break;
 565         }
 566         rb->yield();
 567     }
 568
 569     backlight_use_settings(); /* backlight control in lib/helper.c */
 570     return PLUGIN_OK;
 571 }