apps/plugins/maze.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 the implementation of a maze generation algorithm.
  24  * The generated mazes are "perfect", i.e. there is one and only
  25  * one path from any point in the maze to any other point.
  26  *
  27  *
  28  * The implemented algorithm is called "Depth-First search", the
  29  * solving is done by a dead-end filler routine.
  30  *
  31  */
  32
  33 #include "plugin.h"
  34 #include "lib/helper.h"
  35
  36 PLUGIN_HEADER
  37
  38 /* key assignments */
  39
  40 #if (CONFIG_KEYPAD == IPOD_4G_PAD) || \
  41     (CONFIG_KEYPAD == IPOD_3G_PAD) || \
  42     (CONFIG_KEYPAD == IPOD_1G2G_PAD)
  43 #   define MAZE_NEW      (BUTTON_SELECT | BUTTON_REPEAT)
  44 #   define MAZE_NEW_PRE  BUTTON_SELECT
  45 #   define MAZE_QUIT     (BUTTON_SELECT | BUTTON_MENU)
  46 #   define MAZE_SOLVE    (BUTTON_SELECT | BUTTON_PLAY)
  47 #   define MAZE_RIGHT    BUTTON_RIGHT
  48 #   define MAZE_LEFT     BUTTON_LEFT
  49 #   define MAZE_UP       BUTTON_MENU
  50 #   define MAZE_DOWN     BUTTON_PLAY
  51 #   define MAZE_RRIGHT   (BUTTON_RIGHT | BUTTON_REPEAT)
  52 #   define MAZE_RLEFT    (BUTTON_LEFT | BUTTON_REPEAT)
  53 #   define MAZE_RUP      (BUTTON_MENU | BUTTON_REPEAT)
  54 #   define MAZE_RDOWN    (BUTTON_PLAY | BUTTON_REPEAT)
  55
  56 #else
  57 #   include "lib/pluginlib_actions.h"
  58 #   define MAZE_NEW      PLA_START
  59 #   define MAZE_QUIT     PLA_QUIT
  60 #   define MAZE_SOLVE    PLA_FIRE
  61 #   define MAZE_RIGHT    PLA_RIGHT
  62 #   define MAZE_LEFT     PLA_LEFT
  63 #   define MAZE_UP       PLA_UP
  64 #   define MAZE_DOWN     PLA_DOWN
  65 #   define MAZE_RRIGHT   PLA_RIGHT_REPEAT
  66 #   define MAZE_RLEFT    PLA_LEFT_REPEAT
  67 #   define MAZE_RUP      PLA_UP_REPEAT
  68 #   define MAZE_RDOWN    PLA_DOWN_REPEAT
  69 static const struct button_mapping *plugin_contexts[]
  70 = {generic_directions, generic_actions};
  71
  72 #endif
  73
  74 /* cell property bits */
  75 #define WALL_N    0x0001
  76 #define WALL_E    0x0002
  77 #define WALL_S    0x0004
  78 #define WALL_W    0x0008
  79 #define WALL_ALL  (WALL_N | WALL_E | WALL_S | WALL_W)
  80 #define PATH      0x0010
  81
  82 /* border tests */
  83 #define BORDER_N(y) ((y) == 0)
  84 #define BORDER_E(x) ((x) == MAZE_WIDTH-1)
  85 #define BORDER_S(y) ((y) == MAZE_HEIGHT-1)
  86 #define BORDER_W(x) ((x) == 0)
  87
  88 /* the API */
  89 static const struct plugin_api* rb;
  90
  91 // we can and should change this to make square boxes
  92 #if ( LCD_WIDTH == 112 )
  93 #define MAZE_WIDTH  16
  94 #define MAZE_HEIGHT 12
  95 #elif( LCD_WIDTH == 132 )
  96 #define MAZE_WIDTH  26
  97 #define MAZE_HEIGHT 16
  98 #else
  99 #define MAZE_WIDTH  32
 100 #define MAZE_HEIGHT 24
 101 #endif
 102
 103 struct maze
 104 {
 105     int show_path;
 106     int solved;
 107     int player_x;
 108     int player_y;
 109     uint8_t maze[MAZE_WIDTH][MAZE_HEIGHT];
 110 };
 111
 112 static void maze_init(struct maze* maze)
 113 {
 114     int x, y;
 115
 116     /* initialize the properties */
 117     maze->show_path = false;
 118     maze->solved = false;
 119     maze->player_x = 0;
 120     maze->player_y = 0;
 121
 122     /* all walls are up */
 123     for(y=0; y<MAZE_HEIGHT; y++){
 124         for(x=0; x<MAZE_WIDTH; x++){
 125             maze->maze[x][y] = WALL_ALL;
 126         }
 127     }
 128 }
 129
 130 static void maze_draw(struct maze* maze, struct screen* display)
 131 {
 132     int x, y;
 133     int wx, wy;
 134     int point_width, point_height, point_offset_x, point_offset_y;
 135     uint8_t cell;
 136
 137     /* calculate the size variables */
 138
 139     wx = (int) display->lcdwidth / MAZE_WIDTH;
 140     wy = (int) display->lcdheight / MAZE_HEIGHT;
 141
 142     if(wx>3){
 143         point_width=wx-3;
 144         point_offset_x=2;
 145     }else{
 146         point_width=1;
 147         point_offset_x=1;
 148     }
 149
 150     if(wy>3){
 151         point_height=wy-3;
 152         point_offset_y=2;
 153     }else{
 154         point_height=1;
 155         point_offset_y=1;
 156     }
 157
 158     /* start drawing */
 159
 160     display->clear_display();
 161
 162     /* draw the walls */
 163     for(y=0; y<MAZE_HEIGHT; y++){
 164         for(x=0; x<MAZE_WIDTH; x++){
 165             cell = maze->maze[x][y];
 166             if(cell & WALL_N)
 167                 display->hline(x*wx, x*wx+wx, y*wy);
 168             if(cell & WALL_E)
 169                 display->vline(x*wx+wx, y*wy, y*wy+wy);
 170             if(cell & WALL_S)
 171                 display->hline(x*wx, x*wx+wx, y*wy+wy);
 172             if(cell & WALL_W)
 173                 display->vline(x*wx, y*wy, y*wy+wy);
 174         }
 175     }
 176
 177     /* draw the path */
 178     if(maze->show_path){
 179 #if LCD_DEPTH >= 16
 180         if(display->depth>=16)
 181             display->set_foreground(LCD_RGBPACK(127,127,127));
 182 #endif
 183 #if LCD_DEPTH >= 2
 184         if(display->depth==2)
 185             display->set_foreground(1);
 186 #endif
 187
 188         /* highlight the path */
 189         for(y=0; y<MAZE_HEIGHT; y++){
 190             for(x=0; x<MAZE_WIDTH; x++){
 191                 cell = maze->maze[x][y];
 192                 if(cell & PATH)
 193                     display->fillrect(x*wx+point_offset_x,
 194                                       y*wy+point_offset_y,
 195                                       point_width, point_height);
 196             }
 197         }
 198
 199         /* link the cells in the path together */
 200         for(y=0; y<MAZE_HEIGHT; y++){
 201             for(x=0; x<MAZE_WIDTH; x++){
 202                 cell = maze->maze[x][y];
 203                 if(cell & PATH){
 204                     if(!(cell & WALL_N) && (maze->maze[x][y-1] & PATH))
 205                         display->fillrect(x*wx+point_offset_x,
 206                                           y*wy,
 207                                           point_width, wy-point_height);
 208                     if(!(cell & WALL_E) && (maze->maze[x+1][y] & PATH))
 209                         display->fillrect(x*wx+wx-point_offset_x,
 210                                           y*wy+point_offset_y,
 211                                           wx-point_width, point_height);
 212                     if(!(cell & WALL_S) && (maze->maze[x][y+1] & PATH))
 213                         display->fillrect(x*wx+point_offset_x,
 214                                           y*wy+wy-point_offset_y,
 215                                           point_width, wy-point_height);
 216                     if(!(cell & WALL_W) && (maze->maze[x-1][y] & PATH))
 217                         display->fillrect(x*wx,
 218                                           y*wy+point_offset_y,
 219                                           wx-point_width, point_height);
 220                 }
 221             }
 222         }
 223
 224 #if LCD_DEPTH >= 16
 225         if(display->depth>=16)
 226             display->set_foreground(LCD_RGBPACK(0,0,0));
 227 #endif
 228 #if LCD_DEPTH >= 2
 229         if(display->depth==2)
 230             display->set_foreground(0);
 231 #endif
 232     }
 233
 234     /* mark start and end */
 235     display->drawline(0, 0, wx, wy);
 236     display->drawline(0, wy, wx, 0);
 237     display->drawline((MAZE_WIDTH-1)*wx,(MAZE_HEIGHT-1)*wy,
 238                      (MAZE_WIDTH-1)*wx+wx, (MAZE_HEIGHT-1)*wy+wy);
 239     display->drawline((MAZE_WIDTH-1)*wx,(MAZE_HEIGHT-1)*wy+wy,
 240                      (MAZE_WIDTH-1)*wx+wx, (MAZE_HEIGHT-1)*wy);
 241
 242     /* draw current position */
 243     display->fillrect(maze->player_x*wx+point_offset_x,
 244                       maze->player_y*wy+point_offset_y,
 245                       point_width, point_height);
 246
 247     /* update the display */
 248     display->update();
 249 }
 250
 251
 252 struct coord_stack
 253 {
 254     uint8_t x[MAZE_WIDTH*MAZE_HEIGHT];
 255     uint8_t y[MAZE_WIDTH*MAZE_HEIGHT];
 256     int stp;
 257 };
 258
 259 static void coord_stack_init(struct coord_stack* stack)
 260 {
 261     rb->memset(stack->x, 0, sizeof(stack->x));
 262     rb->memset(stack->y, 0, sizeof(stack->y));
 263     stack->stp = 0;
 264 }
 265
 266 static void coord_stack_push(struct coord_stack* stack, int x, int y)
 267 {
 268     stack->x[stack->stp] = x;
 269     stack->y[stack->stp] = y;
 270     stack->stp++;
 271 }
 272
 273 static void coord_stack_pop(struct coord_stack* stack, int* x, int* y)
 274 {
 275     stack->stp--;
 276     *x = stack->x[stack->stp];
 277     *y = stack->y[stack->stp];
 278 }
 279
 280 static int maze_pick_random_neighbour_cell_with_walls(struct maze* maze,
 281                                      int x, int y, int *pnx, int *pny)
 282 {
 283     int n, i;
 284     int px[4], py[4];
 285
 286     n = 0;
 287
 288     /* look for neighbours with all walls set up */
 289
 290     if(!BORDER_N(y) && ((maze->maze[x][y-1] & WALL_ALL) == WALL_ALL)){
 291         px[n] = x;
 292         py[n] = y-1;
 293         n++;
 294     }
 295
 296     if(!BORDER_E(x) && ((maze->maze[x+1][y] & WALL_ALL) == WALL_ALL)){
 297         px[n] = x+1;
 298         py[n] = y;
 299         n++;
 300     }
 301
 302     if(!BORDER_S(y) && ((maze->maze[x][y+1] & WALL_ALL) == WALL_ALL)){
 303         px[n] = x;
 304         py[n] = y+1;
 305         n++;
 306     }
 307
 308     if(!BORDER_W(x) && ((maze->maze[x-1][y] & WALL_ALL) == WALL_ALL)){
 309         px[n] = x-1;
 310         py[n] = y;
 311         n++;
 312     }
 313
 314     /* then choose one */
 315     if (n > 0){
 316         i = rb->rand() % n;
 317         *pnx = px[i];
 318         *pny = py[i];
 319     }
 320
 321     return n;
 322 }
 323
 324 /* Removes the wall between the cell (x,y) and the cell (nx,ny) */
 325 static void maze_remove_wall(struct maze* maze, int x, int y, int nx, int ny)
 326 {
 327     /* where is our neighbour? */
 328
 329     /* north or south */
 330     if(x==nx){
 331         if(y<ny){
 332             /*south*/
 333             maze->maze[x][y] &= ~WALL_S;
 334             maze->maze[nx][ny] &= ~WALL_N;
 335         } else {
 336             /*north*/
 337             maze->maze[x][y] &= ~WALL_N;
 338             maze->maze[nx][ny] &= ~WALL_S;
 339         }
 340     } else {
 341         /* east or west */
 342         if(y==ny){
 343             if(x<nx){
 344                 /* east */
 345                 maze->maze[x][y] &= ~WALL_E;
 346                 maze->maze[nx][ny] &= ~WALL_W;
 347             } else {
 348                 /*west*/
 349                 maze->maze[x][y] &= ~WALL_W;
 350                 maze->maze[nx][ny] &= ~WALL_E;
 351             }
 352         }
 353     }
 354 }
 355
 356 static void maze_generate(struct maze* maze)
 357 {
 358     int total_cells = MAZE_WIDTH * MAZE_HEIGHT;
 359     int visited_cells;
 360     int available_neighbours;
 361     int x, y;
 362     int nx = 0;
 363     int ny = 0;
 364     struct coord_stack done_cells;
 365
 366     coord_stack_init(&done_cells);
 367
 368     x = rb->rand()%MAZE_WIDTH;
 369     y = rb->rand()%MAZE_HEIGHT;
 370
 371     visited_cells = 1;
 372     while (visited_cells < total_cells){
 373         available_neighbours =
 374             maze_pick_random_neighbour_cell_with_walls(maze, x, y, &nx, &ny);
 375         if(available_neighbours == 0){
 376             /* pop from stack */
 377             coord_stack_pop(&done_cells, &x, &y);
 378         } else {
 379             /* remove the wall */
 380             maze_remove_wall(maze, x, y, nx, ny);
 381             /* save our position on the stack */
 382             coord_stack_push(&done_cells, x, y);
 383             /* move to the next cell */
 384             x=nx;
 385             y=ny;
 386             /* keep track of visited cells count */
 387             visited_cells++;
 388         }
 389     }
 390 }
 391
 392
 393 static void maze_solve(struct maze* maze)
 394 {
 395     int x, y;
 396     int dead_ends = 1;
 397     uint8_t cell;
 398     uint8_t wall;
 399     uint8_t solved_maze[MAZE_WIDTH][MAZE_HEIGHT];
 400
 401     /* toggle the visibility of the path */
 402     maze->show_path = ~(maze->show_path);
 403
 404     /* no need to solve the maze if already solved */
 405     if (maze->solved)
 406         return;
 407
 408     /* work on a copy of the maze */
 409     rb->memcpy(solved_maze, maze->maze, sizeof(maze->maze));
 410
 411     /* remove walls on start and end point */
 412     solved_maze[0][0] &= ~WALL_N;
 413     solved_maze[MAZE_WIDTH-1][MAZE_HEIGHT-1] &= ~WALL_S;
 414
 415     /* first, mark all the cells as reachable */
 416     for(y=0; y<MAZE_HEIGHT; y++){
 417         for(x=0; x<MAZE_WIDTH; x++){
 418             solved_maze[x][y] |= PATH;
 419         }
 420     }
 421
 422     /* start solving */
 423     while(dead_ends){
 424         /* solve by blocking off dead ends -- backward approach */
 425         dead_ends = 0;
 426         /* scan for dead ends */
 427         for(y=0; y<MAZE_HEIGHT; y++){
 428             rb->yield();
 429             for(x=0; x<MAZE_WIDTH; x++){
 430                 cell = solved_maze[x][y];
 431                 wall = cell & WALL_ALL;
 432                 if((wall == (WALL_E | WALL_S | WALL_W)) ||
 433                    (wall == (WALL_N | WALL_S | WALL_W)) ||
 434                    (wall == (WALL_N | WALL_E | WALL_W)) ||
 435                    (wall == (WALL_N | WALL_E | WALL_S))){
 436                     /* found dead end, clear path bit and set all its walls */
 437                     solved_maze[x][y] &= ~PATH;
 438                     solved_maze[x][y] |= WALL_ALL;
 439                     /* don't forget the neighbours */
 440                     if(!BORDER_S(y))
 441                         solved_maze[x][y+1] |= WALL_N;
 442                     if(!BORDER_W(x))
 443                         solved_maze[x-1][y] |= WALL_E;
 444                     if(!BORDER_N(y))
 445                         solved_maze[x][y-1] |= WALL_S;
 446                     if(!BORDER_E(x))
 447                         solved_maze[x+1][y] |= WALL_W;
 448                     dead_ends++;
 449                 }
 450             }
 451         }
 452     }
 453
 454     /* copy all the path bits to the maze */
 455     for(y=0; y<MAZE_HEIGHT; y++){
 456         for(x=0; x<MAZE_WIDTH; x++){
 457             maze->maze[x][y] |= solved_maze[x][y] & PATH;
 458         }
 459     }
 460
 461     /* mark the maze as solved */
 462     maze->solved = true;
 463 }
 464
 465 static void maze_move_player_up(struct maze* maze)
 466 {
 467     uint8_t cell = maze->maze[maze->player_x][maze->player_y];
 468     if(!BORDER_N(maze->player_y) && !(cell & WALL_N))
 469         maze->player_y--;
 470 }
 471
 472 static void maze_move_player_right(struct maze* maze)
 473 {
 474     uint8_t cell = maze->maze[maze->player_x][maze->player_y];
 475     if(!BORDER_E(maze->player_x) && !(cell & WALL_E))
 476         maze->player_x++;
 477 }
 478
 479 static void maze_move_player_down(struct maze* maze)
 480 {
 481     uint8_t cell = maze->maze[maze->player_x][maze->player_y];
 482     if(!BORDER_S(maze->player_y) && !(cell & WALL_S))
 483         maze->player_y++;
 484 }
 485
 486 static void maze_move_player_left(struct maze* maze)
 487 {
 488     uint8_t cell = maze->maze[maze->player_x][maze->player_y];
 489     if(!BORDER_W(maze->player_x) && !(cell & WALL_W))
 490         maze->player_x--;
 491 }
 492
 493 /**********************************/
 494 /* this is the plugin entry point */
 495 /**********************************/
 496 enum plugin_status plugin_start(const struct plugin_api* api, const void* parameter)
 497 {
 498     int button, lastbutton = BUTTON_NONE;
 499     int quit = 0;
 500     int i;
 501     struct maze maze;
 502     (void)parameter;
 503     rb = api;
 504
 505     /* Turn off backlight timeout */
 506     backlight_force_on(rb); /* backlight control in lib/helper.c */
 507
 508     /* Seed the RNG */
 509     rb->srand(*rb->current_tick);
 510
 511     FOR_NB_SCREENS(i)
 512         rb->screens[i]->set_viewport(NULL);
 513
 514     /* Draw the background */
 515 #if LCD_DEPTH > 1
 516     rb->lcd_set_backdrop(NULL);
 517 #if LCD_DEPTH >= 16
 518     rb->lcd_set_foreground(LCD_RGBPACK( 0, 0, 0));
 519     rb->lcd_set_background(LCD_RGBPACK(182, 198, 229)); /* rockbox blue */
 520 #elif LCD_DEPTH == 2
 521     rb->lcd_set_foreground(0);
 522     rb->lcd_set_background(LCD_DEFAULT_BG);
 523 #endif
 524 #endif
 525
 526     /* Initialize and draw the maze */
 527     maze_init(&maze);
 528     maze_generate(&maze);
 529     FOR_NB_SCREENS(i)
 530         maze_draw(&maze, rb->screens[i]);
 531
 532     while(!quit) {
 533 #ifdef __PLUGINLIB_ACTIONS_H__
 534         button = pluginlib_getaction(rb, TIMEOUT_BLOCK, plugin_contexts, 2);
 535 #else
 536         button = rb->button_get(true);
 537 #endif
 538         switch(button) {
 539         case MAZE_NEW:
 540 #ifdef MAZE_NEW_PRE
 541             if(lastbutton != MAZE_NEW_PRE)
 542                 break;
 543 #endif
 544             maze_init(&maze);
 545             maze_generate(&maze);
 546             FOR_NB_SCREENS(i)
 547                 maze_draw(&maze, rb->screens[i]);
 548             break;
 549         case MAZE_SOLVE:
 550             maze_solve(&maze);
 551             FOR_NB_SCREENS(i)
 552                 maze_draw(&maze, rb->screens[i]);
 553             break;
 554         case MAZE_UP:
 555         case MAZE_RUP:
 556             maze_move_player_up(&maze);
 557             FOR_NB_SCREENS(i)
 558                 maze_draw(&maze, rb->screens[i]);
 559             break;
 560         case MAZE_RIGHT:
 561         case MAZE_RRIGHT:
 562             maze_move_player_right(&maze);
 563             FOR_NB_SCREENS(i)
 564                 maze_draw(&maze, rb->screens[i]);
 565             break;
 566         case MAZE_DOWN:
 567         case MAZE_RDOWN:
 568             maze_move_player_down(&maze);
 569             FOR_NB_SCREENS(i)
 570                 maze_draw(&maze, rb->screens[i]);
 571             break;
 572         case MAZE_LEFT:
 573         case MAZE_RLEFT:
 574             maze_move_player_left(&maze);
 575             FOR_NB_SCREENS(i)
 576                 maze_draw(&maze, rb->screens[i]);
 577             break;
 578         case MAZE_QUIT:
 579             /* quit plugin */
 580             quit=1;
 581             break;
 582         default:
 583             if (rb->default_event_handler(button) == SYS_USB_CONNECTED) {
 584                 /* quit plugin */
 585                 quit=2;
 586             }
 587             break;
 588         }
 589         if( button != BUTTON_NONE )
 590             lastbutton = button;
 591
 592     }
 593     /* Turn on backlight timeout (revert to settings) */
 594     backlight_use_settings(rb); /* backlight control in lib/helper.c */
 595     return ((quit == 1) ? PLUGIN_OK : PLUGIN_USB_CONNECTED);
 596 }