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  128
 138 # define logo_height 128
 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       XGetGeometry (dpy, logo_map, &r, &x, &y, &w, &h, &bw, &d);
1132       if (d == 1)
1133         XCopyPlane (dpy, logo_map, win, logo_gc,
1134                     0, 0, w, h,
1135                     border_x + 3 + grid_width * logo_x,
1136                     border_y + 3 + grid_height * logo_y, 1);
1137       else
1138         XCopyArea (dpy, logo_map, win, logo_gc,
1139                    0, 0, w, h,
1140                    border_x + 3 + grid_width * logo_x,
1141                    border_y + 3 + grid_height * logo_y);
1142     }
1143   draw_solid_square (start_x, start_y, WALL_TOP >> start_dir, tgc);
1144   draw_solid_square (end_x, end_y, WALL_TOP >> end_dir, tgc);
1145 }
1146
1147
1148 static void
1149 draw_wall(int i, int j, int dir, GC gc)                /* draw a single wall */
1150 {
1151   switch (dir) {
1152   case 0:
1153     XDrawLine(dpy, win, gc,
1154               border_x + grid_width * i,
1155               border_y + grid_height * j,
1156               border_x + grid_width * (i+1),
1157               border_y + grid_height * j);
1158     break;
1159   case 1:
1160     XDrawLine(dpy, win, gc,
1161               border_x + grid_width * (i+1),
1162               border_y + grid_height * j,
1163               border_x + grid_width * (i+1),
1164               border_y + grid_height * (j+1));
1165     break;
1166   case 2:
1167     XDrawLine(dpy, win, gc,
1168               border_x + grid_width * i,
1169               border_y + grid_height * (j+1),
1170               border_x + grid_width * (i+1),
1171               border_y + grid_height * (j+1));
1172     break;
1173   case 3:
1174     XDrawLine(dpy, win, gc,
1175               border_x + grid_width * i,
1176               border_y + grid_height * j,
1177               border_x + grid_width * i,
1178               border_y + grid_height * (j+1));
1179     break;
1180   }
1181   if(sync_p)
1182     XSync(dpy, False);
1183 }
1184
1185 /* Actually build a wall. */
1186 static void
1187 build_wall(i, j, dir)
1188      int i, j, dir;
1189 {
1190   /* Draw it on the screen. */
1191   draw_wall(i, j, dir, gc);
1192   /* Put it in the maze. */
1193   switch(dir)
1194     {
1195     case 0:
1196       maze[i][j] |= WALL_TOP;
1197       if(j>0)
1198         maze[i][j-1] |= WALL_BOTTOM;
1199       break;
1200     case 1:
1201       maze[i][j] |= WALL_RIGHT;
1202       if(i<maze_size_x-1)
1203         maze[i+1][j] |= WALL_LEFT;
1204       break;
1205     case 2:
1206       maze[i][j] |= WALL_BOTTOM;
1207       if(j<maze_size_y-1)
1208         maze[i][j+1] |= WALL_TOP;
1209       break;
1210     case 3:
1211       maze[i][j] |= WALL_LEFT;
1212       if(i>0)
1213         maze[i-1][j] |= WALL_RIGHT;
1214       break;
1215     }
1216 }
1217
1218 /* Break out a wall. */
1219 #if 0
1220 static void
1221 break_wall(i, j, dir)
1222      int i, j, dir;
1223 {
1224   /* Draw it on the screen. */
1225   draw_wall(i, j, dir, erase_gc);
1226   /* Put it in the maze. */
1227   switch(dir)
1228     {
1229     case 0:
1230       maze[i][j] &= ~WALL_TOP;
1231       if(j>0)
1232         maze[i][j-1] &= ~WALL_BOTTOM;
1233       break;
1234     case 1:
1235       maze[i][j] &= ~WALL_RIGHT;
1236       if(i<maze_size_x-1)
1237         maze[i+1][j] &= ~WALL_LEFT;
1238       break;
1239     case 2:
1240       maze[i][j] &= ~WALL_BOTTOM;
1241       if(j<maze_size_y-1)
1242         maze[i][j+1] &= ~WALL_BOTTOM;
1243       break;
1244     case 3:
1245       maze[i][j] &= ~WALL_LEFT;
1246       if(i>0)
1247         maze[i-1][j] &= ~WALL_RIGHT;
1248       break;
1249     }
1250 }
1251 #endif /* 0 */
1252
1253
1254 static void
1255 draw_solid_square(int i, int j,          /* draw a solid square in a square */
1256                   int dir, GC gc)
1257 {
1258   switch (dir) {
1259   case WALL_TOP:
1260       XFillRectangle(dpy, win, gc,
1261                      border_x + bw + grid_width * i,
1262                      border_y - bw + grid_height * j,
1263                      grid_width - (bw+bw), grid_height);
1264       break;
1265   case WALL_RIGHT:
1266       XFillRectangle(dpy, win, gc,
1267                      border_x + bw + grid_width * i,
1268                      border_y + bw + grid_height * j,
1269                      grid_width, grid_height - (bw+bw));
1270       break;
1271   case WALL_BOTTOM:
1272       XFillRectangle(dpy, win, gc,
1273                      border_x + bw + grid_width * i,
1274                      border_y + bw + grid_height * j,
1275                      grid_width - (bw+bw), grid_height);
1276       break;
1277   case WALL_LEFT:
1278       XFillRectangle(dpy, win, gc,
1279                      border_x - bw + grid_width * i,
1280                      border_y + bw + grid_height * j,
1281                      grid_width, grid_height - (bw+bw));
1282       break;
1283   }
1284   XSync (dpy, False);
1285 }
1286
1287 int
1288 longdeadend_p(int x1, int y1, int x2, int y2, int endwall)
1289 {
1290     int dx = x2 - x1, dy = y2 - y1;
1291     int sidewalls;
1292
1293     sidewalls = endwall | (endwall >> 2 | endwall << 2);
1294     sidewalls = ~sidewalls & WALL_ANY;
1295
1296     while((maze[x2][y2] & WALL_ANY) == sidewalls)
1297     {
1298         x2 += dx;
1299         y2 += dy;
1300     }
1301
1302     if((maze[x2][y2] & WALL_ANY) == (sidewalls | endwall))
1303     {
1304         endwall = (endwall >> 2 | endwall << 2) & WALL_ANY;
1305         while(x1 != x2 || y1 != y2)
1306         {
1307             x1 += dx;
1308             y1 += dy;
1309             draw_solid_square(x1, y1, endwall, sgc);
1310             maze[x1][y1] |= SOLVER_VISIT;
1311         }
1312         return 1;
1313     }
1314     else
1315         return 0;
1316 }
1317
1318 /* Find all dead regions -- areas from which the goal cannot be reached --
1319    and mark them visited. */
1320 void
1321 find_dead_regions(void)
1322 {
1323     int x, y, flipped;
1324
1325     /* Find all not SOLVER_VISIT squares bordering NOT_DEAD squares
1326        and mark them NOT_DEAD also.  Repeat until no more such squares. */
1327     maze[start_x][start_y] |= NOT_DEAD;
1328
1329     do
1330     {
1331         flipped = 0;
1332         for(x = 0; x < maze_size_x; x++)
1333             for(y = 0; y < maze_size_y; y++)
1334                 if(!(maze[x][y] & (SOLVER_VISIT | NOT_DEAD))
1335                    && (   (x && (maze[x-1][y] & NOT_DEAD))
1336                        || (y && (maze[x][y-1] & NOT_DEAD))))
1337                 {
1338                     flipped = 1;
1339                     maze[x][y] |= NOT_DEAD;
1340                 }
1341         for(x = maze_size_x-1; x >= 0; x--)
1342             for(y = maze_size_y-1; y >= 0; y--)
1343                 if(!(maze[x][y] & (SOLVER_VISIT | NOT_DEAD))
1344                    && (   (x != maze_size_x-1 && (maze[x+1][y] & NOT_DEAD))
1345                        || (y != maze_size_y-1 && (maze[x][y+1] & NOT_DEAD))))
1346                 {
1347                     flipped = 1;
1348                     maze[x][y] |= NOT_DEAD;
1349                 }
1350     }
1351     while(flipped);
1352
1353     for (y = 0; y < maze_size_y; y++)
1354       for (x = 0; x < maze_size_x; x++)
1355       {
1356         if (maze[x][y] & NOT_DEAD)
1357           maze[x][y] &= ~NOT_DEAD;
1358         else if (!(maze[x][y] & SOLVER_VISIT))
1359         {
1360           maze[x][y] |= SOLVER_VISIT;
1361           if((x < logo_x || x > logo_x + logo_width / grid_width) ||
1362              (y < logo_y || y > logo_y + logo_height / grid_height))
1363           {
1364             if (!maze[x][y] & WALL_ANY)
1365               XFillRectangle(dpy, win, ugc,
1366                              border_x + bw + grid_width * x,
1367                              border_y + bw + grid_height * y,
1368                              grid_width - (bw+bw), grid_height - (bw+bw));
1369             else
1370             {
1371               if (! (maze[x][y] & WALL_LEFT))
1372                 draw_solid_square(x, y, WALL_LEFT, ugc);
1373               if (! (maze[x][y] & WALL_RIGHT))
1374                 draw_solid_square(x, y, WALL_RIGHT, ugc);
1375               if (! (maze[x][y] & WALL_TOP))
1376                 draw_solid_square(x, y, WALL_TOP, ugc);
1377               if (! (maze[x][y] & WALL_BOTTOM))
1378                 draw_solid_square(x, y, WALL_BOTTOM, ugc);
1379             }
1380           }
1381         }
1382       }
1383     XSync(dpy, False);
1384 }
1385
1386 static void
1387 solve_maze (void)                     /* solve it with graphical feedback */
1388 {
1389     int i, dir, from, x, y, ways, bt = 0;
1390
1391     /* plug up the surrounding wall */
1392     maze[end_x][end_y] |= (WALL_TOP >> end_dir);
1393
1394     /* initialize search path */
1395     i = 0;
1396     path[i].x = end_x;
1397     path[i].y = end_y;
1398     path[i].dir = 0;
1399     maze[end_x][end_y] |= SOLVER_VISIT;
1400
1401     /* do it */
1402     while (1)
1403     {
1404         if ( maze[path[i].x][path[i].y] & START_SQUARE )
1405             return;
1406
1407         /* Abort solve on expose - cheapo repaint strategy */
1408         if (check_events()) return;
1409
1410         if (solve_delay) usleep (solve_delay);
1411
1412         if(!path[i].dir)
1413         {
1414             ways = 0;
1415             /* First visit this square.  Which adjacent squares are open? */
1416             for(dir = WALL_TOP; dir & WALL_ANY; dir >>= 1)
1417             {
1418                 if(maze[path[i].x][path[i].y] & dir)
1419                     continue;
1420
1421                 y = path[i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1422                 x = path[i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1423
1424                 if(maze[x][y] & SOLVER_VISIT)
1425                     continue;
1426
1427                 from = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1428                 /* don't enter obvious dead ends */
1429                 if(((maze[x][y] & WALL_ANY) | from) != WALL_ANY)
1430                 {
1431                     if(!longdeadend_p(path[i].x, path[i].y, x, y, dir))
1432                         ways |= dir;
1433                 }
1434                 else
1435                 {
1436                     draw_solid_square(x, y, from, sgc);
1437                     maze[x][y] |= SOLVER_VISIT;
1438                 }
1439             }
1440         }
1441         else
1442             ways = path[i].ways;
1443         /* ways now has a bitmask of open paths. */
1444
1445         if(!ways)
1446             goto backtrack;
1447
1448         if (!ignorant_p)
1449           {
1450             x = path[i].x - start_x;
1451             y = path[i].y - start_y;
1452             /* choice one */
1453             if(abs(y) <= abs(x))
1454               dir = (x > 0) ? WALL_LEFT : WALL_RIGHT;
1455             else
1456               dir = (y > 0) ? WALL_TOP : WALL_BOTTOM;
1457
1458             if(dir & ways)
1459               goto found;
1460
1461             /* choice two */
1462             switch(dir)
1463               {
1464               case WALL_LEFT:
1465               case WALL_RIGHT:
1466                 dir = (y > 0) ? WALL_TOP : WALL_BOTTOM; break;
1467               case WALL_TOP:
1468               case WALL_BOTTOM:
1469                 dir = (x > 0) ? WALL_LEFT : WALL_RIGHT;
1470               }
1471
1472             if(dir & ways)
1473               goto found;
1474
1475             /* choice three */
1476
1477             dir = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1478             if(dir & ways)
1479               goto found;
1480
1481             /* choice four */
1482             dir = ways;
1483             if(!dir)
1484               goto backtrack;
1485
1486           found: ;
1487           }
1488         else
1489           {
1490             if(ways&WALL_TOP)
1491               dir = WALL_TOP;
1492             else if(ways&WALL_LEFT)
1493               dir = WALL_LEFT;
1494             else if(ways&WALL_BOTTOM)
1495               dir = WALL_BOTTOM;
1496             else if(ways&WALL_RIGHT)
1497               dir = WALL_RIGHT;
1498             else
1499               goto backtrack;
1500           }
1501         bt = 0;
1502         ways &= ~dir;  /* tried this one */
1503
1504         y = path[i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1505         x = path[i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1506
1507         /* advance in direction dir */
1508         path[i].dir = dir;
1509         path[i].ways = ways;
1510         draw_solid_square(path[i].x, path[i].y, dir, tgc);
1511
1512         i++;
1513         path[i].dir = 0;
1514         path[i].ways = 0;
1515         path[i].x = x;
1516         path[i].y = y;
1517         maze[x][y] |= SOLVER_VISIT;
1518         continue;
1519
1520     backtrack:
1521         if(i == 0)
1522         {
1523             printf("Unsolvable maze.\n");
1524             return;
1525         }
1526
1527         if(!bt && !ignorant_p)
1528             find_dead_regions();
1529         bt = 1;
1530         from = path[i-1].dir;
1531         from = (from << 2 & WALL_ANY) | (from >> 2 & WALL_ANY);
1532
1533         draw_solid_square(path[i].x, path[i].y, from, cgc);
1534         i--;
1535     }
1536 }
1537
1538 #if 0
1539 static void
1540 enter_square (int n)                      /* move into a neighboring square */
1541 {
1542   draw_solid_square( (int)path[n].x, (int)path[n].y,
1543                     (int)path[n].dir, tgc);
1544
1545   path[n+1].dir = -1;
1546   switch (path[n].dir) {
1547   case 0: path[n+1].x = path[n].x;
1548     path[n+1].y = path[n].y - 1;
1549     break;
1550   case 1: path[n+1].x = path[n].x + 1;
1551     path[n+1].y = path[n].y;
1552     break;
1553   case 2: path[n+1].x = path[n].x;
1554     path[n+1].y = path[n].y + 1;
1555     break;
1556   case 3: path[n+1].x = path[n].x - 1;
1557     path[n+1].y = path[n].y;
1558     break;
1559   }
1560 }
1561 #endif /* 0 */
1562
1563
1564 /*
1565  *  jmr additions for Jamie Zawinski's <jwz@jwz.org> screensaver stuff,
1566  *  note that the code above this has probably been hacked about in some
1567  *  arbitrary way.
1568  */
1569
1570 char *progclass = "Maze";
1571
1572 char *defaults[] = {
1573   ".background: black",
1574   ".foreground: white",
1575   "*gridSize:   0",
1576   "*solveDelay: 5000",
1577   "*preDelay:   2000000",
1578   "*postDelay:  4000000",
1579   "*liveColor:  green",
1580   "*deadColor:  red",
1581   "*skipColor:  orange",
1582   "*surroundColor: slateblue",
1583   "*generator:  -1",
1584   "*maxLength:  5",
1585   "*syncDraw:   False",
1586   "*bridge:     False",
1587   0
1588 };
1589
1590 XrmOptionDescRec options[] = {
1591   { "-ignorant",        ".ignorant",    XrmoptionNoArg, "True" },
1592   { "-no-ignorant",     ".ignorant",    XrmoptionNoArg, "False" },
1593   { "-grid-size",       ".gridSize",    XrmoptionSepArg, 0 },
1594   { "-solve-delay",     ".solveDelay",  XrmoptionSepArg, 0 },
1595   { "-pre-delay",       ".preDelay",    XrmoptionSepArg, 0 },
1596   { "-post-delay",      ".postDelay",   XrmoptionSepArg, 0 },
1597   { "-live-color",      ".liveColor",   XrmoptionSepArg, 0 },
1598   { "-dead-color",      ".deadColor",   XrmoptionSepArg, 0 },
1599   { "-skip-color",      ".skipColor",   XrmoptionSepArg, 0 },
1600   { "-surround-color",  ".surroundColor",XrmoptionSepArg, 0 },
1601   { "-generator",       ".generator",   XrmoptionSepArg, 0 },
1602   { "-max-length",      ".maxLength",   XrmoptionSepArg, 0 },
1603   { "-bridge",          ".bridge",      XrmoptionNoArg, "True" },
1604   { "-no-bridge",       ".bridge",      XrmoptionNoArg, "False" },
1605   { 0, 0, 0, 0 }
1606 };
1607
1608 #ifdef XSCREENSAVER_LOGO
1609 extern void xscreensaver_logo (Display *,Drawable,Colormap, Bool next_frame_p);
1610 #endif
1611
1612 void
1613 screenhack(Display *display, Window window)
1614 {
1615   Pixmap gray;
1616   int size, root, generator, this_gen;
1617   XWindowAttributes xgwa;
1618   unsigned long bg, fg, pfg, pbg, sfg, ufg;
1619
1620   size = get_integer_resource ("gridSize", "Dimension");
1621   root = get_boolean_resource("root", "Boolean");
1622   solve_delay = get_integer_resource ("solveDelay", "Integer");
1623   pre_solve_delay = get_integer_resource ("preDelay", "Integer");
1624   post_solve_delay = get_integer_resource ("postDelay", "Integer");
1625   generator = get_integer_resource("generator", "Integer");
1626   max_length = get_integer_resource("maxLength", "Integer");
1627   bridge_p = get_boolean_resource("bridge", "Boolean");
1628   ignorant_p = get_boolean_resource("ignorant", "Boolean");
1629
1630   if (size < 2) size = 7 + (random () % 30);
1631   grid_width = grid_height = size;
1632   bw = (size > 6 ? 3 : (size-1)/2);
1633
1634   dpy = display; win = window; /* the maze stuff uses global variables */
1635
1636   XGetWindowAttributes (dpy, win, &xgwa);
1637
1638   x = 0;
1639   y = 0;
1640
1641   set_maze_sizes (xgwa.width, xgwa.height);
1642
1643   if (! root)
1644     {
1645       XWindowAttributes xgwa;
1646       XGetWindowAttributes (dpy, window, &xgwa);
1647       XSelectInput (dpy, win,
1648                     xgwa.your_event_mask | ExposureMask |
1649                     ButtonPressMask |StructureNotifyMask);
1650     }
1651
1652   gc  = XCreateGC(dpy, win, 0, 0);
1653   cgc = XCreateGC(dpy, win, 0, 0);
1654   tgc = XCreateGC(dpy, win, 0, 0);
1655   sgc = XCreateGC(dpy, win, 0, 0);
1656   ugc = XCreateGC(dpy, win, 0, 0);
1657   logo_gc = XCreateGC(dpy, win, 0, 0);
1658   erase_gc = XCreateGC(dpy, win, 0, 0);
1659
1660   gray = XCreateBitmapFromData (dpy,win,gray1_bits,gray1_width,gray1_height);
1661
1662   bg  = get_pixel_resource ("background","Background", dpy, xgwa.colormap);
1663   fg  = get_pixel_resource ("foreground","Foreground", dpy, xgwa.colormap);
1664   pfg = get_pixel_resource ("liveColor", "Foreground", dpy, xgwa.colormap);
1665   pbg = get_pixel_resource ("deadColor", "Foreground", dpy, xgwa.colormap);
1666   sfg = get_pixel_resource ("skipColor", "Foreground", dpy, xgwa.colormap);
1667   ufg = get_pixel_resource ("surroundColor", "Foreground", dpy, xgwa.colormap);
1668
1669   XSetForeground (dpy, gc, fg);
1670   XSetBackground (dpy, gc, bg);
1671   XSetForeground (dpy, cgc, pbg);
1672   XSetBackground (dpy, cgc, bg);
1673   XSetForeground (dpy, tgc, pfg);
1674   XSetBackground (dpy, tgc, bg);
1675   XSetForeground (dpy, sgc, sfg);
1676   XSetBackground (dpy, sgc, bg);
1677   XSetForeground (dpy, ugc, ufg);
1678   XSetBackground (dpy, ugc, bg);
1679   XSetForeground (dpy, logo_gc, fg);
1680   XSetBackground (dpy, logo_gc, bg);
1681   XSetForeground (dpy, erase_gc, bg);
1682   XSetBackground (dpy, erase_gc, bg);
1683
1684   XSetStipple (dpy, cgc, gray);
1685   XSetFillStyle (dpy, cgc, FillOpaqueStippled);
1686   XSetStipple (dpy, sgc, gray);
1687   XSetFillStyle (dpy, sgc, FillOpaqueStippled);
1688   XSetStipple (dpy, ugc, gray);
1689   XSetFillStyle (dpy, ugc, FillOpaqueStippled);
1690
1691 #ifdef XSCREENSAVER_LOGO
1692   {
1693     int w, h;
1694     /* round up to grid size */
1695     w = ((logo_width  / grid_width) + 1)  * grid_width;
1696     h = ((logo_height / grid_height) + 1) * grid_height;
1697     logo_map = XCreatePixmap (dpy, win, w, h, xgwa.depth);
1698     xscreensaver_logo (dpy, logo_map, xgwa.colormap, False);
1699   }
1700 #else
1701   if  (!(logo_map = XCreateBitmapFromData (dpy, win, logo_bits,
1702                                            logo_width, logo_height)))
1703     {
1704       fprintf (stderr, "Can't create logo pixmap\n");
1705       exit (1);
1706     }
1707 #endif
1708   XMapRaised(dpy, win);
1709
1710   restart = root;
1711
1712   sync_p = !(random() % 10);
1713
1714   while (1) {                            /* primary execution loop [ rhess ] */
1715     if (check_events()) continue ;
1716     if (restart || stop) goto pop;
1717     switch (state) {
1718     case 1:
1719       initialize_maze();
1720       break;
1721     case 2:
1722       XClearWindow(dpy, win);
1723       draw_maze_border();
1724       break;
1725     case 3:
1726       this_gen = generator;
1727       if(this_gen<0 || this_gen>2)
1728         this_gen = random()%3;
1729
1730       switch(this_gen)
1731         {
1732         case 0:
1733           create_maze();
1734           break;
1735         case 1:
1736           alt_create_maze();
1737           break;
1738         case 2:
1739           set_create_maze();
1740           break;
1741         }
1742       break;
1743     case 4:
1744       XSync (dpy, False);
1745       usleep (pre_solve_delay);
1746       break;
1747     case 5:
1748       solve_maze();
1749       break;
1750     case 6:
1751       XSync (dpy, False);
1752       usleep (post_solve_delay);
1753       state = 0 ;
1754       erase_full_window(display, window);
1755       break;
1756     default:
1757       abort ();
1758     }
1759     ++state;
1760   pop:
1761     if (restart)
1762       {
1763         static XWindowAttributes wattr;
1764         restart = 0;
1765         stop = 0;
1766         state = 1;
1767         XGetWindowAttributes (dpy, win, &wattr);
1768         set_maze_sizes (wattr.width, wattr.height);
1769         XClearWindow (dpy, win);
1770         XSync (dpy, False);
1771         sync_p = !(random() % 10);
1772       }
1773   }
1774 }