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