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