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

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