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   st->cur_sq_x = st->move_list[st->sqnum].x;
 875   st->cur_sq_y = st->move_list[st->sqnum].y;
 876   return ( st->sqnum );
 877 }
 878
 879
 880 /****************************************************************************
 881  Drawing the maze
 882  ****************************************************************************/
 883
 884 /* draws the maze outline, and the logo */
 885 static void
 886 draw_maze_border (struct state *st)
 887 {
 888   int i, j;
 889
 890   for ( i=0; i<st->maze_size_x; i++) {
 891     if ( st->maze[i][0] & WALL_TOP ) {
 892       XDrawLine(st->dpy, st->window, st->gc,
 893                 border_x + st->grid_width * i,
 894                 border_y,
 895                 border_x + st->grid_width * (i+1) - 1,
 896                 border_y);
 897     }
 898     if ((st->maze[i][st->maze_size_y - 1] & WALL_BOTTOM)) {
 899       XDrawLine(st->dpy, st->window, st->gc,
 900                 border_x + st->grid_width * i,
 901                 border_y + st->grid_height * (st->maze_size_y) - 1,
 902                 border_x + st->grid_width * (i+1) - 1,
 903                 border_y + st->grid_height * (st->maze_size_y) - 1);
 904     }
 905   }
 906   for ( j=0; j<st->maze_size_y; j++) {
 907     if ( st->maze[st->maze_size_x - 1][j] & WALL_RIGHT ) {
 908       XDrawLine(st->dpy, st->window, st->gc,
 909                 border_x + st->grid_width * st->maze_size_x - 1,
 910                 border_y + st->grid_height * j,
 911                 border_x + st->grid_width * st->maze_size_x - 1,
 912                 border_y + st->grid_height * (j+1) - 1);
 913     }
 914     if ( st->maze[0][j] & WALL_LEFT ) {
 915       XDrawLine(st->dpy, st->window, st->gc,
 916                 border_x,
 917                 border_y + st->grid_height * j,
 918                 border_x,
 919                 border_y + st->grid_height * (j+1) - 1);
 920     }
 921   }
 922
 923   if (st->logo_x != -1)
 924     {
 925       Window r;
 926       int xx, yy;
 927       unsigned int w, h, bbw, d;
 928
 929       /* round up to grid size */
 930       int ww = ((st->logo_width  / st->grid_width) + 1)  * st->grid_width;
 931       int hh = ((st->logo_height / st->grid_height) + 1) * st->grid_height;
 932       int lx, ly;
 933
 934       XGetGeometry (st->dpy, st->logo_map, &r, &xx, &yy, &w, &h, &bbw, &d);
 935
 936       /* kludge: if the logo "hole" is around the same size as the logo,
 937          don't center it (since the xscreensaver logo image is a little
 938          off center...  But do center it if the hole/gridsize is large. */
 939       if (ww < st->logo_width  + 5) ww = w;
 940       if (hh < st->logo_height + 5) hh = h;
 941
 942
 943       lx = border_x + 3 + st->grid_width  * st->logo_x + ((ww - w) / 2);
 944       ly = border_y + 3 + st->grid_height * st->logo_y + ((hh - h) / 2);
 945
 946       /* Fill the background of the logo box with the "unreachable" color */
 947       XFillRectangle (st->dpy, st->window, st->ugc,
 948                       border_x + 3 + st->grid_width  * st->logo_x,
 949                       border_y + 3 + st->grid_height * st->logo_y,
 950                       ww, hh);
 951
 952       XSetClipOrigin (st->dpy, st->logo_gc, lx, ly);
 953       if (d == 1)
 954         XCopyPlane (st->dpy, st->logo_map, st->window, st->logo_gc,
 955                     0, 0, w, h, lx, ly, 1);
 956       else
 957         XCopyArea (st->dpy, st->logo_map, st->window, st->logo_gc,
 958                    0, 0, w, h, lx, ly);
 959     }
 960   draw_solid_square (st, st->start_x, st->start_y, WALL_TOP >> st->start_dir, st->tgc);
 961   draw_solid_square (st, st->end_x, st->end_y, WALL_TOP >> st->end_dir, st->tgc);
 962 }
 963
 964
 965 /* Mark the maze grid as having a wall at the given coordinate,
 966    and draw that wall on the screen. */
 967 static void
 968 build_wall(struct state *st, int i, int j, int dir)
 969 {
 970   /* Draw it on the screen. */
 971   draw_wall(st, i, j, dir, st->gc);
 972   /* Put it in the maze. */
 973   switch(dir)
 974     {
 975     case 0:
 976       st->maze[i][j] |= WALL_TOP;
 977       if(j>0)
 978         st->maze[i][j-1] |= WALL_BOTTOM;
 979       break;
 980     case 1:
 981       st->maze[i][j] |= WALL_RIGHT;
 982       if(i<st->maze_size_x-1)
 983         st->maze[i+1][j] |= WALL_LEFT;
 984       break;
 985     case 2:
 986       st->maze[i][j] |= WALL_BOTTOM;
 987       if(j<st->maze_size_y-1)
 988         st->maze[i][j+1] |= WALL_TOP;
 989       break;
 990     case 3:
 991       st->maze[i][j] |= WALL_LEFT;
 992       if(i>0)
 993         st->maze[i-1][j] |= WALL_RIGHT;
 994       break;
 995     }
 996 }
 997
 998
 999 static void
1000 draw_wall(struct state *st, int i, int j, int dir, GC with_gc)                /* draw a single wall */
1001 {
1002   switch (dir) {
1003   case 0:
1004     XDrawLine(st->dpy, st->window, with_gc,
1005               border_x + st->grid_width * i,
1006               border_y + st->grid_height * j,
1007               border_x + st->grid_width * (i+1),
1008               border_y + st->grid_height * j);
1009     break;
1010   case 1:
1011     XDrawLine(st->dpy, st->window, with_gc,
1012               border_x + st->grid_width * (i+1),
1013               border_y + st->grid_height * j,
1014               border_x + st->grid_width * (i+1),
1015               border_y + st->grid_height * (j+1));
1016     break;
1017   case 2:
1018     XDrawLine(st->dpy, st->window, with_gc,
1019               border_x + st->grid_width * i,
1020               border_y + st->grid_height * (j+1),
1021               border_x + st->grid_width * (i+1),
1022               border_y + st->grid_height * (j+1));
1023     break;
1024   case 3:
1025     XDrawLine(st->dpy, st->window, with_gc,
1026               border_x + st->grid_width * i,
1027               border_y + st->grid_height * j,
1028               border_x + st->grid_width * i,
1029               border_y + st->grid_height * (j+1));
1030     break;
1031   }
1032
1033   if(st->sync_p) {
1034     /* too slow if we sync on every wall, so only sync about ten times
1035        during the maze-creation process.
1036      */
1037     st->sync_tick--;
1038     if (st->sync_tick <= 0) {
1039       XSync(st->dpy, False);
1040       st->sync_tick = st->maze_size_x * st->maze_size_x / 10;
1041     }
1042   }
1043 }
1044
1045
1046 static void
1047 draw_solid_square(struct state *st,
1048                   int i, int j,
1049                   int dir, GC with_gc)
1050 {
1051   switch (dir) {
1052   case WALL_TOP:
1053       XFillRectangle(st->dpy, st->window, with_gc,
1054                      border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1055                      border_y - st->bw-(st->bw==0?1:0) + st->grid_height * j,
1056                      st->grid_width - (st->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
1057       break;
1058   case WALL_RIGHT:
1059       XFillRectangle(st->dpy, st->window, with_gc,
1060                      border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1061                      border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1062                      st->grid_width, st->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
1063       break;
1064   case WALL_BOTTOM:
1065       XFillRectangle(st->dpy, st->window, with_gc,
1066                      border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1067                      border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1068                      st->grid_width - (st->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
1069       break;
1070   case WALL_LEFT:
1071       XFillRectangle(st->dpy, st->window, with_gc,
1072                      border_x - st->bw-(st->bw==0?1:0) + st->grid_width * i,
1073                      border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1074                      st->grid_width, st->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
1075       break;
1076   }
1077 }
1078
1079 /****************************************************************************
1080  Solving the maze
1081  ****************************************************************************/
1082
1083 static int
1084 longdeadend_p(struct state *st, int x1, int y1, int x2, int y2, int endwall)
1085 {
1086     int dx = x2 - x1, dy = y2 - y1;
1087     int sidewalls;
1088
1089     sidewalls = endwall | (endwall >> 2 | endwall << 2);
1090     sidewalls = ~sidewalls & WALL_ANY;
1091
1092     while((st->maze[x2][y2] & WALL_ANY) == sidewalls)
1093     {
1094         if (x2 + dx < 0 || x2 + dx >= st->maze_size_x ||
1095             y2 + dy < 0 || y2 + dy >= st->maze_size_y)
1096           break;
1097         x2 += dx;
1098         y2 += dy;
1099     }
1100
1101     if((st->maze[x2][y2] & WALL_ANY) == (sidewalls | endwall))
1102     {
1103         endwall = (endwall >> 2 | endwall << 2) & WALL_ANY;
1104         while(x1 != x2 || y1 != y2)
1105         {
1106             x1 += dx;
1107             y1 += dy;
1108             draw_solid_square(st, x1, y1, endwall, st->sgc);
1109             st->maze[x1][y1] |= SOLVER_VISIT;
1110         }
1111         return 1;
1112     }
1113     else
1114         return 0;
1115 }
1116
1117 /* Find all dead regions -- areas from which the goal cannot be reached --
1118    and mark them visited. */
1119 static void
1120 find_dead_regions(struct state *st)
1121 {
1122     int xx, yy, flipped;
1123
1124     /* Find all not SOLVER_VISIT squares bordering NOT_DEAD squares
1125        and mark them NOT_DEAD also.  Repeat until no more such squares. */
1126     st->maze[st->start_x][st->start_y] |= NOT_DEAD;
1127
1128     do
1129     {
1130         flipped = 0;
1131         for(xx = 0; xx < st->maze_size_x; xx++)
1132             for(yy = 0; yy < st->maze_size_y; yy++)
1133                 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1134                    && (   (xx && (st->maze[xx-1][yy] & NOT_DEAD))
1135                        || (yy && (st->maze[xx][yy-1] & NOT_DEAD))))
1136                 {
1137                     flipped = 1;
1138                     st->maze[xx][yy] |= NOT_DEAD;
1139                 }
1140         for(xx = st->maze_size_x-1; xx >= 0; xx--)
1141             for(yy = st->maze_size_y-1; yy >= 0; yy--)
1142                 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1143                    && (   (xx != st->maze_size_x-1 && (st->maze[xx+1][yy] & NOT_DEAD))
1144                        || (yy != st->maze_size_y-1 && (st->maze[xx][yy+1] & NOT_DEAD))))
1145                 {
1146                     flipped = 1;
1147                     st->maze[xx][yy] |= NOT_DEAD;
1148                 }
1149     }
1150     while(flipped);
1151
1152     for (yy = 0; yy < st->maze_size_y; yy++)
1153       for (xx = 0; xx < st->maze_size_x; xx++)
1154       {
1155         if (st->maze[xx][yy] & NOT_DEAD)
1156           st->maze[xx][yy] &= ~NOT_DEAD;
1157         else if (!(st->maze[xx][yy] & SOLVER_VISIT))
1158         {
1159           st->maze[xx][yy] |= SOLVER_VISIT;
1160           if((xx < st->logo_x || xx > st->logo_x + st->logo_width / st->grid_width) ||
1161              (yy < st->logo_y || yy > st->logo_y + st->logo_height / st->grid_height))
1162           {
1163             /* if we are completely surrounded by walls, just draw the
1164                inside part */
1165             if ((st->maze[xx][yy] & WALL_ANY) == WALL_ANY)
1166               XFillRectangle(st->dpy, st->window, st->ugc,
1167                              border_x + st->bw + st->grid_width * xx,
1168                              border_y + st->bw + st->grid_height * yy,
1169                              st->grid_width - (st->bw+st->bw), st->grid_height - (st->bw+st->bw));
1170             else
1171             {
1172               if (! (st->maze[xx][yy] & WALL_LEFT))
1173                 draw_solid_square(st, xx, yy, WALL_LEFT, st->ugc);
1174               if (! (st->maze[xx][yy] & WALL_RIGHT))
1175                 draw_solid_square(st, xx, yy, WALL_RIGHT, st->ugc);
1176               if (! (st->maze[xx][yy] & WALL_TOP))
1177                 draw_solid_square(st, xx, yy, WALL_TOP, st->ugc);
1178               if (! (st->maze[xx][yy] & WALL_BOTTOM))
1179                 draw_solid_square(st, xx, yy, WALL_BOTTOM, st->ugc);
1180             }
1181           }
1182         }
1183       }
1184 }
1185
1186 /* solve the maze by one more tick */
1187 static int
1188 solve_maze (struct state *st)
1189 {
1190   struct solve_state *ss = st->solve_state;
1191   if (!ss)
1192     ss = st->solve_state = (struct solve_state *) calloc (1, sizeof(*ss));
1193
1194   if (!ss->running) {
1195     /* plug up the surrounding wall */
1196     st->maze[st->end_x][st->end_y] |= (WALL_TOP >> st->end_dir);
1197
1198     /* initialize search path */
1199     ss->i = 0;
1200     st->path[ss->i].x = st->end_x;
1201     st->path[ss->i].y = st->end_y;
1202     st->path[ss->i].dir = 0;
1203     st->maze[st->end_x][st->end_y] |= SOLVER_VISIT;
1204
1205     ss->running = 1;
1206   }
1207
1208     /* do it */
1209     /* while (1) */
1210     {
1211         int dir, from, ways;
1212
1213         if ( st->maze[st->path[ss->i].x][st->path[ss->i].y] & START_SQUARE )
1214           {
1215             ss->running = 0;
1216             return 1;
1217           }
1218
1219         if(!st->path[ss->i].dir)
1220         {
1221             ways = 0;
1222             /* First visit this square.  Which adjacent squares are open? */
1223             for(dir = WALL_TOP; dir & WALL_ANY; dir >>= 1)
1224             {
1225                 if(st->maze[st->path[ss->i].x][st->path[ss->i].y] & dir)
1226                     continue;
1227
1228                 ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1229                 ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1230
1231                 if(st->maze[ss->x][ss->y] & SOLVER_VISIT)
1232                   continue;
1233
1234                 from = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1235                 /* don't enter obvious dead ends */
1236                 if(((st->maze[ss->x][ss->y] & WALL_ANY) | from) != WALL_ANY)
1237                 {
1238                     if(!longdeadend_p(st, st->path[ss->i].x, st->path[ss->i].y, ss->x, ss->y, dir))
1239                         ways |= dir;
1240                 }
1241                 else
1242                 {
1243                     draw_solid_square(st, ss->x, ss->y, from, st->sgc);
1244                     st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1245                 }
1246             }
1247         }
1248         else
1249             ways = st->path[ss->i].ways;
1250         /* ways now has a bitmask of open paths. */
1251
1252         if(!ways)
1253             goto backtrack;
1254
1255         if (!st->ignorant_p)
1256           {
1257             ss->x = st->path[ss->i].x - st->start_x;
1258             ss->y = st->path[ss->i].y - st->start_y;
1259             /* choice one */
1260             if(abs(ss->y) <= abs(ss->x))
1261               dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1262             else
1263               dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM;
1264
1265             if(dir & ways)
1266               goto found;
1267
1268             /* choice two */
1269             switch(dir)
1270               {
1271               case WALL_LEFT:
1272               case WALL_RIGHT:
1273                 dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM; break;
1274               case WALL_TOP:
1275               case WALL_BOTTOM:
1276                 dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1277               }
1278
1279             if(dir & ways)
1280               goto found;
1281
1282             /* choice three */
1283
1284             dir = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1285             if(dir & ways)
1286               goto found;
1287
1288             /* choice four */
1289             dir = ways;
1290             if(!dir)
1291               goto backtrack;
1292
1293           found: ;
1294           }
1295         else
1296           {
1297             if(ways&WALL_TOP)
1298               dir = WALL_TOP;
1299             else if(ways&WALL_LEFT)
1300               dir = WALL_LEFT;
1301             else if(ways&WALL_BOTTOM)
1302               dir = WALL_BOTTOM;
1303             else if(ways&WALL_RIGHT)
1304               dir = WALL_RIGHT;
1305             else
1306               goto backtrack;
1307           }
1308         ss->bt = 0;
1309         ways &= ~dir;  /* tried this one */
1310
1311         ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1312         ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1313
1314         /* advance in direction dir */
1315         st->path[ss->i].dir = dir;
1316         st->path[ss->i].ways = ways;
1317         draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, dir, st->tgc);
1318
1319         ss->i++;
1320         st->path[ss->i].dir = 0;
1321         st->path[ss->i].ways = 0;
1322         st->path[ss->i].x = ss->x;
1323         st->path[ss->i].y = ss->y;
1324         st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1325         return 0;
1326         /* continue; */
1327
1328     backtrack:
1329         if(ss->i == 0)
1330         {
1331             printf("Unsolvable maze.\n");
1332             ss->running = 0;
1333             return 1;
1334         }
1335
1336         if(!ss->bt && !st->ignorant_p)
1337             find_dead_regions(st);
1338         ss->bt = 1;
1339         from = st->path[ss->i-1].dir;
1340         from = (from << 2 & WALL_ANY) | (from >> 2 & WALL_ANY);
1341
1342         draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, from, st->cgc);
1343         ss->i--;
1344     }
1345
1346     return 0;
1347 }
1348
1349
1350 /****************************************************************************
1351  XScreenSaver boilerplate: resources, command line options, and main loop.
1352  ****************************************************************************/
1353
1354 static const char *maze_defaults[] = {
1355   ".background:    black",
1356   ".foreground:    white",
1357   "*fpsSolid:      true",
1358   "*gridSize:      0",
1359   "*generator:     -1",
1360   "*maxLength:     5",
1361   "*ignorant:      False",
1362
1363   "*solveDelay:    10000",
1364   "*preDelay:      2000000",
1365   "*postDelay:     4000000",
1366
1367   "*liveColor:     #00FF00",
1368   "*deadColor:     #880000",
1369   "*skipColor:     #8B5A00",
1370   "*surroundColor: #220055",
1371
1372   0
1373 };
1374
1375 static XrmOptionDescRec maze_options[] = {
1376   { "-ignorant",        ".ignorant",    XrmoptionNoArg, "True" },
1377   { "-no-ignorant",     ".ignorant",    XrmoptionNoArg, "False" },
1378   { "-grid-size",       ".gridSize",    XrmoptionSepArg, 0 },
1379   { "-solve-delay",     ".solveDelay",  XrmoptionSepArg, 0 },
1380   { "-pre-delay",       ".preDelay",    XrmoptionSepArg, 0 },
1381   { "-post-delay",      ".postDelay",   XrmoptionSepArg, 0 },
1382   { "-bg-color",        ".background",  XrmoptionSepArg, 0 },
1383   { "-fg-color",        ".foreground",  XrmoptionSepArg, 0 },
1384   { "-live-color",      ".liveColor",   XrmoptionSepArg, 0 },
1385   { "-dead-color",      ".deadColor",   XrmoptionSepArg, 0 },
1386   { "-skip-color",      ".skipColor",   XrmoptionSepArg, 0 },
1387   { "-surround-color",  ".surroundColor",XrmoptionSepArg, 0 },
1388   { "-generator",       ".generator",   XrmoptionSepArg, 0 },
1389   { "-max-length",      ".maxLength",   XrmoptionSepArg, 0 },
1390   { 0, 0, 0, 0 }
1391 };
1392
1393 static int generator = 0;
1394
1395 static void *
1396 maze_init (Display *dpy_arg, Window window_arg)
1397 {
1398   struct state *st = (struct state *) calloc (1, sizeof(*st));
1399   int size;
1400   XWindowAttributes xgwa;
1401   unsigned long bg, fg, pfg, pbg, sfg, ufg;
1402
1403   st->dpy = dpy_arg;
1404   st->window = window_arg;
1405
1406   st->stop = 0;
1407   st->state = 1;
1408   st->restart = 1;
1409
1410   st->ifrandom = 0;
1411   st->ifinit = 1;
1412
1413   size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1414   st->solve_delay = get_integer_resource (st->dpy, "solveDelay", "Integer");
1415   st->pre_solve_delay = get_integer_resource (st->dpy, "preDelay", "Integer");
1416   st->post_solve_delay = get_integer_resource (st->dpy, "postDelay", "Integer");
1417   generator = get_integer_resource(st->dpy, "generator", "Integer");
1418   st->max_length = get_integer_resource(st->dpy, "maxLength", "Integer");
1419   st->ignorant_p = get_boolean_resource(st->dpy, "ignorant", "Boolean");
1420
1421   if (get_boolean_resource (st->dpy, "doFPS", "DoFPS"))
1422     {
1423       /* Just guess, rather than loading and measuring the "fpsFont"... */
1424       st->fps_width = 210;
1425       st->fps_height = 62;
1426     }
1427
1428   if (!size) st->ifrandom = 1;
1429
1430   if (size < 2) size = 7 + (random () % 30);
1431   st->grid_width = st->grid_height = size;
1432   st->bw = (size > 6 ? 3 : (size-1)/2);
1433
1434   XGetWindowAttributes (st->dpy, st->window, &xgwa);
1435
1436   st->x = 0;
1437   st->y = 0;
1438
1439   set_maze_sizes (st, xgwa.width, xgwa.height);
1440
1441   st->gc  = XCreateGC(st->dpy, st->window, 0, 0);
1442   st->cgc = XCreateGC(st->dpy, st->window, 0, 0);
1443   st->tgc = XCreateGC(st->dpy, st->window, 0, 0);
1444   st->sgc = XCreateGC(st->dpy, st->window, 0, 0);
1445   st->ugc = XCreateGC(st->dpy, st->window, 0, 0);
1446   st->logo_gc = XCreateGC(st->dpy, st->window, 0, 0);
1447   st->erase_gc = XCreateGC(st->dpy, st->window, 0, 0);
1448
1449   bg  = get_pixel_resource (st->dpy, xgwa.colormap, "background","Background");
1450   fg  = get_pixel_resource (st->dpy, xgwa.colormap, "foreground","Foreground");
1451   pfg = get_pixel_resource (st->dpy, xgwa.colormap, "liveColor", "Foreground");
1452   pbg = get_pixel_resource (st->dpy, xgwa.colormap, "deadColor", "Foreground");
1453   sfg = get_pixel_resource (st->dpy, xgwa.colormap, "skipColor", "Foreground");
1454   ufg = get_pixel_resource (st->dpy, xgwa.colormap, "surroundColor", "Foreground");
1455
1456   XSetForeground (st->dpy, st->gc, fg);
1457   XSetBackground (st->dpy, st->gc, bg);
1458   XSetForeground (st->dpy, st->cgc, pbg);
1459   XSetBackground (st->dpy, st->cgc, bg);
1460   XSetForeground (st->dpy, st->tgc, pfg);
1461   XSetBackground (st->dpy, st->tgc, bg);
1462   XSetForeground (st->dpy, st->sgc, sfg);
1463   XSetBackground (st->dpy, st->sgc, bg);
1464   XSetForeground (st->dpy, st->ugc, ufg);
1465   XSetBackground (st->dpy, st->ugc, bg);
1466   XSetForeground (st->dpy, st->logo_gc, fg);
1467   XSetBackground (st->dpy, st->logo_gc, bg);
1468   XSetForeground (st->dpy, st->erase_gc, bg);
1469   XSetBackground (st->dpy, st->erase_gc, bg);
1470
1471   {
1472     Window r;
1473     int x, y;
1474     unsigned int w, h, bbw, d;
1475     unsigned long *pixels;
1476     int npixels;
1477     Pixmap logo_mask = 0;
1478     st->logo_map = xscreensaver_logo (xgwa.screen, xgwa.visual, st->window,
1479                                       xgwa.colormap, bg,
1480                                       &pixels, &npixels, &logo_mask,
1481                                       xgwa.width > 800 || xgwa.height > 800);
1482     if (logo_mask) {
1483       XSetClipMask (st->dpy, st->logo_gc, logo_mask);
1484       XFreePixmap (st->dpy, logo_mask);
1485     }
1486     if (pixels) free (pixels);
1487     XGetGeometry (st->dpy, st->logo_map, &r, &x, &y, &w, &h, &bbw, &d);
1488     st->logo_width = w;
1489     st->logo_height = h;
1490   }
1491
1492
1493   st->restart = 0;
1494   st->sync_p = 1;
1495
1496   return st;
1497 }
1498
1499
1500 static void
1501 maze_reshape (Display *dpy, Window window, void *closure,
1502                  unsigned int w, unsigned int h)
1503 {
1504   struct state *st = (struct state *) closure;
1505   st->restart = 1;
1506 }
1507
1508
1509 static unsigned long
1510 maze_draw (Display *dpy, Window window, void *closure)
1511 {
1512   struct state *st = (struct state *) closure;
1513   int this_delay = st->solve_delay;
1514
1515   if (st->eraser || st->erase_window)
1516     {
1517       st->erase_window = 0;
1518       st->eraser = erase_window (st->dpy, st->window, st->eraser);
1519       if (st->eraser)
1520         this_delay = 10000;
1521       else {
1522         this_delay = 1000000;
1523         if (this_delay > st->pre_solve_delay)
1524           this_delay = st->pre_solve_delay;
1525       }
1526       goto END;
1527     }
1528
1529     if (st->restart || st->stop) goto pop;
1530     switch (st->state) {
1531     case 1:
1532       initialize_maze(st);
1533       if (st->ifrandom && st->ifinit)
1534        {
1535          int size;
1536          size = 7 + (random () % 30);
1537          st->grid_width = st->grid_height = size;
1538          st->bw = (size > 6 ? 3 : (size-1)/2);
1539          st->ifinit = 0;
1540          st->restart = 1;
1541        }
1542       break;
1543     case 2:
1544       XClearWindow(st->dpy, st->window);
1545       draw_maze_border(st);
1546       break;
1547     case 3:
1548       st->this_gen = generator;
1549       if(st->this_gen<0 || st->this_gen>2)
1550         st->this_gen = random()%3;
1551
1552       switch(st->this_gen)
1553         {
1554         case 0:
1555           create_maze(st);
1556           break;
1557         case 1:
1558           alt_create_maze(st);
1559           break;
1560         case 2:
1561           set_create_maze(st);
1562           break;
1563         }
1564       break;
1565     case 4:
1566       this_delay = st->pre_solve_delay;
1567       break;
1568     case 5:
1569       if (! solve_maze(st))
1570         --st->state;  /* stay in state 5 */
1571       break;
1572     case 6:
1573       st->erase_window = 1;
1574       this_delay = st->post_solve_delay;
1575       st->state = 0 ;
1576       st->ifinit = 1;
1577       break;
1578     default:
1579       abort ();
1580     }
1581     ++st->state;
1582   pop:
1583     if (st->restart)
1584       {
1585         XWindowAttributes xgwa;
1586         int size;
1587
1588         st->restart = 0;
1589         st->stop = 0;
1590         st->state = 1;
1591
1592         if (st->solve_state && st->solve_state->running)
1593           st->solve_state->running = 0;
1594
1595         st->sync_p = ((random() % 4) != 0);
1596
1597         size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1598         if (size < 2) size = 7 + (random () % 30);
1599         st->grid_width = st->grid_height = size;
1600         st->bw = (size > 6 ? 3 : (size-1)/2);
1601
1602         XGetWindowAttributes (st->dpy, st->window, &xgwa);
1603         set_maze_sizes (st, xgwa.width, xgwa.height);
1604       }
1605
1606  END:
1607     return this_delay;
1608 }
1609
1610
1611 static Bool
1612 maze_event (Display *dpy, Window window, void *closure, XEvent *event)
1613 {
1614   struct state *st = (struct state *) closure;
1615   switch (event->type)
1616     {
1617     case ButtonPress:
1618       switch (event->xbutton.button)
1619         {
1620         case 2:
1621           st->stop = !st->stop ;
1622           if (st->state == 5) st->state = 4 ;
1623           else {
1624             st->restart = 1;
1625             st->stop = 0;
1626           }
1627           return True;
1628
1629         default:
1630           st->restart = 1 ;
1631           st->stop = 0 ;
1632           return True;
1633         }
1634       break;
1635
1636     case Expose:
1637       st->restart = 1;
1638       break;
1639
1640     default:
1641       break;
1642     }
1643   return False;
1644 }
1645
1646
1647 static void
1648 maze_free (Display *dpy, Window window, void *closure)
1649 {
1650   struct state *st = (struct state *) closure;
1651   free (st);
1652 }
1653
1654 XSCREENSAVER_MODULE ("Maze", maze)