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 retry_count = 0;
 214   int i, j, wall;
 215   int logow = 1 + st->logo_width / st->grid_width;
 216   int logoh = 1 + st->logo_height / st->grid_height;
 217
 218  AGAIN:
 219
 220   /* This can happen if the window is really small. Let's not sweat it. */
 221   if (++retry_count > 100) return;
 222
 223
 224   /* initialize all squares */
 225   for ( i=0; i<st->maze_size_x; i++) {
 226     for ( j=0; j<st->maze_size_y; j++) {
 227       st->maze[i][j] = 0;
 228     }
 229   }
 230
 231   /* top wall */
 232   for ( i=0; i<st->maze_size_x; i++ ) {
 233     st->maze[i][0] |= WALL_TOP;
 234   }
 235
 236   /* right wall */
 237   for ( j=0; j<st->maze_size_y; j++ ) {
 238     st->maze[st->maze_size_x-1][j] |= WALL_RIGHT;
 239   }
 240
 241   /* bottom wall */
 242   for ( i=0; i<st->maze_size_x; i++ ) {
 243     st->maze[i][st->maze_size_y-1] |= WALL_BOTTOM;
 244   }
 245
 246   /* left wall */
 247   for ( j=0; j<st->maze_size_y; j++ ) {
 248     st->maze[0][j] |= WALL_LEFT;
 249   }
 250
 251   /* set start square */
 252   wall = get_random(4);
 253   switch (wall) {
 254   case 0:
 255     i = get_random(st->maze_size_x);
 256     j = 0;
 257     break;
 258   case 1:
 259     i = st->maze_size_x - 1;
 260     j = get_random(st->maze_size_y);
 261     break;
 262   case 2:
 263     i = get_random(st->maze_size_x);
 264     j = st->maze_size_y - 1;
 265     break;
 266   case 3:
 267     i = 0;
 268     j = get_random(st->maze_size_y);
 269     break;
 270   }
 271   st->maze[i][j] |= START_SQUARE;
 272   st->maze[i][j] |= ( DOOR_IN_TOP >> wall );
 273   st->maze[i][j] &= ~( WALL_TOP >> wall );
 274   st->cur_sq_x = i;
 275   st->cur_sq_y = j;
 276   st->start_x = i;
 277   st->start_y = j;
 278   st->start_dir = wall;
 279   st->sqnum = 0;
 280
 281   /* set end square */
 282   wall = (wall + 2)%4;
 283   switch (wall) {
 284   case 0:
 285     i = get_random(st->maze_size_x);
 286     j = 0;
 287     break;
 288   case 1:
 289     i = st->maze_size_x - 1;
 290     j = get_random(st->maze_size_y);
 291     break;
 292   case 2:
 293     i = get_random(st->maze_size_x);
 294     j = st->maze_size_y - 1;
 295     break;
 296   case 3:
 297     i = 0;
 298     j = get_random(st->maze_size_y);
 299     break;
 300   }
 301   st->maze[i][j] |= END_SQUARE;
 302   st->maze[i][j] |= ( DOOR_OUT_TOP >> wall );
 303   st->maze[i][j] &= ~( WALL_TOP >> wall );
 304   st->end_x = i;
 305   st->end_y = j;
 306   st->end_dir = wall;
 307
 308   /* set logo */
 309   if ((st->maze_size_x-logow >= 6) && (st->maze_size_y-logoh >= 6))
 310     {
 311       /* not closer than 3 grid units from a wall, to ensure that it
 312          won't overlap the entrance or exit. */
 313       st->logo_x = get_random (st->maze_size_x - logow - 5) + 3;
 314       st->logo_y = get_random (st->maze_size_y - logoh - 5) + 3;
 315       for (i=0; i<logow; i++)
 316         for (j=0; j<logoh; j++)
 317           /* mark as having doors to prevent these cells being used in maze. */
 318           st->maze[st->logo_x + i][st->logo_y + j] |= DOOR_IN_ANY;
 319     }
 320   else
 321     st->logo_y = st->logo_x = -1;
 322
 323   /* mask out the fps area */
 324   if (st->fps_width > 0)
 325     {
 326       int fpsw = 1 + st->fps_width  / st->grid_width;
 327       int fpsh = 1 + st->fps_height / st->grid_width;
 328
 329       /* if the chosen logo position overlapped the fps area, try again! */
 330       if (st->logo_x < fpsw+3 && st->logo_y+logoh > st->maze_size_y-fpsh-4)
 331         goto AGAIN;
 332
 333       /* if the start or end point is inside the fps area, try again! */
 334       if ((st->start_x <= fpsw && st->start_y >= st->maze_size_y-fpsh-1) ||
 335           (st->end_x   <= fpsw && st->end_y   >= st->maze_size_y-fpsh-1))
 336         goto AGAIN;
 337
 338       for (i=0; i<fpsw; i++)
 339         for (j=0; j<fpsh; j++) {
 340           /* mark as having doors to prevent these cells being used in maze.
 341              mark as visit to prevent it being colored "unreachable". */
 342           st->maze[i][st->maze_size_y - j - 1] |= DOOR_IN_ANY|SOLVER_VISIT;
 343           /* take off left/bottom wall or the FPS text overlaps it */
 344           st->maze[i][st->maze_size_y - j - 1] &= ~(WALL_BOTTOM|WALL_LEFT);
 345         }
 346     }
 347 }
 348
 349
 350 /****************************************************************************
 351  Generator 2: Set-based maze generator.
 352
 353  Put each square in the maze in a separate set.  Also, make a list of all the
 354  hedges.  Randomize that list.  Walk through the list. If, for a certain
 355  hedge, the two squares on both sides of it are in different sets, union the
 356  sets and remove the hedge.  Continue until all hedges have been processed or
 357  only one set remains.
 358
 359  This is essentially the "Kruskal" algorithm.
 360
 361  ****************************************************************************/
 362
 363 static void mask_out_set_rect(struct state *st, int x, int y, int w, int h);
 364
 365 /* Initialise the sets. */
 366 static void
 367 init_sets(struct state *st)
 368 {
 369   int i, t, r;
 370
 371   if(st->sets)
 372     free(st->sets);
 373   st->sets = (int *)malloc(st->maze_size_x*st->maze_size_y*sizeof(int));
 374   if(!st->sets)
 375     abort();
 376   for(i = 0; i < st->maze_size_x*st->maze_size_y; i++)
 377     {
 378       st->sets[i] = i;
 379     }
 380
 381   if(st->hedges)
 382     free(st->hedges);
 383   st->hedges = (int *)malloc(st->maze_size_x*st->maze_size_y*2*sizeof(int));
 384   if(!st->hedges)
 385     abort();
 386   for(i = 0; i < st->maze_size_x*st->maze_size_y*2; i++)
 387     {
 388       st->hedges[i] = i;
 389     }
 390   /* Mask out outside walls. */
 391   for(i = 0; i < st->maze_size_y; i++)
 392     {
 393       st->hedges[2*((st->maze_size_x)*i+st->maze_size_x-1)+1] = -1;
 394     }
 395   for(i = 0; i < st->maze_size_x; i++)
 396     {
 397       st->hedges[2*((st->maze_size_y-1)*st->maze_size_x+i)] = -1;
 398     }
 399
 400   /* Mask out the logo area. */
 401   if(st->logo_x!=-1)
 402     {
 403       int logow = 1 + st->logo_width  / st->grid_width;
 404       int logoh = 1 + st->logo_height / st->grid_height;
 405       mask_out_set_rect(st, st->logo_x, st->logo_y, logow, logoh);
 406     }
 407
 408   /* Mask out the FPS area. */
 409   if(st->fps_width > 0)
 410     {
 411       int fpsw = 1 + st->fps_width  / st->grid_width;
 412       int fpsh = 1 + st->fps_height / st->grid_height;
 413       mask_out_set_rect(st, 0, st->maze_size_y-fpsh, fpsw, fpsh);
 414     }
 415
 416   for(i = 0; i < st->maze_size_x*st->maze_size_y*2; i++)
 417     {
 418       t = st->hedges[i];
 419       r = random()%(st->maze_size_x*st->maze_size_y*2);
 420       st->hedges[i] = st->hedges[r];
 421       st->hedges[r] = t;
 422     }
 423 }
 424
 425 /* Get the representative of a set. */
 426 static int
 427 get_set(struct state *st, int num)
 428 {
 429   int s;
 430
 431   if(st->sets[num]==num)
 432     return num;
 433   else
 434     {
 435       s = get_set(st, st->sets[num]);
 436       st->sets[num] = s;
 437       return s;
 438     }
 439 }
 440
 441 /* Join two sets together. */
 442 static void
 443 join_sets(struct state *st, int num1, int num2)
 444 {
 445   int s1, s2;
 446
 447   s1 = get_set(st, num1);
 448   s2 = get_set(st, num2);
 449
 450   if(s1<s2)
 451     st->sets[s2] = s1;
 452   else
 453     st->sets[s1] = s2;
 454 }
 455
 456 /* Exitialise the sets. */
 457 static void
 458 exit_sets(struct state *st)
 459 {
 460   if(st->hedges)
 461     free(st->hedges);
 462   st->hedges = 0;
 463   if(st->sets)
 464     free(st->sets);
 465   st->sets = 0;
 466 }
 467
 468
 469 static void
 470 set_create_maze(struct state *st)
 471 {
 472   int i, h, xx, yy, dir, v, w;
 473
 474   /* Do almost all the setup. */
 475   init_sets(st);
 476
 477   /* Start running through the hedges. */
 478   for(i = 0; i < 2*st->maze_size_x*st->maze_size_y; i++)
 479     {
 480       h = st->hedges[i];
 481
 482       /* This one is in the logo or outside border. */
 483       if(h==-1)
 484         continue;
 485
 486       dir = h%2?1:2;
 487       xx = (h>>1)%st->maze_size_x;
 488       yy = (h>>1)/st->maze_size_x;
 489
 490       v = xx;
 491       w = yy;
 492       switch(dir)
 493         {
 494         case 1:
 495           v++;
 496           break;
 497         case 2:
 498           w++;
 499           break;
 500         }
 501
 502       if(get_set(st, xx+yy*st->maze_size_x)!=get_set(st, v+w*st->maze_size_x))
 503         {
 504           join_sets(st, xx+yy*st->maze_size_x, v+w*st->maze_size_x);
 505           /* Don't draw the wall. */
 506         }
 507       else
 508         {
 509           /* Don't join the sets. */
 510           build_wall(st, xx, yy, dir);
 511         }
 512     }
 513
 514   /* Free some memory. */
 515   exit_sets(st);
 516 }
 517
 518 /* mark a rectangle as being unavailable for usage in the maze */
 519 static void
 520 mask_out_set_rect(struct state *st, int x, int y, int w, int h)
 521 {
 522   int xx, yy;
 523   for(xx = x; xx < x+w; xx++)
 524     for(yy = y; yy < y+h; yy++)
 525       {
 526         st->hedges[2*(xx+st->maze_size_x*yy)+1] = -1;
 527         st->hedges[2*(xx+st->maze_size_x*yy)] = -1;
 528       }
 529   for(xx = x; xx < x+w; xx++)
 530     {
 531       build_wall(st, xx, y, 0);
 532       build_wall(st, xx, y+h, 0);
 533       st->hedges[2*(xx+st->maze_size_x*(y-1))] = -1;
 534     }
 535   for(yy = y; yy < y+h; yy++)
 536     {
 537       build_wall(st, x, yy, 3);
 538       build_wall(st, x+w, yy, 3);
 539       st->hedges[2*(x-1+st->maze_size_x*yy)+1] = -1;
 540     }
 541 }
 542
 543
 544 /****************************************************************************
 545  Generator 1: Wall-building maze generator.
 546
 547  Pick a random, empty corner in the maze.  Pick a random direction. Draw a
 548  wall in that direction, from that corner until we hit a wall.  Option: Only
 549  draw the wall if it's going to be shorter than a certain length.  Otherwise
 550  we get lots of long walls.
 551
 552  This is essentially the "Prim" algorithm.
 553  ****************************************************************************/
 554
 555 static void alt_mask_out_rect(struct state *st, char *corners,
 556                               int x, int y, int w, int h);
 557
 558 static void
 559 alt_create_maze(struct state *st)
 560 {
 561   char *corners;
 562   int *c_idx;
 563   int i, j, height, width, open_corners, k, dir, xx, yy;
 564
 565   height = st->maze_size_y+1;
 566   width = st->maze_size_x+1;
 567
 568   /* Allocate and clear some mem. */
 569   corners = (char *)calloc(height*width, 1);
 570   if(!corners)
 571     return;
 572
 573   /* Set up the indexing array. */
 574   c_idx = (int *)malloc(sizeof(int)*height*width);
 575   if(!c_idx)
 576     {
 577       free(corners);
 578       return;
 579     }
 580   for(i = 0; i < height*width; i++)
 581     c_idx[i] = i;
 582   for(i = 0; i < height*width; i++)
 583     {
 584       j = c_idx[i];
 585       k = random()%(height*width);
 586       c_idx[i] = c_idx[k];
 587       c_idx[k] = j;
 588     }
 589
 590   /* Set up some initial walls. */
 591   /* Outside walls. */
 592   for(i = 0; i < width; i++)
 593     {
 594       corners[i] = 1;
 595       corners[i+width*(height-1)] = 1;
 596     }
 597   for(i = 0; i < height; i++)
 598     {
 599       corners[i*width] = 1;
 600       corners[i*width+width-1] = 1;
 601     }
 602
 603   /* mask out the logo area */
 604   if(st->logo_x!=-1)
 605     {
 606       int logow = 1 + st->logo_width / st->grid_width;
 607       int logoh = 1 + st->logo_height / st->grid_height;
 608       alt_mask_out_rect (st, corners, st->logo_x, st->logo_y, logow, logoh);
 609     }
 610
 611   /* mask out the FPS area */
 612   if(st->fps_width>0)
 613     {
 614       int fpsw = 1 + st->fps_width  / st->grid_width;
 615       int fpsh = 1 + st->fps_height / st->grid_height;
 616       alt_mask_out_rect (st, corners, 0, st->maze_size_y-fpsh, fpsw, fpsh);
 617     }
 618
 619   /* Count open gridpoints. */
 620   open_corners = 0;
 621   for(i = 0; i < width; i++)
 622     for(j = 0; j < height; j++)
 623       if(!corners[i+width*j])
 624         open_corners++;
 625
 626   /* Now do actual maze generation. */
 627   while(open_corners>0)
 628     {
 629       for(i = 0; i < width*height; i++)
 630         {
 631           if(!corners[c_idx[i]])
 632             {
 633               xx = c_idx[i]%width;
 634               yy = c_idx[i]/width;
 635               /* Choose a random direction. */
 636               dir = random()%4;
 637
 638               k = 0;
 639               /* Measure the length of the wall we'd draw. */
 640               while(!corners[xx+width*yy])
 641                 {
 642                   k++;
 643                   switch(dir)
 644                     {
 645                     case 0:
 646                       yy--;
 647                       break;
 648                     case 1:
 649                       xx++;
 650                       break;
 651                     case 2:
 652                       yy++;
 653                       break;
 654                     case 3:
 655                       xx--;
 656                       break;
 657                     }
 658                 }
 659
 660               if(k<=st->max_length)
 661                 {
 662                   xx = c_idx[i]%width;
 663                   yy = c_idx[i]/width;
 664
 665                   /* Draw a wall until we hit something. */
 666                   while(!corners[xx+width*yy])
 667                     {
 668                       open_corners--;
 669                       corners[xx+width*yy] = 1;
 670                       switch(dir)
 671                         {
 672                         case 0:
 673                           build_wall(st, xx-1, yy-1, 1);
 674                           yy--;
 675                           break;
 676                         case 1:
 677                           build_wall(st, xx, yy, 0);
 678                           xx++;
 679                           break;
 680                         case 2:
 681                           build_wall(st, xx, yy, 3);
 682                           yy++;
 683                           break;
 684                         case 3:
 685                           build_wall(st, xx-1, yy-1, 2);
 686                           xx--;
 687                           break;
 688                         }
 689                     }
 690                 }
 691             }
 692         }
 693     }
 694
 695   /* Free some memory we used. */
 696   free(corners);
 697   free(c_idx);
 698 }
 699
 700
 701 /* mark a rectangle as being unavailable for usage in the maze */
 702 static void
 703 alt_mask_out_rect(struct state *st, char *corners, int x, int y, int w, int h)
 704 {
 705   int i, j, xx, yy;
 706   int mazew = st->maze_size_x+1;
 707
 708   for(i = x; i <= x+w; i++)
 709     for(j = y; j <= y+h; j++)
 710       corners[i+mazew*j] = 1;
 711
 712   for(xx = x; xx < x+w; xx++)
 713     {
 714       build_wall(st, xx, y, 0);
 715       if (y+h < st->maze_size_y)
 716         build_wall(st, xx, y+h, 0);
 717     }
 718   for(yy = y; yy < y+h; yy++)
 719     {
 720       if (x > 0)
 721         build_wall(st, x, yy, 3);
 722       build_wall(st, x+w, yy, 3);
 723     }
 724 }
 725
 726
 727 /****************************************************************************
 728  Generator 0: The original maze generator.
 729
 730  Start somewhere.  Take a step in a random direction.  Keep doing this until
 731  we hit a wall.  Then, backtrack until we find a point where we can go in
 732  another direction.
 733
 734  This is essentially the "depth-first recursive backtracker" algorithm.
 735  ****************************************************************************/
 736
 737 static int choose_door (struct state *st);
 738 static int backup (struct state *st);
 739
 740 static void
 741 create_maze (struct state *st)    /* create a maze layout given the initialized maze */
 742 {
 743   int i, newdoor = 0;
 744
 745   do {
 746     st->move_list[st->sqnum].x = st->cur_sq_x;
 747     st->move_list[st->sqnum].y = st->cur_sq_y;
 748     st->move_list[st->sqnum].dir = newdoor;
 749     while ( ( newdoor = choose_door(st) ) == -1 ) { /* pick a door */
 750       if ( backup(st) == -1 ) { /* no more doors ... backup */
 751         return; /* done ... return */
 752       }
 753     }
 754
 755     /* mark the out door */
 756     st->maze[st->cur_sq_x][st->cur_sq_y] |= ( DOOR_OUT_TOP >> newdoor );
 757
 758     switch (newdoor) {
 759     case 0: st->cur_sq_y--;
 760       break;
 761     case 1: st->cur_sq_x++;
 762       break;
 763     case 2: st->cur_sq_y++;
 764       break;
 765     case 3: st->cur_sq_x--;
 766       break;
 767     }
 768     st->sqnum++;
 769
 770     /* mark the in door */
 771     st->maze[st->cur_sq_x][st->cur_sq_y] |= ( DOOR_IN_TOP >> ((newdoor+2)%4) );
 772
 773     /* if end square set path length and save path */
 774     if ( st->maze[st->cur_sq_x][st->cur_sq_y] & END_SQUARE ) {
 775       st->path_length = st->sqnum;
 776       for ( i=0; i<st->path_length; i++) {
 777         st->save_path[i].x = st->move_list[i].x;
 778         st->save_path[i].y = st->move_list[i].y;
 779         st->save_path[i].dir = st->move_list[i].dir;
 780       }
 781     }
 782
 783   } while (1);
 784
 785 }
 786
 787
 788 static int
 789 choose_door (struct state *st)                                   /* pick a new path */
 790 {
 791   int candidates[3];
 792   int num_candidates;
 793
 794   num_candidates = 0;
 795
 796   /* top wall */
 797   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_TOP )
 798     goto rightwall;
 799   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_TOP )
 800     goto rightwall;
 801   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_TOP )
 802     goto rightwall;
 803   if ( st->maze[st->cur_sq_x][st->cur_sq_y - 1] & DOOR_IN_ANY ) {
 804     st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_TOP;
 805     st->maze[st->cur_sq_x][st->cur_sq_y - 1] |= WALL_BOTTOM;
 806     draw_wall(st, st->cur_sq_x, st->cur_sq_y, 0, st->gc);
 807     goto rightwall;
 808   }
 809   candidates[num_candidates++] = 0;
 810
 811  rightwall:
 812   /* right wall */
 813   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_RIGHT )
 814     goto bottomwall;
 815   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_RIGHT )
 816     goto bottomwall;
 817   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_RIGHT )
 818     goto bottomwall;
 819   if ( st->maze[st->cur_sq_x + 1][st->cur_sq_y] & DOOR_IN_ANY ) {
 820     st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_RIGHT;
 821     st->maze[st->cur_sq_x + 1][st->cur_sq_y] |= WALL_LEFT;
 822     draw_wall(st, st->cur_sq_x, st->cur_sq_y, 1, st->gc);
 823     goto bottomwall;
 824   }
 825   candidates[num_candidates++] = 1;
 826
 827  bottomwall:
 828   /* bottom wall */
 829   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_BOTTOM )
 830     goto leftwall;
 831   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_BOTTOM )
 832     goto leftwall;
 833   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_BOTTOM )
 834     goto leftwall;
 835   if ( st->maze[st->cur_sq_x][st->cur_sq_y + 1] & DOOR_IN_ANY ) {
 836     st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_BOTTOM;
 837     st->maze[st->cur_sq_x][st->cur_sq_y + 1] |= WALL_TOP;
 838     draw_wall(st, st->cur_sq_x, st->cur_sq_y, 2, st->gc);
 839     goto leftwall;
 840   }
 841   candidates[num_candidates++] = 2;
 842
 843  leftwall:
 844   /* left wall */
 845   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_LEFT )
 846     goto donewall;
 847   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_LEFT )
 848     goto donewall;
 849   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_LEFT )
 850     goto donewall;
 851   if ( st->maze[st->cur_sq_x - 1][st->cur_sq_y] & DOOR_IN_ANY ) {
 852     st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_LEFT;
 853     st->maze[st->cur_sq_x - 1][st->cur_sq_y] |= WALL_RIGHT;
 854     draw_wall(st, st->cur_sq_x, st->cur_sq_y, 3, st->gc);
 855     goto donewall;
 856   }
 857   candidates[num_candidates++] = 3;
 858
 859  donewall:
 860   if (num_candidates == 0)
 861     return ( -1 );
 862   if (num_candidates == 1)
 863     return ( candidates[0] );
 864   return ( candidates[ get_random(num_candidates) ] );
 865
 866 }
 867
 868
 869 static int
 870 backup (struct state *st)                                          /* back up a move */
 871 {
 872   st->sqnum--;
 873   st->cur_sq_x = st->move_list[st->sqnum].x;
 874   st->cur_sq_y = st->move_list[st->sqnum].y;
 875   return ( st->sqnum );
 876 }
 877
 878
 879 /****************************************************************************
 880  Drawing the maze
 881  ****************************************************************************/
 882
 883 /* draws the maze outline, and the logo */
 884 static void
 885 draw_maze_border (struct state *st)
 886 {
 887   int i, j;
 888
 889   for ( i=0; i<st->maze_size_x; i++) {
 890     if ( st->maze[i][0] & WALL_TOP ) {
 891       XDrawLine(st->dpy, st->window, st->gc,
 892                 border_x + st->grid_width * i,
 893                 border_y,
 894                 border_x + st->grid_width * (i+1) - 1,
 895                 border_y);
 896     }
 897     if ((st->maze[i][st->maze_size_y - 1] & WALL_BOTTOM)) {
 898       XDrawLine(st->dpy, st->window, st->gc,
 899                 border_x + st->grid_width * i,
 900                 border_y + st->grid_height * (st->maze_size_y) - 1,
 901                 border_x + st->grid_width * (i+1) - 1,
 902                 border_y + st->grid_height * (st->maze_size_y) - 1);
 903     }
 904   }
 905   for ( j=0; j<st->maze_size_y; j++) {
 906     if ( st->maze[st->maze_size_x - 1][j] & WALL_RIGHT ) {
 907       XDrawLine(st->dpy, st->window, st->gc,
 908                 border_x + st->grid_width * st->maze_size_x - 1,
 909                 border_y + st->grid_height * j,
 910                 border_x + st->grid_width * st->maze_size_x - 1,
 911                 border_y + st->grid_height * (j+1) - 1);
 912     }
 913     if ( st->maze[0][j] & WALL_LEFT ) {
 914       XDrawLine(st->dpy, st->window, st->gc,
 915                 border_x,
 916                 border_y + st->grid_height * j,
 917                 border_x,
 918                 border_y + st->grid_height * (j+1) - 1);
 919     }
 920   }
 921
 922   if (st->logo_x != -1)
 923     {
 924       Window r;
 925       int xx, yy;
 926       unsigned int w, h, bbw, d;
 927
 928       /* round up to grid size */
 929       int ww = ((st->logo_width  / st->grid_width) + 1)  * st->grid_width;
 930       int hh = ((st->logo_height / st->grid_height) + 1) * st->grid_height;
 931       int lx, ly;
 932
 933       XGetGeometry (st->dpy, st->logo_map, &r, &xx, &yy, &w, &h, &bbw, &d);
 934
 935       /* kludge: if the logo "hole" is around the same size as the logo,
 936          don't center it (since the xscreensaver logo image is a little
 937          off center...  But do center it if the hole/gridsize is large. */
 938       if (ww < st->logo_width  + 5) ww = w;
 939       if (hh < st->logo_height + 5) hh = h;
 940
 941
 942       lx = border_x + 3 + st->grid_width  * st->logo_x + ((ww - w) / 2);
 943       ly = border_y + 3 + st->grid_height * st->logo_y + ((hh - h) / 2);
 944
 945       /* Fill the background of the logo box with the "unreachable" color */
 946       XFillRectangle (st->dpy, st->window, st->ugc,
 947                       border_x + 3 + st->grid_width  * st->logo_x,
 948                       border_y + 3 + st->grid_height * st->logo_y,
 949                       ww, hh);
 950
 951       XSetClipOrigin (st->dpy, st->logo_gc, lx, ly);
 952       if (d == 1)
 953         XCopyPlane (st->dpy, st->logo_map, st->window, st->logo_gc,
 954                     0, 0, w, h, lx, ly, 1);
 955       else
 956         XCopyArea (st->dpy, st->logo_map, st->window, st->logo_gc,
 957                    0, 0, w, h, lx, ly);
 958     }
 959   draw_solid_square (st, st->start_x, st->start_y, WALL_TOP >> st->start_dir, st->tgc);
 960   draw_solid_square (st, st->end_x, st->end_y, WALL_TOP >> st->end_dir, st->tgc);
 961 }
 962
 963
 964 /* Mark the maze grid as having a wall at the given coordinate,
 965    and draw that wall on the screen. */
 966 static void
 967 build_wall(struct state *st, int i, int j, int dir)
 968 {
 969   /* Draw it on the screen. */
 970   draw_wall(st, i, j, dir, st->gc);
 971   /* Put it in the maze. */
 972   switch(dir)
 973     {
 974     case 0:
 975       st->maze[i][j] |= WALL_TOP;
 976       if(j>0)
 977         st->maze[i][j-1] |= WALL_BOTTOM;
 978       break;
 979     case 1:
 980       st->maze[i][j] |= WALL_RIGHT;
 981       if(i<st->maze_size_x-1)
 982         st->maze[i+1][j] |= WALL_LEFT;
 983       break;
 984     case 2:
 985       st->maze[i][j] |= WALL_BOTTOM;
 986       if(j<st->maze_size_y-1)
 987         st->maze[i][j+1] |= WALL_TOP;
 988       break;
 989     case 3:
 990       st->maze[i][j] |= WALL_LEFT;
 991       if(i>0)
 992         st->maze[i-1][j] |= WALL_RIGHT;
 993       break;
 994     }
 995 }
 996
 997
 998 static void
 999 draw_wall(struct state *st, int i, int j, int dir, GC with_gc)                /* draw a single wall */
1000 {
1001   switch (dir) {
1002   case 0:
1003     XDrawLine(st->dpy, st->window, with_gc,
1004               border_x + st->grid_width * i,
1005               border_y + st->grid_height * j,
1006               border_x + st->grid_width * (i+1),
1007               border_y + st->grid_height * j);
1008     break;
1009   case 1:
1010     XDrawLine(st->dpy, st->window, with_gc,
1011               border_x + st->grid_width * (i+1),
1012               border_y + st->grid_height * j,
1013               border_x + st->grid_width * (i+1),
1014               border_y + st->grid_height * (j+1));
1015     break;
1016   case 2:
1017     XDrawLine(st->dpy, st->window, with_gc,
1018               border_x + st->grid_width * i,
1019               border_y + st->grid_height * (j+1),
1020               border_x + st->grid_width * (i+1),
1021               border_y + st->grid_height * (j+1));
1022     break;
1023   case 3:
1024     XDrawLine(st->dpy, st->window, with_gc,
1025               border_x + st->grid_width * i,
1026               border_y + st->grid_height * j,
1027               border_x + st->grid_width * i,
1028               border_y + st->grid_height * (j+1));
1029     break;
1030   }
1031
1032   if(st->sync_p) {
1033     /* too slow if we sync on every wall, so only sync about ten times
1034        during the maze-creation process.
1035      */
1036     st->sync_tick--;
1037     if (st->sync_tick <= 0) {
1038       XSync(st->dpy, False);
1039       st->sync_tick = st->maze_size_x * st->maze_size_x / 10;
1040     }
1041   }
1042 }
1043
1044
1045 static void
1046 draw_solid_square(struct state *st,
1047                   int i, int j,
1048                   int dir, GC with_gc)
1049 {
1050   switch (dir) {
1051   case WALL_TOP:
1052       XFillRectangle(st->dpy, st->window, with_gc,
1053                      border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1054                      border_y - st->bw-(st->bw==0?1:0) + st->grid_height * j,
1055                      st->grid_width - (st->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
1056       break;
1057   case WALL_RIGHT:
1058       XFillRectangle(st->dpy, st->window, with_gc,
1059                      border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1060                      border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1061                      st->grid_width, st->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
1062       break;
1063   case WALL_BOTTOM:
1064       XFillRectangle(st->dpy, st->window, with_gc,
1065                      border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1066                      border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1067                      st->grid_width - (st->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
1068       break;
1069   case WALL_LEFT:
1070       XFillRectangle(st->dpy, st->window, with_gc,
1071                      border_x - st->bw-(st->bw==0?1:0) + st->grid_width * i,
1072                      border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1073                      st->grid_width, st->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
1074       break;
1075   }
1076 }
1077
1078 /****************************************************************************
1079  Solving the maze
1080  ****************************************************************************/
1081
1082 static int
1083 longdeadend_p(struct state *st, int x1, int y1, int x2, int y2, int endwall)
1084 {
1085     int dx = x2 - x1, dy = y2 - y1;
1086     int sidewalls;
1087
1088     sidewalls = endwall | (endwall >> 2 | endwall << 2);
1089     sidewalls = ~sidewalls & WALL_ANY;
1090
1091     while((st->maze[x2][y2] & WALL_ANY) == sidewalls)
1092     {
1093         if (x2 + dx < 0 || x2 + dx >= st->maze_size_x ||
1094             y2 + dy < 0 || y2 + dy >= st->maze_size_y)
1095           break;
1096         x2 += dx;
1097         y2 += dy;
1098     }
1099
1100     if((st->maze[x2][y2] & WALL_ANY) == (sidewalls | endwall))
1101     {
1102         endwall = (endwall >> 2 | endwall << 2) & WALL_ANY;
1103         while(x1 != x2 || y1 != y2)
1104         {
1105             x1 += dx;
1106             y1 += dy;
1107             draw_solid_square(st, x1, y1, endwall, st->sgc);
1108             st->maze[x1][y1] |= SOLVER_VISIT;
1109         }
1110         return 1;
1111     }
1112     else
1113         return 0;
1114 }
1115
1116 /* Find all dead regions -- areas from which the goal cannot be reached --
1117    and mark them visited. */
1118 static void
1119 find_dead_regions(struct state *st)
1120 {
1121     int xx, yy, flipped;
1122
1123     /* Find all not SOLVER_VISIT squares bordering NOT_DEAD squares
1124        and mark them NOT_DEAD also.  Repeat until no more such squares. */
1125     st->maze[st->start_x][st->start_y] |= NOT_DEAD;
1126
1127     do
1128     {
1129         flipped = 0;
1130         for(xx = 0; xx < st->maze_size_x; xx++)
1131             for(yy = 0; yy < st->maze_size_y; yy++)
1132                 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1133                    && (   (xx && (st->maze[xx-1][yy] & NOT_DEAD))
1134                        || (yy && (st->maze[xx][yy-1] & NOT_DEAD))))
1135                 {
1136                     flipped = 1;
1137                     st->maze[xx][yy] |= NOT_DEAD;
1138                 }
1139         for(xx = st->maze_size_x-1; xx >= 0; xx--)
1140             for(yy = st->maze_size_y-1; yy >= 0; yy--)
1141                 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1142                    && (   (xx != st->maze_size_x-1 && (st->maze[xx+1][yy] & NOT_DEAD))
1143                        || (yy != st->maze_size_y-1 && (st->maze[xx][yy+1] & NOT_DEAD))))
1144                 {
1145                     flipped = 1;
1146                     st->maze[xx][yy] |= NOT_DEAD;
1147                 }
1148     }
1149     while(flipped);
1150
1151     for (yy = 0; yy < st->maze_size_y; yy++)
1152       for (xx = 0; xx < st->maze_size_x; xx++)
1153       {
1154         if (st->maze[xx][yy] & NOT_DEAD)
1155           st->maze[xx][yy] &= ~NOT_DEAD;
1156         else if (!(st->maze[xx][yy] & SOLVER_VISIT))
1157         {
1158           st->maze[xx][yy] |= SOLVER_VISIT;
1159           if((xx < st->logo_x || xx > st->logo_x + st->logo_width / st->grid_width) ||
1160              (yy < st->logo_y || yy > st->logo_y + st->logo_height / st->grid_height))
1161           {
1162             /* if we are completely surrounded by walls, just draw the
1163                inside part */
1164             if ((st->maze[xx][yy] & WALL_ANY) == WALL_ANY)
1165               XFillRectangle(st->dpy, st->window, st->ugc,
1166                              border_x + st->bw + st->grid_width * xx,
1167                              border_y + st->bw + st->grid_height * yy,
1168                              st->grid_width - (st->bw+st->bw), st->grid_height - (st->bw+st->bw));
1169             else
1170             {
1171               if (! (st->maze[xx][yy] & WALL_LEFT))
1172                 draw_solid_square(st, xx, yy, WALL_LEFT, st->ugc);
1173               if (! (st->maze[xx][yy] & WALL_RIGHT))
1174                 draw_solid_square(st, xx, yy, WALL_RIGHT, st->ugc);
1175               if (! (st->maze[xx][yy] & WALL_TOP))
1176                 draw_solid_square(st, xx, yy, WALL_TOP, st->ugc);
1177               if (! (st->maze[xx][yy] & WALL_BOTTOM))
1178                 draw_solid_square(st, xx, yy, WALL_BOTTOM, st->ugc);
1179             }
1180           }
1181         }
1182       }
1183 }
1184
1185 /* solve the maze by one more tick */
1186 static int
1187 solve_maze (struct state *st)
1188 {
1189   struct solve_state *ss = st->solve_state;
1190   if (!ss)
1191     ss = st->solve_state = (struct solve_state *) calloc (1, sizeof(*ss));
1192
1193   if (!ss->running) {
1194     /* plug up the surrounding wall */
1195     st->maze[st->end_x][st->end_y] |= (WALL_TOP >> st->end_dir);
1196
1197     /* initialize search path */
1198     ss->i = 0;
1199     st->path[ss->i].x = st->end_x;
1200     st->path[ss->i].y = st->end_y;
1201     st->path[ss->i].dir = 0;
1202     st->maze[st->end_x][st->end_y] |= SOLVER_VISIT;
1203
1204     ss->running = 1;
1205   }
1206
1207     /* do it */
1208     /* while (1) */
1209     {
1210         int dir, from, ways;
1211
1212         if ( st->maze[st->path[ss->i].x][st->path[ss->i].y] & START_SQUARE )
1213           {
1214             ss->running = 0;
1215             return 1;
1216           }
1217
1218         if(!st->path[ss->i].dir)
1219         {
1220             ways = 0;
1221             /* First visit this square.  Which adjacent squares are open? */
1222             for(dir = WALL_TOP; dir & WALL_ANY; dir >>= 1)
1223             {
1224                 if(st->maze[st->path[ss->i].x][st->path[ss->i].y] & dir)
1225                     continue;
1226
1227                 ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1228                 ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1229
1230                 if(st->maze[ss->x][ss->y] & SOLVER_VISIT)
1231                   continue;
1232
1233                 from = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1234                 /* don't enter obvious dead ends */
1235                 if(((st->maze[ss->x][ss->y] & WALL_ANY) | from) != WALL_ANY)
1236                 {
1237                     if(!longdeadend_p(st, st->path[ss->i].x, st->path[ss->i].y, ss->x, ss->y, dir))
1238                         ways |= dir;
1239                 }
1240                 else
1241                 {
1242                     draw_solid_square(st, ss->x, ss->y, from, st->sgc);
1243                     st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1244                 }
1245             }
1246         }
1247         else
1248             ways = st->path[ss->i].ways;
1249         /* ways now has a bitmask of open paths. */
1250
1251         if(!ways)
1252             goto backtrack;
1253
1254         if (!st->ignorant_p)
1255           {
1256             ss->x = st->path[ss->i].x - st->start_x;
1257             ss->y = st->path[ss->i].y - st->start_y;
1258             /* choice one */
1259             if(abs(ss->y) <= abs(ss->x))
1260               dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1261             else
1262               dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM;
1263
1264             if(dir & ways)
1265               goto found;
1266
1267             /* choice two */
1268             switch(dir)
1269               {
1270               case WALL_LEFT:
1271               case WALL_RIGHT:
1272                 dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM; break;
1273               case WALL_TOP:
1274               case WALL_BOTTOM:
1275                 dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1276               }
1277
1278             if(dir & ways)
1279               goto found;
1280
1281             /* choice three */
1282
1283             dir = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1284             if(dir & ways)
1285               goto found;
1286
1287             /* choice four */
1288             dir = ways;
1289             if(!dir)
1290               goto backtrack;
1291
1292           found: ;
1293           }
1294         else
1295           {
1296             if(ways&WALL_TOP)
1297               dir = WALL_TOP;
1298             else if(ways&WALL_LEFT)
1299               dir = WALL_LEFT;
1300             else if(ways&WALL_BOTTOM)
1301               dir = WALL_BOTTOM;
1302             else if(ways&WALL_RIGHT)
1303               dir = WALL_RIGHT;
1304             else
1305               goto backtrack;
1306           }
1307         ss->bt = 0;
1308         ways &= ~dir;  /* tried this one */
1309
1310         ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1311         ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1312
1313         /* advance in direction dir */
1314         st->path[ss->i].dir = dir;
1315         st->path[ss->i].ways = ways;
1316         draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, dir, st->tgc);
1317
1318         ss->i++;
1319         st->path[ss->i].dir = 0;
1320         st->path[ss->i].ways = 0;
1321         st->path[ss->i].x = ss->x;
1322         st->path[ss->i].y = ss->y;
1323         st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1324         return 0;
1325         /* continue; */
1326
1327     backtrack:
1328         if(ss->i == 0)
1329         {
1330             printf("Unsolvable maze.\n");
1331             ss->running = 0;
1332             return 1;
1333         }
1334
1335         if(!ss->bt && !st->ignorant_p)
1336             find_dead_regions(st);
1337         ss->bt = 1;
1338         from = st->path[ss->i-1].dir;
1339         from = (from << 2 & WALL_ANY) | (from >> 2 & WALL_ANY);
1340
1341         draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, from, st->cgc);
1342         ss->i--;
1343     }
1344
1345     return 0;
1346 }
1347
1348
1349 /****************************************************************************
1350  XScreenSaver boilerplate: resources, command line options, and main loop.
1351  ****************************************************************************/
1352
1353 static const char *maze_defaults[] = {
1354   ".background:    black",
1355   ".foreground:    white",
1356   "*fpsSolid:      true",
1357   "*gridSize:      0",
1358   "*generator:     -1",
1359   "*maxLength:     5",
1360   "*ignorant:      False",
1361
1362   "*solveDelay:    10000",
1363   "*preDelay:      2000000",
1364   "*postDelay:     4000000",
1365
1366   "*liveColor:     #00FF00",
1367   "*deadColor:     #880000",
1368   "*skipColor:     #8B5A00",
1369   "*surroundColor: #220055",
1370
1371   0
1372 };
1373
1374 static XrmOptionDescRec maze_options[] = {
1375   { "-ignorant",        ".ignorant",    XrmoptionNoArg, "True" },
1376   { "-no-ignorant",     ".ignorant",    XrmoptionNoArg, "False" },
1377   { "-grid-size",       ".gridSize",    XrmoptionSepArg, 0 },
1378   { "-solve-delay",     ".solveDelay",  XrmoptionSepArg, 0 },
1379   { "-pre-delay",       ".preDelay",    XrmoptionSepArg, 0 },
1380   { "-post-delay",      ".postDelay",   XrmoptionSepArg, 0 },
1381   { "-bg-color",        ".background",  XrmoptionSepArg, 0 },
1382   { "-fg-color",        ".foreground",  XrmoptionSepArg, 0 },
1383   { "-live-color",      ".liveColor",   XrmoptionSepArg, 0 },
1384   { "-dead-color",      ".deadColor",   XrmoptionSepArg, 0 },
1385   { "-skip-color",      ".skipColor",   XrmoptionSepArg, 0 },
1386   { "-surround-color",  ".surroundColor",XrmoptionSepArg, 0 },
1387   { "-generator",       ".generator",   XrmoptionSepArg, 0 },
1388   { "-max-length",      ".maxLength",   XrmoptionSepArg, 0 },
1389   { 0, 0, 0, 0 }
1390 };
1391
1392 static int generator = 0;
1393
1394 static void *
1395 maze_init (Display *dpy_arg, Window window_arg)
1396 {
1397   struct state *st = (struct state *) calloc (1, sizeof(*st));
1398   int size;
1399   XWindowAttributes xgwa;
1400   unsigned long bg, fg, pfg, pbg, sfg, ufg;
1401
1402   st->dpy = dpy_arg;
1403   st->window = window_arg;
1404
1405   st->stop = 0;
1406   st->state = 1;
1407   st->restart = 1;
1408
1409   st->ifrandom = 0;
1410   st->ifinit = 1;
1411
1412   size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1413   st->solve_delay = get_integer_resource (st->dpy, "solveDelay", "Integer");
1414   st->pre_solve_delay = get_integer_resource (st->dpy, "preDelay", "Integer");
1415   st->post_solve_delay = get_integer_resource (st->dpy, "postDelay", "Integer");
1416   generator = get_integer_resource(st->dpy, "generator", "Integer");
1417   st->max_length = get_integer_resource(st->dpy, "maxLength", "Integer");
1418   st->ignorant_p = get_boolean_resource(st->dpy, "ignorant", "Boolean");
1419
1420   if (get_boolean_resource (st->dpy, "doFPS", "DoFPS"))
1421     {
1422       /* Just guess, rather than loading and measuring the "fpsFont"... */
1423       st->fps_width = 210;
1424       st->fps_height = 62;
1425     }
1426
1427   if (!size) st->ifrandom = 1;
1428
1429   if (size < 2) size = 7 + (random () % 30);
1430   st->grid_width = st->grid_height = size;
1431   st->bw = (size > 6 ? 3 : (size-1)/2);
1432
1433   XGetWindowAttributes (st->dpy, st->window, &xgwa);
1434
1435   st->x = 0;
1436   st->y = 0;
1437
1438   set_maze_sizes (st, xgwa.width, xgwa.height);
1439
1440   st->gc  = XCreateGC(st->dpy, st->window, 0, 0);
1441   st->cgc = XCreateGC(st->dpy, st->window, 0, 0);
1442   st->tgc = XCreateGC(st->dpy, st->window, 0, 0);
1443   st->sgc = XCreateGC(st->dpy, st->window, 0, 0);
1444   st->ugc = XCreateGC(st->dpy, st->window, 0, 0);
1445   st->logo_gc = XCreateGC(st->dpy, st->window, 0, 0);
1446   st->erase_gc = XCreateGC(st->dpy, st->window, 0, 0);
1447
1448   bg  = get_pixel_resource (st->dpy, xgwa.colormap, "background","Background");
1449   fg  = get_pixel_resource (st->dpy, xgwa.colormap, "foreground","Foreground");
1450   pfg = get_pixel_resource (st->dpy, xgwa.colormap, "liveColor", "Foreground");
1451   pbg = get_pixel_resource (st->dpy, xgwa.colormap, "deadColor", "Foreground");
1452   sfg = get_pixel_resource (st->dpy, xgwa.colormap, "skipColor", "Foreground");
1453   ufg = get_pixel_resource (st->dpy, xgwa.colormap, "surroundColor", "Foreground");
1454
1455   XSetForeground (st->dpy, st->gc, fg);
1456   XSetBackground (st->dpy, st->gc, bg);
1457   XSetForeground (st->dpy, st->cgc, pbg);
1458   XSetBackground (st->dpy, st->cgc, bg);
1459   XSetForeground (st->dpy, st->tgc, pfg);
1460   XSetBackground (st->dpy, st->tgc, bg);
1461   XSetForeground (st->dpy, st->sgc, sfg);
1462   XSetBackground (st->dpy, st->sgc, bg);
1463   XSetForeground (st->dpy, st->ugc, ufg);
1464   XSetBackground (st->dpy, st->ugc, bg);
1465   XSetForeground (st->dpy, st->logo_gc, fg);
1466   XSetBackground (st->dpy, st->logo_gc, bg);
1467   XSetForeground (st->dpy, st->erase_gc, bg);
1468   XSetBackground (st->dpy, st->erase_gc, bg);
1469
1470   {
1471     Window r;
1472     int x, y;
1473     unsigned int w, h, bbw, d;
1474     unsigned long *pixels;
1475     int npixels;
1476     Pixmap logo_mask = 0;
1477     st->logo_map = xscreensaver_logo (xgwa.screen, xgwa.visual, st->window,
1478                                       xgwa.colormap, bg,
1479                                       &pixels, &npixels, &logo_mask,
1480                                       xgwa.width > 800 || xgwa.height > 800);
1481     if (logo_mask) {
1482       XSetClipMask (st->dpy, st->logo_gc, logo_mask);
1483       XFreePixmap (st->dpy, logo_mask);
1484     }
1485     if (pixels) free (pixels);
1486     XGetGeometry (st->dpy, st->logo_map, &r, &x, &y, &w, &h, &bbw, &d);
1487     st->logo_width = w;
1488     st->logo_height = h;
1489   }
1490
1491
1492   st->restart = 0;
1493   st->sync_p = 1;
1494
1495   return st;
1496 }
1497
1498
1499 static void
1500 maze_reshape (Display *dpy, Window window, void *closure,
1501                  unsigned int w, unsigned int h)
1502 {
1503   struct state *st = (struct state *) closure;
1504   st->restart = 1;
1505 }
1506
1507
1508 static unsigned long
1509 maze_draw (Display *dpy, Window window, void *closure)
1510 {
1511   struct state *st = (struct state *) closure;
1512   int this_delay = st->solve_delay;
1513
1514   if (st->eraser || st->erase_window)
1515     {
1516       st->erase_window = 0;
1517       st->eraser = erase_window (st->dpy, st->window, st->eraser);
1518       if (st->eraser)
1519         this_delay = 10000;
1520       else {
1521         this_delay = 1000000;
1522         if (this_delay > st->pre_solve_delay)
1523           this_delay = st->pre_solve_delay;
1524       }
1525       goto END;
1526     }
1527
1528     if (st->restart || st->stop) goto pop;
1529     switch (st->state) {
1530     case 1:
1531       initialize_maze(st);
1532       if (st->ifrandom && st->ifinit)
1533        {
1534          int size;
1535          size = 7 + (random () % 30);
1536          st->grid_width = st->grid_height = size;
1537          st->bw = (size > 6 ? 3 : (size-1)/2);
1538          st->ifinit = 0;
1539          st->restart = 1;
1540        }
1541       break;
1542     case 2:
1543       XClearWindow(st->dpy, st->window);
1544       draw_maze_border(st);
1545       break;
1546     case 3:
1547       st->this_gen = generator;
1548       if(st->this_gen<0 || st->this_gen>2)
1549         st->this_gen = random()%3;
1550
1551       switch(st->this_gen)
1552         {
1553         case 0:
1554           create_maze(st);
1555           break;
1556         case 1:
1557           alt_create_maze(st);
1558           break;
1559         case 2:
1560           set_create_maze(st);
1561           break;
1562         }
1563       break;
1564     case 4:
1565       this_delay = st->pre_solve_delay;
1566       break;
1567     case 5:
1568       if (! solve_maze(st))
1569         --st->state;  /* stay in state 5 */
1570       break;
1571     case 6:
1572       st->erase_window = 1;
1573       this_delay = st->post_solve_delay;
1574       st->state = 0 ;
1575       st->ifinit = 1;
1576       break;
1577     default:
1578       abort ();
1579     }
1580     ++st->state;
1581   pop:
1582     if (st->restart)
1583       {
1584         XWindowAttributes xgwa;
1585         int size;
1586
1587         st->restart = 0;
1588         st->stop = 0;
1589         st->state = 1;
1590
1591         if (st->solve_state && st->solve_state->running)
1592           st->solve_state->running = 0;
1593
1594         st->sync_p = ((random() % 4) != 0);
1595
1596         size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1597         if (size < 2) size = 7 + (random () % 30);
1598         st->grid_width = st->grid_height = size;
1599         st->bw = (size > 6 ? 3 : (size-1)/2);
1600
1601         XGetWindowAttributes (st->dpy, st->window, &xgwa);
1602         set_maze_sizes (st, xgwa.width, xgwa.height);
1603       }
1604
1605  END:
1606     return this_delay;
1607 }
1608
1609
1610 static Bool
1611 maze_event (Display *dpy, Window window, void *closure, XEvent *event)
1612 {
1613   struct state *st = (struct state *) closure;
1614   switch (event->type)
1615     {
1616     case ButtonPress:
1617       switch (event->xbutton.button)
1618         {
1619         case 2:
1620           st->stop = !st->stop ;
1621           if (st->state == 5) st->state = 4 ;
1622           else {
1623             st->restart = 1;
1624             st->stop = 0;
1625           }
1626           return True;
1627
1628         default:
1629           st->restart = 1 ;
1630           st->stop = 0 ;
1631           return True;
1632         }
1633       break;
1634
1635     case Expose:
1636       st->restart = 1;
1637       break;
1638
1639     default:
1640       break;
1641     }
1642   return False;
1643 }
1644
1645
1646 static void
1647 maze_free (Display *dpy, Window window, void *closure)
1648 {
1649   struct state *st = (struct state *) closure;
1650   free (st);
1651 }
1652
1653 XSCREENSAVER_MODULE ("Maze", maze)