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