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

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