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 # include "sys$common:[decw$include.bitmaps]gray1.xbm"
100 #define MAX_MAZE_SIZE_X 500
101 #define MAX_MAZE_SIZE_Y 500
103 #define MOVE_LIST_SIZE (MAX_MAZE_SIZE_X * MAX_MAZE_SIZE_Y)
105 #define NOT_DEAD 0x8000
106 #define SOLVER_VISIT 0x4000
107 #define START_SQUARE 0x2000
108 #define END_SQUARE 0x1000
111 #define WALL_RIGHT 0x4
112 #define WALL_BOTTOM 0x2
113 #define WALL_LEFT 0x1
116 #define DOOR_IN_TOP 0x800
117 #define DOOR_IN_RIGHT 0x400
118 #define DOOR_IN_BOTTOM 0x200
119 #define DOOR_IN_LEFT 0x100
120 #define DOOR_IN_ANY 0xF00
122 #define DOOR_OUT_TOP 0x80
123 #define DOOR_OUT_RIGHT 0x40
124 #define DOOR_OUT_BOTTOM 0x20
125 #define DOOR_OUT_LEFT 0x10
131 #define get_random(x) (random() % (x))
134 static int logo_x, logo_y;
136 #ifdef XSCREENSAVER_LOGO
137 # define logo_width 50
138 # define logo_height 50
140 # include <X11/bitmaps/xlogo64>
141 # define logo_width xlogo64_width
142 # define logo_height xlogo64_height
143 # define logo_bits xlogo64_bits
146 static unsigned short maze[MAX_MAZE_SIZE_X][MAX_MAZE_SIZE_Y];
151 unsigned char dir, ways;
152 } move_list[MOVE_LIST_SIZE], save_path[MOVE_LIST_SIZE], path[MOVE_LIST_SIZE];
154 static int maze_size_x, maze_size_y;
155 static int sqnum, cur_sq_x, cur_sq_y, path_length;
156 static int start_x, start_y, start_dir, end_x, end_y, end_dir;
157 static int grid_width, grid_height;
162 static GC gc, cgc, tgc, sgc, ugc, logo_gc, erase_gc;
163 static Pixmap logo_map;
165 static int x = 0, y = 0, restart = 0, stop = 1, state = 1, max_length;
166 static int sync_p, bridge_p, ignorant_p;
169 check_events (void) /* X event handler [ rhess ] */
178 switch (e.xbutton.button) {
184 if (state == 5) state = 4 ;
197 case ConfigureNotify:
202 XClearWindow (dpy, win);
209 screenhack_handle_event(dpy, &e);
219 set_maze_sizes (int width, int height)
221 maze_size_x = width / grid_width;
222 maze_size_y = height / grid_height;
227 initialize_maze (void) /* draw the surrounding wall and start/end squares */
229 register int i, j, wall;
230 int logow = 1 + logo_width / grid_width;
231 int logoh = 1 + logo_height / grid_height;
233 /* initialize all squares */
234 for ( i=0; i<maze_size_x; i++) {
235 for ( j=0; j<maze_size_y; j++) {
241 for ( i=0; i<maze_size_x; i++ ) {
242 maze[i][0] |= WALL_TOP;
246 for ( j=0; j<maze_size_y; j++ ) {
247 maze[maze_size_x-1][j] |= WALL_RIGHT;
251 for ( i=0; i<maze_size_x; i++ ) {
252 maze[i][maze_size_y-1] |= WALL_BOTTOM;
256 for ( j=0; j<maze_size_y; j++ ) {
257 maze[0][j] |= WALL_LEFT;
260 /* set start square */
261 wall = get_random(4);
264 i = get_random(maze_size_x);
269 j = get_random(maze_size_y);
272 i = get_random(maze_size_x);
277 j = get_random(maze_size_y);
280 maze[i][j] |= START_SQUARE;
281 maze[i][j] |= ( DOOR_IN_TOP >> wall );
282 maze[i][j] &= ~( WALL_TOP >> wall );
294 i = get_random(maze_size_x);
299 j = get_random(maze_size_y);
302 i = get_random(maze_size_x);
307 j = get_random(maze_size_y);
310 maze[i][j] |= END_SQUARE;
311 maze[i][j] |= ( DOOR_OUT_TOP >> wall );
312 maze[i][j] &= ~( WALL_TOP >> wall );
318 if ((maze_size_x-logow >= 6) && (maze_size_y-logoh >= 6))
320 /* not closer than 3 grid units from a wall */
321 logo_x = get_random (maze_size_x - logow - 5) + 3;
322 logo_y = get_random (maze_size_y - logoh - 5) + 3;
323 for (i=0; i<logow; i++)
324 for (j=0; j<logoh; j++)
325 maze[logo_x + i][logo_y + j] |= DOOR_IN_TOP;
328 logo_y = logo_x = -1;
331 static int choose_door (void);
332 static int backup (void);
333 static void draw_wall (int, int, int, GC);
334 static void draw_solid_square (int, int, int, GC);
335 /*static void enter_square (int);*/
336 static void build_wall (int, int, int);
337 /*static void break_wall (int, int, int);*/
339 static void join_sets(int, int);
341 /* For set_create_maze. */
342 /* The sets that our squares are in. */
343 static int *sets = 0;
344 /* The `list' of hedges. */
345 static int *hedges = 0;
349 /* Initialise the sets. */
357 sets = (int *)malloc(maze_size_x*maze_size_y*sizeof(int));
360 for(i = 0; i < maze_size_x*maze_size_y; i++)
367 hedges = (int *)malloc(maze_size_x*maze_size_y*2*sizeof(int));
370 for(i = 0; i < maze_size_x*maze_size_y*2; i++)
374 /* Mask out outside walls. */
375 for(i = 0; i < maze_size_y; i++)
377 hedges[2*((maze_size_x)*i+maze_size_x-1)+1] = -1;
379 for(i = 0; i < maze_size_x; i++)
381 hedges[2*((maze_size_y-1)*maze_size_x+i)] = -1;
383 /* Mask out a possible logo. */
386 int logow = 1 + logo_width / grid_width;
387 int logoh = 1 + logo_height / grid_height;
388 int bridge_dir, bridge_c;
390 if(bridge_p && logoh>=3 && logow>=3)
392 bridge_dir = 1+random()%2;
395 bridge_c = logo_y+random()%(logoh-2)+1;
399 bridge_c = logo_x+random()%(logow-2)+1;
408 for(x = logo_x; x < logo_x+logow; x++)
409 for(y = logo_y; y < logo_y+logoh; y++)
411 /* I should check for the bridge here, except that I join the
412 * bridge together below.
414 hedges[2*(x+maze_size_x*y)+1] = -1;
415 hedges[2*(x+maze_size_x*y)] = -1;
417 for(x = logo_x; x < logo_x+logow; x++)
419 if(!(bridge_dir==2 && x==bridge_c))
421 build_wall(x, logo_y, 0);
422 build_wall(x, logo_y+logoh, 0);
424 hedges[2*(x+maze_size_x*(logo_y-1))] = -1;
427 build_wall(x, bridge_c, 0);
428 build_wall(x, bridge_c, 2);
431 for(y = logo_y; y < logo_y+logoh; y++)
433 if(!(bridge_dir==1 && y==bridge_c))
435 build_wall(logo_x, y, 3);
436 build_wall(logo_x+logow, y, 3);
438 hedges[2*(logo_x-1+maze_size_x*y)+1] = -1;
441 build_wall(bridge_c, y, 1);
442 build_wall(bridge_c, y, 3);
445 /* Join the whole bridge together. */
452 for(i = logo_x; i < logo_x+logow+1; i++)
453 join_sets(x+y*maze_size_x, i+y*maze_size_x);
459 for(i = logo_y; i < logo_y+logoh+1; i++)
460 join_sets(x+y*maze_size_x, x+i*maze_size_x);
465 for(i = 0; i < maze_size_x*maze_size_y*2; i++)
468 r = random()%(maze_size_x*maze_size_y*2);
469 hedges[i] = hedges[r];
474 /* Get the representative of a set. */
484 s = get_set(sets[num]);
490 /* Join two sets together. */
492 join_sets(num1, num2)
506 /* Exitialise the sets. */
519 /* Temporary hack. */
521 show_set(int num, GC gc)
527 for(x = 0; x < maze_size_x; x++)
528 for(y = 0; y < maze_size_y; y++)
530 if(get_set(x+y*maze_size_x)==set)
532 XFillRectangle(dpy, win, gc, border_x + bw + grid_width * x,
533 border_y + bw + grid_height * y,
534 grid_width-2*bw , grid_height-2*bw);
540 /* Second alternative maze creator: Put each square in the maze in a
541 * separate set. Also, make a list of all the hedges. Randomize that list.
542 * Walk through the list. If, for a certain hedge, the two squares on both
543 * sides of it are in different sets, union the sets and remove the hedge.
544 * Continue until all hedges have been processed or only one set remains.
547 set_create_maze(void)
549 int i, h, x, y, dir, v, w;
555 /* Do almost all the setup. */
558 /* Start running through the hedges. */
559 for(i = 0; i < 2*maze_size_x*maze_size_y; i++)
563 /* This one is in the logo or outside border. */
568 x = (h>>1)%maze_size_x;
569 y = (h>>1)/maze_size_x;
584 show_set(x+y*maze_size_x, logo_gc);
585 show_set(v+w*maze_size_x, tgc);
587 if(get_set(x+y*maze_size_x)!=get_set(v+w*maze_size_x))
592 join_sets(x+y*maze_size_x, v+w*maze_size_x);
593 /* Don't draw the wall. */
600 /* Don't join the sets. */
601 build_wall(x, y, dir);
611 show_set(x+y*maze_size_x, erase_gc);
612 show_set(v+w*maze_size_x, erase_gc);
616 /* Free some memory. */
620 /* First alternative maze creator: Pick a random, empty corner in the maze.
621 * Pick a random direction. Draw a wall in that direction, from that corner
622 * until we hit a wall. Option: Only draw the wall if it's going to be
623 * shorter than a certain length. Otherwise we get lots of long walls.
626 alt_create_maze(void)
630 int i, j, height, width, open_corners, k, dir, x, y;
632 height = maze_size_y+1;
633 width = maze_size_x+1;
635 /* Allocate and clear some mem. */
636 corners = (char *)calloc(height*width, 1);
640 /* Set up the indexing array. */
641 c_idx = (int *)malloc(sizeof(int)*height*width);
647 for(i = 0; i < height*width; i++)
649 for(i = 0; i < height*width; i++)
652 k = random()%(height*width);
657 /* Set up some initial walls. */
659 for(i = 0; i < width; i++)
662 corners[i+width*(height-1)] = 1;
664 for(i = 0; i < height; i++)
666 corners[i*width] = 1;
667 corners[i*width+width-1] = 1;
669 /* Walls around logo. In fact, inside the logo, too. */
670 /* Also draw the walls. */
673 int logow = 1 + logo_width / grid_width;
674 int logoh = 1 + logo_height / grid_height;
675 int bridge_dir, bridge_c;
677 if(bridge_p && logoh>=3 && logow>=3)
679 bridge_dir = 1+random()%2;
682 bridge_c = logo_y+random()%(logoh-2)+1;
686 bridge_c = logo_x+random()%(logow-2)+1;
694 for(i = logo_x; i <= logo_x + logow; i++)
696 for(j = logo_y; j <= logo_y + logoh; j++)
698 corners[i+width*j] = 1;
701 for(x = logo_x; x < logo_x+logow; x++)
703 if(!(bridge_dir==2 && x==bridge_c))
705 build_wall(x, logo_y, 0);
706 build_wall(x, logo_y+logoh, 0);
710 build_wall(x, bridge_c, 0);
711 build_wall(x, bridge_c, 2);
714 for(y = logo_y; y < logo_y+logoh; y++)
716 if(!(bridge_dir==1 && y==bridge_c))
718 build_wall(logo_x, y, 3);
719 build_wall(logo_x+logow, y, 3);
723 build_wall(bridge_c, y, 1);
724 build_wall(bridge_c, y, 3);
727 /* Connect one wall of the logo with an outside wall. */
729 dir = (bridge_dir+1)%4;
735 x = logo_x+(random()%(logow+1));
740 y = logo_y+(random()%(logoh+1));
743 x = logo_x+(random()%(logow+1));
748 y = logo_y+(random()%(logoh+1));
753 corners[x+width*y] = 1;
757 build_wall(x-1, y-1, 1);
769 build_wall(x-1, y-1, 2);
774 while(!corners[x+width*y]);
781 x = logo_x+(random()%(logow+1));
786 y = logo_y+(random()%(logoh+1));
789 x = logo_x+(random()%(logow+1));
794 y = logo_y+(random()%(logoh+1));
799 corners[x+width*y] = 1;
803 build_wall(x-1, y-1, 1);
815 build_wall(x-1, y-1, 2);
820 while(!corners[x+width*y]);
824 /* Count open gridpoints. */
826 for(i = 0; i < width; i++)
827 for(j = 0; j < height; j++)
828 if(!corners[i+width*j])
831 /* Now do actual maze generation. */
832 while(open_corners>0)
834 for(i = 0; i < width*height; i++)
836 if(!corners[c_idx[i]])
840 /* Choose a random direction. */
844 /* Measure the length of the wall we'd draw. */
845 while(!corners[x+width*y])
870 /* Draw a wall until we hit something. */
871 while(!corners[x+width*y])
874 corners[x+width*y] = 1;
878 build_wall(x-1, y-1, 1);
890 build_wall(x-1, y-1, 2);
900 /* Free some memory we used. */
905 /* The original maze creator. Start somewhere. Take a step in a random
906 * direction. Keep doing this until we hit a wall. Then, backtrack until
907 * we find a point where we can go in another direction.
910 create_maze (void) /* create a maze layout given the initialized maze */
912 register int i, newdoor = 0;
913 int logow = 1 + logo_width / grid_width;
914 int logoh = 1 + logo_height / grid_height;
916 /* Maybe we should make a bridge? */
917 if(bridge_p && logo_x>=0 && logow>=3 && logoh>=3)
919 int bridge_dir, bridge_c;
921 bridge_dir = 1+random()%2;
925 bridge_c = logo_y+random()%(logoh-2)+1;
927 bridge_c = logo_y+random()%logoh;
932 bridge_c = logo_x+random()%(logow-2)+1;
934 bridge_c = logo_x+random()%logow;
939 for(i = logo_x; i < logo_x+logow; i++)
941 maze[i][bridge_c] &= ~DOOR_IN_TOP;
946 for(i = logo_y; i < logo_y+logoh; i++)
948 maze[bridge_c][i] &= ~DOOR_IN_TOP;
954 move_list[sqnum].x = cur_sq_x;
955 move_list[sqnum].y = cur_sq_y;
956 move_list[sqnum].dir = newdoor;
957 while ( ( newdoor = choose_door() ) == -1 ) { /* pick a door */
958 if ( backup() == -1 ) { /* no more doors ... backup */
959 return; /* done ... return */
963 /* mark the out door */
964 maze[cur_sq_x][cur_sq_y] |= ( DOOR_OUT_TOP >> newdoor );
978 /* mark the in door */
979 maze[cur_sq_x][cur_sq_y] |= ( DOOR_IN_TOP >> ((newdoor+2)%4) );
981 /* if end square set path length and save path */
982 if ( maze[cur_sq_x][cur_sq_y] & END_SQUARE ) {
984 for ( i=0; i<path_length; i++) {
985 save_path[i].x = move_list[i].x;
986 save_path[i].y = move_list[i].y;
987 save_path[i].dir = move_list[i].dir;
997 choose_door (void) /* pick a new path */
1000 register int num_candidates;
1005 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_TOP )
1007 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_TOP )
1009 if ( maze[cur_sq_x][cur_sq_y] & WALL_TOP )
1011 if ( maze[cur_sq_x][cur_sq_y - 1] & DOOR_IN_ANY ) {
1012 maze[cur_sq_x][cur_sq_y] |= WALL_TOP;
1013 maze[cur_sq_x][cur_sq_y - 1] |= WALL_BOTTOM;
1014 draw_wall(cur_sq_x, cur_sq_y, 0, gc);
1017 candidates[num_candidates++] = 0;
1021 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_RIGHT )
1023 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_RIGHT )
1025 if ( maze[cur_sq_x][cur_sq_y] & WALL_RIGHT )
1027 if ( maze[cur_sq_x + 1][cur_sq_y] & DOOR_IN_ANY ) {
1028 maze[cur_sq_x][cur_sq_y] |= WALL_RIGHT;
1029 maze[cur_sq_x + 1][cur_sq_y] |= WALL_LEFT;
1030 draw_wall(cur_sq_x, cur_sq_y, 1, gc);
1033 candidates[num_candidates++] = 1;
1037 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_BOTTOM )
1039 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_BOTTOM )
1041 if ( maze[cur_sq_x][cur_sq_y] & WALL_BOTTOM )
1043 if ( maze[cur_sq_x][cur_sq_y + 1] & DOOR_IN_ANY ) {
1044 maze[cur_sq_x][cur_sq_y] |= WALL_BOTTOM;
1045 maze[cur_sq_x][cur_sq_y + 1] |= WALL_TOP;
1046 draw_wall(cur_sq_x, cur_sq_y, 2, gc);
1049 candidates[num_candidates++] = 2;
1053 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_LEFT )
1055 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_LEFT )
1057 if ( maze[cur_sq_x][cur_sq_y] & WALL_LEFT )
1059 if ( maze[cur_sq_x - 1][cur_sq_y] & DOOR_IN_ANY ) {
1060 maze[cur_sq_x][cur_sq_y] |= WALL_LEFT;
1061 maze[cur_sq_x - 1][cur_sq_y] |= WALL_RIGHT;
1062 draw_wall(cur_sq_x, cur_sq_y, 3, gc);
1065 candidates[num_candidates++] = 3;
1068 if (num_candidates == 0)
1070 if (num_candidates == 1)
1071 return ( candidates[0] );
1072 return ( candidates[ get_random(num_candidates) ] );
1078 backup (void) /* back up a move */
1081 cur_sq_x = move_list[sqnum].x;
1082 cur_sq_y = move_list[sqnum].y;
1088 draw_maze_border (void) /* draw the maze outline */
1093 for ( i=0; i<maze_size_x; i++) {
1094 if ( maze[i][0] & WALL_TOP ) {
1095 XDrawLine(dpy, win, gc,
1096 border_x + grid_width * i,
1098 border_x + grid_width * (i+1) - 1,
1101 if ((maze[i][maze_size_y - 1] & WALL_BOTTOM)) {
1102 XDrawLine(dpy, win, gc,
1103 border_x + grid_width * i,
1104 border_y + grid_height * (maze_size_y) - 1,
1105 border_x + grid_width * (i+1) - 1,
1106 border_y + grid_height * (maze_size_y) - 1);
1109 for ( j=0; j<maze_size_y; j++) {
1110 if ( maze[maze_size_x - 1][j] & WALL_RIGHT ) {
1111 XDrawLine(dpy, win, gc,
1112 border_x + grid_width * maze_size_x - 1,
1113 border_y + grid_height * j,
1114 border_x + grid_width * maze_size_x - 1,
1115 border_y + grid_height * (j+1) - 1);
1117 if ( maze[0][j] & WALL_LEFT ) {
1118 XDrawLine(dpy, win, gc,
1120 border_y + grid_height * j,
1122 border_y + grid_height * (j+1) - 1);
1130 unsigned int w, h, bw, d;
1132 /* round up to grid size */
1133 int ww = ((logo_width / grid_width) + 1) * grid_width;
1134 int hh = ((logo_height / grid_height) + 1) * grid_height;
1136 XGetGeometry (dpy, logo_map, &r, &x, &y, &w, &h, &bw, &d);
1138 XCopyPlane (dpy, logo_map, win, logo_gc,
1140 border_x + 3 + grid_width * logo_x + ((ww - w) / 2),
1141 border_y + 3 + grid_height * logo_y + ((hh - h) / 2),
1144 XCopyArea (dpy, logo_map, win, logo_gc,
1146 border_x + 3 + grid_width * logo_x + ((ww - w) / 2),
1147 border_y + 3 + grid_height * logo_y + ((hh - h) / 2));
1149 draw_solid_square (start_x, start_y, WALL_TOP >> start_dir, tgc);
1150 draw_solid_square (end_x, end_y, WALL_TOP >> end_dir, tgc);
1155 draw_wall(int i, int j, int dir, GC gc) /* draw a single wall */
1159 XDrawLine(dpy, win, gc,
1160 border_x + grid_width * i,
1161 border_y + grid_height * j,
1162 border_x + grid_width * (i+1),
1163 border_y + grid_height * j);
1166 XDrawLine(dpy, win, gc,
1167 border_x + grid_width * (i+1),
1168 border_y + grid_height * j,
1169 border_x + grid_width * (i+1),
1170 border_y + grid_height * (j+1));
1173 XDrawLine(dpy, win, gc,
1174 border_x + grid_width * i,
1175 border_y + grid_height * (j+1),
1176 border_x + grid_width * (i+1),
1177 border_y + grid_height * (j+1));
1180 XDrawLine(dpy, win, gc,
1181 border_x + grid_width * i,
1182 border_y + grid_height * j,
1183 border_x + grid_width * i,
1184 border_y + grid_height * (j+1));
1191 /* Actually build a wall. */
1193 build_wall(i, j, dir)
1196 /* Draw it on the screen. */
1197 draw_wall(i, j, dir, gc);
1198 /* Put it in the maze. */
1202 maze[i][j] |= WALL_TOP;
1204 maze[i][j-1] |= WALL_BOTTOM;
1207 maze[i][j] |= WALL_RIGHT;
1209 maze[i+1][j] |= WALL_LEFT;
1212 maze[i][j] |= WALL_BOTTOM;
1214 maze[i][j+1] |= WALL_TOP;
1217 maze[i][j] |= WALL_LEFT;
1219 maze[i-1][j] |= WALL_RIGHT;
1224 /* Break out a wall. */
1227 break_wall(i, j, dir)
1230 /* Draw it on the screen. */
1231 draw_wall(i, j, dir, erase_gc);
1232 /* Put it in the maze. */
1236 maze[i][j] &= ~WALL_TOP;
1238 maze[i][j-1] &= ~WALL_BOTTOM;
1241 maze[i][j] &= ~WALL_RIGHT;
1243 maze[i+1][j] &= ~WALL_LEFT;
1246 maze[i][j] &= ~WALL_BOTTOM;
1248 maze[i][j+1] &= ~WALL_BOTTOM;
1251 maze[i][j] &= ~WALL_LEFT;
1253 maze[i-1][j] &= ~WALL_RIGHT;
1261 draw_solid_square(int i, int j, /* draw a solid square in a square */
1266 XFillRectangle(dpy, win, gc,
1267 border_x + bw + grid_width * i,
1268 border_y - bw + grid_height * j,
1269 grid_width - (bw+bw), grid_height);
1272 XFillRectangle(dpy, win, gc,
1273 border_x + bw + grid_width * i,
1274 border_y + bw + grid_height * j,
1275 grid_width, grid_height - (bw+bw));
1278 XFillRectangle(dpy, win, gc,
1279 border_x + bw + grid_width * i,
1280 border_y + bw + grid_height * j,
1281 grid_width - (bw+bw), grid_height);
1284 XFillRectangle(dpy, win, gc,
1285 border_x - bw + grid_width * i,
1286 border_y + bw + grid_height * j,
1287 grid_width, grid_height - (bw+bw));
1294 longdeadend_p(int x1, int y1, int x2, int y2, int endwall)
1296 int dx = x2 - x1, dy = y2 - y1;
1299 sidewalls = endwall | (endwall >> 2 | endwall << 2);
1300 sidewalls = ~sidewalls & WALL_ANY;
1302 while((maze[x2][y2] & WALL_ANY) == sidewalls)
1308 if((maze[x2][y2] & WALL_ANY) == (sidewalls | endwall))
1310 endwall = (endwall >> 2 | endwall << 2) & WALL_ANY;
1311 while(x1 != x2 || y1 != y2)
1315 draw_solid_square(x1, y1, endwall, sgc);
1316 maze[x1][y1] |= SOLVER_VISIT;
1324 /* Find all dead regions -- areas from which the goal cannot be reached --
1325 and mark them visited. */
1327 find_dead_regions(void)
1331 /* Find all not SOLVER_VISIT squares bordering NOT_DEAD squares
1332 and mark them NOT_DEAD also. Repeat until no more such squares. */
1333 maze[start_x][start_y] |= NOT_DEAD;
1338 for(x = 0; x < maze_size_x; x++)
1339 for(y = 0; y < maze_size_y; y++)
1340 if(!(maze[x][y] & (SOLVER_VISIT | NOT_DEAD))
1341 && ( (x && (maze[x-1][y] & NOT_DEAD))
1342 || (y && (maze[x][y-1] & NOT_DEAD))))
1345 maze[x][y] |= NOT_DEAD;
1347 for(x = maze_size_x-1; x >= 0; x--)
1348 for(y = maze_size_y-1; y >= 0; y--)
1349 if(!(maze[x][y] & (SOLVER_VISIT | NOT_DEAD))
1350 && ( (x != maze_size_x-1 && (maze[x+1][y] & NOT_DEAD))
1351 || (y != maze_size_y-1 && (maze[x][y+1] & NOT_DEAD))))
1354 maze[x][y] |= NOT_DEAD;
1359 for (y = 0; y < maze_size_y; y++)
1360 for (x = 0; x < maze_size_x; x++)
1362 if (maze[x][y] & NOT_DEAD)
1363 maze[x][y] &= ~NOT_DEAD;
1364 else if (!(maze[x][y] & SOLVER_VISIT))
1366 maze[x][y] |= SOLVER_VISIT;
1367 if((x < logo_x || x > logo_x + logo_width / grid_width) ||
1368 (y < logo_y || y > logo_y + logo_height / grid_height))
1370 if (!maze[x][y] & WALL_ANY)
1371 XFillRectangle(dpy, win, ugc,
1372 border_x + bw + grid_width * x,
1373 border_y + bw + grid_height * y,
1374 grid_width - (bw+bw), grid_height - (bw+bw));
1377 if (! (maze[x][y] & WALL_LEFT))
1378 draw_solid_square(x, y, WALL_LEFT, ugc);
1379 if (! (maze[x][y] & WALL_RIGHT))
1380 draw_solid_square(x, y, WALL_RIGHT, ugc);
1381 if (! (maze[x][y] & WALL_TOP))
1382 draw_solid_square(x, y, WALL_TOP, ugc);
1383 if (! (maze[x][y] & WALL_BOTTOM))
1384 draw_solid_square(x, y, WALL_BOTTOM, ugc);
1393 solve_maze (void) /* solve it with graphical feedback */
1395 int i, dir, from, x, y, ways, bt = 0;
1397 /* plug up the surrounding wall */
1398 maze[end_x][end_y] |= (WALL_TOP >> end_dir);
1400 /* initialize search path */
1405 maze[end_x][end_y] |= SOLVER_VISIT;
1410 if ( maze[path[i].x][path[i].y] & START_SQUARE )
1413 /* Abort solve on expose - cheapo repaint strategy */
1414 if (check_events()) return;
1416 if (solve_delay) usleep (solve_delay);
1421 /* First visit this square. Which adjacent squares are open? */
1422 for(dir = WALL_TOP; dir & WALL_ANY; dir >>= 1)
1424 if(maze[path[i].x][path[i].y] & dir)
1427 y = path[i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1428 x = path[i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1430 if(maze[x][y] & SOLVER_VISIT)
1433 from = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1434 /* don't enter obvious dead ends */
1435 if(((maze[x][y] & WALL_ANY) | from) != WALL_ANY)
1437 if(!longdeadend_p(path[i].x, path[i].y, x, y, dir))
1442 draw_solid_square(x, y, from, sgc);
1443 maze[x][y] |= SOLVER_VISIT;
1448 ways = path[i].ways;
1449 /* ways now has a bitmask of open paths. */
1456 x = path[i].x - start_x;
1457 y = path[i].y - start_y;
1459 if(abs(y) <= abs(x))
1460 dir = (x > 0) ? WALL_LEFT : WALL_RIGHT;
1462 dir = (y > 0) ? WALL_TOP : WALL_BOTTOM;
1472 dir = (y > 0) ? WALL_TOP : WALL_BOTTOM; break;
1475 dir = (x > 0) ? WALL_LEFT : WALL_RIGHT;
1483 dir = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1498 else if(ways&WALL_LEFT)
1500 else if(ways&WALL_BOTTOM)
1502 else if(ways&WALL_RIGHT)
1508 ways &= ~dir; /* tried this one */
1510 y = path[i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1511 x = path[i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1513 /* advance in direction dir */
1515 path[i].ways = ways;
1516 draw_solid_square(path[i].x, path[i].y, dir, tgc);
1523 maze[x][y] |= SOLVER_VISIT;
1529 printf("Unsolvable maze.\n");
1533 if(!bt && !ignorant_p)
1534 find_dead_regions();
1536 from = path[i-1].dir;
1537 from = (from << 2 & WALL_ANY) | (from >> 2 & WALL_ANY);
1539 draw_solid_square(path[i].x, path[i].y, from, cgc);
1546 enter_square (int n) /* move into a neighboring square */
1548 draw_solid_square( (int)path[n].x, (int)path[n].y,
1549 (int)path[n].dir, tgc);
1552 switch (path[n].dir) {
1553 case 0: path[n+1].x = path[n].x;
1554 path[n+1].y = path[n].y - 1;
1556 case 1: path[n+1].x = path[n].x + 1;
1557 path[n+1].y = path[n].y;
1559 case 2: path[n+1].x = path[n].x;
1560 path[n+1].y = path[n].y + 1;
1562 case 3: path[n+1].x = path[n].x - 1;
1563 path[n+1].y = path[n].y;
1571 * jmr additions for Jamie Zawinski's <jwz@jwz.org> screensaver stuff,
1572 * note that the code above this has probably been hacked about in some
1576 char *progclass = "Maze";
1578 char *defaults[] = {
1579 ".background: black",
1580 ".foreground: white",
1582 "*solveDelay: 5000",
1583 "*preDelay: 2000000",
1584 "*postDelay: 4000000",
1585 "*liveColor: green",
1587 "*skipColor: orange",
1588 "*surroundColor: slateblue",
1596 XrmOptionDescRec options[] = {
1597 { "-ignorant", ".ignorant", XrmoptionNoArg, "True" },
1598 { "-no-ignorant", ".ignorant", XrmoptionNoArg, "False" },
1599 { "-grid-size", ".gridSize", XrmoptionSepArg, 0 },
1600 { "-solve-delay", ".solveDelay", XrmoptionSepArg, 0 },
1601 { "-pre-delay", ".preDelay", XrmoptionSepArg, 0 },
1602 { "-post-delay", ".postDelay", XrmoptionSepArg, 0 },
1603 { "-live-color", ".liveColor", XrmoptionSepArg, 0 },
1604 { "-dead-color", ".deadColor", XrmoptionSepArg, 0 },
1605 { "-skip-color", ".skipColor", XrmoptionSepArg, 0 },
1606 { "-surround-color", ".surroundColor",XrmoptionSepArg, 0 },
1607 { "-generator", ".generator", XrmoptionSepArg, 0 },
1608 { "-max-length", ".maxLength", XrmoptionSepArg, 0 },
1609 { "-bridge", ".bridge", XrmoptionNoArg, "True" },
1610 { "-no-bridge", ".bridge", XrmoptionNoArg, "False" },
1615 screenhack(Display *display, Window window)
1618 int size, root, generator, this_gen;
1619 XWindowAttributes xgwa;
1620 unsigned long bg, fg, pfg, pbg, sfg, ufg;
1622 size = get_integer_resource ("gridSize", "Dimension");
1623 root = get_boolean_resource("root", "Boolean");
1624 solve_delay = get_integer_resource ("solveDelay", "Integer");
1625 pre_solve_delay = get_integer_resource ("preDelay", "Integer");
1626 post_solve_delay = get_integer_resource ("postDelay", "Integer");
1627 generator = get_integer_resource("generator", "Integer");
1628 max_length = get_integer_resource("maxLength", "Integer");
1629 bridge_p = get_boolean_resource("bridge", "Boolean");
1630 ignorant_p = get_boolean_resource("ignorant", "Boolean");
1632 if (size < 2) size = 7 + (random () % 30);
1633 grid_width = grid_height = size;
1634 bw = (size > 6 ? 3 : (size-1)/2);
1636 dpy = display; win = window; /* the maze stuff uses global variables */
1638 XGetWindowAttributes (dpy, win, &xgwa);
1643 set_maze_sizes (xgwa.width, xgwa.height);
1647 XWindowAttributes xgwa;
1648 XGetWindowAttributes (dpy, window, &xgwa);
1649 XSelectInput (dpy, win,
1650 xgwa.your_event_mask | ExposureMask |
1651 ButtonPressMask |StructureNotifyMask);
1654 gc = XCreateGC(dpy, win, 0, 0);
1655 cgc = XCreateGC(dpy, win, 0, 0);
1656 tgc = XCreateGC(dpy, win, 0, 0);
1657 sgc = XCreateGC(dpy, win, 0, 0);
1658 ugc = XCreateGC(dpy, win, 0, 0);
1659 logo_gc = XCreateGC(dpy, win, 0, 0);
1660 erase_gc = XCreateGC(dpy, win, 0, 0);
1662 gray = XCreateBitmapFromData (dpy,win,gray1_bits,gray1_width,gray1_height);
1664 bg = get_pixel_resource ("background","Background", dpy, xgwa.colormap);
1665 fg = get_pixel_resource ("foreground","Foreground", dpy, xgwa.colormap);
1666 pfg = get_pixel_resource ("liveColor", "Foreground", dpy, xgwa.colormap);
1667 pbg = get_pixel_resource ("deadColor", "Foreground", dpy, xgwa.colormap);
1668 sfg = get_pixel_resource ("skipColor", "Foreground", dpy, xgwa.colormap);
1669 ufg = get_pixel_resource ("surroundColor", "Foreground", dpy, xgwa.colormap);
1671 XSetForeground (dpy, gc, fg);
1672 XSetBackground (dpy, gc, bg);
1673 XSetForeground (dpy, cgc, pbg);
1674 XSetBackground (dpy, cgc, bg);
1675 XSetForeground (dpy, tgc, pfg);
1676 XSetBackground (dpy, tgc, bg);
1677 XSetForeground (dpy, sgc, sfg);
1678 XSetBackground (dpy, sgc, bg);
1679 XSetForeground (dpy, ugc, ufg);
1680 XSetBackground (dpy, ugc, bg);
1681 XSetForeground (dpy, logo_gc, fg);
1682 XSetBackground (dpy, logo_gc, bg);
1683 XSetForeground (dpy, erase_gc, bg);
1684 XSetBackground (dpy, erase_gc, bg);
1686 XSetStipple (dpy, cgc, gray);
1687 XSetFillStyle (dpy, cgc, FillOpaqueStippled);
1688 XSetStipple (dpy, sgc, gray);
1689 XSetFillStyle (dpy, sgc, FillOpaqueStippled);
1690 XSetStipple (dpy, ugc, gray);
1691 XSetFillStyle (dpy, ugc, FillOpaqueStippled);
1693 #ifdef XSCREENSAVER_LOGO
1695 unsigned long *pixels; /* ignored - unfreed */
1697 logo_map = xscreensaver_logo (dpy, win, xgwa.colormap, bg,
1702 if (!(logo_map = XCreateBitmapFromData (dpy, win, logo_bits,
1703 logo_width, logo_height)))
1705 fprintf (stderr, "Can't create logo pixmap\n");
1709 XMapRaised(dpy, win);
1713 sync_p = !(random() % 10);
1715 while (1) { /* primary execution loop [ rhess ] */
1716 if (check_events()) continue ;
1717 if (restart || stop) goto pop;
1723 XClearWindow(dpy, win);
1727 this_gen = generator;
1728 if(this_gen<0 || this_gen>2)
1729 this_gen = random()%3;
1746 usleep (pre_solve_delay);
1753 usleep (post_solve_delay);
1755 erase_full_window(display, window);
1764 static XWindowAttributes wattr;
1768 XGetWindowAttributes (dpy, win, &wattr);
1769 set_maze_sizes (wattr.width, wattr.height);
1770 XClearWindow (dpy, win);
1772 sync_p = !(random() % 10);