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