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

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