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