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