1 /******************************************************************************
4 * modified: [ 1-04-00 ] Johannes Keukelaar <johannes@nada.kth.se>
5 * Added -ignorant option (not the default) to remove knowlege
6 * of the direction in which the exit lies.
8 * modified: [ 6-28-98 ] Zack Weinberg <zack@rabi.phys.columbia.edu>
10 * Made the maze-solver somewhat more intelligent. There are
11 * three optimizations:
13 * - Straight-line lookahead: the solver does not enter dead-end
14 * corridors. This is a win with all maze generators.
16 * - First order direction choice: the solver knows where the
17 * exit is in relation to itself, and will try paths leading in
18 * that direction first. This is a major win on maze generator 1
19 * which tends to offer direct routes to the exit.
21 * - Dead region elimination: the solver already has a map of
22 * all squares visited. Whenever it starts to backtrack, it
23 * consults this map and marks off all squares that cannot be
24 * reached from the exit without crossing a square already
25 * visited. Those squares can never contribute to the path to
26 * the exit, so it doesn't bother checking them. This helps a
27 * lot with maze generator 2 and somewhat less with generator 1.
29 * Further improvements would require knowledge of the wall map
30 * as well as the position of the exit and the squares visited.
31 * I would consider that to be cheating. Generator 0 makes
32 * mazes which are remarkably difficult to solve mechanically --
33 * even with these optimizations the solver generally must visit
34 * at least two-thirds of the squares. This is partially
35 * because generator 0's mazes have longer paths to the exit.
37 * modified: [ 4-10-97 ] Johannes Keukelaar <johannes@nada.kth.se>
38 * Added multiple maze creators. Robustified solver.
39 * Added bridge option.
40 * modified: [ 8-11-95 ] Ed James <james@mml.mmc.com>
41 * added fill of dead-end box to solve_maze while loop.
42 * modified: [ 3-7-93 ] Jamie Zawinski <jwz@jwz.org>
43 * added the XRoger logo, cleaned up resources, made
44 * grid size a parameter.
45 * modified: [ 3-3-93 ] Jim Randell <jmr@mddjmr.fc.hp.com>
46 * Added the colour stuff and integrated it with jwz's
47 * screenhack stuff. There's still some work that could
48 * be done on this, particularly allowing a resource to
49 * specify how big the squares are.
50 * modified: [ 10-4-88 ] Richard Hess ...!uunet!cimshop!rhess
51 * [ Revised primary execution loop within main()...
52 * [ Extended X event handler, check_events()...
53 * modified: [ 1-29-88 ] Dave Lemke lemke@sun.com
55 * [ Note the word "hacked" -- this is extremely ugly, but at
56 * [ least it does the job. NOT a good programming example
58 * original: [ 6/21/85 ] Martin Weiss Sun Microsystems [ SunView ]
60 ******************************************************************************
61 Copyright 1988 by Sun Microsystems, Inc. Mountain View, CA.
65 Permission to use, copy, modify, and distribute this software and its
66 documentation for any purpose and without fee is hereby granted,
67 provided that the above copyright notice appear in all copies and that
68 both that copyright notice and this permission notice appear in
69 supporting documentation, and that the names of Sun or MIT not be
70 used in advertising or publicity pertaining to distribution of the
71 software without specific prior written permission. Sun and M.I.T.
72 make no representations about the suitability of this software for
73 any purpose. It is provided "as is" without any express or implied warranty.
75 SUN DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
76 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
77 PURPOSE. IN NO EVENT SHALL SUN BE LIABLE FOR ANY SPECIAL, INDIRECT
78 OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
79 OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
80 OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE
81 OR PERFORMANCE OF THIS SOFTWARE.
82 *****************************************************************************/
84 #include "screenhack.h"
87 #define XSCREENSAVER_LOGO
89 static int solve_delay, pre_solve_delay, post_solve_delay;
93 #include <X11/Xutil.h>
95 /* #include <X11/bitmaps/gray1> */
97 #define gray1_height 2
98 static char gray1_bits[] = { 0x01, 0x02 };
101 #define MAX_MAZE_SIZE_X 1000
102 #define MAX_MAZE_SIZE_Y 1000
104 #define MOVE_LIST_SIZE (MAX_MAZE_SIZE_X * MAX_MAZE_SIZE_Y)
106 #define NOT_DEAD 0x8000
107 #define SOLVER_VISIT 0x4000
108 #define START_SQUARE 0x2000
109 #define END_SQUARE 0x1000
112 #define WALL_RIGHT 0x4
113 #define WALL_BOTTOM 0x2
114 #define WALL_LEFT 0x1
117 #define DOOR_IN_TOP 0x800
118 #define DOOR_IN_RIGHT 0x400
119 #define DOOR_IN_BOTTOM 0x200
120 #define DOOR_IN_LEFT 0x100
121 #define DOOR_IN_ANY 0xF00
123 #define DOOR_OUT_TOP 0x80
124 #define DOOR_OUT_RIGHT 0x40
125 #define DOOR_OUT_BOTTOM 0x20
126 #define DOOR_OUT_LEFT 0x10
132 #define get_random(x) (random() % (x))
135 static int logo_x, logo_y;
137 #ifdef XSCREENSAVER_LOGO
138 # define logo_width 54
139 # define logo_height 54
141 # include <X11/bitmaps/xlogo64>
142 # define logo_width xlogo64_width
143 # define logo_height xlogo64_height
144 # define logo_bits xlogo64_bits
147 static unsigned short maze[MAX_MAZE_SIZE_X][MAX_MAZE_SIZE_Y];
152 unsigned char dir, ways;
153 } move_list[MOVE_LIST_SIZE], save_path[MOVE_LIST_SIZE], path[MOVE_LIST_SIZE];
155 static int maze_size_x, maze_size_y;
156 static int sqnum, cur_sq_x, cur_sq_y, path_length;
157 static int start_x, start_y, start_dir, end_x, end_y, end_dir;
158 static int grid_width, grid_height;
163 static GC gc, cgc, tgc, sgc, ugc, logo_gc, erase_gc;
164 static Pixmap logo_map;
166 static int x = 0, y = 0, restart = 0, stop = 1, state = 1, max_length;
167 static int sync_p, bridge_p, ignorant_p;
170 check_events (void) /* X event handler [ rhess ] */
179 switch (e.xbutton.button) {
185 if (state == 5) state = 4 ;
198 case ConfigureNotify:
203 XClearWindow (dpy, win);
210 screenhack_handle_event(dpy, &e);
220 set_maze_sizes (int width, int height)
222 maze_size_x = width / grid_width;
223 maze_size_y = height / grid_height;
228 initialize_maze (void) /* draw the surrounding wall and start/end squares */
230 register int i, j, wall;
231 int logow = 1 + logo_width / grid_width;
232 int logoh = 1 + logo_height / grid_height;
234 /* initialize all squares */
235 for ( i=0; i<maze_size_x; i++) {
236 for ( j=0; j<maze_size_y; j++) {
242 for ( i=0; i<maze_size_x; i++ ) {
243 maze[i][0] |= WALL_TOP;
247 for ( j=0; j<maze_size_y; j++ ) {
248 maze[maze_size_x-1][j] |= WALL_RIGHT;
252 for ( i=0; i<maze_size_x; i++ ) {
253 maze[i][maze_size_y-1] |= WALL_BOTTOM;
257 for ( j=0; j<maze_size_y; j++ ) {
258 maze[0][j] |= WALL_LEFT;
261 /* set start square */
262 wall = get_random(4);
265 i = get_random(maze_size_x);
270 j = get_random(maze_size_y);
273 i = get_random(maze_size_x);
278 j = get_random(maze_size_y);
281 maze[i][j] |= START_SQUARE;
282 maze[i][j] |= ( DOOR_IN_TOP >> wall );
283 maze[i][j] &= ~( WALL_TOP >> wall );
295 i = get_random(maze_size_x);
300 j = get_random(maze_size_y);
303 i = get_random(maze_size_x);
308 j = get_random(maze_size_y);
311 maze[i][j] |= END_SQUARE;
312 maze[i][j] |= ( DOOR_OUT_TOP >> wall );
313 maze[i][j] &= ~( WALL_TOP >> wall );
319 if ((maze_size_x-logow >= 6) && (maze_size_y-logoh >= 6))
321 /* not closer than 3 grid units from a wall */
322 logo_x = get_random (maze_size_x - logow - 5) + 3;
323 logo_y = get_random (maze_size_y - logoh - 5) + 3;
324 for (i=0; i<logow; i++)
325 for (j=0; j<logoh; j++)
326 maze[logo_x + i][logo_y + j] |= DOOR_IN_TOP;
329 logo_y = logo_x = -1;
332 static int choose_door (void);
333 static int backup (void);
334 static void draw_wall (int, int, int, GC);
335 static void draw_solid_square (int, int, int, GC);
336 /*static void enter_square (int);*/
337 static void build_wall (int, int, int);
338 /*static void break_wall (int, int, int);*/
340 static void join_sets(int, int);
342 /* For set_create_maze. */
343 /* The sets that our squares are in. */
344 static int *sets = 0;
345 /* The `list' of hedges. */
346 static int *hedges = 0;
350 /* Initialise the sets. */
358 sets = (int *)malloc(maze_size_x*maze_size_y*sizeof(int));
361 for(i = 0; i < maze_size_x*maze_size_y; i++)
368 hedges = (int *)malloc(maze_size_x*maze_size_y*2*sizeof(int));
371 for(i = 0; i < maze_size_x*maze_size_y*2; i++)
375 /* Mask out outside walls. */
376 for(i = 0; i < maze_size_y; i++)
378 hedges[2*((maze_size_x)*i+maze_size_x-1)+1] = -1;
380 for(i = 0; i < maze_size_x; i++)
382 hedges[2*((maze_size_y-1)*maze_size_x+i)] = -1;
384 /* Mask out a possible logo. */
387 int logow = 1 + logo_width / grid_width;
388 int logoh = 1 + logo_height / grid_height;
389 int bridge_dir, bridge_c;
391 if(bridge_p && logoh>=3 && logow>=3)
393 bridge_dir = 1+random()%2;
396 bridge_c = logo_y+random()%(logoh-2)+1;
400 bridge_c = logo_x+random()%(logow-2)+1;
409 for(x = logo_x; x < logo_x+logow; x++)
410 for(y = logo_y; y < logo_y+logoh; y++)
412 /* I should check for the bridge here, except that I join the
413 * bridge together below.
415 hedges[2*(x+maze_size_x*y)+1] = -1;
416 hedges[2*(x+maze_size_x*y)] = -1;
418 for(x = logo_x; x < logo_x+logow; x++)
420 if(!(bridge_dir==2 && x==bridge_c))
422 build_wall(x, logo_y, 0);
423 build_wall(x, logo_y+logoh, 0);
425 hedges[2*(x+maze_size_x*(logo_y-1))] = -1;
428 build_wall(x, bridge_c, 0);
429 build_wall(x, bridge_c, 2);
432 for(y = logo_y; y < logo_y+logoh; y++)
434 if(!(bridge_dir==1 && y==bridge_c))
436 build_wall(logo_x, y, 3);
437 build_wall(logo_x+logow, y, 3);
439 hedges[2*(logo_x-1+maze_size_x*y)+1] = -1;
442 build_wall(bridge_c, y, 1);
443 build_wall(bridge_c, y, 3);
446 /* Join the whole bridge together. */
453 for(i = logo_x; i < logo_x+logow+1; i++)
454 join_sets(x+y*maze_size_x, i+y*maze_size_x);
460 for(i = logo_y; i < logo_y+logoh+1; i++)
461 join_sets(x+y*maze_size_x, x+i*maze_size_x);
466 for(i = 0; i < maze_size_x*maze_size_y*2; i++)
469 r = random()%(maze_size_x*maze_size_y*2);
470 hedges[i] = hedges[r];
475 /* Get the representative of a set. */
485 s = get_set(sets[num]);
491 /* Join two sets together. */
493 join_sets(num1, num2)
507 /* Exitialise the sets. */
520 /* Temporary hack. */
522 show_set(int num, GC gc)
528 for(x = 0; x < maze_size_x; x++)
529 for(y = 0; y < maze_size_y; y++)
531 if(get_set(x+y*maze_size_x)==set)
533 XFillRectangle(dpy, win, gc, border_x + bw + grid_width * x,
534 border_y + bw + grid_height * y,
535 grid_width-2*bw , grid_height-2*bw);
541 /* Second alternative maze creator: Put each square in the maze in a
542 * separate set. Also, make a list of all the hedges. Randomize that list.
543 * Walk through the list. If, for a certain hedge, the two squares on both
544 * sides of it are in different sets, union the sets and remove the hedge.
545 * Continue until all hedges have been processed or only one set remains.
548 set_create_maze(void)
550 int i, h, x, y, dir, v, w;
556 /* Do almost all the setup. */
559 /* Start running through the hedges. */
560 for(i = 0; i < 2*maze_size_x*maze_size_y; i++)
564 /* This one is in the logo or outside border. */
569 x = (h>>1)%maze_size_x;
570 y = (h>>1)/maze_size_x;
585 show_set(x+y*maze_size_x, logo_gc);
586 show_set(v+w*maze_size_x, tgc);
588 if(get_set(x+y*maze_size_x)!=get_set(v+w*maze_size_x))
593 join_sets(x+y*maze_size_x, v+w*maze_size_x);
594 /* Don't draw the wall. */
601 /* Don't join the sets. */
602 build_wall(x, y, dir);
612 show_set(x+y*maze_size_x, erase_gc);
613 show_set(v+w*maze_size_x, erase_gc);
617 /* Free some memory. */
621 /* First alternative maze creator: Pick a random, empty corner in the maze.
622 * Pick a random direction. Draw a wall in that direction, from that corner
623 * until we hit a wall. Option: Only draw the wall if it's going to be
624 * shorter than a certain length. Otherwise we get lots of long walls.
627 alt_create_maze(void)
631 int i, j, height, width, open_corners, k, dir, x, y;
633 height = maze_size_y+1;
634 width = maze_size_x+1;
636 /* Allocate and clear some mem. */
637 corners = (char *)calloc(height*width, 1);
641 /* Set up the indexing array. */
642 c_idx = (int *)malloc(sizeof(int)*height*width);
648 for(i = 0; i < height*width; i++)
650 for(i = 0; i < height*width; i++)
653 k = random()%(height*width);
658 /* Set up some initial walls. */
660 for(i = 0; i < width; i++)
663 corners[i+width*(height-1)] = 1;
665 for(i = 0; i < height; i++)
667 corners[i*width] = 1;
668 corners[i*width+width-1] = 1;
670 /* Walls around logo. In fact, inside the logo, too. */
671 /* Also draw the walls. */
674 int logow = 1 + logo_width / grid_width;
675 int logoh = 1 + logo_height / grid_height;
676 int bridge_dir, bridge_c;
678 if(bridge_p && logoh>=3 && logow>=3)
680 bridge_dir = 1+random()%2;
683 bridge_c = logo_y+random()%(logoh-2)+1;
687 bridge_c = logo_x+random()%(logow-2)+1;
695 for(i = logo_x; i <= logo_x + logow; i++)
697 for(j = logo_y; j <= logo_y + logoh; j++)
699 corners[i+width*j] = 1;
702 for(x = logo_x; x < logo_x+logow; x++)
704 if(!(bridge_dir==2 && x==bridge_c))
706 build_wall(x, logo_y, 0);
707 build_wall(x, logo_y+logoh, 0);
711 build_wall(x, bridge_c, 0);
712 build_wall(x, bridge_c, 2);
715 for(y = logo_y; y < logo_y+logoh; y++)
717 if(!(bridge_dir==1 && y==bridge_c))
719 build_wall(logo_x, y, 3);
720 build_wall(logo_x+logow, y, 3);
724 build_wall(bridge_c, y, 1);
725 build_wall(bridge_c, y, 3);
728 /* Connect one wall of the logo with an outside wall. */
730 dir = (bridge_dir+1)%4;
736 x = logo_x+(random()%(logow+1));
741 y = logo_y+(random()%(logoh+1));
744 x = logo_x+(random()%(logow+1));
749 y = logo_y+(random()%(logoh+1));
754 corners[x+width*y] = 1;
758 build_wall(x-1, y-1, 1);
770 build_wall(x-1, y-1, 2);
775 while(!corners[x+width*y]);
782 x = logo_x+(random()%(logow+1));
787 y = logo_y+(random()%(logoh+1));
790 x = logo_x+(random()%(logow+1));
795 y = logo_y+(random()%(logoh+1));
800 corners[x+width*y] = 1;
804 build_wall(x-1, y-1, 1);
816 build_wall(x-1, y-1, 2);
821 while(!corners[x+width*y]);
825 /* Count open gridpoints. */
827 for(i = 0; i < width; i++)
828 for(j = 0; j < height; j++)
829 if(!corners[i+width*j])
832 /* Now do actual maze generation. */
833 while(open_corners>0)
835 for(i = 0; i < width*height; i++)
837 if(!corners[c_idx[i]])
841 /* Choose a random direction. */
845 /* Measure the length of the wall we'd draw. */
846 while(!corners[x+width*y])
871 /* Draw a wall until we hit something. */
872 while(!corners[x+width*y])
875 corners[x+width*y] = 1;
879 build_wall(x-1, y-1, 1);
891 build_wall(x-1, y-1, 2);
901 /* Free some memory we used. */
906 /* The original maze creator. Start somewhere. Take a step in a random
907 * direction. Keep doing this until we hit a wall. Then, backtrack until
908 * we find a point where we can go in another direction.
911 create_maze (void) /* create a maze layout given the initialized maze */
913 register int i, newdoor = 0;
914 int logow = 1 + logo_width / grid_width;
915 int logoh = 1 + logo_height / grid_height;
917 /* Maybe we should make a bridge? */
918 if(bridge_p && logo_x>=0 && logow>=3 && logoh>=3)
920 int bridge_dir, bridge_c;
922 bridge_dir = 1+random()%2;
926 bridge_c = logo_y+random()%(logoh-2)+1;
928 bridge_c = logo_y+random()%logoh;
933 bridge_c = logo_x+random()%(logow-2)+1;
935 bridge_c = logo_x+random()%logow;
940 for(i = logo_x; i < logo_x+logow; i++)
942 maze[i][bridge_c] &= ~DOOR_IN_TOP;
947 for(i = logo_y; i < logo_y+logoh; i++)
949 maze[bridge_c][i] &= ~DOOR_IN_TOP;
955 move_list[sqnum].x = cur_sq_x;
956 move_list[sqnum].y = cur_sq_y;
957 move_list[sqnum].dir = newdoor;
958 while ( ( newdoor = choose_door() ) == -1 ) { /* pick a door */
959 if ( backup() == -1 ) { /* no more doors ... backup */
960 return; /* done ... return */
964 /* mark the out door */
965 maze[cur_sq_x][cur_sq_y] |= ( DOOR_OUT_TOP >> newdoor );
979 /* mark the in door */
980 maze[cur_sq_x][cur_sq_y] |= ( DOOR_IN_TOP >> ((newdoor+2)%4) );
982 /* if end square set path length and save path */
983 if ( maze[cur_sq_x][cur_sq_y] & END_SQUARE ) {
985 for ( i=0; i<path_length; i++) {
986 save_path[i].x = move_list[i].x;
987 save_path[i].y = move_list[i].y;
988 save_path[i].dir = move_list[i].dir;
998 choose_door (void) /* pick a new path */
1001 register int num_candidates;
1006 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_TOP )
1008 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_TOP )
1010 if ( maze[cur_sq_x][cur_sq_y] & WALL_TOP )
1012 if ( maze[cur_sq_x][cur_sq_y - 1] & DOOR_IN_ANY ) {
1013 maze[cur_sq_x][cur_sq_y] |= WALL_TOP;
1014 maze[cur_sq_x][cur_sq_y - 1] |= WALL_BOTTOM;
1015 draw_wall(cur_sq_x, cur_sq_y, 0, gc);
1018 candidates[num_candidates++] = 0;
1022 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_RIGHT )
1024 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_RIGHT )
1026 if ( maze[cur_sq_x][cur_sq_y] & WALL_RIGHT )
1028 if ( maze[cur_sq_x + 1][cur_sq_y] & DOOR_IN_ANY ) {
1029 maze[cur_sq_x][cur_sq_y] |= WALL_RIGHT;
1030 maze[cur_sq_x + 1][cur_sq_y] |= WALL_LEFT;
1031 draw_wall(cur_sq_x, cur_sq_y, 1, gc);
1034 candidates[num_candidates++] = 1;
1038 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_BOTTOM )
1040 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_BOTTOM )
1042 if ( maze[cur_sq_x][cur_sq_y] & WALL_BOTTOM )
1044 if ( maze[cur_sq_x][cur_sq_y + 1] & DOOR_IN_ANY ) {
1045 maze[cur_sq_x][cur_sq_y] |= WALL_BOTTOM;
1046 maze[cur_sq_x][cur_sq_y + 1] |= WALL_TOP;
1047 draw_wall(cur_sq_x, cur_sq_y, 2, gc);
1050 candidates[num_candidates++] = 2;
1054 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_LEFT )
1056 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_LEFT )
1058 if ( maze[cur_sq_x][cur_sq_y] & WALL_LEFT )
1060 if ( maze[cur_sq_x - 1][cur_sq_y] & DOOR_IN_ANY ) {
1061 maze[cur_sq_x][cur_sq_y] |= WALL_LEFT;
1062 maze[cur_sq_x - 1][cur_sq_y] |= WALL_RIGHT;
1063 draw_wall(cur_sq_x, cur_sq_y, 3, gc);
1066 candidates[num_candidates++] = 3;
1069 if (num_candidates == 0)
1071 if (num_candidates == 1)
1072 return ( candidates[0] );
1073 return ( candidates[ get_random(num_candidates) ] );
1079 backup (void) /* back up a move */
1082 cur_sq_x = move_list[sqnum].x;
1083 cur_sq_y = move_list[sqnum].y;
1089 draw_maze_border (void) /* draw the maze outline */
1094 for ( i=0; i<maze_size_x; i++) {
1095 if ( maze[i][0] & WALL_TOP ) {
1096 XDrawLine(dpy, win, gc,
1097 border_x + grid_width * i,
1099 border_x + grid_width * (i+1) - 1,
1102 if ((maze[i][maze_size_y - 1] & WALL_BOTTOM)) {
1103 XDrawLine(dpy, win, gc,
1104 border_x + grid_width * i,
1105 border_y + grid_height * (maze_size_y) - 1,
1106 border_x + grid_width * (i+1) - 1,
1107 border_y + grid_height * (maze_size_y) - 1);
1110 for ( j=0; j<maze_size_y; j++) {
1111 if ( maze[maze_size_x - 1][j] & WALL_RIGHT ) {
1112 XDrawLine(dpy, win, gc,
1113 border_x + grid_width * maze_size_x - 1,
1114 border_y + grid_height * j,
1115 border_x + grid_width * maze_size_x - 1,
1116 border_y + grid_height * (j+1) - 1);
1118 if ( maze[0][j] & WALL_LEFT ) {
1119 XDrawLine(dpy, win, gc,
1121 border_y + grid_height * j,
1123 border_y + grid_height * (j+1) - 1);
1131 unsigned int w, h, bw, d;
1133 /* round up to grid size */
1134 int ww = ((logo_width / grid_width) + 1) * grid_width;
1135 int hh = ((logo_height / grid_height) + 1) * grid_height;
1137 XGetGeometry (dpy, logo_map, &r, &x, &y, &w, &h, &bw, &d);
1139 # ifdef XSCREENSAVER_LOGO
1140 /* kludge: if the logo "hole" is around the same size as the logo,
1141 don't center it (since the xscreensaver logo image is a little
1142 off center... But do center if if the hole/gridsize is large. */
1143 if (ww < logo_width + 5) ww = w;
1144 if (hh < logo_height + 5) hh = h;
1145 # endif /* XSCREENSAVER_LOGO */
1148 XCopyPlane (dpy, logo_map, win, logo_gc,
1150 border_x + 3 + grid_width * logo_x + ((ww - w) / 2),
1151 border_y + 3 + grid_height * logo_y + ((hh - h) / 2),
1154 XCopyArea (dpy, logo_map, win, logo_gc,
1156 border_x + 3 + grid_width * logo_x + ((ww - w) / 2),
1157 border_y + 3 + grid_height * logo_y + ((hh - h) / 2));
1159 draw_solid_square (start_x, start_y, WALL_TOP >> start_dir, tgc);
1160 draw_solid_square (end_x, end_y, WALL_TOP >> end_dir, tgc);
1165 draw_wall(int i, int j, int dir, GC gc) /* draw a single wall */
1169 XDrawLine(dpy, win, gc,
1170 border_x + grid_width * i,
1171 border_y + grid_height * j,
1172 border_x + grid_width * (i+1),
1173 border_y + grid_height * j);
1176 XDrawLine(dpy, win, gc,
1177 border_x + grid_width * (i+1),
1178 border_y + grid_height * j,
1179 border_x + grid_width * (i+1),
1180 border_y + grid_height * (j+1));
1183 XDrawLine(dpy, win, gc,
1184 border_x + grid_width * i,
1185 border_y + grid_height * (j+1),
1186 border_x + grid_width * (i+1),
1187 border_y + grid_height * (j+1));
1190 XDrawLine(dpy, win, gc,
1191 border_x + grid_width * i,
1192 border_y + grid_height * j,
1193 border_x + grid_width * i,
1194 border_y + grid_height * (j+1));
1201 /* Actually build a wall. */
1203 build_wall(i, j, dir)
1206 /* Draw it on the screen. */
1207 draw_wall(i, j, dir, gc);
1208 /* Put it in the maze. */
1212 maze[i][j] |= WALL_TOP;
1214 maze[i][j-1] |= WALL_BOTTOM;
1217 maze[i][j] |= WALL_RIGHT;
1219 maze[i+1][j] |= WALL_LEFT;
1222 maze[i][j] |= WALL_BOTTOM;
1224 maze[i][j+1] |= WALL_TOP;
1227 maze[i][j] |= WALL_LEFT;
1229 maze[i-1][j] |= WALL_RIGHT;
1234 /* Break out a wall. */
1237 break_wall(i, j, dir)
1240 /* Draw it on the screen. */
1241 draw_wall(i, j, dir, erase_gc);
1242 /* Put it in the maze. */
1246 maze[i][j] &= ~WALL_TOP;
1248 maze[i][j-1] &= ~WALL_BOTTOM;
1251 maze[i][j] &= ~WALL_RIGHT;
1253 maze[i+1][j] &= ~WALL_LEFT;
1256 maze[i][j] &= ~WALL_BOTTOM;
1258 maze[i][j+1] &= ~WALL_BOTTOM;
1261 maze[i][j] &= ~WALL_LEFT;
1263 maze[i-1][j] &= ~WALL_RIGHT;
1271 draw_solid_square(int i, int j, /* draw a solid square in a square */
1276 XFillRectangle(dpy, win, gc,
1277 border_x + bw+(bw==0?1:0) + grid_width * i,
1278 border_y - bw-(bw==0?1:0) + grid_height * j,
1279 grid_width - (bw+bw+(bw==0?1:0)), grid_height);
1282 XFillRectangle(dpy, win, gc,
1283 border_x + bw+(bw==0?1:0) + grid_width * i,
1284 border_y + bw+(bw==0?1:0) + grid_height * j,
1285 grid_width, grid_height - (bw+bw+(bw==0?1:0)));
1288 XFillRectangle(dpy, win, gc,
1289 border_x + bw+(bw==0?1:0) + grid_width * i,
1290 border_y + bw+(bw==0?1:0) + grid_height * j,
1291 grid_width - (bw+bw+(bw==0?1:0)), grid_height);
1294 XFillRectangle(dpy, win, gc,
1295 border_x - bw-(bw==0?1:0) + grid_width * i,
1296 border_y + bw+(bw==0?1:0) + grid_height * j,
1297 grid_width, grid_height - (bw+bw+(bw==0?1:0)));
1304 longdeadend_p(int x1, int y1, int x2, int y2, int endwall)
1306 int dx = x2 - x1, dy = y2 - y1;
1309 sidewalls = endwall | (endwall >> 2 | endwall << 2);
1310 sidewalls = ~sidewalls & WALL_ANY;
1312 while((maze[x2][y2] & WALL_ANY) == sidewalls)
1318 if((maze[x2][y2] & WALL_ANY) == (sidewalls | endwall))
1320 endwall = (endwall >> 2 | endwall << 2) & WALL_ANY;
1321 while(x1 != x2 || y1 != y2)
1325 draw_solid_square(x1, y1, endwall, sgc);
1326 maze[x1][y1] |= SOLVER_VISIT;
1334 /* Find all dead regions -- areas from which the goal cannot be reached --
1335 and mark them visited. */
1337 find_dead_regions(void)
1341 /* Find all not SOLVER_VISIT squares bordering NOT_DEAD squares
1342 and mark them NOT_DEAD also. Repeat until no more such squares. */
1343 maze[start_x][start_y] |= NOT_DEAD;
1348 for(x = 0; x < maze_size_x; x++)
1349 for(y = 0; y < maze_size_y; y++)
1350 if(!(maze[x][y] & (SOLVER_VISIT | NOT_DEAD))
1351 && ( (x && (maze[x-1][y] & NOT_DEAD))
1352 || (y && (maze[x][y-1] & NOT_DEAD))))
1355 maze[x][y] |= NOT_DEAD;
1357 for(x = maze_size_x-1; x >= 0; x--)
1358 for(y = maze_size_y-1; y >= 0; y--)
1359 if(!(maze[x][y] & (SOLVER_VISIT | NOT_DEAD))
1360 && ( (x != maze_size_x-1 && (maze[x+1][y] & NOT_DEAD))
1361 || (y != maze_size_y-1 && (maze[x][y+1] & NOT_DEAD))))
1364 maze[x][y] |= NOT_DEAD;
1369 for (y = 0; y < maze_size_y; y++)
1370 for (x = 0; x < maze_size_x; x++)
1372 if (maze[x][y] & NOT_DEAD)
1373 maze[x][y] &= ~NOT_DEAD;
1374 else if (!(maze[x][y] & SOLVER_VISIT))
1376 maze[x][y] |= SOLVER_VISIT;
1377 if((x < logo_x || x > logo_x + logo_width / grid_width) ||
1378 (y < logo_y || y > logo_y + logo_height / grid_height))
1380 /* if we are completely surrounded by walls, just draw the
1382 if ((maze[x][y] & WALL_ANY) == WALL_ANY)
1383 XFillRectangle(dpy, win, ugc,
1384 border_x + bw + grid_width * x,
1385 border_y + bw + grid_height * y,
1386 grid_width - (bw+bw), grid_height - (bw+bw));
1389 if (! (maze[x][y] & WALL_LEFT))
1390 draw_solid_square(x, y, WALL_LEFT, ugc);
1391 if (! (maze[x][y] & WALL_RIGHT))
1392 draw_solid_square(x, y, WALL_RIGHT, ugc);
1393 if (! (maze[x][y] & WALL_TOP))
1394 draw_solid_square(x, y, WALL_TOP, ugc);
1395 if (! (maze[x][y] & WALL_BOTTOM))
1396 draw_solid_square(x, y, WALL_BOTTOM, ugc);
1405 solve_maze (void) /* solve it with graphical feedback */
1407 int i, dir, from, x, y, ways, bt = 0;
1409 /* plug up the surrounding wall */
1410 maze[end_x][end_y] |= (WALL_TOP >> end_dir);
1412 /* initialize search path */
1417 maze[end_x][end_y] |= SOLVER_VISIT;
1422 if ( maze[path[i].x][path[i].y] & START_SQUARE )
1425 /* Abort solve on expose - cheapo repaint strategy */
1426 if (check_events()) return;
1428 if (solve_delay) usleep (solve_delay);
1433 /* First visit this square. Which adjacent squares are open? */
1434 for(dir = WALL_TOP; dir & WALL_ANY; dir >>= 1)
1436 if(maze[path[i].x][path[i].y] & dir)
1439 y = path[i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1440 x = path[i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1442 if(maze[x][y] & SOLVER_VISIT)
1445 from = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1446 /* don't enter obvious dead ends */
1447 if(((maze[x][y] & WALL_ANY) | from) != WALL_ANY)
1449 if(!longdeadend_p(path[i].x, path[i].y, x, y, dir))
1454 draw_solid_square(x, y, from, sgc);
1455 maze[x][y] |= SOLVER_VISIT;
1460 ways = path[i].ways;
1461 /* ways now has a bitmask of open paths. */
1468 x = path[i].x - start_x;
1469 y = path[i].y - start_y;
1471 if(abs(y) <= abs(x))
1472 dir = (x > 0) ? WALL_LEFT : WALL_RIGHT;
1474 dir = (y > 0) ? WALL_TOP : WALL_BOTTOM;
1484 dir = (y > 0) ? WALL_TOP : WALL_BOTTOM; break;
1487 dir = (x > 0) ? WALL_LEFT : WALL_RIGHT;
1495 dir = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1510 else if(ways&WALL_LEFT)
1512 else if(ways&WALL_BOTTOM)
1514 else if(ways&WALL_RIGHT)
1520 ways &= ~dir; /* tried this one */
1522 y = path[i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1523 x = path[i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1525 /* advance in direction dir */
1527 path[i].ways = ways;
1528 draw_solid_square(path[i].x, path[i].y, dir, tgc);
1535 maze[x][y] |= SOLVER_VISIT;
1541 printf("Unsolvable maze.\n");
1545 if(!bt && !ignorant_p)
1546 find_dead_regions();
1548 from = path[i-1].dir;
1549 from = (from << 2 & WALL_ANY) | (from >> 2 & WALL_ANY);
1551 draw_solid_square(path[i].x, path[i].y, from, cgc);
1558 enter_square (int n) /* move into a neighboring square */
1560 draw_solid_square( (int)path[n].x, (int)path[n].y,
1561 (int)path[n].dir, tgc);
1564 switch (path[n].dir) {
1565 case 0: path[n+1].x = path[n].x;
1566 path[n+1].y = path[n].y - 1;
1568 case 1: path[n+1].x = path[n].x + 1;
1569 path[n+1].y = path[n].y;
1571 case 2: path[n+1].x = path[n].x;
1572 path[n+1].y = path[n].y + 1;
1574 case 3: path[n+1].x = path[n].x - 1;
1575 path[n+1].y = path[n].y;
1583 * jmr additions for Jamie Zawinski's <jwz@jwz.org> screensaver stuff,
1584 * note that the code above this has probably been hacked about in some
1588 char *progclass = "Maze";
1590 char *defaults[] = {
1591 ".background: black",
1592 ".foreground: white",
1594 "*solveDelay: 5000",
1595 "*preDelay: 2000000",
1596 "*postDelay: 4000000",
1597 "*liveColor: green",
1599 "*skipColor: orange",
1600 "*surroundColor: slateblue",
1608 XrmOptionDescRec options[] = {
1609 { "-ignorant", ".ignorant", XrmoptionNoArg, "True" },
1610 { "-no-ignorant", ".ignorant", XrmoptionNoArg, "False" },
1611 { "-grid-size", ".gridSize", XrmoptionSepArg, 0 },
1612 { "-solve-delay", ".solveDelay", XrmoptionSepArg, 0 },
1613 { "-pre-delay", ".preDelay", XrmoptionSepArg, 0 },
1614 { "-post-delay", ".postDelay", XrmoptionSepArg, 0 },
1615 { "-bg-color", ".background", XrmoptionSepArg, 0 },
1616 { "-fg-color", ".foreground", XrmoptionSepArg, 0 },
1617 { "-live-color", ".liveColor", XrmoptionSepArg, 0 },
1618 { "-dead-color", ".deadColor", XrmoptionSepArg, 0 },
1619 { "-skip-color", ".skipColor", XrmoptionSepArg, 0 },
1620 { "-surround-color", ".surroundColor",XrmoptionSepArg, 0 },
1621 { "-generator", ".generator", XrmoptionSepArg, 0 },
1622 { "-max-length", ".maxLength", XrmoptionSepArg, 0 },
1623 { "-bridge", ".bridge", XrmoptionNoArg, "True" },
1624 { "-no-bridge", ".bridge", XrmoptionNoArg, "False" },
1629 screenhack(Display *display, Window window)
1632 int size, root, generator, this_gen;
1633 XWindowAttributes xgwa;
1634 unsigned long bg, fg, pfg, pbg, sfg, ufg;
1636 size = get_integer_resource ("gridSize", "Dimension");
1637 root = get_boolean_resource("root", "Boolean");
1638 solve_delay = get_integer_resource ("solveDelay", "Integer");
1639 pre_solve_delay = get_integer_resource ("preDelay", "Integer");
1640 post_solve_delay = get_integer_resource ("postDelay", "Integer");
1641 generator = get_integer_resource("generator", "Integer");
1642 max_length = get_integer_resource("maxLength", "Integer");
1643 bridge_p = get_boolean_resource("bridge", "Boolean");
1644 ignorant_p = get_boolean_resource("ignorant", "Boolean");
1646 if (size < 2) size = 7 + (random () % 30);
1647 grid_width = grid_height = size;
1648 bw = (size > 6 ? 3 : (size-1)/2);
1650 dpy = display; win = window; /* the maze stuff uses global variables */
1652 XGetWindowAttributes (dpy, win, &xgwa);
1657 set_maze_sizes (xgwa.width, xgwa.height);
1661 XWindowAttributes xgwa;
1662 XGetWindowAttributes (dpy, window, &xgwa);
1663 XSelectInput (dpy, win,
1664 xgwa.your_event_mask | ExposureMask | ButtonPressMask);
1667 gc = XCreateGC(dpy, win, 0, 0);
1668 cgc = XCreateGC(dpy, win, 0, 0);
1669 tgc = XCreateGC(dpy, win, 0, 0);
1670 sgc = XCreateGC(dpy, win, 0, 0);
1671 ugc = XCreateGC(dpy, win, 0, 0);
1672 logo_gc = XCreateGC(dpy, win, 0, 0);
1673 erase_gc = XCreateGC(dpy, win, 0, 0);
1675 gray = XCreateBitmapFromData (dpy,win,gray1_bits,gray1_width,gray1_height);
1677 bg = get_pixel_resource ("background","Background", dpy, xgwa.colormap);
1678 fg = get_pixel_resource ("foreground","Foreground", dpy, xgwa.colormap);
1679 pfg = get_pixel_resource ("liveColor", "Foreground", dpy, xgwa.colormap);
1680 pbg = get_pixel_resource ("deadColor", "Foreground", dpy, xgwa.colormap);
1681 sfg = get_pixel_resource ("skipColor", "Foreground", dpy, xgwa.colormap);
1682 ufg = get_pixel_resource ("surroundColor", "Foreground", dpy, xgwa.colormap);
1684 XSetForeground (dpy, gc, fg);
1685 XSetBackground (dpy, gc, bg);
1686 XSetForeground (dpy, cgc, pbg);
1687 XSetBackground (dpy, cgc, bg);
1688 XSetForeground (dpy, tgc, pfg);
1689 XSetBackground (dpy, tgc, bg);
1690 XSetForeground (dpy, sgc, sfg);
1691 XSetBackground (dpy, sgc, bg);
1692 XSetForeground (dpy, ugc, ufg);
1693 XSetBackground (dpy, ugc, bg);
1694 XSetForeground (dpy, logo_gc, fg);
1695 XSetBackground (dpy, logo_gc, bg);
1696 XSetForeground (dpy, erase_gc, bg);
1697 XSetBackground (dpy, erase_gc, bg);
1699 XSetStipple (dpy, cgc, gray);
1700 XSetFillStyle (dpy, cgc, FillOpaqueStippled);
1701 XSetStipple (dpy, sgc, gray);
1702 XSetFillStyle (dpy, sgc, FillOpaqueStippled);
1703 XSetStipple (dpy, ugc, gray);
1704 XSetFillStyle (dpy, ugc, FillOpaqueStippled);
1706 #ifdef XSCREENSAVER_LOGO
1708 unsigned long *pixels; /* ignored - unfreed */
1710 logo_map = xscreensaver_logo (xgwa.screen, xgwa.visual, win,
1712 &pixels, &npixels, 0,
1716 if (!(logo_map = XCreateBitmapFromData (dpy, win, logo_bits,
1717 logo_width, logo_height)))
1719 fprintf (stderr, "Can't create logo pixmap\n");
1723 XMapRaised(dpy, win);
1727 sync_p = !(random() % 10);
1729 while (1) { /* primary execution loop [ rhess ] */
1730 if (check_events()) continue ;
1731 if (restart || stop) goto pop;
1737 XClearWindow(dpy, win);
1741 this_gen = generator;
1742 if(this_gen<0 || this_gen>2)
1743 this_gen = random()%3;
1760 usleep (pre_solve_delay);
1767 usleep (post_solve_delay);
1769 erase_full_window(display, window);
1778 static XWindowAttributes wattr;
1782 XGetWindowAttributes (dpy, win, &wattr);
1783 set_maze_sizes (wattr.width, wattr.height);
1784 XClearWindow (dpy, win);
1786 sync_p = !(random() % 10);