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