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