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