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 #include  <stdio.h>
  88
  89 /* #include  <X11/bitmaps/gray1> */
  90 #define gray1_width  2
  91 #define gray1_height 2
  92 static const char gray1_bits[] = { 0x01, 0x02 };
  93
  94
  95 #define MAX_MAZE_SIZE_X 1000
  96 #define MAX_MAZE_SIZE_Y 1000
  97
  98 #define MOVE_LIST_SIZE  (MAX_MAZE_SIZE_X * MAX_MAZE_SIZE_Y)
  99
 100 #define NOT_DEAD        0x8000
 101 #define SOLVER_VISIT    0x4000
 102 #define START_SQUARE    0x2000
 103 #define END_SQUARE      0x1000
 104
 105 #define WALL_TOP        0x8
 106 #define WALL_RIGHT      0x4
 107 #define WALL_BOTTOM     0x2
 108 #define WALL_LEFT       0x1
 109 #define WALL_ANY        0xF
 110
 111 #define DOOR_IN_TOP     0x800
 112 #define DOOR_IN_RIGHT   0x400
 113 #define DOOR_IN_BOTTOM  0x200
 114 #define DOOR_IN_LEFT    0x100
 115 #define DOOR_IN_ANY     0xF00
 116
 117 #define DOOR_OUT_TOP    0x80
 118 #define DOOR_OUT_RIGHT  0x40
 119 #define DOOR_OUT_BOTTOM 0x20
 120 #define DOOR_OUT_LEFT   0x10
 121
 122
 123 #define border_x        (0)
 124 #define border_y        (0)
 125
 126 #define get_random(x)   (random() % (x))
 127
 128
 129 struct move_list_struct {
 130   unsigned short x;
 131   unsigned short y;
 132   unsigned char dir, ways;
 133 };
 134
 135 struct solve_state {
 136   int running;
 137   int i, x, y, bt;
 138 };
 139
 140
 141 struct state {
 142   Display *dpy;
 143   Window window;
 144
 145   GC    gc, cgc, tgc, sgc, ugc, logo_gc, erase_gc;
 146   Pixmap logo_map;
 147   int logo_width, logo_height; /* in pixels */
 148
 149   int solve_delay, pre_solve_delay, post_solve_delay;
 150   int logo_x, logo_y;
 151
 152   unsigned short maze[MAX_MAZE_SIZE_X][MAX_MAZE_SIZE_Y];
 153
 154   struct move_list_struct move_list[MOVE_LIST_SIZE];
 155   struct move_list_struct save_path[MOVE_LIST_SIZE];
 156   struct move_list_struct path[MOVE_LIST_SIZE];
 157
 158   int maze_size_x, maze_size_y;
 159   int sqnum, cur_sq_x, cur_sq_y, path_length;
 160   int start_x, start_y, start_dir, end_x, end_y, end_dir;
 161   int grid_width, grid_height;
 162   int bw;
 163
 164   int x, y, restart, stop, state, max_length;
 165   int sync_p, sync_tick;
 166   int bridge_p, ignorant_p;
 167
 168   struct solve_state *solve_state;
 169
 170   int *sets;            /* The sets that our squares are in. */
 171   int *hedges;          /* The `list' of hedges. */
 172
 173   int this_gen;
 174   int erase_window;
 175   eraser_state *eraser;
 176
 177   int ifrandom;
 178   int ifinit;
 179
 180 };
 181
 182
 183 static void
 184 set_maze_sizes (struct state *st, int width, int height)
 185 {
 186   st->maze_size_x = width / st->grid_width;
 187   st->maze_size_y = height / st->grid_height;
 188
 189   if (st->maze_size_x < 4) st->maze_size_x = 4;
 190   if (st->maze_size_y < 4) st->maze_size_y = 4;
 191 }
 192
 193
 194 static void
 195 initialize_maze (struct state *st) /* draw the surrounding wall and start/end squares */
 196 {
 197   register int i, j, wall;
 198   int logow = 1 + st->logo_width / st->grid_width;
 199   int logoh = 1 + st->logo_height / st->grid_height;
 200
 201   /* initialize all squares */
 202   for ( i=0; i<st->maze_size_x; i++) {
 203     for ( j=0; j<st->maze_size_y; j++) {
 204       st->maze[i][j] = 0;
 205     }
 206   }
 207
 208   /* top wall */
 209   for ( i=0; i<st->maze_size_x; i++ ) {
 210     st->maze[i][0] |= WALL_TOP;
 211   }
 212
 213   /* right wall */
 214   for ( j=0; j<st->maze_size_y; j++ ) {
 215     st->maze[st->maze_size_x-1][j] |= WALL_RIGHT;
 216   }
 217
 218   /* bottom wall */
 219   for ( i=0; i<st->maze_size_x; i++ ) {
 220     st->maze[i][st->maze_size_y-1] |= WALL_BOTTOM;
 221   }
 222
 223   /* left wall */
 224   for ( j=0; j<st->maze_size_y; j++ ) {
 225     st->maze[0][j] |= WALL_LEFT;
 226   }
 227
 228   /* set start square */
 229   wall = get_random(4);
 230   switch (wall) {
 231   case 0:
 232     i = get_random(st->maze_size_x);
 233     j = 0;
 234     break;
 235   case 1:
 236     i = st->maze_size_x - 1;
 237     j = get_random(st->maze_size_y);
 238     break;
 239   case 2:
 240     i = get_random(st->maze_size_x);
 241     j = st->maze_size_y - 1;
 242     break;
 243   case 3:
 244     i = 0;
 245     j = get_random(st->maze_size_y);
 246     break;
 247   }
 248   st->maze[i][j] |= START_SQUARE;
 249   st->maze[i][j] |= ( DOOR_IN_TOP >> wall );
 250   st->maze[i][j] &= ~( WALL_TOP >> wall );
 251   st->cur_sq_x = i;
 252   st->cur_sq_y = j;
 253   st->start_x = i;
 254   st->start_y = j;
 255   st->start_dir = wall;
 256   st->sqnum = 0;
 257
 258   /* set end square */
 259   wall = (wall + 2)%4;
 260   switch (wall) {
 261   case 0:
 262     i = get_random(st->maze_size_x);
 263     j = 0;
 264     break;
 265   case 1:
 266     i = st->maze_size_x - 1;
 267     j = get_random(st->maze_size_y);
 268     break;
 269   case 2:
 270     i = get_random(st->maze_size_x);
 271     j = st->maze_size_y - 1;
 272     break;
 273   case 3:
 274     i = 0;
 275     j = get_random(st->maze_size_y);
 276     break;
 277   }
 278   st->maze[i][j] |= END_SQUARE;
 279   st->maze[i][j] |= ( DOOR_OUT_TOP >> wall );
 280   st->maze[i][j] &= ~( WALL_TOP >> wall );
 281   st->end_x = i;
 282   st->end_y = j;
 283   st->end_dir = wall;
 284
 285   /* set logo */
 286   if ((st->maze_size_x-logow >= 6) && (st->maze_size_y-logoh >= 6))
 287     {
 288       /* not closer than 3 grid units from a wall */
 289       st->logo_x = get_random (st->maze_size_x - logow - 5) + 3;
 290       st->logo_y = get_random (st->maze_size_y - logoh - 5) + 3;
 291       for (i=0; i<logow; i++)
 292         for (j=0; j<logoh; j++)
 293           st->maze[st->logo_x + i][st->logo_y + j] |= DOOR_IN_TOP;
 294     }
 295   else
 296     st->logo_y = st->logo_x = -1;
 297
 298   /* #### should mask out the cells covered by the FPS display if "doFPS"
 299           is true.  But that's hard, because the "logo_x" crap that does
 300           that trick for the logo is scattered all around the code... */
 301 }
 302
 303 static int choose_door (struct state *st);
 304 static int backup (struct state *st);
 305 static void draw_wall (struct state *, int, int, int, GC);
 306 static void draw_solid_square (struct state *, int, int, int, GC);
 307 /*static void enter_square (struct state *, int);*/
 308 static void build_wall (struct state *, int, int, int);
 309 /*static void break_wall (struct state *, int, int, int);*/
 310
 311 static void join_sets(struct state *, int, int);
 312
 313 #define DEBUG_SETS 0
 314
 315 /* Initialise the sets. */
 316 static void
 317 init_sets(struct state *st)
 318 {
 319   int i, t, r, xx, yy;
 320
 321   if(st->sets)
 322     free(st->sets);
 323   st->sets = (int *)malloc(st->maze_size_x*st->maze_size_y*sizeof(int));
 324   if(!st->sets)
 325     abort();
 326   for(i = 0; i < st->maze_size_x*st->maze_size_y; i++)
 327     {
 328       st->sets[i] = i;
 329     }
 330
 331   if(st->hedges)
 332     free(st->hedges);
 333   st->hedges = (int *)malloc(st->maze_size_x*st->maze_size_y*2*sizeof(int));
 334   if(!st->hedges)
 335     abort();
 336   for(i = 0; i < st->maze_size_x*st->maze_size_y*2; i++)
 337     {
 338       st->hedges[i] = i;
 339     }
 340   /* Mask out outside walls. */
 341   for(i = 0; i < st->maze_size_y; i++)
 342     {
 343       st->hedges[2*((st->maze_size_x)*i+st->maze_size_x-1)+1] = -1;
 344     }
 345   for(i = 0; i < st->maze_size_x; i++)
 346     {
 347       st->hedges[2*((st->maze_size_y-1)*st->maze_size_x+i)] = -1;
 348     }
 349   /* Mask out a possible logo. */
 350   if(st->logo_x!=-1)
 351     {
 352       int logow = 1 + st->logo_width / st->grid_width;
 353       int logoh = 1 + st->logo_height / st->grid_height;
 354       int bridge_dir, bridge_c;
 355
 356       if(st->bridge_p && logoh>=3 && logow>=3)
 357         {
 358           bridge_dir = 1+random()%2;
 359           if(bridge_dir==1)
 360             {
 361               bridge_c = st->logo_y+random()%(logoh-2)+1;
 362             }
 363           else
 364             {
 365               bridge_c = st->logo_x+random()%(logow-2)+1;
 366             }
 367         }
 368       else
 369         {
 370           bridge_dir = 0;
 371           bridge_c = -1;
 372         }
 373
 374       for(xx = st->logo_x; xx < st->logo_x+logow; xx++)
 375         for(yy = st->logo_y; yy < st->logo_y+logoh; yy++)
 376           {
 377             /* I should check for the bridge here, except that I join the
 378              * bridge together below.
 379              */
 380             st->hedges[2*(xx+st->maze_size_x*yy)+1] = -1;
 381             st->hedges[2*(xx+st->maze_size_x*yy)] = -1;
 382           }
 383       for(xx = st->logo_x; xx < st->logo_x+logow; xx++)
 384         {
 385           if(!(bridge_dir==2 && xx==bridge_c))
 386             {
 387               build_wall(st, xx, st->logo_y, 0);
 388               build_wall(st, xx, st->logo_y+logoh, 0);
 389             }
 390           st->hedges[2*(xx+st->maze_size_x*(st->logo_y-1))] = -1;
 391           if(bridge_dir==1)
 392             {
 393               build_wall(st, xx, bridge_c, 0);
 394               build_wall(st, xx, bridge_c, 2);
 395             }
 396         }
 397       for(yy = st->logo_y; yy < st->logo_y+logoh; yy++)
 398         {
 399           if(!(bridge_dir==1 && yy==bridge_c))
 400             {
 401               build_wall(st, st->logo_x, yy, 3);
 402               build_wall(st, st->logo_x+logow, yy, 3);
 403             }
 404           st->hedges[2*(st->logo_x-1+st->maze_size_x*yy)+1] = -1;
 405           if(bridge_dir==2)
 406             {
 407               build_wall(st, bridge_c, yy, 1);
 408               build_wall(st, bridge_c, yy, 3);
 409             }
 410         }
 411       /* Join the whole bridge together. */
 412       if(st->bridge_p)
 413         {
 414           if(bridge_dir==1)
 415             {
 416               xx = st->logo_x-1;
 417               yy = bridge_c;
 418               for(i = st->logo_x; i < st->logo_x+logow+1; i++)
 419                 join_sets(st, xx+yy*st->maze_size_x, i+yy*st->maze_size_x);
 420             }
 421           else
 422             {
 423               yy = st->logo_y-1;
 424               xx = bridge_c;
 425               for(i = st->logo_y; i < st->logo_y+logoh+1; i++)
 426                 join_sets(st, xx+yy*st->maze_size_x, xx+i*st->maze_size_x);
 427             }
 428         }
 429     }
 430
 431   for(i = 0; i < st->maze_size_x*st->maze_size_y*2; i++)
 432     {
 433       t = st->hedges[i];
 434       r = random()%(st->maze_size_x*st->maze_size_y*2);
 435       st->hedges[i] = st->hedges[r];
 436       st->hedges[r] = t;
 437     }
 438 }
 439
 440 /* Get the representative of a set. */
 441 static int
 442 get_set(struct state *st, int num)
 443 {
 444   int s;
 445
 446   if(st->sets[num]==num)
 447     return num;
 448   else
 449     {
 450       s = get_set(st, st->sets[num]);
 451       st->sets[num] = s;
 452       return s;
 453     }
 454 }
 455
 456 /* Join two sets together. */
 457 static void
 458 join_sets(struct state *st, int num1, int num2)
 459 {
 460   int s1, s2;
 461
 462   s1 = get_set(st, num1);
 463   s2 = get_set(st, num2);
 464
 465   if(s1<s2)
 466     st->sets[s2] = s1;
 467   else
 468     st->sets[s1] = s2;
 469 }
 470
 471 /* Exitialise the sets. */
 472 static void
 473 exit_sets(struct state *st)
 474 {
 475   if(st->hedges)
 476     free(st->hedges);
 477   st->hedges = 0;
 478   if(st->sets)
 479     free(st->sets);
 480   st->sets = 0;
 481 }
 482
 483 #if DEBUG_SETS
 484 /* Temporary hack. */
 485 static void
 486 show_set(int num, GC gc)
 487 {
 488   int st->x, st->y, set;
 489
 490   set = get_set(num);
 491
 492   for(st->x = 0; st->x < st->maze_size_x; st->x++)
 493     for(st->y = 0; st->y < st->maze_size_y; st->y++)
 494       {
 495         if(get_set(st->x+st->y*st->maze_size_x)==set)
 496           {
 497             XFillRectangle(st->dpy, st->window, st->gc,  border_x + st->bw + st->grid_width * st->x,
 498                          border_y + st->bw + st->grid_height * st->y,
 499                          st->grid_width-2*st->bw , st->grid_height-2*st->bw);
 500           }
 501       }
 502 }
 503 #endif
 504
 505 /* Second alternative maze creator: Put each square in the maze in a
 506  * separate set. Also, make a list of all the hedges. Randomize that list.
 507  * Walk through the list. If, for a certain hedge, the two squares on both
 508  * sides of it are in different sets, union the sets and remove the hedge.
 509  * Continue until all hedges have been processed or only one set remains.
 510  */
 511 static void
 512 set_create_maze(struct state *st)
 513 {
 514   int i, h, xx, yy, dir, v, w;
 515 #if DEBUG_SETS
 516   int cont = 0;
 517   char c;
 518 #endif
 519
 520   /* Do almost all the setup. */
 521   init_sets(st);
 522
 523   /* Start running through the hedges. */
 524   for(i = 0; i < 2*st->maze_size_x*st->maze_size_y; i++)
 525     {
 526       h = st->hedges[i];
 527
 528       /* This one is in the logo or outside border. */
 529       if(h==-1)
 530         continue;
 531
 532       dir = h%2?1:2;
 533       xx = (h>>1)%st->maze_size_x;
 534       yy = (h>>1)/st->maze_size_x;
 535
 536       v = xx;
 537       w = yy;
 538       switch(dir)
 539         {
 540         case 1:
 541           v++;
 542           break;
 543         case 2:
 544           w++;
 545           break;
 546         }
 547
 548 #if DEBUG_SETS
 549       show_set(st, xx+yy*st->maze_size_x, st->logo_gc);
 550       show_set(st, v+w*st->maze_size_x, st->tgc);
 551 #endif
 552       if(get_set(st, xx+yy*st->maze_size_x)!=get_set(st, v+w*st->maze_size_x))
 553         {
 554 #if DEBUG_SETS
 555           printf("Join!");
 556 #endif
 557           join_sets(st, xx+yy*st->maze_size_x, v+w*st->maze_size_x);
 558           /* Don't draw the wall. */
 559         }
 560       else
 561         {
 562 #if DEBUG_SETS
 563           printf("Build.");
 564 #endif
 565           /* Don't join the sets. */
 566           build_wall(st, xx, yy, dir);
 567         }
 568 #if DEBUG_SETS
 569       if(!cont)
 570         {
 571           XSync(st->dpy, False);
 572           c = getchar();
 573           if(c=='c')
 574             cont = 1;
 575         }
 576       show_set(xx+yy*st->maze_size_x, st->erase_gc);
 577       show_set(v+w*st->maze_size_x, st->erase_gc);
 578 #endif
 579     }
 580
 581   /* Free some memory. */
 582   exit_sets(st);
 583 }
 584
 585 /* First alternative maze creator: Pick a random, empty corner in the maze.
 586  * Pick a random direction. Draw a wall in that direction, from that corner
 587  * until we hit a wall. Option: Only draw the wall if it's going to be
 588  * shorter than a certain length. Otherwise we get lots of long walls.
 589  */
 590 static void
 591 alt_create_maze(struct state *st)
 592 {
 593   char *corners;
 594   int *c_idx;
 595   int i, j, height, width, open_corners, k, dir, xx, yy;
 596
 597   height = st->maze_size_y+1;
 598   width = st->maze_size_x+1;
 599
 600   /* Allocate and clear some mem. */
 601   corners = (char *)calloc(height*width, 1);
 602   if(!corners)
 603     return;
 604
 605   /* Set up the indexing array. */
 606   c_idx = (int *)malloc(sizeof(int)*height*width);
 607   if(!c_idx)
 608     {
 609       free(corners);
 610       return;
 611     }
 612   for(i = 0; i < height*width; i++)
 613     c_idx[i] = i;
 614   for(i = 0; i < height*width; i++)
 615     {
 616       j = c_idx[i];
 617       k = random()%(height*width);
 618       c_idx[i] = c_idx[k];
 619       c_idx[k] = j;
 620     }
 621
 622   /* Set up some initial walls. */
 623   /* Outside walls. */
 624   for(i = 0; i < width; i++)
 625     {
 626       corners[i] = 1;
 627       corners[i+width*(height-1)] = 1;
 628     }
 629   for(i = 0; i < height; i++)
 630     {
 631       corners[i*width] = 1;
 632       corners[i*width+width-1] = 1;
 633     }
 634   /* Walls around logo. In fact, inside the logo, too. */
 635   /* Also draw the walls. */
 636   if(st->logo_x!=-1)
 637     {
 638       int logow = 1 + st->logo_width / st->grid_width;
 639       int logoh = 1 + st->logo_height / st->grid_height;
 640       int bridge_dir, bridge_c;
 641
 642       if(st->bridge_p && logoh>=3 && logow>=3)
 643         {
 644           bridge_dir = 1+random()%2;
 645           if(bridge_dir==1)
 646             {
 647               bridge_c = st->logo_y+random()%(logoh-2)+1;
 648             }
 649           else
 650             {
 651               bridge_c = st->logo_x+random()%(logow-2)+1;
 652             }
 653         }
 654       else
 655         {
 656           bridge_dir = 0;
 657           bridge_c = -1;
 658         }
 659       for(i = st->logo_x; i <= st->logo_x + logow; i++)
 660         {
 661           for(j = st->logo_y; j <= st->logo_y + logoh; j++)
 662             {
 663               corners[i+width*j] = 1;
 664             }
 665         }
 666       for(xx = st->logo_x; xx < st->logo_x+logow; xx++)
 667         {
 668           if(!(bridge_dir==2 && xx==bridge_c))
 669             {
 670               build_wall(st, xx, st->logo_y, 0);
 671               build_wall(st, xx, st->logo_y+logoh, 0);
 672             }
 673           if(bridge_dir==1)
 674             {
 675               build_wall(st, xx, bridge_c, 0);
 676               build_wall(st, xx, bridge_c, 2);
 677             }
 678         }
 679       for(yy = st->logo_y; yy < st->logo_y+logoh; yy++)
 680         {
 681           if(!(bridge_dir==1 && yy==bridge_c))
 682             {
 683               build_wall(st, st->logo_x, yy, 3);
 684               build_wall(st, st->logo_x+logow, yy, 3);
 685             }
 686           if(bridge_dir==2)
 687             {
 688               build_wall(st, bridge_c, yy, 1);
 689               build_wall(st, bridge_c, yy, 3);
 690             }
 691         }
 692       /* Connect one wall of the logo with an outside wall. */
 693       if(st->bridge_p)
 694         dir = (bridge_dir+1)%4;
 695       else
 696         dir = random()%4;
 697       switch(dir)
 698         {
 699         case 0:
 700           xx = st->logo_x+(random()%(logow+1));
 701           yy = st->logo_y;
 702           break;
 703         case 1:
 704           xx = st->logo_x+logow;
 705           yy = st->logo_y+(random()%(logoh+1));
 706           break;
 707         case 2:
 708           xx = st->logo_x+(random()%(logow+1));
 709           yy = st->logo_y+logoh;
 710           break;
 711         case 3:
 712           xx = st->logo_x;
 713           yy = st->logo_y+(random()%(logoh+1));
 714           break;
 715         }
 716       do
 717         {
 718           corners[xx+width*yy] = 1;
 719           switch(dir)
 720             {
 721             case 0:
 722               build_wall(st, xx-1, yy-1, 1);
 723               yy--;
 724               break;
 725             case 1:
 726               build_wall(st, xx, yy, 0);
 727               xx++;
 728               break;
 729             case 2:
 730               build_wall(st, xx, yy, 3);
 731               yy++;
 732               break;
 733             case 3:
 734               build_wall(st, xx-1, yy-1, 2);
 735               xx--;
 736               break;
 737             }
 738         }
 739       while(!corners[xx+width*yy]);
 740       if(st->bridge_p)
 741         {
 742           dir = (dir+2)%4;
 743           switch(dir)
 744             {
 745             case 0:
 746               xx = st->logo_x+(random()%(logow+1));
 747               yy = st->logo_y;
 748               break;
 749             case 1:
 750               xx = st->logo_x+logow;
 751               yy = st->logo_y+(random()%(logoh+1));
 752               break;
 753             case 2:
 754               xx = st->logo_x+(random()%(logow+1));
 755               yy = st->logo_y+logoh;
 756               break;
 757             case 3:
 758               xx = st->logo_x;
 759               yy = st->logo_y+(random()%(logoh+1));
 760               break;
 761             }
 762           do
 763             {
 764               corners[xx+width*yy] = 1;
 765               switch(dir)
 766                 {
 767                 case 0:
 768                   build_wall(st, xx-1, yy-1, 1);
 769                   yy--;
 770                   break;
 771                 case 1:
 772                   build_wall(st, xx, yy, 0);
 773                   xx++;
 774                   break;
 775                 case 2:
 776                   build_wall(st, xx, yy, 3);
 777                   yy++;
 778                   break;
 779                 case 3:
 780                   build_wall(st, xx-1, yy-1, 2);
 781                   xx--;
 782                   break;
 783                 }
 784             }
 785           while(!corners[xx+width*yy]);
 786         }
 787     }
 788
 789   /* Count open gridpoints. */
 790   open_corners = 0;
 791   for(i = 0; i < width; i++)
 792     for(j = 0; j < height; j++)
 793       if(!corners[i+width*j])
 794         open_corners++;
 795
 796   /* Now do actual maze generation. */
 797   while(open_corners>0)
 798     {
 799       for(i = 0; i < width*height; i++)
 800         {
 801           if(!corners[c_idx[i]])
 802             {
 803               xx = c_idx[i]%width;
 804               yy = c_idx[i]/width;
 805               /* Choose a random direction. */
 806               dir = random()%4;
 807
 808               k = 0;
 809               /* Measure the length of the wall we'd draw. */
 810               while(!corners[xx+width*yy])
 811                 {
 812                   k++;
 813                   switch(dir)
 814                     {
 815                     case 0:
 816                       yy--;
 817                       break;
 818                     case 1:
 819                       xx++;
 820                       break;
 821                     case 2:
 822                       yy++;
 823                       break;
 824                     case 3:
 825                       xx--;
 826                       break;
 827                     }
 828                 }
 829
 830               if(k<=st->max_length)
 831                 {
 832                   xx = c_idx[i]%width;
 833                   yy = c_idx[i]/width;
 834
 835                   /* Draw a wall until we hit something. */
 836                   while(!corners[xx+width*yy])
 837                     {
 838                       open_corners--;
 839                       corners[xx+width*yy] = 1;
 840                       switch(dir)
 841                         {
 842                         case 0:
 843                           build_wall(st, xx-1, yy-1, 1);
 844                           yy--;
 845                           break;
 846                         case 1:
 847                           build_wall(st, xx, yy, 0);
 848                           xx++;
 849                           break;
 850                         case 2:
 851                           build_wall(st, xx, yy, 3);
 852                           yy++;
 853                           break;
 854                         case 3:
 855                           build_wall(st, xx-1, yy-1, 2);
 856                           xx--;
 857                           break;
 858                         }
 859                     }
 860                 }
 861             }
 862         }
 863     }
 864
 865   /* Free some memory we used. */
 866   free(corners);
 867   free(c_idx);
 868 }
 869
 870 /* The original maze creator. Start somewhere. Take a step in a random
 871  * direction. Keep doing this until we hit a wall. Then, backtrack until
 872  * we find a point where we can go in another direction.
 873  */
 874 static void
 875 create_maze (struct state *st)    /* create a maze layout given the initialized maze */
 876 {
 877   register int i, newdoor = 0;
 878   int logow = 1 + st->logo_width / st->grid_width;
 879   int logoh = 1 + st->logo_height / st->grid_height;
 880
 881   /* Maybe we should make a bridge? */
 882   if(st->bridge_p && st->logo_x >= 0 && logow>=3 && logoh>=3)
 883     {
 884       int bridge_dir, bridge_c;
 885
 886       bridge_dir = 1+random()%2;
 887       if(bridge_dir==1)
 888         {
 889           if(logoh>=3)
 890             bridge_c = st->logo_y+random()%(logoh-2)+1;
 891           else
 892             bridge_c = st->logo_y+random()%logoh;
 893         }
 894       else
 895         {
 896           if(logow>=3)
 897             bridge_c = st->logo_x+random()%(logow-2)+1;
 898           else
 899             bridge_c = st->logo_x+random()%logow;
 900         }
 901
 902       if(bridge_dir==1)
 903         {
 904           for(i = st->logo_x; i < st->logo_x+logow; i++)
 905             {
 906               st->maze[i][bridge_c] &= ~DOOR_IN_TOP;
 907             }
 908         }
 909       else
 910         {
 911           for(i = st->logo_y; i < st->logo_y+logoh; i++)
 912             {
 913               st->maze[bridge_c][i] &= ~DOOR_IN_TOP;
 914             }
 915         }
 916     }
 917
 918   do {
 919     st->move_list[st->sqnum].x = st->cur_sq_x;
 920     st->move_list[st->sqnum].y = st->cur_sq_y;
 921     st->move_list[st->sqnum].dir = newdoor;
 922     while ( ( newdoor = choose_door(st) ) == -1 ) { /* pick a door */
 923       if ( backup(st) == -1 ) { /* no more doors ... backup */
 924         return; /* done ... return */
 925       }
 926     }
 927
 928     /* mark the out door */
 929     st->maze[st->cur_sq_x][st->cur_sq_y] |= ( DOOR_OUT_TOP >> newdoor );
 930
 931     switch (newdoor) {
 932     case 0: st->cur_sq_y--;
 933       break;
 934     case 1: st->cur_sq_x++;
 935       break;
 936     case 2: st->cur_sq_y++;
 937       break;
 938     case 3: st->cur_sq_x--;
 939       break;
 940     }
 941     st->sqnum++;
 942
 943     /* mark the in door */
 944     st->maze[st->cur_sq_x][st->cur_sq_y] |= ( DOOR_IN_TOP >> ((newdoor+2)%4) );
 945
 946     /* if end square set path length and save path */
 947     if ( st->maze[st->cur_sq_x][st->cur_sq_y] & END_SQUARE ) {
 948       st->path_length = st->sqnum;
 949       for ( i=0; i<st->path_length; i++) {
 950         st->save_path[i].x = st->move_list[i].x;
 951         st->save_path[i].y = st->move_list[i].y;
 952         st->save_path[i].dir = st->move_list[i].dir;
 953       }
 954     }
 955
 956   } while (1);
 957
 958 }
 959
 960
 961 static int
 962 choose_door (struct state *st)                                   /* pick a new path */
 963 {
 964   int candidates[3];
 965   register int num_candidates;
 966
 967   num_candidates = 0;
 968
 969   /* top wall */
 970   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_TOP )
 971     goto rightwall;
 972   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_TOP )
 973     goto rightwall;
 974   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_TOP )
 975     goto rightwall;
 976   if ( st->maze[st->cur_sq_x][st->cur_sq_y - 1] & DOOR_IN_ANY ) {
 977     st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_TOP;
 978     st->maze[st->cur_sq_x][st->cur_sq_y - 1] |= WALL_BOTTOM;
 979     draw_wall(st, st->cur_sq_x, st->cur_sq_y, 0, st->gc);
 980     goto rightwall;
 981   }
 982   candidates[num_candidates++] = 0;
 983
 984  rightwall:
 985   /* right wall */
 986   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_RIGHT )
 987     goto bottomwall;
 988   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_RIGHT )
 989     goto bottomwall;
 990   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_RIGHT )
 991     goto bottomwall;
 992   if ( st->maze[st->cur_sq_x + 1][st->cur_sq_y] & DOOR_IN_ANY ) {
 993     st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_RIGHT;
 994     st->maze[st->cur_sq_x + 1][st->cur_sq_y] |= WALL_LEFT;
 995     draw_wall(st, st->cur_sq_x, st->cur_sq_y, 1, st->gc);
 996     goto bottomwall;
 997   }
 998   candidates[num_candidates++] = 1;
 999
1000  bottomwall:
1001   /* bottom wall */
1002   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_BOTTOM )
1003     goto leftwall;
1004   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_BOTTOM )
1005     goto leftwall;
1006   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_BOTTOM )
1007     goto leftwall;
1008   if ( st->maze[st->cur_sq_x][st->cur_sq_y + 1] & DOOR_IN_ANY ) {
1009     st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_BOTTOM;
1010     st->maze[st->cur_sq_x][st->cur_sq_y + 1] |= WALL_TOP;
1011     draw_wall(st, st->cur_sq_x, st->cur_sq_y, 2, st->gc);
1012     goto leftwall;
1013   }
1014   candidates[num_candidates++] = 2;
1015
1016  leftwall:
1017   /* left wall */
1018   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_LEFT )
1019     goto donewall;
1020   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_LEFT )
1021     goto donewall;
1022   if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_LEFT )
1023     goto donewall;
1024   if ( st->maze[st->cur_sq_x - 1][st->cur_sq_y] & DOOR_IN_ANY ) {
1025     st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_LEFT;
1026     st->maze[st->cur_sq_x - 1][st->cur_sq_y] |= WALL_RIGHT;
1027     draw_wall(st, st->cur_sq_x, st->cur_sq_y, 3, st->gc);
1028     goto donewall;
1029   }
1030   candidates[num_candidates++] = 3;
1031
1032  donewall:
1033   if (num_candidates == 0)
1034     return ( -1 );
1035   if (num_candidates == 1)
1036     return ( candidates[0] );
1037   return ( candidates[ get_random(num_candidates) ] );
1038
1039 }
1040
1041
1042 static int
1043 backup (struct state *st)                                          /* back up a move */
1044 {
1045   st->sqnum--;
1046   st->cur_sq_x = st->move_list[st->sqnum].x;
1047   st->cur_sq_y = st->move_list[st->sqnum].y;
1048   return ( st->sqnum );
1049 }
1050
1051
1052 static void
1053 draw_maze_border (struct state *st)                         /* draw the maze outline */
1054 {
1055   register int i, j;
1056
1057
1058   for ( i=0; i<st->maze_size_x; i++) {
1059     if ( st->maze[i][0] & WALL_TOP ) {
1060       XDrawLine(st->dpy, st->window, st->gc,
1061                 border_x + st->grid_width * i,
1062                 border_y,
1063                 border_x + st->grid_width * (i+1) - 1,
1064                 border_y);
1065     }
1066     if ((st->maze[i][st->maze_size_y - 1] & WALL_BOTTOM)) {
1067       XDrawLine(st->dpy, st->window, st->gc,
1068                 border_x + st->grid_width * i,
1069                 border_y + st->grid_height * (st->maze_size_y) - 1,
1070                 border_x + st->grid_width * (i+1) - 1,
1071                 border_y + st->grid_height * (st->maze_size_y) - 1);
1072     }
1073   }
1074   for ( j=0; j<st->maze_size_y; j++) {
1075     if ( st->maze[st->maze_size_x - 1][j] & WALL_RIGHT ) {
1076       XDrawLine(st->dpy, st->window, st->gc,
1077                 border_x + st->grid_width * st->maze_size_x - 1,
1078                 border_y + st->grid_height * j,
1079                 border_x + st->grid_width * st->maze_size_x - 1,
1080                 border_y + st->grid_height * (j+1) - 1);
1081     }
1082     if ( st->maze[0][j] & WALL_LEFT ) {
1083       XDrawLine(st->dpy, st->window, st->gc,
1084                 border_x,
1085                 border_y + st->grid_height * j,
1086                 border_x,
1087                 border_y + st->grid_height * (j+1) - 1);
1088     }
1089   }
1090
1091   if (st->logo_x != -1)
1092     {
1093       Window r;
1094       int xx, yy;
1095       unsigned int w, h, bbw, d;
1096
1097       /* round up to grid size */
1098       int ww = ((st->logo_width  / st->grid_width) + 1)  * st->grid_width;
1099       int hh = ((st->logo_height / st->grid_height) + 1) * st->grid_height;
1100       int lx, ly;
1101
1102       XGetGeometry (st->dpy, st->logo_map, &r, &xx, &yy, &w, &h, &bbw, &d);
1103
1104       /* kludge: if the logo "hole" is around the same size as the logo,
1105          don't center it (since the xscreensaver logo image is a little
1106          off center...  But do center it if the hole/gridsize is large. */
1107       if (ww < st->logo_width  + 5) ww = w;
1108       if (hh < st->logo_height + 5) hh = h;
1109
1110
1111       lx = border_x + 3 + st->grid_width  * st->logo_x + ((ww - w) / 2);
1112       ly = border_y + 3 + st->grid_height * st->logo_y + ((hh - h) / 2);
1113
1114       /* Fill the background of the logo box with the "unreachable" color */
1115       XFillRectangle (st->dpy, st->window, st->ugc,
1116                       border_x + 3 + st->grid_width  * st->logo_x,
1117                       border_y + 3 + st->grid_height * st->logo_y,
1118                       ww, hh);
1119
1120       XSetClipOrigin (st->dpy, st->logo_gc, lx, ly);
1121       if (d == 1)
1122         XCopyPlane (st->dpy, st->logo_map, st->window, st->logo_gc,
1123                     0, 0, w, h, lx, ly, 1);
1124       else
1125         XCopyArea (st->dpy, st->logo_map, st->window, st->logo_gc,
1126                    0, 0, w, h, lx, ly);
1127     }
1128   draw_solid_square (st, st->start_x, st->start_y, WALL_TOP >> st->start_dir, st->tgc);
1129   draw_solid_square (st, st->end_x, st->end_y, WALL_TOP >> st->end_dir, st->tgc);
1130 }
1131
1132
1133 static void
1134 draw_wall(struct state *st, int i, int j, int dir, GC with_gc)                /* draw a single wall */
1135 {
1136   switch (dir) {
1137   case 0:
1138     XDrawLine(st->dpy, st->window, with_gc,
1139               border_x + st->grid_width * i,
1140               border_y + st->grid_height * j,
1141               border_x + st->grid_width * (i+1),
1142               border_y + st->grid_height * j);
1143     break;
1144   case 1:
1145     XDrawLine(st->dpy, st->window, with_gc,
1146               border_x + st->grid_width * (i+1),
1147               border_y + st->grid_height * j,
1148               border_x + st->grid_width * (i+1),
1149               border_y + st->grid_height * (j+1));
1150     break;
1151   case 2:
1152     XDrawLine(st->dpy, st->window, with_gc,
1153               border_x + st->grid_width * i,
1154               border_y + st->grid_height * (j+1),
1155               border_x + st->grid_width * (i+1),
1156               border_y + st->grid_height * (j+1));
1157     break;
1158   case 3:
1159     XDrawLine(st->dpy, st->window, with_gc,
1160               border_x + st->grid_width * i,
1161               border_y + st->grid_height * j,
1162               border_x + st->grid_width * i,
1163               border_y + st->grid_height * (j+1));
1164     break;
1165   }
1166
1167   if(st->sync_p) {
1168     /* too slow if we sync on every wall, so only sync about ten times
1169        during the maze-creation process.
1170      */
1171     st->sync_tick--;
1172     if (st->sync_tick <= 0) {
1173       XSync(st->dpy, False);
1174       st->sync_tick = st->maze_size_x * st->maze_size_x / 10;
1175     }
1176   }
1177 }
1178
1179 /* Actually build a wall. */
1180 static void
1181 build_wall(struct state *st, int i, int j, int dir)
1182 {
1183   /* Draw it on the screen. */
1184   draw_wall(st, i, j, dir, st->gc);
1185   /* Put it in the maze. */
1186   switch(dir)
1187     {
1188     case 0:
1189       st->maze[i][j] |= WALL_TOP;
1190       if(j>0)
1191         st->maze[i][j-1] |= WALL_BOTTOM;
1192       break;
1193     case 1:
1194       st->maze[i][j] |= WALL_RIGHT;
1195       if(i<st->maze_size_x-1)
1196         st->maze[i+1][j] |= WALL_LEFT;
1197       break;
1198     case 2:
1199       st->maze[i][j] |= WALL_BOTTOM;
1200       if(j<st->maze_size_y-1)
1201         st->maze[i][j+1] |= WALL_TOP;
1202       break;
1203     case 3:
1204       st->maze[i][j] |= WALL_LEFT;
1205       if(i>0)
1206         st->maze[i-1][j] |= WALL_RIGHT;
1207       break;
1208     }
1209 }
1210
1211 /* Break out a wall. */
1212 #if 0
1213 static void
1214 break_wall(i, j, dir)
1215      int i, j, dir;
1216 {
1217   /* Draw it on the screen. */
1218   draw_wall(i, j, dir, st->erase_gc);
1219   /* Put it in the maze. */
1220   switch(dir)
1221     {
1222     case 0:
1223       st->maze[i][j] &= ~WALL_TOP;
1224       if(j>0)
1225         maze[i][j-1] &= ~WALL_BOTTOM;
1226       break;
1227     case 1:
1228       st->maze[i][j] &= ~WALL_RIGHT;
1229       if(i<st->maze_size_x-1)
1230         maze[i+1][j] &= ~WALL_LEFT;
1231       break;
1232     case 2:
1233       st->maze[i][j] &= ~WALL_BOTTOM;
1234       if(j<st->maze_size_y-1)
1235         maze[i][j+1] &= ~WALL_BOTTOM;
1236       break;
1237     case 3:
1238       st->maze[i][j] &= ~WALL_LEFT;
1239       if(i>0)
1240         maze[i-1][j] &= ~WALL_RIGHT;
1241       break;
1242     }
1243 }
1244 #endif /* 0 */
1245
1246
1247 static void
1248 draw_solid_square(struct state *st,
1249                   int i, int j,          /* draw a solid square in a square */
1250                   int dir, GC with_gc)
1251 {
1252   switch (dir) {
1253   case WALL_TOP:
1254       XFillRectangle(st->dpy, st->window, with_gc,
1255                      border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1256                      border_y - st->bw-(st->bw==0?1:0) + st->grid_height * j,
1257                      st->grid_width - (st->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
1258       break;
1259   case WALL_RIGHT:
1260       XFillRectangle(st->dpy, st->window, with_gc,
1261                      border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1262                      border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1263                      st->grid_width, st->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
1264       break;
1265   case WALL_BOTTOM:
1266       XFillRectangle(st->dpy, st->window, with_gc,
1267                      border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1268                      border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1269                      st->grid_width - (st->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
1270       break;
1271   case WALL_LEFT:
1272       XFillRectangle(st->dpy, st->window, with_gc,
1273                      border_x - st->bw-(st->bw==0?1:0) + st->grid_width * i,
1274                      border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1275                      st->grid_width, st->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
1276       break;
1277   }
1278 }
1279
1280 static int
1281 longdeadend_p(struct state *st, int x1, int y1, int x2, int y2, int endwall)
1282 {
1283     int dx = x2 - x1, dy = y2 - y1;
1284     int sidewalls;
1285
1286     sidewalls = endwall | (endwall >> 2 | endwall << 2);
1287     sidewalls = ~sidewalls & WALL_ANY;
1288
1289     while((st->maze[x2][y2] & WALL_ANY) == sidewalls)
1290     {
1291         if (x2 + dx < 0 || x2 + dx >= st->maze_size_x ||
1292             y2 + dy < 0 || y2 + dy >= st->maze_size_y)
1293           break;
1294         x2 += dx;
1295         y2 += dy;
1296     }
1297
1298     if((st->maze[x2][y2] & WALL_ANY) == (sidewalls | endwall))
1299     {
1300         endwall = (endwall >> 2 | endwall << 2) & WALL_ANY;
1301         while(x1 != x2 || y1 != y2)
1302         {
1303             x1 += dx;
1304             y1 += dy;
1305             draw_solid_square(st, x1, y1, endwall, st->sgc);
1306             st->maze[x1][y1] |= SOLVER_VISIT;
1307         }
1308         return 1;
1309     }
1310     else
1311         return 0;
1312 }
1313
1314 /* Find all dead regions -- areas from which the goal cannot be reached --
1315    and mark them visited. */
1316 static void
1317 find_dead_regions(struct state *st)
1318 {
1319     int xx, yy, flipped;
1320
1321     /* Find all not SOLVER_VISIT squares bordering NOT_DEAD squares
1322        and mark them NOT_DEAD also.  Repeat until no more such squares. */
1323     st->maze[st->start_x][st->start_y] |= NOT_DEAD;
1324
1325     do
1326     {
1327         flipped = 0;
1328         for(xx = 0; xx < st->maze_size_x; xx++)
1329             for(yy = 0; yy < st->maze_size_y; yy++)
1330                 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1331                    && (   (xx && (st->maze[xx-1][yy] & NOT_DEAD))
1332                        || (yy && (st->maze[xx][yy-1] & NOT_DEAD))))
1333                 {
1334                     flipped = 1;
1335                     st->maze[xx][yy] |= NOT_DEAD;
1336                 }
1337         for(xx = st->maze_size_x-1; xx >= 0; xx--)
1338             for(yy = st->maze_size_y-1; yy >= 0; yy--)
1339                 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1340                    && (   (xx != st->maze_size_x-1 && (st->maze[xx+1][yy] & NOT_DEAD))
1341                        || (yy != st->maze_size_y-1 && (st->maze[xx][yy+1] & NOT_DEAD))))
1342                 {
1343                     flipped = 1;
1344                     st->maze[xx][yy] |= NOT_DEAD;
1345                 }
1346     }
1347     while(flipped);
1348
1349     for (yy = 0; yy < st->maze_size_y; yy++)
1350       for (xx = 0; xx < st->maze_size_x; xx++)
1351       {
1352         if (st->maze[xx][yy] & NOT_DEAD)
1353           st->maze[xx][yy] &= ~NOT_DEAD;
1354         else if (!(st->maze[xx][yy] & SOLVER_VISIT))
1355         {
1356           st->maze[xx][yy] |= SOLVER_VISIT;
1357           if((xx < st->logo_x || xx > st->logo_x + st->logo_width / st->grid_width) ||
1358              (yy < st->logo_y || yy > st->logo_y + st->logo_height / st->grid_height))
1359           {
1360             /* if we are completely surrounded by walls, just draw the
1361                inside part */
1362             if ((st->maze[xx][yy] & WALL_ANY) == WALL_ANY)
1363               XFillRectangle(st->dpy, st->window, st->ugc,
1364                              border_x + st->bw + st->grid_width * xx,
1365                              border_y + st->bw + st->grid_height * yy,
1366                              st->grid_width - (st->bw+st->bw), st->grid_height - (st->bw+st->bw));
1367             else
1368             {
1369               if (! (st->maze[xx][yy] & WALL_LEFT))
1370                 draw_solid_square(st, xx, yy, WALL_LEFT, st->ugc);
1371               if (! (st->maze[xx][yy] & WALL_RIGHT))
1372                 draw_solid_square(st, xx, yy, WALL_RIGHT, st->ugc);
1373               if (! (st->maze[xx][yy] & WALL_TOP))
1374                 draw_solid_square(st, xx, yy, WALL_TOP, st->ugc);
1375               if (! (st->maze[xx][yy] & WALL_BOTTOM))
1376                 draw_solid_square(st, xx, yy, WALL_BOTTOM, st->ugc);
1377             }
1378           }
1379         }
1380       }
1381 }
1382
1383 static int
1384 solve_maze (struct state *st)                     /* solve it with graphical feedback */
1385 {
1386   struct solve_state *ss = st->solve_state;
1387   if (!ss)
1388     ss = st->solve_state = (struct solve_state *) calloc (1, sizeof(*ss));
1389
1390   if (!ss->running) {
1391     /* plug up the surrounding wall */
1392     st->maze[st->end_x][st->end_y] |= (WALL_TOP >> st->end_dir);
1393
1394     /* initialize search path */
1395     ss->i = 0;
1396     st->path[ss->i].x = st->end_x;
1397     st->path[ss->i].y = st->end_y;
1398     st->path[ss->i].dir = 0;
1399     st->maze[st->end_x][st->end_y] |= SOLVER_VISIT;
1400
1401     ss->running = 1;
1402   }
1403
1404     /* do it */
1405     /* while (1) */
1406     {
1407         int dir, from, ways;
1408
1409         if ( st->maze[st->path[ss->i].x][st->path[ss->i].y] & START_SQUARE )
1410           {
1411             ss->running = 0;
1412             return 1;
1413           }
1414
1415         if(!st->path[ss->i].dir)
1416         {
1417             ways = 0;
1418             /* First visit this square.  Which adjacent squares are open? */
1419             for(dir = WALL_TOP; dir & WALL_ANY; dir >>= 1)
1420             {
1421                 if(st->maze[st->path[ss->i].x][st->path[ss->i].y] & dir)
1422                     continue;
1423
1424                 ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1425                 ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1426
1427                 if(st->maze[ss->x][ss->y] & SOLVER_VISIT)
1428                   continue;
1429
1430                 from = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1431                 /* don't enter obvious dead ends */
1432                 if(((st->maze[ss->x][ss->y] & WALL_ANY) | from) != WALL_ANY)
1433                 {
1434                     if(!longdeadend_p(st, st->path[ss->i].x, st->path[ss->i].y, ss->x, ss->y, dir))
1435                         ways |= dir;
1436                 }
1437                 else
1438                 {
1439                     draw_solid_square(st, ss->x, ss->y, from, st->sgc);
1440                     st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1441                 }
1442             }
1443         }
1444         else
1445             ways = st->path[ss->i].ways;
1446         /* ways now has a bitmask of open paths. */
1447
1448         if(!ways)
1449             goto backtrack;
1450
1451         if (!st->ignorant_p)
1452           {
1453             ss->x = st->path[ss->i].x - st->start_x;
1454             ss->y = st->path[ss->i].y - st->start_y;
1455             /* choice one */
1456             if(abs(ss->y) <= abs(ss->x))
1457               dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1458             else
1459               dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM;
1460
1461             if(dir & ways)
1462               goto found;
1463
1464             /* choice two */
1465             switch(dir)
1466               {
1467               case WALL_LEFT:
1468               case WALL_RIGHT:
1469                 dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM; break;
1470               case WALL_TOP:
1471               case WALL_BOTTOM:
1472                 dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1473               }
1474
1475             if(dir & ways)
1476               goto found;
1477
1478             /* choice three */
1479
1480             dir = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1481             if(dir & ways)
1482               goto found;
1483
1484             /* choice four */
1485             dir = ways;
1486             if(!dir)
1487               goto backtrack;
1488
1489           found: ;
1490           }
1491         else
1492           {
1493             if(ways&WALL_TOP)
1494               dir = WALL_TOP;
1495             else if(ways&WALL_LEFT)
1496               dir = WALL_LEFT;
1497             else if(ways&WALL_BOTTOM)
1498               dir = WALL_BOTTOM;
1499             else if(ways&WALL_RIGHT)
1500               dir = WALL_RIGHT;
1501             else
1502               goto backtrack;
1503           }
1504         ss->bt = 0;
1505         ways &= ~dir;  /* tried this one */
1506
1507         ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1508         ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1509
1510         /* advance in direction dir */
1511         st->path[ss->i].dir = dir;
1512         st->path[ss->i].ways = ways;
1513         draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, dir, st->tgc);
1514
1515         ss->i++;
1516         st->path[ss->i].dir = 0;
1517         st->path[ss->i].ways = 0;
1518         st->path[ss->i].x = ss->x;
1519         st->path[ss->i].y = ss->y;
1520         st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1521         return 0;
1522         /* continue; */
1523
1524     backtrack:
1525         if(ss->i == 0)
1526         {
1527             printf("Unsolvable maze.\n");
1528             ss->running = 0;
1529             return 1;
1530         }
1531
1532         if(!ss->bt && !st->ignorant_p)
1533             find_dead_regions(st);
1534         ss->bt = 1;
1535         from = st->path[ss->i-1].dir;
1536         from = (from << 2 & WALL_ANY) | (from >> 2 & WALL_ANY);
1537
1538         draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, from, st->cgc);
1539         ss->i--;
1540     }
1541
1542     return 0;
1543 }
1544
1545 #if 0
1546 static void
1547 enter_square (int n)                      /* move into a neighboring square */
1548 {
1549   draw_solid_square( (int)st->path[n].x, (int)st->path[n].y,
1550                     (int)st->path[n].dir, st->tgc);
1551
1552   st->path[n+1].dir = -1;
1553   switch (st->path[n].dir) {
1554   case 0: st->path[n+1].x = st->path[n].x;
1555     st->path[n+1].y = st->path[n].y - 1;
1556     break;
1557   case 1: st->path[n+1].x = st->path[n].x + 1;
1558     st->path[n+1].y = st->path[n].y;
1559     break;
1560   case 2: st->path[n+1].x = st->path[n].x;
1561     st->path[n+1].y = st->path[n].y + 1;
1562     break;
1563   case 3: st->path[n+1].x = st->path[n].x - 1;
1564     st->path[n+1].y = st->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 static const char *maze_defaults[] = {
1578   ".background:    black",
1579   ".foreground:    white",
1580   "*fpsSolid:      true",
1581   "*gridSize:      0",
1582   "*generator:     -1",
1583   "*maxLength:     5",
1584   "*bridge:        False",
1585   "*ignorant:      False",
1586
1587   "*solveDelay:    10000",
1588   "*preDelay:      2000000",
1589   "*postDelay:     4000000",
1590
1591   "*liveColor:     #00FF00",
1592   "*deadColor:     #880000",
1593   "*skipColor:     #8B5A00",
1594   "*surroundColor: #220055",
1595
1596   0
1597 };
1598
1599 static XrmOptionDescRec maze_options[] = {
1600   { "-ignorant",        ".ignorant",    XrmoptionNoArg, "True" },
1601   { "-no-ignorant",     ".ignorant",    XrmoptionNoArg, "False" },
1602   { "-grid-size",       ".gridSize",    XrmoptionSepArg, 0 },
1603   { "-solve-delay",     ".solveDelay",  XrmoptionSepArg, 0 },
1604   { "-pre-delay",       ".preDelay",    XrmoptionSepArg, 0 },
1605   { "-post-delay",      ".postDelay",   XrmoptionSepArg, 0 },
1606   { "-bg-color",        ".background",  XrmoptionSepArg, 0 },
1607   { "-fg-color",        ".foreground",  XrmoptionSepArg, 0 },
1608   { "-live-color",      ".liveColor",   XrmoptionSepArg, 0 },
1609   { "-dead-color",      ".deadColor",   XrmoptionSepArg, 0 },
1610   { "-skip-color",      ".skipColor",   XrmoptionSepArg, 0 },
1611   { "-surround-color",  ".surroundColor",XrmoptionSepArg, 0 },
1612   { "-generator",       ".generator",   XrmoptionSepArg, 0 },
1613   { "-max-length",      ".maxLength",   XrmoptionSepArg, 0 },
1614   { "-bridge",          ".bridge",      XrmoptionNoArg, "True" },
1615   { "-no-bridge",       ".bridge",      XrmoptionNoArg, "False" },
1616   { 0, 0, 0, 0 }
1617 };
1618
1619 static int generator = 0;
1620
1621 static void *
1622 maze_init (Display *dpy_arg, Window window_arg)
1623 {
1624   struct state *st = (struct state *) calloc (1, sizeof(*st));
1625 # ifdef DO_STIPPLE
1626   Pixmap gray;
1627 # endif
1628   int size;
1629   XWindowAttributes xgwa;
1630   unsigned long bg, fg, pfg, pbg, sfg, ufg;
1631
1632   st->dpy = dpy_arg;
1633   st->window = window_arg;
1634
1635   st->stop = 0;
1636   st->state = 1;
1637   st->restart = 1;
1638
1639   st->ifrandom = 0;
1640   st->ifinit = 1;
1641
1642   size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1643   st->solve_delay = get_integer_resource (st->dpy, "solveDelay", "Integer");
1644   st->pre_solve_delay = get_integer_resource (st->dpy, "preDelay", "Integer");
1645   st->post_solve_delay = get_integer_resource (st->dpy, "postDelay", "Integer");
1646   generator = get_integer_resource(st->dpy, "generator", "Integer");
1647   st->max_length = get_integer_resource(st->dpy, "maxLength", "Integer");
1648   st->bridge_p = get_boolean_resource(st->dpy, "bridge", "Boolean");
1649   st->ignorant_p = get_boolean_resource(st->dpy, "ignorant", "Boolean");
1650
1651   if (!size) st->ifrandom = 1;
1652
1653   if (size < 2) size = 7 + (random () % 30);
1654   st->grid_width = st->grid_height = size;
1655   st->bw = (size > 6 ? 3 : (size-1)/2);
1656
1657   XGetWindowAttributes (st->dpy, st->window, &xgwa);
1658
1659   st->x = 0;
1660   st->y = 0;
1661
1662   set_maze_sizes (st, xgwa.width, xgwa.height);
1663
1664   st->gc  = XCreateGC(st->dpy, st->window, 0, 0);
1665   st->cgc = XCreateGC(st->dpy, st->window, 0, 0);
1666   st->tgc = XCreateGC(st->dpy, st->window, 0, 0);
1667   st->sgc = XCreateGC(st->dpy, st->window, 0, 0);
1668   st->ugc = XCreateGC(st->dpy, st->window, 0, 0);
1669   st->logo_gc = XCreateGC(st->dpy, st->window, 0, 0);
1670   st->erase_gc = XCreateGC(st->dpy, st->window, 0, 0);
1671
1672 # ifdef DO_STIPPLE
1673   gray = XCreateBitmapFromData (st->dpy,st->window,gray1_bits,gray1_width,gray1_height);
1674 # endif
1675
1676   bg  = get_pixel_resource (st->dpy, xgwa.colormap, "background","Background");
1677   fg  = get_pixel_resource (st->dpy, xgwa.colormap, "foreground","Foreground");
1678   pfg = get_pixel_resource (st->dpy, xgwa.colormap, "liveColor", "Foreground");
1679   pbg = get_pixel_resource (st->dpy, xgwa.colormap, "deadColor", "Foreground");
1680   sfg = get_pixel_resource (st->dpy, xgwa.colormap, "skipColor", "Foreground");
1681   ufg = get_pixel_resource (st->dpy, xgwa.colormap, "surroundColor", "Foreground");
1682
1683   XSetForeground (st->dpy, st->gc, fg);
1684   XSetBackground (st->dpy, st->gc, bg);
1685   XSetForeground (st->dpy, st->cgc, pbg);
1686   XSetBackground (st->dpy, st->cgc, bg);
1687   XSetForeground (st->dpy, st->tgc, pfg);
1688   XSetBackground (st->dpy, st->tgc, bg);
1689   XSetForeground (st->dpy, st->sgc, sfg);
1690   XSetBackground (st->dpy, st->sgc, bg);
1691   XSetForeground (st->dpy, st->ugc, ufg);
1692   XSetBackground (st->dpy, st->ugc, bg);
1693   XSetForeground (st->dpy, st->logo_gc, fg);
1694   XSetBackground (st->dpy, st->logo_gc, bg);
1695   XSetForeground (st->dpy, st->erase_gc, bg);
1696   XSetBackground (st->dpy, st->erase_gc, bg);
1697
1698 # ifdef DO_STIPPLE
1699   XSetStipple (st->dpy, st->cgc, gray);
1700   XSetFillStyle (st->dpy, st->cgc, FillOpaqueStippled);
1701   XSetStipple (st->dpy, st->sgc, gray);
1702   XSetFillStyle (st->dpy, st->sgc, FillOpaqueStippled);
1703   XSetStipple (st->dpy, st->ugc, gray);
1704   XSetFillStyle (st->dpy, st->ugc, FillOpaqueStippled);
1705 # endif
1706
1707   {
1708     Window r;
1709     int x, y;
1710     unsigned int w, h, bbw, d;
1711     unsigned long *pixels;
1712     int npixels;
1713     Pixmap logo_mask = 0;
1714     st->logo_map = xscreensaver_logo (xgwa.screen, xgwa.visual, st->window,
1715                                       xgwa.colormap, bg,
1716                                       &pixels, &npixels, &logo_mask,
1717                                       xgwa.width > 800);
1718     if (logo_mask) {
1719       XSetClipMask (st->dpy, st->logo_gc, logo_mask);
1720       XFreePixmap (st->dpy, logo_mask);
1721     }
1722     if (pixels) free (pixels);
1723     XGetGeometry (st->dpy, st->logo_map, &r, &x, &y, &w, &h, &bbw, &d);
1724     st->logo_width = w;
1725     st->logo_height = h;
1726   }
1727
1728
1729   st->restart = 0;
1730   st->sync_p = 1;
1731
1732   return st;
1733 }
1734
1735
1736 static void
1737 maze_reshape (Display *dpy, Window window, void *closure,
1738                  unsigned int w, unsigned int h)
1739 {
1740   struct state *st = (struct state *) closure;
1741   st->restart = 1;
1742 }
1743
1744
1745 static unsigned long
1746 maze_draw (Display *dpy, Window window, void *closure)
1747 {
1748   struct state *st = (struct state *) closure;
1749   int this_delay = st->solve_delay;
1750
1751   if (st->eraser || st->erase_window)
1752     {
1753       st->erase_window = 0;
1754       st->eraser = erase_window (st->dpy, st->window, st->eraser);
1755       if (st->eraser)
1756         this_delay = 10000;
1757       else {
1758         this_delay = 1000000;
1759         if (this_delay > st->pre_solve_delay)
1760           this_delay = st->pre_solve_delay;
1761       }
1762       goto END;
1763     }
1764
1765     if (st->restart || st->stop) goto pop;
1766     switch (st->state) {
1767     case 1:
1768       initialize_maze(st);
1769       if (st->ifrandom && st->ifinit)
1770        {
1771          int size;
1772          size = 7 + (random () % 30);
1773          st->grid_width = st->grid_height = size;
1774          st->bw = (size > 6 ? 3 : (size-1)/2);
1775          st->ifinit = 0;
1776          st->restart = 1;
1777        }
1778       break;
1779     case 2:
1780       XClearWindow(st->dpy, st->window);
1781       draw_maze_border(st);
1782       break;
1783     case 3:
1784       st->this_gen = generator;
1785       if(st->this_gen<0 || st->this_gen>2)
1786         st->this_gen = random()%3;
1787
1788       switch(st->this_gen)
1789         {
1790         case 0:
1791           create_maze(st);
1792           break;
1793         case 1:
1794           alt_create_maze(st);
1795           break;
1796         case 2:
1797           set_create_maze(st);
1798           break;
1799         }
1800       break;
1801     case 4:
1802       this_delay = st->pre_solve_delay;
1803       break;
1804     case 5:
1805       if (! solve_maze(st))
1806         --st->state;  /* stay in state 5 */
1807       break;
1808     case 6:
1809       st->erase_window = 1;
1810       this_delay = st->post_solve_delay;
1811       st->state = 0 ;
1812       st->ifinit = 1;
1813       break;
1814     default:
1815       abort ();
1816     }
1817     ++st->state;
1818   pop:
1819     if (st->restart)
1820       {
1821         XWindowAttributes xgwa;
1822         int size;
1823
1824         st->restart = 0;
1825         st->stop = 0;
1826         st->state = 1;
1827
1828         st->sync_p = ((random() % 4) != 0);
1829
1830         size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1831         if (size < 2) size = 7 + (random () % 30);
1832         st->grid_width = st->grid_height = size;
1833         st->bw = (size > 6 ? 3 : (size-1)/2);
1834
1835         XGetWindowAttributes (st->dpy, st->window, &xgwa);
1836         set_maze_sizes (st, xgwa.width, xgwa.height);
1837       }
1838
1839  END:
1840     return this_delay;
1841 }
1842
1843
1844 static Bool
1845 maze_event (Display *dpy, Window window, void *closure, XEvent *event)
1846 {
1847   struct state *st = (struct state *) closure;
1848   switch (event->type)
1849     {
1850     case ButtonPress:
1851       switch (event->xbutton.button)
1852         {
1853         case 2:
1854           st->stop = !st->stop ;
1855           if (st->state == 5) st->state = 4 ;
1856           else {
1857             st->restart = 1;
1858             st->stop = 0;
1859           }
1860           return True;
1861
1862         default:
1863           st->restart = 1 ;
1864           st->stop = 0 ;
1865           return True;
1866         }
1867       break;
1868
1869     case Expose:
1870       st->restart = 1;
1871       break;
1872
1873     default:
1874       break;
1875     }
1876   return False;
1877 }
1878
1879
1880 static void
1881 maze_free (Display *dpy, Window window, void *closure)
1882 {
1883   struct state *st = (struct state *) closure;
1884   free (st);
1885 }
1886
1887 XSCREENSAVER_MODULE ("Maze", maze)