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

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