git.hungrycats.org Git - xscreensaver/blob - hacks/maze.c

   1 /******************************************************************************
   2  * [ maze ] ...
   3  *
   4  * modified:  [ 13-08-08 ] Jamie Zawinski <jwz@jwz.org>
   5  *              Removed the bridge option: it didn't look good, and it made
   6  *              the code a lot harder to understand.
   7  *              Made the maze stay out of the area used for the -fps display.
   8  *              Cleaned up and commented.
   9  *
  10  * modified:  [ 1-04-00 ]  Johannes Keukelaar <johannes@nada.kth.se>
  11  *              Added -ignorant option (not the default) to remove knowlege
  12  *              of the direction in which the exit lies.
  13  *
  14  * modified:  [ 6-28-98 ]  Zack Weinberg <zack@rabi.phys.columbia.edu>
  15  *
  16  *              Made the maze-solver somewhat more intelligent.  There are
  17  *              three optimizations:
  18  *
  19  *              - Straight-line lookahead: the solver does not enter dead-end
  20  *                corridors.  This is a win with all maze generators.
  21  *
  22  *              - First order direction choice: the solver knows where the
  23  *                exit is in relation to itself, and will try paths leading in
  24  *                that direction first. This is a major win on maze generator 1
  25  *                which tends to offer direct routes to the exit.
  26  *
  27  *              - Dead region elimination: the solver already has a map of
  28  *                all squares visited.  Whenever it starts to backtrack, it
  29  *                consults this map and marks off all squares that cannot be
  30  *                reached from the exit without crossing a square already
  31  *                visited.  Those squares can never contribute to the path to
  32  *                the exit, so it doesn't bother checking them.  This helps a
  33  *                lot with maze generator 2 and somewhat less with generator 1.
  34  *
  35  *              Further improvements would require knowledge of the wall map
  36  *              as well as the position of the exit and the squares visited.
  37  *              I would consider that to be cheating.  Generator 0 makes
  38  *              mazes which are remarkably difficult to solve mechanically --
  39  *              even with these optimizations the solver generally must visit
  40  *              at least two-thirds of the squares.  This is partially
  41  *              because generator 0's mazes have longer paths to the exit.
  42  *
  43  * modified:  [ 4-10-97 ]  Johannes Keukelaar <johannes@nada.kth.se>
  44  *              Added multiple maze creators. Robustified solver.
  45  *              Added bridge option.
  46  * modified:  [ 8-11-95 ] Ed James <james@mml.mmc.com>
  47  *              added fill of dead-end box to solve_maze while loop.
  48  * modified:  [ 3-7-93 ]  Jamie Zawinski <jwz@jwz.org>
  49  *              added the XRoger logo, cleaned up resources, made
  50  *              grid size a parameter.
  51  * modified:  [ 3-3-93 ]  Jim Randell <jmr@mddjmr.fc.hp.com>
  52  *              Added the colour stuff and integrated it with jwz's
  53  *              screenhack stuff.  There's still some work that could
  54  *              be done on this, particularly allowing a resource to
  55  *              specify how big the squares are.
  56  * modified:  [ 10-4-88 ]  Richard Hess    ...!uunet!cimshop!rhess
  57  *              [ Revised primary execution loop within main()...
  58  *              [ Extended X event handler, check_events()...
  59  * modified:  [ 1-29-88 ]  Dave Lemke      lemke@sun.com
  60  *              [ Hacked for X11...
  61  *              [  Note the word "hacked" -- this is extremely ugly, but at
  62  *              [   least it does the job.  NOT a good programming example
  63  *              [   for X.
  64  * original:  [ 6/21/85 ]  Martin Weiss    Sun Microsystems  [ SunView ]
  65  *
  66  ******************************************************************************
  67  Copyright 1988 by Sun Microsystems, Inc. Mountain View, CA.
  68
  69  All Rights Reserved
  70
  71  Permission to use, copy, modify, and distribute this software and its
  72  documentation for any purpose and without fee is hereby granted,
  73  provided that the above copyright notice appear in all copies and that
  74  both that copyright notice and this permission notice appear in
  75  supporting documentation, and that the names of Sun or MIT not be
  76  used in advertising or publicity pertaining to distribution of the
  77  software without specific prior written permission. Sun and M.I.T.
  78  make no representations about the suitability of this software for
  79  any purpose. It is provided "as is" without any express or implied warranty.
  80
  81  SUN DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  82  ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  83  PURPOSE. IN NO EVENT SHALL SUN BE LIABLE FOR ANY SPECIAL, INDIRECT
  84  OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
  85  OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  86  OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE
  87  OR PERFORMANCE OF THIS SOFTWARE.
  88  *****************************************************************************/
  89
  90 #include "screenhack.h"
  91 #include "erase.h"
  92
  93 #include  <stdio.h>
  94
  95 /* #include  <X11/bitmaps/gray1> */
  96 #define gray1_width  2
  97 #define gray1_height 2
  98 static const char gray1_bits[] = { 0x01, 0x02 };
  99
 100
 101 #define MAX_MAZE_SIZE_X 1000
 102 #define MAX_MAZE_SIZE_Y 1000
 103
 104 #define MOVE_LIST_SIZE  (MAX_MAZE_SIZE_X * MAX_MAZE_SIZE_Y)
 105
 106 #define NOT_DEAD        0x8000
 107 #define SOLVER_VISIT    0x4000
 108 #define START_SQUARE    0x2000
 109 #define END_SQUARE      0x1000
 110
 111 #define WALL_TOP        0x8
 112 #define WALL_RIGHT      0x4
 113 #define WALL_BOTTOM     0x2
 114 #define WALL_LEFT       0x1
 115 #define WALL_ANY        0xF
 116
 117 #define DOOR_IN_TOP     0x800
 118 #define DOOR_IN_RIGHT   0x400
 119 #define DOOR_IN_BOTTOM  0x200
 120 #define DOOR_IN_LEFT    0x100
 121 #define DOOR_IN_ANY     0xF00
 122
 123 #define DOOR_OUT_TOP    0x80
 124 #define DOOR_OUT_RIGHT  0x40
 125 #define DOOR_OUT_BOTTOM 0x20
 126 #define DOOR_OUT_LEFT   0x10
 127
 128
 129 #define border_x        (0)
 130 #define border_y        (0)
 131
 132 #define get_random(x)   (random() % (x))
 133
 134
 135 struct move_list_struct {
 136   unsigned short x;
 137   unsigned short y;
 138   unsigned char dir, ways;
 139 };
 140
 141 struct solve_state {
 142   int running;
 143   int i, x, y, bt;
 144 };
 145
 146
 147 struct state {
 148   Display *dpy;
 149   Window window;
 150
 151   GC    gc, cgc, tgc, sgc, ugc, logo_gc, erase_gc;
 152   Pixmap logo_map;
 153
 154   int logo_x, logo_y;           /* in grid cells (or -1) */
 155   int logo_width, logo_height;  /* in pixels */
 156   int fps_width, fps_height;    /* in pixels */
 157
 158   int solve_delay, pre_solve_delay, post_solve_delay;
 159
 160   unsigned short maze[MAX_MAZE_SIZE_X][MAX_MAZE_SIZE_Y];
 161
 162   struct move_list_struct move_list[MOVE_LIST_SIZE];
 163   struct move_list_struct save_path[MOVE_LIST_SIZE];
 164   struct move_list_struct path[MOVE_LIST_SIZE];
 165
 166   int maze_size_x, maze_size_y;
 167   int sqnum, cur_sq_x, cur_sq_y, path_length;
 168   int start_x, start_y, start_dir, end_x, end_y, end_dir;
 169   int grid_width, grid_height;
 170   int bw;
 171
 172   int x, y, restart, stop, state, max_length;
 173   int sync_p, sync_tick;
 174   int ignorant_p;
 175
 176   struct solve_state *solve_state;
 177
 178   int *sets;            /* The sets that our squares are in. */
 179   int *hedges;          /* The `list' of hedges. */
 180
 181   int this_gen;
 182   int erase_window;
 183   eraser_state *eraser;
 184
 185   int ifrandom;
 186   int ifinit;
 187
 188 };
 189
 190
 191 static void draw_wall (struct state *, int, int, int, GC);
 192 static void draw_solid_square (struct state *, int, int, int, GC);
 193 static void build_wall (struct state *, int, int, int);
 194
 195
 196 static void
 197 set_maze_sizes (struct state *st, int width, int height)
 198 {
 199   st->maze_size_x = width / st->grid_width;
 200   st->maze_size_y = height / st->grid_height;
 201
 202   if (st->maze_size_x < 4) st->maze_size_x = 4;
 203   if (st->maze_size_y < 4) st->maze_size_y = 4;
 204 }
 205
 206
 207 /* Resets the maze grid, picks the starting and ending points,
 208    and the position of the logo, if any.
 209  */
 210 static void
 211 initialize_maze (struct state *st)
 212 {
 213   int i, j, wall;
 214   int logow = 1 + st->logo_width / st->grid_width;
 215   int logoh = 1 + st->logo_height / st->grid_height;
 216
 217  AGAIN:
 218
 219   /* initialize all squares */
 220   for ( i=0; i<st->maze_size_x; i++) {
 221     for ( j=0; j<st->maze_size_y; j++) {
 222       st->maze[i][j] = 0;
 223     }
 224   }
 225
 226   /* top wall */
 227   for ( i=0; i<st->maze_size_x; i++ ) {
 228     st->maze[i][0] |= WALL_TOP;
 229   }
 230
 231   /* right wall */
 232   for ( j=0; j<st->maze_size_y; j++ ) {
 233     st->maze[st->maze_size_x-1][j] |= WALL_RIGHT;
 234   }
 235
 236   /* bottom wall */
 237   for ( i=0; i<st->maze_size_x; i++ ) {
 238     st->maze[i][st->maze_size_y-1] |= WALL_BOTTOM;
 239   }
 240
 241   /* left wall */
 242   for ( j=0; j<st->maze_size_y; j++ ) {
 243     st->maze[0][j] |= WALL_LEFT;
 244   }
 245
 246   /* set start square */
 247   wall = get_random(4);
 248   switch (wall) {
 249   case 0:
 250     i = get_random(st->maze_size_x);
 251     j = 0;
 252     break;
 253   case 1:
 254     i = st->maze_size_x - 1;
 255     j = get_random(st->maze_size_y);
 256     break;
 257   case 2:
 258     i = get_random(st->maze_size_x);
 259     j = st->maze_size_y - 1;
 260     break;
 261   case 3:
 262     i = 0;
 263     j = get_random(st->maze_size_y);
 264     break;
 265   }
 266   st->maze[i][j] |= START_SQUARE;
 267   st->maze[i][j] |= ( DOOR_IN_TOP >> wall );
 268   st->maze[i][j] &= ~( WALL_TOP >> wall );
 269   st->cur_sq_x = i;
 270   st->cur_sq_y = j;
 271   st->start_x = i;
 272   st->start_y = j;
 273   st->start_dir = wall;
 274   st->sqnum = 0;
 275
 276   /* set end square */
 277   wall = (wall + 2)%4;
 278   switch (wall) {
 279   case 0:
 280     i = get_random(st->maze_size_x);
 281     j = 0;
 282     break;
 283   case 1:
 284     i = st->maze_size_x - 1;
 285     j = get_random(st->maze_size_y);
 286     break;
 287   case 2:
 288     i = get_random(st->maze_size_x);
 289     j = st->maze_size_y - 1;
 290     break;
 291   case 3:
 292     i = 0;
 293     j = get_random(st->maze_size_y);
 294     break;
 295   }
 296   st->maze[i][j] |= END_SQUARE;
 297   st->maze[i][j] |= ( DOOR_OUT_TOP >> wall );
 298   st->maze[i][j] &= ~( WALL_TOP >> wall );
 299   st->end_x = i;
 300   st->end_y = j;
 301   st->end_dir = wall;
 302
 303   /* set logo */
 304   if ((st->maze_size_x-logow >= 6) && (st->maze_size_y-logoh >= 6))
 305     {
 306       /* not closer than 3 grid units from a wall, to ensure that it
 307          won't overlap the entrance or exit. */
 308       st->logo_x = get_random (st->maze_size_x - logow - 5) + 3;
 309       st->logo_y = get_random (st->maze_size_y - logoh - 5) + 3;
 310       for (i=0; i<logow; i++)
 311         for (j=0; j<logoh; j++)
 312           /* mark as having doors to prevent these cells being used in maze. */
 313           st->maze[st->logo_x + i][st->logo_y + j] |= DOOR_IN_ANY;
 314     }
 315   else
 316     st->logo_y = st->logo_x = -1;
 317
 318   /* mask out the fps area */
 319   if (st->fps_width > 0)
 320     {
 321       int fpsw = 1 + st->fps_width  / st->grid_width;
 322       int fpsh = 1 + st->fps_height / st->grid_width;
 323
 324       /* if the chosen logo position overlapped the fps area, try again! */
 325       if (st->logo_x < fpsw+3 && st->logo_y+logoh > st->maze_size_y-fpsh-4)
 326         goto AGAIN;
 327
 328       /* if the start or end point is inside the fps area, try again! */
 329       if ((st->start_x <= fpsw && st->start_y >= st->maze_size_y-fpsh-1) ||
 330           (st->end_x   <= fpsw && st->end_y   >= st->maze_size_y-fpsh-1))
 331         goto AGAIN;
 332
 333       for (i=0; i<fpsw; i++)
 334         for (j=0; j<fpsh; j++) {
 335           /* mark as having doors to prevent these cells being used in maze.
 336              mark as visit to prevent it being colored "unreachable". */
 337           st->maze[i][st->maze_size_y - j - 1] |= DOOR_IN_ANY|SOLVER_VISIT;
 338           /* take off left/bottom wall or the FPS text overlaps it */
 339           st->maze[i][st->maze_size_y - j - 1] &= ~(WALL_BOTTOM|WALL_LEFT);
 340         }
 341     }
 342 }
 343
 344
 345 /****************************************************************************
 346  Generator 2: Set-based maze generator.
 347
 348  Put each square in the maze in a separate set.  Also, make a list of all the
 349  hedges.  Randomize that list.  Walk through the list. If, for a certain
 350  hedge, the two squares on both sides of it are in different sets, union the
 351  sets and remove the hedge.  Continue until all hedges have been processed or
 352  only one set remains.
 353
 354  This is essentially the "Kruskal" algorithm.
 355
 356  ****************************************************************************/
 357
 358 static void mask_out_set_rect(struct state *st, int x, int y, int w, int h);
 359
 360 /* Initialise the sets. */
 361 static void
 362 init_sets(struct state *st)
 363 {
 364   int i, t, r;
 365
 366   if(st->sets)
 367     free(st->sets);
 368   st->sets = (int *)malloc(st->maze_size_x*st->maze_size_y*sizeof(int));
 369   if(!st->sets)
 370     abort();
 371   for(i = 0; i < st->maze_size_x*st->maze_size_y; i++)
 372     {
 373       st->sets[i] = i;
 374     }
 375
 376   if(st->hedges)
 377     free(st->hedges);
 378   st->hedges = (int *)malloc(st->maze_size_x*st->maze_size_y*2*sizeof(int));
 379   if(!st->hedges)
 380     abort();
 381   for(i = 0; i < st->maze_size_x*st->maze_size_y*2; i++)
 382     {
 383       st->hedges[i] = i;
 384     }
 385   /* Mask out outside walls. */
 386   for(i = 0; i < st->maze_size_y; i++)
 387     {
 388       st->hedges[2*((st->maze_size_x)*i+st->maze_size_x-1)+1] = -1;
 389     }
 390   for(i = 0; i < st->maze_size_x; i++)
 391     {
 392       st->hedges[2*((st->maze_size_y-1)*st->maze_size_x+i)] = -1;
 393     }
 394
 395   /* Mask out the logo area. */
 396   if(st->logo_x!=-1)
 397     {
 398       int logow = 1 + st->logo_width  / st->grid_width;
 399       int logoh = 1 + st->logo_height / st->grid_height;
 400       mask_out_set_rect(st, st->logo_x, st->logo_y, logow, logoh);
 401     }
 402
 403   /* Mask out the FPS area. */
 404   if(st->fps_width > 0)
 405     {
 406       int fpsw = 1 + st->fps_width  / st->grid_width;
 407       int fpsh = 1 + st->fps_height / st->grid_height;
 408       mask_out_set_rect(st, 0, st->maze_size_y-fpsh, fpsw, fpsh);
 409     }
 410
 411   for(i = 0; i < st->maze_size_x*st->maze_size_y*2; i++)
 412     {
 413       t = st->hedges[i];
 414       r = random()%(st->maze_size_x*st->maze_size_y*2);
 415       st->hedges[i] = st->hedges[r];
 416       st->hedges[r] = t;
 417     }
 418 }
 419
 420 /* Get the representative of a set. */
 421 static int
 422 get_set(struct state *st, int num)
 423 {
 424   int s;
 425
 426   if(st->sets[num]==num)
 427     return num;
 428   else
 429     {
 430       s = get_set(st, st->sets[num]);
 431       st->sets[num] = s;
 432       return s;
 433     }
 434 }
 435
 436 /* Join two sets together. */
 437 static void
 438 join_sets(struct state *st, int num1, int num2)
 439 {
 440   int s1, s2;
 441
 442   s1 = get_set(st, num1);
 443   s2 = get_set(st, num2);
 444
 445   if(s1<s2)
 446     st->sets[s2] = s1;
 447   else
 448     st->sets[s1] = s2;
 449 }
 450
 451 /* Exitialise the sets. */
 452 static void
 453 exit_sets(struct state *st)
 454 {
 455   if(st->hedges)
 456     free(st->hedges);
 457   st->hedges = 0;
 458   if(st->sets)
 459     free(st->sets);
 460   st->sets = 0;
 461 }
 462
 463
 464 static void
 465 set_create_maze(struct state *st)
 466 {
 467   int i, h, xx, yy, dir, v, w;
 468
 469   /* Do almost all the setup. */
 470   init_sets(st);
 471
 472   /* Start running through the hedges. */
 473   for(i = 0; i < 2*st->maze_size_x*st->maze_size_y; i++)
 474     {
 475       h = st->hedges[i];
 476
 477       /* This one is in the logo or outside border. */
 478       if(h==-1)
 479         continue;
 480
 481       dir = h%2?1:2;
 482       xx = (h>>1)%st->maze_size_x;
 483       yy = (h>>1)/st->maze_size_x;
 484
 485       v = xx;
 486       w = yy;
 487       switch(dir)
 488         {
 489         case 1:
 490           v++;
 491           break;
 492         case 2:
 493           w++;
 494           break;
 495         }
 496
 497       if(get_set(st, xx+yy*st->maze_size_x)!=get_set(st, v+w*st->maze_size_x))
 498         {
 499           join_sets(st, xx+yy*st->maze_size_x, v+w*st->maze_size_x);
 500           /* Don't draw the wall. */
 501         }
 502       else
 503         {
 504           /* Don't join the sets. */
 505           build_wall(st, xx, yy, dir);
 506         }
 507     }
 508
 509   /* Free some memory. */
 510   exit_sets(st);
 511 }
 512
 513 /* mark a rectangle as being unavailable for usage in the maze */
 514 static void
 515 mask_out_set_rect(struct state *st, int x, int y, int w, int h)
 516 {
 517   int xx, yy;
 518   for(xx = x; xx < x+w; xx++)
 519     for(yy = y; yy < y+h; yy++)
 520       {
 521         st->hedges[2*(xx+st->maze_size_x*yy)+1] = -1;
 522         st->hedges[2*(xx+st->maze_size_x*yy)] = -1;
 523       }
 524   for(xx = x; xx < x+w; xx++)
 525     {
 526       build_wall(st, xx, y, 0);
 527       build_wall(st, xx, y+h, 0);
 528       st->hedges[2*(xx+st->maze_size_x*(y-1))] = -1;
 529     }
 530   for(yy = y; yy < y+h; yy++)
 531     {
 532       build_wall(st, x, yy, 3);
 533       build_wall(st, x+w, yy, 3);
 534       st->hedges[2*(x-1+st->maze_size_x*yy)+1] = -1;
 535     }
 536 }
 537
 538
 539 /****************************************************************************
 540  Generator 1: Wall-building maze generator.
 541
 542  Pick a random, empty corner in the maze.  Pick a random direction. Draw a
 543  wall in that direction, from that corner until we hit a wall.  Option: Only
 544  draw the wall if it's going to be shorter than a certain length.  Otherwise
 545  we get lots of long walls.
 546
 547  This is essentially the "Prim" algorithm.
 548  ****************************************************************************/
 549
 550 static void alt_mask_out_rect(struct state *st, char *corners,
 551                               int x, int y, int w, int h);
 552
 553 static void
 554 alt_create_maze(struct state *st)
 555 {
 556   char *corners;
 557   int *c_idx;
 558   int i, j, height, width, open_corners, k, dir, xx, yy;
 559
 560   height = st->maze_size_y+1;
 561   width = st->maze_size_x+1;
 562
 563   /* Allocate and clear some mem. */
 564   corners = (char *)calloc(height*width, 1);
 565   if(!corners)
 566     return;
 567
 568   /* Set up the indexing array. */
 569   c_idx = (int *)malloc(sizeof(int)*height*width);
 570   if(!c_idx)
 571     {
 572       free(corners);
 573       return;
 574     }
 575   for(i = 0; i < height*width; i++)
 576     c_idx[i] = i;
 577   for(i = 0; i < height*width; i++)
 578     {
 579       j = c_idx[i];
 580       k = random()%(height*width);
 581       c_idx[i] = c_idx[k];
 582       c_idx[k] = j;
 583     }
 584
 585   /* Set up some initial walls. */
 586   /* Outside walls. */
 587   for(i = 0; i < width; i++)
 588     {
 589       corners[i] = 1;
 590       corners[i+width*(height-1)] = 1;
 591     }
 592   for(i = 0; i < height; i++)
 593     {
 594       corners[i*width] = 1;
 595       corners[i*width+width-1] = 1;
 596     }
 597
 598   /* mask out the logo area */
 599   if(st->logo_x!=-1)
 600     {
 601       int logow = 1 + st->logo_width / st->grid_width;
 602       int logoh = 1 + st->logo_height / st->grid_height;
 603       alt_mask_out_rect (st, corners, st->logo_x, st->logo_y, logow, logoh);
 604     }
 605
 606   /* mask out the FPS area */
 607   if(st->fps_width>0)
 608     {
 609       int fpsw = 1 + st->fps_width  / st->grid_width;
 610       int fpsh = 1 + st->fps_height / st->grid_height;
 611       alt_mask_out_rect (st, corners, 0, st->maze_size_y-fpsh, fpsw, fpsh);
 612     }
 613
 614   /* Count open gridpoints. */
 615   open_corners = 0;
 616   for(i = 0; i < width; i++)
 617     for(j = 0; j < height; j++)
 618       if(!corners[i+width*j])
 619         open_corners++;
 620
 621   /* Now do actual maze generation. */
 622   while(open_corners>0)
 623     {
 624       for(i = 0; i < width*height; i++)
 625         {
 626           if(!corners[c_idx[i]])
 627             {
 628               xx = c_idx[i]%width;
 629               yy = c_idx[i]/width;
 630               /* Choose a random direction. */
 631               dir = random()%4;
 632
 633               k = 0;
 634               /* Measure the length of the wall we'd draw. */
 635               while(!corners[xx+width*yy])
 636                 {
 637                   k++;
 638                   switch(dir)
 639                     {
 640                     case 0:
 641                       yy--;
 642                       break;
 643                     case 1:
 644                       xx++;
 645                       break;
 646                     case 2:
 647                       yy++;
 648                       break;
 649                     case 3:
 650                       xx--;
 651                       break;
 652                     }
 653                 }
 654
 655               if(k<=st->max_length)
 656                 {
 657                   xx = c_idx[i]%width;
 658                   yy = c_idx[i]/width;
 659
 660                   /* Draw a wall until we hit something. */
 661                   while(!corners[xx+width*yy])
 662                     {
 663                       open_corners--;
 664                       corners[xx+width*yy] = 1;
 665                       switch(dir)
 666                         {
 667                         case 0:
 668                           build_wall(st, xx-1, yy-1, 1);
 669                           yy--;
 670                           break;
 671                         case 1:
 672                           build_wall(st, xx, yy, 0);
 673                           xx++;
 674                           break;
 675                         case 2:
 676                           build_wall(st, xx, yy, 3);
 677                           yy++;
 678                           break;
 679                         case 3:
 680                           build_wall(st, xx-1, yy-1, 2);
 681                           xx--;
 682                           break;
 683                         }
 684                     }
 685                 }
 686             }
 687         }
 688     }
 689
 690   /* Free some memory we used. */
 691   free(corners);
 692   free(c_idx);
 693 }
 694
 695
 696 /* mark a rectangle as being unavailable for usage in the maze */
 697 static void
 698 alt_mask_out_rect(struct state *st, char *corners, int x, int y, int w, int h)
 699 {
 700   int i, j, xx, yy;
 701   int mazew = st->maze_size_x+1;
 702
 703   for(i = x; i <= x+w; i++)
 704     for(j = y; j <= y+h; j++)
 705       corners[i+mazew*j] = 1;
 706
 707   for(xx = x; xx < x+w; xx++)
 708     {
 709       build_wall(st, xx, y, 0);
 710       if (y+h < st->maze_size_y)
 711         build_wall(st, xx, y+h, 0);
 712     }
 713   for(yy = y; yy < y+h; yy++)
 714     {
 715       if (x > 0)
 716         build_wall(st, x, yy, 3);
 717       build_wall(st, x+w, yy, 3);
 718     }
 719 }
 720
 721
 722 /****************************************************************************
 723  Generator 0: The original maze generator.
 724
 725  Start somewhere.  Take a step in a random direction.  Keep doing this until
 726  we hit a wall.  Then, backtrack until we find a point where we can go in
 727  another direction.
 728
 729  This is essentially the "depth-first recursive backtracker" algorithm.
 730  ****************************************************************************/
 731
 732 static int choose_door (struct state *st);
 733 static int backup (struct state *st);
 734
 735 static void
 736 create_maze (struct state *st)    /* create a maze layout given the initialized maze */
 737 {
 738   int i, newdoor = 0;
 739
 740   do {
 741     st->move_list[st->sqnum].x = st->cur_sq_x;
 742     st->move_list[st->sqnum].y = st->cur_sq_y;
 743     st->move_list[st->sqnum].dir = newdoor;
 744     while ( ( newdoor = choose_door(st) ) == -1 ) { /* pick a door */
 745       if ( backup(st) == -1 ) { /* no more doors ... backup */
 746         return; /* done ... return */
 747       }
 748     }
 749
 750     /* mark the out door */
 751     st->maze[st->cur_sq_x][st->cur_sq_y] |= ( DOOR_OUT_TOP >> newdoor );
 752
 753     switch (newdoor) {
 754     case 0: st->cur_sq_y--;
 755       break;
 756     case 1: st->cur_sq_x++;
 757       break;
 758     case 2: st->cur_sq_y++;
 759       break;
 760     case 3: st->cur_sq_x--;
 761       break;
 762     }
 763     st->sqnum++;
 764
 765     /* mark the in door */
 766     st->maze[st->cur_sq_x][st->cur_sq_y] |= ( DOOR_IN_TOP >> ((newdoor+2)%4) );
 767
 768     /* if end square set path length and save path */
 769     if ( st->maze[st->cur_sq_x][st->cur_sq_y] & END_SQUARE ) {
 770       st->path_length = st->sqnum;
 771       for ( i=0; i<st->path_length; i++) {
 772         st->save_path[i].x = st->move_list[i].x;
 773         st->save_path[i].y = st->move_list[i].y;
 774         st->save_path[i].dir = st->move_list[i].dir;
 775       }
 776     }
 777
 778   } while (1);
 779
 780 }
 781
 782
 783 static int
 784 choose_door (struct state *st)                                   /* pick a new path */
 785 {
 786   int candidates[3];
 787   int num_candidates;
 788
 789   num_candidates = 0;
 790
 791   /* top wall */
 792   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_TOP )
 793     goto rightwall;
 794   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_TOP )
 795     goto rightwall;
 796   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_TOP )
 797     goto rightwall;
 798   if ( st->maze[st->cur_sq_x][st->cur_sq_y - 1] & DOOR_IN_ANY ) {
 799     st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_TOP;
 800     st->maze[st->cur_sq_x][st->cur_sq_y - 1] |= WALL_BOTTOM;
 801     draw_wall(st, st->cur_sq_x, st->cur_sq_y, 0, st->gc);
 802     goto rightwall;
 803   }
 804   candidates[num_candidates++] = 0;
 805
 806  rightwall:
 807   /* right wall */
 808   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_RIGHT )
 809     goto bottomwall;
 810   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_RIGHT )
 811     goto bottomwall;
 812   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_RIGHT )
 813     goto bottomwall;
 814   if ( st->maze[st->cur_sq_x + 1][st->cur_sq_y] & DOOR_IN_ANY ) {
 815     st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_RIGHT;
 816     st->maze[st->cur_sq_x + 1][st->cur_sq_y] |= WALL_LEFT;
 817     draw_wall(st, st->cur_sq_x, st->cur_sq_y, 1, st->gc);
 818     goto bottomwall;
 819   }
 820   candidates[num_candidates++] = 1;
 821
 822  bottomwall:
 823   /* bottom wall */
 824   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_BOTTOM )
 825     goto leftwall;
 826   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_BOTTOM )
 827     goto leftwall;
 828   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_BOTTOM )
 829     goto leftwall;
 830   if ( st->maze[st->cur_sq_x][st->cur_sq_y + 1] & DOOR_IN_ANY ) {
 831     st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_BOTTOM;
 832     st->maze[st->cur_sq_x][st->cur_sq_y + 1] |= WALL_TOP;
 833     draw_wall(st, st->cur_sq_x, st->cur_sq_y, 2, st->gc);
 834     goto leftwall;
 835   }
 836   candidates[num_candidates++] = 2;
 837
 838  leftwall:
 839   /* left wall */
 840   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_LEFT )
 841     goto donewall;
 842   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_LEFT )
 843     goto donewall;
 844   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_LEFT )
 845     goto donewall;
 846   if ( st->maze[st->cur_sq_x - 1][st->cur_sq_y] & DOOR_IN_ANY ) {
 847     st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_LEFT;
 848     st->maze[st->cur_sq_x - 1][st->cur_sq_y] |= WALL_RIGHT;
 849     draw_wall(st, st->cur_sq_x, st->cur_sq_y, 3, st->gc);
 850     goto donewall;
 851   }
 852   candidates[num_candidates++] = 3;
 853
 854  donewall:
 855   if (num_candidates == 0)
 856     return ( -1 );
 857   if (num_candidates == 1)
 858     return ( candidates[0] );
 859   return ( candidates[ get_random(num_candidates) ] );
 860
 861 }
 862
 863
 864 static int
 865 backup (struct state *st)                                          /* back up a move */
 866 {
 867   st->sqnum--;
 868   st->cur_sq_x = st->move_list[st->sqnum].x;
 869   st->cur_sq_y = st->move_list[st->sqnum].y;
 870   return ( st->sqnum );
 871 }
 872
 873
 874 /****************************************************************************
 875  Drawing the maze
 876  ****************************************************************************/
 877
 878 /* draws the maze outline, and the logo */
 879 static void
 880 draw_maze_border (struct state *st)
 881 {
 882   int i, j;
 883
 884   for ( i=0; i<st->maze_size_x; i++) {
 885     if ( st->maze[i][0] & WALL_TOP ) {
 886       XDrawLine(st->dpy, st->window, st->gc,
 887                 border_x + st->grid_width * i,
 888                 border_y,
 889                 border_x + st->grid_width * (i+1) - 1,
 890                 border_y);
 891     }
 892     if ((st->maze[i][st->maze_size_y - 1] & WALL_BOTTOM)) {
 893       XDrawLine(st->dpy, st->window, st->gc,
 894                 border_x + st->grid_width * i,
 895                 border_y + st->grid_height * (st->maze_size_y) - 1,
 896                 border_x + st->grid_width * (i+1) - 1,
 897                 border_y + st->grid_height * (st->maze_size_y) - 1);
 898     }
 899   }
 900   for ( j=0; j<st->maze_size_y; j++) {
 901     if ( st->maze[st->maze_size_x - 1][j] & WALL_RIGHT ) {
 902       XDrawLine(st->dpy, st->window, st->gc,
 903                 border_x + st->grid_width * st->maze_size_x - 1,
 904                 border_y + st->grid_height * j,
 905                 border_x + st->grid_width * st->maze_size_x - 1,
 906                 border_y + st->grid_height * (j+1) - 1);
 907     }
 908     if ( st->maze[0][j] & WALL_LEFT ) {
 909       XDrawLine(st->dpy, st->window, st->gc,
 910                 border_x,
 911                 border_y + st->grid_height * j,
 912                 border_x,
 913                 border_y + st->grid_height * (j+1) - 1);
 914     }
 915   }
 916
 917   if (st->logo_x != -1)
 918     {
 919       Window r;
 920       int xx, yy;
 921       unsigned int w, h, bbw, d;
 922
 923       /* round up to grid size */
 924       int ww = ((st->logo_width  / st->grid_width) + 1)  * st->grid_width;
 925       int hh = ((st->logo_height / st->grid_height) + 1) * st->grid_height;
 926       int lx, ly;
 927
 928       XGetGeometry (st->dpy, st->logo_map, &r, &xx, &yy, &w, &h, &bbw, &d);
 929
 930       /* kludge: if the logo "hole" is around the same size as the logo,
 931          don't center it (since the xscreensaver logo image is a little
 932          off center...  But do center it if the hole/gridsize is large. */
 933       if (ww < st->logo_width  + 5) ww = w;
 934       if (hh < st->logo_height + 5) hh = h;
 935
 936
 937       lx = border_x + 3 + st->grid_width  * st->logo_x + ((ww - w) / 2);
 938       ly = border_y + 3 + st->grid_height * st->logo_y + ((hh - h) / 2);
 939
 940       /* Fill the background of the logo box with the "unreachable" color */
 941       XFillRectangle (st->dpy, st->window, st->ugc,
 942                       border_x + 3 + st->grid_width  * st->logo_x,
 943                       border_y + 3 + st->grid_height * st->logo_y,
 944                       ww, hh);
 945
 946       XSetClipOrigin (st->dpy, st->logo_gc, lx, ly);
 947       if (d == 1)
 948         XCopyPlane (st->dpy, st->logo_map, st->window, st->logo_gc,
 949                     0, 0, w, h, lx, ly, 1);
 950       else
 951         XCopyArea (st->dpy, st->logo_map, st->window, st->logo_gc,
 952                    0, 0, w, h, lx, ly);
 953     }
 954   draw_solid_square (st, st->start_x, st->start_y, WALL_TOP >> st->start_dir, st->tgc);
 955   draw_solid_square (st, st->end_x, st->end_y, WALL_TOP >> st->end_dir, st->tgc);
 956 }
 957
 958
 959 /* Mark the maze grid as having a wall at the given coordinate,
 960    and draw that wall on the screen. */
 961 static void
 962 build_wall(struct state *st, int i, int j, int dir)
 963 {
 964   /* Draw it on the screen. */
 965   draw_wall(st, i, j, dir, st->gc);
 966   /* Put it in the maze. */
 967   switch(dir)
 968     {
 969     case 0:
 970       st->maze[i][j] |= WALL_TOP;
 971       if(j>0)
 972         st->maze[i][j-1] |= WALL_BOTTOM;
 973       break;
 974     case 1:
 975       st->maze[i][j] |= WALL_RIGHT;
 976       if(i<st->maze_size_x-1)
 977         st->maze[i+1][j] |= WALL_LEFT;
 978       break;
 979     case 2:
 980       st->maze[i][j] |= WALL_BOTTOM;
 981       if(j<st->maze_size_y-1)
 982         st->maze[i][j+1] |= WALL_TOP;
 983       break;
 984     case 3:
 985       st->maze[i][j] |= WALL_LEFT;
 986       if(i>0)
 987         st->maze[i-1][j] |= WALL_RIGHT;
 988       break;
 989     }
 990 }
 991
 992
 993 static void
 994 draw_wall(struct state *st, int i, int j, int dir, GC with_gc)                /* draw a single wall */
 995 {
 996   switch (dir) {
 997   case 0:
 998     XDrawLine(st->dpy, st->window, with_gc,
 999               border_x + st->grid_width * i,
1000               border_y + st->grid_height * j,
1001               border_x + st->grid_width * (i+1),
1002               border_y + st->grid_height * j);
1003     break;
1004   case 1:
1005     XDrawLine(st->dpy, st->window, with_gc,
1006               border_x + st->grid_width * (i+1),
1007               border_y + st->grid_height * j,
1008               border_x + st->grid_width * (i+1),
1009               border_y + st->grid_height * (j+1));
1010     break;
1011   case 2:
1012     XDrawLine(st->dpy, st->window, with_gc,
1013               border_x + st->grid_width * i,
1014               border_y + st->grid_height * (j+1),
1015               border_x + st->grid_width * (i+1),
1016               border_y + st->grid_height * (j+1));
1017     break;
1018   case 3:
1019     XDrawLine(st->dpy, st->window, with_gc,
1020               border_x + st->grid_width * i,
1021               border_y + st->grid_height * j,
1022               border_x + st->grid_width * i,
1023               border_y + st->grid_height * (j+1));
1024     break;
1025   }
1026
1027   if(st->sync_p) {
1028     /* too slow if we sync on every wall, so only sync about ten times
1029        during the maze-creation process.
1030      */
1031     st->sync_tick--;
1032     if (st->sync_tick <= 0) {
1033       XSync(st->dpy, False);
1034       st->sync_tick = st->maze_size_x * st->maze_size_x / 10;
1035     }
1036   }
1037 }
1038
1039
1040 static void
1041 draw_solid_square(struct state *st,
1042                   int i, int j,
1043                   int dir, GC with_gc)
1044 {
1045   switch (dir) {
1046   case WALL_TOP:
1047       XFillRectangle(st->dpy, st->window, with_gc,
1048                      border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1049                      border_y - st->bw-(st->bw==0?1:0) + st->grid_height * j,
1050                      st->grid_width - (st->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
1051       break;
1052   case WALL_RIGHT:
1053       XFillRectangle(st->dpy, st->window, with_gc,
1054                      border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1055                      border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1056                      st->grid_width, st->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
1057       break;
1058   case WALL_BOTTOM:
1059       XFillRectangle(st->dpy, st->window, with_gc,
1060                      border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1061                      border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1062                      st->grid_width - (st->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
1063       break;
1064   case WALL_LEFT:
1065       XFillRectangle(st->dpy, st->window, with_gc,
1066                      border_x - st->bw-(st->bw==0?1:0) + st->grid_width * i,
1067                      border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1068                      st->grid_width, st->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
1069       break;
1070   }
1071 }
1072
1073 /****************************************************************************
1074  Solving the maze
1075  ****************************************************************************/
1076
1077 static int
1078 longdeadend_p(struct state *st, int x1, int y1, int x2, int y2, int endwall)
1079 {
1080     int dx = x2 - x1, dy = y2 - y1;
1081     int sidewalls;
1082
1083     sidewalls = endwall | (endwall >> 2 | endwall << 2);
1084     sidewalls = ~sidewalls & WALL_ANY;
1085
1086     while((st->maze[x2][y2] & WALL_ANY) == sidewalls)
1087     {
1088         if (x2 + dx < 0 || x2 + dx >= st->maze_size_x ||
1089             y2 + dy < 0 || y2 + dy >= st->maze_size_y)
1090           break;
1091         x2 += dx;
1092         y2 += dy;
1093     }
1094
1095     if((st->maze[x2][y2] & WALL_ANY) == (sidewalls | endwall))
1096     {
1097         endwall = (endwall >> 2 | endwall << 2) & WALL_ANY;
1098         while(x1 != x2 || y1 != y2)
1099         {
1100             x1 += dx;
1101             y1 += dy;
1102             draw_solid_square(st, x1, y1, endwall, st->sgc);
1103             st->maze[x1][y1] |= SOLVER_VISIT;
1104         }
1105         return 1;
1106     }
1107     else
1108         return 0;
1109 }
1110
1111 /* Find all dead regions -- areas from which the goal cannot be reached --
1112    and mark them visited. */
1113 static void
1114 find_dead_regions(struct state *st)
1115 {
1116     int xx, yy, flipped;
1117
1118     /* Find all not SOLVER_VISIT squares bordering NOT_DEAD squares
1119        and mark them NOT_DEAD also.  Repeat until no more such squares. */
1120     st->maze[st->start_x][st->start_y] |= NOT_DEAD;
1121
1122     do
1123     {
1124         flipped = 0;
1125         for(xx = 0; xx < st->maze_size_x; xx++)
1126             for(yy = 0; yy < st->maze_size_y; yy++)
1127                 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1128                    && (   (xx && (st->maze[xx-1][yy] & NOT_DEAD))
1129                        || (yy && (st->maze[xx][yy-1] & NOT_DEAD))))
1130                 {
1131                     flipped = 1;
1132                     st->maze[xx][yy] |= NOT_DEAD;
1133                 }
1134         for(xx = st->maze_size_x-1; xx >= 0; xx--)
1135             for(yy = st->maze_size_y-1; yy >= 0; yy--)
1136                 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1137                    && (   (xx != st->maze_size_x-1 && (st->maze[xx+1][yy] & NOT_DEAD))
1138                        || (yy != st->maze_size_y-1 && (st->maze[xx][yy+1] & NOT_DEAD))))
1139                 {
1140                     flipped = 1;
1141                     st->maze[xx][yy] |= NOT_DEAD;
1142                 }
1143     }
1144     while(flipped);
1145
1146     for (yy = 0; yy < st->maze_size_y; yy++)
1147       for (xx = 0; xx < st->maze_size_x; xx++)
1148       {
1149         if (st->maze[xx][yy] & NOT_DEAD)
1150           st->maze[xx][yy] &= ~NOT_DEAD;
1151         else if (!(st->maze[xx][yy] & SOLVER_VISIT))
1152         {
1153           st->maze[xx][yy] |= SOLVER_VISIT;
1154           if((xx < st->logo_x || xx > st->logo_x + st->logo_width / st->grid_width) ||
1155              (yy < st->logo_y || yy > st->logo_y + st->logo_height / st->grid_height))
1156           {
1157             /* if we are completely surrounded by walls, just draw the
1158                inside part */
1159             if ((st->maze[xx][yy] & WALL_ANY) == WALL_ANY)
1160               XFillRectangle(st->dpy, st->window, st->ugc,
1161                              border_x + st->bw + st->grid_width * xx,
1162                              border_y + st->bw + st->grid_height * yy,
1163                              st->grid_width - (st->bw+st->bw), st->grid_height - (st->bw+st->bw));
1164             else
1165             {
1166               if (! (st->maze[xx][yy] & WALL_LEFT))
1167                 draw_solid_square(st, xx, yy, WALL_LEFT, st->ugc);
1168               if (! (st->maze[xx][yy] & WALL_RIGHT))
1169                 draw_solid_square(st, xx, yy, WALL_RIGHT, st->ugc);
1170               if (! (st->maze[xx][yy] & WALL_TOP))
1171                 draw_solid_square(st, xx, yy, WALL_TOP, st->ugc);
1172               if (! (st->maze[xx][yy] & WALL_BOTTOM))
1173                 draw_solid_square(st, xx, yy, WALL_BOTTOM, st->ugc);
1174             }
1175           }
1176         }
1177       }
1178 }
1179
1180 /* solve the maze by one more tick */
1181 static int
1182 solve_maze (struct state *st)
1183 {
1184   struct solve_state *ss = st->solve_state;
1185   if (!ss)
1186     ss = st->solve_state = (struct solve_state *) calloc (1, sizeof(*ss));
1187
1188   if (!ss->running) {
1189     /* plug up the surrounding wall */
1190     st->maze[st->end_x][st->end_y] |= (WALL_TOP >> st->end_dir);
1191
1192     /* initialize search path */
1193     ss->i = 0;
1194     st->path[ss->i].x = st->end_x;
1195     st->path[ss->i].y = st->end_y;
1196     st->path[ss->i].dir = 0;
1197     st->maze[st->end_x][st->end_y] |= SOLVER_VISIT;
1198
1199     ss->running = 1;
1200   }
1201
1202     /* do it */
1203     /* while (1) */
1204     {
1205         int dir, from, ways;
1206
1207         if ( st->maze[st->path[ss->i].x][st->path[ss->i].y] & START_SQUARE )
1208           {
1209             ss->running = 0;
1210             return 1;
1211           }
1212
1213         if(!st->path[ss->i].dir)
1214         {
1215             ways = 0;
1216             /* First visit this square.  Which adjacent squares are open? */
1217             for(dir = WALL_TOP; dir & WALL_ANY; dir >>= 1)
1218             {
1219                 if(st->maze[st->path[ss->i].x][st->path[ss->i].y] & dir)
1220                     continue;
1221
1222                 ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1223                 ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1224
1225                 if(st->maze[ss->x][ss->y] & SOLVER_VISIT)
1226                   continue;
1227
1228                 from = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1229                 /* don't enter obvious dead ends */
1230                 if(((st->maze[ss->x][ss->y] & WALL_ANY) | from) != WALL_ANY)
1231                 {
1232                     if(!longdeadend_p(st, st->path[ss->i].x, st->path[ss->i].y, ss->x, ss->y, dir))
1233                         ways |= dir;
1234                 }
1235                 else
1236                 {
1237                     draw_solid_square(st, ss->x, ss->y, from, st->sgc);
1238                     st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1239                 }
1240             }
1241         }
1242         else
1243             ways = st->path[ss->i].ways;
1244         /* ways now has a bitmask of open paths. */
1245
1246         if(!ways)
1247             goto backtrack;
1248
1249         if (!st->ignorant_p)
1250           {
1251             ss->x = st->path[ss->i].x - st->start_x;
1252             ss->y = st->path[ss->i].y - st->start_y;
1253             /* choice one */
1254             if(abs(ss->y) <= abs(ss->x))
1255               dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1256             else
1257               dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM;
1258
1259             if(dir & ways)
1260               goto found;
1261
1262             /* choice two */
1263             switch(dir)
1264               {
1265               case WALL_LEFT:
1266               case WALL_RIGHT:
1267                 dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM; break;
1268               case WALL_TOP:
1269               case WALL_BOTTOM:
1270                 dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1271               }
1272
1273             if(dir & ways)
1274               goto found;
1275
1276             /* choice three */
1277
1278             dir = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1279             if(dir & ways)
1280               goto found;
1281
1282             /* choice four */
1283             dir = ways;
1284             if(!dir)
1285               goto backtrack;
1286
1287           found: ;
1288           }
1289         else
1290           {
1291             if(ways&WALL_TOP)
1292               dir = WALL_TOP;
1293             else if(ways&WALL_LEFT)
1294               dir = WALL_LEFT;
1295             else if(ways&WALL_BOTTOM)
1296               dir = WALL_BOTTOM;
1297             else if(ways&WALL_RIGHT)
1298               dir = WALL_RIGHT;
1299             else
1300               goto backtrack;
1301           }
1302         ss->bt = 0;
1303         ways &= ~dir;  /* tried this one */
1304
1305         ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1306         ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1307
1308         /* advance in direction dir */
1309         st->path[ss->i].dir = dir;
1310         st->path[ss->i].ways = ways;
1311         draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, dir, st->tgc);
1312
1313         ss->i++;
1314         st->path[ss->i].dir = 0;
1315         st->path[ss->i].ways = 0;
1316         st->path[ss->i].x = ss->x;
1317         st->path[ss->i].y = ss->y;
1318         st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1319         return 0;
1320         /* continue; */
1321
1322     backtrack:
1323         if(ss->i == 0)
1324         {
1325             printf("Unsolvable maze.\n");
1326             ss->running = 0;
1327             return 1;
1328         }
1329
1330         if(!ss->bt && !st->ignorant_p)
1331             find_dead_regions(st);
1332         ss->bt = 1;
1333         from = st->path[ss->i-1].dir;
1334         from = (from << 2 & WALL_ANY) | (from >> 2 & WALL_ANY);
1335
1336         draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, from, st->cgc);
1337         ss->i--;
1338     }
1339
1340     return 0;
1341 }
1342
1343
1344 /****************************************************************************
1345  XScreenSaver boilerplate: resources, command line options, and main loop.
1346  ****************************************************************************/
1347
1348 static const char *maze_defaults[] = {
1349   ".background:    black",
1350   ".foreground:    white",
1351   "*fpsSolid:      true",
1352   "*gridSize:      0",
1353   "*generator:     -1",
1354   "*maxLength:     5",
1355   "*ignorant:      False",
1356
1357   "*solveDelay:    10000",
1358   "*preDelay:      2000000",
1359   "*postDelay:     4000000",
1360
1361   "*liveColor:     #00FF00",
1362   "*deadColor:     #880000",
1363   "*skipColor:     #8B5A00",
1364   "*surroundColor: #220055",
1365
1366   0
1367 };
1368
1369 static XrmOptionDescRec maze_options[] = {
1370   { "-ignorant",        ".ignorant",    XrmoptionNoArg, "True" },
1371   { "-no-ignorant",     ".ignorant",    XrmoptionNoArg, "False" },
1372   { "-grid-size",       ".gridSize",    XrmoptionSepArg, 0 },
1373   { "-solve-delay",     ".solveDelay",  XrmoptionSepArg, 0 },
1374   { "-pre-delay",       ".preDelay",    XrmoptionSepArg, 0 },
1375   { "-post-delay",      ".postDelay",   XrmoptionSepArg, 0 },
1376   { "-bg-color",        ".background",  XrmoptionSepArg, 0 },
1377   { "-fg-color",        ".foreground",  XrmoptionSepArg, 0 },
1378   { "-live-color",      ".liveColor",   XrmoptionSepArg, 0 },
1379   { "-dead-color",      ".deadColor",   XrmoptionSepArg, 0 },
1380   { "-skip-color",      ".skipColor",   XrmoptionSepArg, 0 },
1381   { "-surround-color",  ".surroundColor",XrmoptionSepArg, 0 },
1382   { "-generator",       ".generator",   XrmoptionSepArg, 0 },
1383   { "-max-length",      ".maxLength",   XrmoptionSepArg, 0 },
1384   { 0, 0, 0, 0 }
1385 };
1386
1387 static int generator = 0;
1388
1389 static void *
1390 maze_init (Display *dpy_arg, Window window_arg)
1391 {
1392   struct state *st = (struct state *) calloc (1, sizeof(*st));
1393   int size;
1394   XWindowAttributes xgwa;
1395   unsigned long bg, fg, pfg, pbg, sfg, ufg;
1396
1397   st->dpy = dpy_arg;
1398   st->window = window_arg;
1399
1400   st->stop = 0;
1401   st->state = 1;
1402   st->restart = 1;
1403
1404   st->ifrandom = 0;
1405   st->ifinit = 1;
1406
1407   size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1408   st->solve_delay = get_integer_resource (st->dpy, "solveDelay", "Integer");
1409   st->pre_solve_delay = get_integer_resource (st->dpy, "preDelay", "Integer");
1410   st->post_solve_delay = get_integer_resource (st->dpy, "postDelay", "Integer");
1411   generator = get_integer_resource(st->dpy, "generator", "Integer");
1412   st->max_length = get_integer_resource(st->dpy, "maxLength", "Integer");
1413   st->ignorant_p = get_boolean_resource(st->dpy, "ignorant", "Boolean");
1414
1415   if (get_boolean_resource (st->dpy, "doFPS", "DoFPS"))
1416     {
1417       /* Just guess, rather than loading and measuring the "fpsFont"... */
1418       st->fps_width = 210;
1419       st->fps_height = 62;
1420     }
1421
1422   if (!size) st->ifrandom = 1;
1423
1424   if (size < 2) size = 7 + (random () % 30);
1425   st->grid_width = st->grid_height = size;
1426   st->bw = (size > 6 ? 3 : (size-1)/2);
1427
1428   XGetWindowAttributes (st->dpy, st->window, &xgwa);
1429
1430   st->x = 0;
1431   st->y = 0;
1432
1433   set_maze_sizes (st, xgwa.width, xgwa.height);
1434
1435   st->gc  = XCreateGC(st->dpy, st->window, 0, 0);
1436   st->cgc = XCreateGC(st->dpy, st->window, 0, 0);
1437   st->tgc = XCreateGC(st->dpy, st->window, 0, 0);
1438   st->sgc = XCreateGC(st->dpy, st->window, 0, 0);
1439   st->ugc = XCreateGC(st->dpy, st->window, 0, 0);
1440   st->logo_gc = XCreateGC(st->dpy, st->window, 0, 0);
1441   st->erase_gc = XCreateGC(st->dpy, st->window, 0, 0);
1442
1443   bg  = get_pixel_resource (st->dpy, xgwa.colormap, "background","Background");
1444   fg  = get_pixel_resource (st->dpy, xgwa.colormap, "foreground","Foreground");
1445   pfg = get_pixel_resource (st->dpy, xgwa.colormap, "liveColor", "Foreground");
1446   pbg = get_pixel_resource (st->dpy, xgwa.colormap, "deadColor", "Foreground");
1447   sfg = get_pixel_resource (st->dpy, xgwa.colormap, "skipColor", "Foreground");
1448   ufg = get_pixel_resource (st->dpy, xgwa.colormap, "surroundColor", "Foreground");
1449
1450   XSetForeground (st->dpy, st->gc, fg);
1451   XSetBackground (st->dpy, st->gc, bg);
1452   XSetForeground (st->dpy, st->cgc, pbg);
1453   XSetBackground (st->dpy, st->cgc, bg);
1454   XSetForeground (st->dpy, st->tgc, pfg);
1455   XSetBackground (st->dpy, st->tgc, bg);
1456   XSetForeground (st->dpy, st->sgc, sfg);
1457   XSetBackground (st->dpy, st->sgc, bg);
1458   XSetForeground (st->dpy, st->ugc, ufg);
1459   XSetBackground (st->dpy, st->ugc, bg);
1460   XSetForeground (st->dpy, st->logo_gc, fg);
1461   XSetBackground (st->dpy, st->logo_gc, bg);
1462   XSetForeground (st->dpy, st->erase_gc, bg);
1463   XSetBackground (st->dpy, st->erase_gc, bg);
1464
1465   {
1466     Window r;
1467     int x, y;
1468     unsigned int w, h, bbw, d;
1469     unsigned long *pixels;
1470     int npixels;
1471     Pixmap logo_mask = 0;
1472     st->logo_map = xscreensaver_logo (xgwa.screen, xgwa.visual, st->window,
1473                                       xgwa.colormap, bg,
1474                                       &pixels, &npixels, &logo_mask,
1475                                       xgwa.width > 800);
1476     if (logo_mask) {
1477       XSetClipMask (st->dpy, st->logo_gc, logo_mask);
1478       XFreePixmap (st->dpy, logo_mask);
1479     }
1480     if (pixels) free (pixels);
1481     XGetGeometry (st->dpy, st->logo_map, &r, &x, &y, &w, &h, &bbw, &d);
1482     st->logo_width = w;
1483     st->logo_height = h;
1484   }
1485
1486
1487   st->restart = 0;
1488   st->sync_p = 1;
1489
1490   return st;
1491 }
1492
1493
1494 static void
1495 maze_reshape (Display *dpy, Window window, void *closure,
1496                  unsigned int w, unsigned int h)
1497 {
1498   struct state *st = (struct state *) closure;
1499   st->restart = 1;
1500 }
1501
1502
1503 static unsigned long
1504 maze_draw (Display *dpy, Window window, void *closure)
1505 {
1506   struct state *st = (struct state *) closure;
1507   int this_delay = st->solve_delay;
1508
1509   if (st->eraser || st->erase_window)
1510     {
1511       st->erase_window = 0;
1512       st->eraser = erase_window (st->dpy, st->window, st->eraser);
1513       if (st->eraser)
1514         this_delay = 10000;
1515       else {
1516         this_delay = 1000000;
1517         if (this_delay > st->pre_solve_delay)
1518           this_delay = st->pre_solve_delay;
1519       }
1520       goto END;
1521     }
1522
1523     if (st->restart || st->stop) goto pop;
1524     switch (st->state) {
1525     case 1:
1526       initialize_maze(st);
1527       if (st->ifrandom && st->ifinit)
1528        {
1529          int size;
1530          size = 7 + (random () % 30);
1531          st->grid_width = st->grid_height = size;
1532          st->bw = (size > 6 ? 3 : (size-1)/2);
1533          st->ifinit = 0;
1534          st->restart = 1;
1535        }
1536       break;
1537     case 2:
1538       XClearWindow(st->dpy, st->window);
1539       draw_maze_border(st);
1540       break;
1541     case 3:
1542       st->this_gen = generator;
1543       if(st->this_gen<0 || st->this_gen>2)
1544         st->this_gen = random()%3;
1545
1546       switch(st->this_gen)
1547         {
1548         case 0:
1549           create_maze(st);
1550           break;
1551         case 1:
1552           alt_create_maze(st);
1553           break;
1554         case 2:
1555           set_create_maze(st);
1556           break;
1557         }
1558       break;
1559     case 4:
1560       this_delay = st->pre_solve_delay;
1561       break;
1562     case 5:
1563       if (! solve_maze(st))
1564         --st->state;  /* stay in state 5 */
1565       break;
1566     case 6:
1567       st->erase_window = 1;
1568       this_delay = st->post_solve_delay;
1569       st->state = 0 ;
1570       st->ifinit = 1;
1571       break;
1572     default:
1573       abort ();
1574     }
1575     ++st->state;
1576   pop:
1577     if (st->restart)
1578       {
1579         XWindowAttributes xgwa;
1580         int size;
1581
1582         st->restart = 0;
1583         st->stop = 0;
1584         st->state = 1;
1585
1586         st->sync_p = ((random() % 4) != 0);
1587
1588         size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1589         if (size < 2) size = 7 + (random () % 30);
1590         st->grid_width = st->grid_height = size;
1591         st->bw = (size > 6 ? 3 : (size-1)/2);
1592
1593         XGetWindowAttributes (st->dpy, st->window, &xgwa);
1594         set_maze_sizes (st, xgwa.width, xgwa.height);
1595       }
1596
1597  END:
1598     return this_delay;
1599 }
1600
1601
1602 static Bool
1603 maze_event (Display *dpy, Window window, void *closure, XEvent *event)
1604 {
1605   struct state *st = (struct state *) closure;
1606   switch (event->type)
1607     {
1608     case ButtonPress:
1609       switch (event->xbutton.button)
1610         {
1611         case 2:
1612           st->stop = !st->stop ;
1613           if (st->state == 5) st->state = 4 ;
1614           else {
1615             st->restart = 1;
1616             st->stop = 0;
1617           }
1618           return True;
1619
1620         default:
1621           st->restart = 1 ;
1622           st->stop = 0 ;
1623           return True;
1624         }
1625       break;
1626
1627     case Expose:
1628       st->restart = 1;
1629       break;
1630
1631     default:
1632       break;
1633     }
1634   return False;
1635 }
1636
1637
1638 static void
1639 maze_free (Display *dpy, Window window, void *closure)
1640 {
1641   struct state *st = (struct state *) closure;
1642   free (st);
1643 }
1644
1645 XSCREENSAVER_MODULE ("Maze", maze)