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