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