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

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