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