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 (!(maze[x][y] & WALL_ANY))
1381 XFillRectangle(dpy, win, ugc,
1382 border_x + bw + grid_width * x,
1383 border_y + bw + grid_height * y,
1384 grid_width - (bw+bw), grid_height - (bw+bw));
1387 if (! (maze[x][y] & WALL_LEFT))
1388 draw_solid_square(x, y, WALL_LEFT, ugc);
1389 if (! (maze[x][y] & WALL_RIGHT))
1390 draw_solid_square(x, y, WALL_RIGHT, ugc);
1391 if (! (maze[x][y] & WALL_TOP))
1392 draw_solid_square(x, y, WALL_TOP, ugc);
1393 if (! (maze[x][y] & WALL_BOTTOM))
1394 draw_solid_square(x, y, WALL_BOTTOM, ugc);
1403 solve_maze (void) /* solve it with graphical feedback */
1405 int i, dir, from, x, y, ways, bt = 0;
1407 /* plug up the surrounding wall */
1408 maze[end_x][end_y] |= (WALL_TOP >> end_dir);
1410 /* initialize search path */
1415 maze[end_x][end_y] |= SOLVER_VISIT;
1420 if ( maze[path[i].x][path[i].y] & START_SQUARE )
1423 /* Abort solve on expose - cheapo repaint strategy */
1424 if (check_events()) return;
1426 if (solve_delay) usleep (solve_delay);
1431 /* First visit this square. Which adjacent squares are open? */
1432 for(dir = WALL_TOP; dir & WALL_ANY; dir >>= 1)
1434 if(maze[path[i].x][path[i].y] & dir)
1437 y = path[i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1438 x = path[i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1440 if(maze[x][y] & SOLVER_VISIT)
1443 from = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1444 /* don't enter obvious dead ends */
1445 if(((maze[x][y] & WALL_ANY) | from) != WALL_ANY)
1447 if(!longdeadend_p(path[i].x, path[i].y, x, y, dir))
1452 draw_solid_square(x, y, from, sgc);
1453 maze[x][y] |= SOLVER_VISIT;
1458 ways = path[i].ways;
1459 /* ways now has a bitmask of open paths. */
1466 x = path[i].x - start_x;
1467 y = path[i].y - start_y;
1469 if(abs(y) <= abs(x))
1470 dir = (x > 0) ? WALL_LEFT : WALL_RIGHT;
1472 dir = (y > 0) ? WALL_TOP : WALL_BOTTOM;
1482 dir = (y > 0) ? WALL_TOP : WALL_BOTTOM; break;
1485 dir = (x > 0) ? WALL_LEFT : WALL_RIGHT;
1493 dir = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1508 else if(ways&WALL_LEFT)
1510 else if(ways&WALL_BOTTOM)
1512 else if(ways&WALL_RIGHT)
1518 ways &= ~dir; /* tried this one */
1520 y = path[i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1521 x = path[i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1523 /* advance in direction dir */
1525 path[i].ways = ways;
1526 draw_solid_square(path[i].x, path[i].y, dir, tgc);
1533 maze[x][y] |= SOLVER_VISIT;
1539 printf("Unsolvable maze.\n");
1543 if(!bt && !ignorant_p)
1544 find_dead_regions();
1546 from = path[i-1].dir;
1547 from = (from << 2 & WALL_ANY) | (from >> 2 & WALL_ANY);
1549 draw_solid_square(path[i].x, path[i].y, from, cgc);
1556 enter_square (int n) /* move into a neighboring square */
1558 draw_solid_square( (int)path[n].x, (int)path[n].y,
1559 (int)path[n].dir, tgc);
1562 switch (path[n].dir) {
1563 case 0: path[n+1].x = path[n].x;
1564 path[n+1].y = path[n].y - 1;
1566 case 1: path[n+1].x = path[n].x + 1;
1567 path[n+1].y = path[n].y;
1569 case 2: path[n+1].x = path[n].x;
1570 path[n+1].y = path[n].y + 1;
1572 case 3: path[n+1].x = path[n].x - 1;
1573 path[n+1].y = path[n].y;
1581 * jmr additions for Jamie Zawinski's <jwz@jwz.org> screensaver stuff,
1582 * note that the code above this has probably been hacked about in some
1586 char *progclass = "Maze";
1588 char *defaults[] = {
1589 ".background: black",
1590 ".foreground: white",
1592 "*solveDelay: 5000",
1593 "*preDelay: 2000000",
1594 "*postDelay: 4000000",
1595 "*liveColor: green",
1597 "*skipColor: orange",
1598 "*surroundColor: slateblue",
1606 XrmOptionDescRec options[] = {
1607 { "-ignorant", ".ignorant", XrmoptionNoArg, "True" },
1608 { "-no-ignorant", ".ignorant", XrmoptionNoArg, "False" },
1609 { "-grid-size", ".gridSize", XrmoptionSepArg, 0 },
1610 { "-solve-delay", ".solveDelay", XrmoptionSepArg, 0 },
1611 { "-pre-delay", ".preDelay", XrmoptionSepArg, 0 },
1612 { "-post-delay", ".postDelay", XrmoptionSepArg, 0 },
1613 { "-bg-color", ".background", XrmoptionSepArg, 0 },
1614 { "-fg-color", ".foreground", XrmoptionSepArg, 0 },
1615 { "-live-color", ".liveColor", XrmoptionSepArg, 0 },
1616 { "-dead-color", ".deadColor", XrmoptionSepArg, 0 },
1617 { "-skip-color", ".skipColor", XrmoptionSepArg, 0 },
1618 { "-surround-color", ".surroundColor",XrmoptionSepArg, 0 },
1619 { "-generator", ".generator", XrmoptionSepArg, 0 },
1620 { "-max-length", ".maxLength", XrmoptionSepArg, 0 },
1621 { "-bridge", ".bridge", XrmoptionNoArg, "True" },
1622 { "-no-bridge", ".bridge", XrmoptionNoArg, "False" },
1627 screenhack(Display *display, Window window)
1630 int size, root, generator, this_gen;
1631 XWindowAttributes xgwa;
1632 unsigned long bg, fg, pfg, pbg, sfg, ufg;
1634 size = get_integer_resource ("gridSize", "Dimension");
1635 root = get_boolean_resource("root", "Boolean");
1636 solve_delay = get_integer_resource ("solveDelay", "Integer");
1637 pre_solve_delay = get_integer_resource ("preDelay", "Integer");
1638 post_solve_delay = get_integer_resource ("postDelay", "Integer");
1639 generator = get_integer_resource("generator", "Integer");
1640 max_length = get_integer_resource("maxLength", "Integer");
1641 bridge_p = get_boolean_resource("bridge", "Boolean");
1642 ignorant_p = get_boolean_resource("ignorant", "Boolean");
1644 if (size < 2) size = 7 + (random () % 30);
1645 grid_width = grid_height = size;
1646 bw = (size > 6 ? 3 : (size-1)/2);
1648 dpy = display; win = window; /* the maze stuff uses global variables */
1650 XGetWindowAttributes (dpy, win, &xgwa);
1655 set_maze_sizes (xgwa.width, xgwa.height);
1659 XWindowAttributes xgwa;
1660 XGetWindowAttributes (dpy, window, &xgwa);
1661 XSelectInput (dpy, win,
1662 xgwa.your_event_mask | ExposureMask |
1663 ButtonPressMask |StructureNotifyMask);
1666 gc = XCreateGC(dpy, win, 0, 0);
1667 cgc = XCreateGC(dpy, win, 0, 0);
1668 tgc = XCreateGC(dpy, win, 0, 0);
1669 sgc = XCreateGC(dpy, win, 0, 0);
1670 ugc = XCreateGC(dpy, win, 0, 0);
1671 logo_gc = XCreateGC(dpy, win, 0, 0);
1672 erase_gc = XCreateGC(dpy, win, 0, 0);
1674 gray = XCreateBitmapFromData (dpy,win,gray1_bits,gray1_width,gray1_height);
1676 bg = get_pixel_resource ("background","Background", dpy, xgwa.colormap);
1677 fg = get_pixel_resource ("foreground","Foreground", dpy, xgwa.colormap);
1678 pfg = get_pixel_resource ("liveColor", "Foreground", dpy, xgwa.colormap);
1679 pbg = get_pixel_resource ("deadColor", "Foreground", dpy, xgwa.colormap);
1680 sfg = get_pixel_resource ("skipColor", "Foreground", dpy, xgwa.colormap);
1681 ufg = get_pixel_resource ("surroundColor", "Foreground", dpy, xgwa.colormap);
1683 XSetForeground (dpy, gc, fg);
1684 XSetBackground (dpy, gc, bg);
1685 XSetForeground (dpy, cgc, pbg);
1686 XSetBackground (dpy, cgc, bg);
1687 XSetForeground (dpy, tgc, pfg);
1688 XSetBackground (dpy, tgc, bg);
1689 XSetForeground (dpy, sgc, sfg);
1690 XSetBackground (dpy, sgc, bg);
1691 XSetForeground (dpy, ugc, ufg);
1692 XSetBackground (dpy, ugc, bg);
1693 XSetForeground (dpy, logo_gc, fg);
1694 XSetBackground (dpy, logo_gc, bg);
1695 XSetForeground (dpy, erase_gc, bg);
1696 XSetBackground (dpy, erase_gc, bg);
1698 XSetStipple (dpy, cgc, gray);
1699 XSetFillStyle (dpy, cgc, FillOpaqueStippled);
1700 XSetStipple (dpy, sgc, gray);
1701 XSetFillStyle (dpy, sgc, FillOpaqueStippled);
1702 XSetStipple (dpy, ugc, gray);
1703 XSetFillStyle (dpy, ugc, FillOpaqueStippled);
1705 #ifdef XSCREENSAVER_LOGO
1707 unsigned long *pixels; /* ignored - unfreed */
1709 logo_map = xscreensaver_logo (xgwa.screen, xgwa.visual, win,
1711 &pixels, &npixels, 0,
1715 if (!(logo_map = XCreateBitmapFromData (dpy, win, logo_bits,
1716 logo_width, logo_height)))
1718 fprintf (stderr, "Can't create logo pixmap\n");
1722 XMapRaised(dpy, win);
1726 sync_p = !(random() % 10);
1728 while (1) { /* primary execution loop [ rhess ] */
1729 if (check_events()) continue ;
1730 if (restart || stop) goto pop;
1736 XClearWindow(dpy, win);
1740 this_gen = generator;
1741 if(this_gen<0 || this_gen>2)
1742 this_gen = random()%3;
1759 usleep (pre_solve_delay);
1766 usleep (post_solve_delay);
1768 erase_full_window(display, window);
1777 static XWindowAttributes wattr;
1781 XGetWindowAttributes (dpy, win, &wattr);
1782 set_maze_sizes (wattr.width, wattr.height);
1783 XClearWindow (dpy, win);
1785 sync_p = !(random() % 10);