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 128
138 # define logo_height 128
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;
1131 XGetGeometry (dpy, logo_map, &r, &x, &y, &w, &h, &bw, &d);
1133 XCopyPlane (dpy, logo_map, win, logo_gc,
1135 border_x + 3 + grid_width * logo_x,
1136 border_y + 3 + grid_height * logo_y, 1);
1138 XCopyArea (dpy, logo_map, win, logo_gc,
1140 border_x + 3 + grid_width * logo_x,
1141 border_y + 3 + grid_height * logo_y);
1143 draw_solid_square (start_x, start_y, WALL_TOP >> start_dir, tgc);
1144 draw_solid_square (end_x, end_y, WALL_TOP >> end_dir, tgc);
1149 draw_wall(int i, int j, int dir, GC gc) /* draw a single wall */
1153 XDrawLine(dpy, win, gc,
1154 border_x + grid_width * i,
1155 border_y + grid_height * j,
1156 border_x + grid_width * (i+1),
1157 border_y + grid_height * j);
1160 XDrawLine(dpy, win, gc,
1161 border_x + grid_width * (i+1),
1162 border_y + grid_height * j,
1163 border_x + grid_width * (i+1),
1164 border_y + grid_height * (j+1));
1167 XDrawLine(dpy, win, gc,
1168 border_x + grid_width * i,
1169 border_y + grid_height * (j+1),
1170 border_x + grid_width * (i+1),
1171 border_y + grid_height * (j+1));
1174 XDrawLine(dpy, win, gc,
1175 border_x + grid_width * i,
1176 border_y + grid_height * j,
1177 border_x + grid_width * i,
1178 border_y + grid_height * (j+1));
1185 /* Actually build a wall. */
1187 build_wall(i, j, dir)
1190 /* Draw it on the screen. */
1191 draw_wall(i, j, dir, gc);
1192 /* Put it in the maze. */
1196 maze[i][j] |= WALL_TOP;
1198 maze[i][j-1] |= WALL_BOTTOM;
1201 maze[i][j] |= WALL_RIGHT;
1203 maze[i+1][j] |= WALL_LEFT;
1206 maze[i][j] |= WALL_BOTTOM;
1208 maze[i][j+1] |= WALL_TOP;
1211 maze[i][j] |= WALL_LEFT;
1213 maze[i-1][j] |= WALL_RIGHT;
1218 /* Break out a wall. */
1221 break_wall(i, j, dir)
1224 /* Draw it on the screen. */
1225 draw_wall(i, j, dir, erase_gc);
1226 /* Put it in the maze. */
1230 maze[i][j] &= ~WALL_TOP;
1232 maze[i][j-1] &= ~WALL_BOTTOM;
1235 maze[i][j] &= ~WALL_RIGHT;
1237 maze[i+1][j] &= ~WALL_LEFT;
1240 maze[i][j] &= ~WALL_BOTTOM;
1242 maze[i][j+1] &= ~WALL_BOTTOM;
1245 maze[i][j] &= ~WALL_LEFT;
1247 maze[i-1][j] &= ~WALL_RIGHT;
1255 draw_solid_square(int i, int j, /* draw a solid square in a square */
1260 XFillRectangle(dpy, win, gc,
1261 border_x + bw + grid_width * i,
1262 border_y - bw + grid_height * j,
1263 grid_width - (bw+bw), grid_height);
1266 XFillRectangle(dpy, win, gc,
1267 border_x + bw + grid_width * i,
1268 border_y + bw + grid_height * j,
1269 grid_width, grid_height - (bw+bw));
1272 XFillRectangle(dpy, win, gc,
1273 border_x + bw + grid_width * i,
1274 border_y + bw + grid_height * j,
1275 grid_width - (bw+bw), grid_height);
1278 XFillRectangle(dpy, win, gc,
1279 border_x - bw + grid_width * i,
1280 border_y + bw + grid_height * j,
1281 grid_width, grid_height - (bw+bw));
1288 longdeadend_p(int x1, int y1, int x2, int y2, int endwall)
1290 int dx = x2 - x1, dy = y2 - y1;
1293 sidewalls = endwall | (endwall >> 2 | endwall << 2);
1294 sidewalls = ~sidewalls & WALL_ANY;
1296 while((maze[x2][y2] & WALL_ANY) == sidewalls)
1302 if((maze[x2][y2] & WALL_ANY) == (sidewalls | endwall))
1304 endwall = (endwall >> 2 | endwall << 2) & WALL_ANY;
1305 while(x1 != x2 || y1 != y2)
1309 draw_solid_square(x1, y1, endwall, sgc);
1310 maze[x1][y1] |= SOLVER_VISIT;
1318 /* Find all dead regions -- areas from which the goal cannot be reached --
1319 and mark them visited. */
1321 find_dead_regions(void)
1325 /* Find all not SOLVER_VISIT squares bordering NOT_DEAD squares
1326 and mark them NOT_DEAD also. Repeat until no more such squares. */
1327 maze[start_x][start_y] |= NOT_DEAD;
1332 for(x = 0; x < maze_size_x; x++)
1333 for(y = 0; y < maze_size_y; y++)
1334 if(!(maze[x][y] & (SOLVER_VISIT | NOT_DEAD))
1335 && ( (x && (maze[x-1][y] & NOT_DEAD))
1336 || (y && (maze[x][y-1] & NOT_DEAD))))
1339 maze[x][y] |= NOT_DEAD;
1341 for(x = maze_size_x-1; x >= 0; x--)
1342 for(y = maze_size_y-1; y >= 0; y--)
1343 if(!(maze[x][y] & (SOLVER_VISIT | NOT_DEAD))
1344 && ( (x != maze_size_x-1 && (maze[x+1][y] & NOT_DEAD))
1345 || (y != maze_size_y-1 && (maze[x][y+1] & NOT_DEAD))))
1348 maze[x][y] |= NOT_DEAD;
1353 for (y = 0; y < maze_size_y; y++)
1354 for (x = 0; x < maze_size_x; x++)
1356 if (maze[x][y] & NOT_DEAD)
1357 maze[x][y] &= ~NOT_DEAD;
1358 else if (!(maze[x][y] & SOLVER_VISIT))
1360 maze[x][y] |= SOLVER_VISIT;
1361 if((x < logo_x || x > logo_x + logo_width / grid_width) ||
1362 (y < logo_y || y > logo_y + logo_height / grid_height))
1364 if (!maze[x][y] & WALL_ANY)
1365 XFillRectangle(dpy, win, ugc,
1366 border_x + bw + grid_width * x,
1367 border_y + bw + grid_height * y,
1368 grid_width - (bw+bw), grid_height - (bw+bw));
1371 if (! (maze[x][y] & WALL_LEFT))
1372 draw_solid_square(x, y, WALL_LEFT, ugc);
1373 if (! (maze[x][y] & WALL_RIGHT))
1374 draw_solid_square(x, y, WALL_RIGHT, ugc);
1375 if (! (maze[x][y] & WALL_TOP))
1376 draw_solid_square(x, y, WALL_TOP, ugc);
1377 if (! (maze[x][y] & WALL_BOTTOM))
1378 draw_solid_square(x, y, WALL_BOTTOM, ugc);
1387 solve_maze (void) /* solve it with graphical feedback */
1389 int i, dir, from, x, y, ways, bt = 0;
1391 /* plug up the surrounding wall */
1392 maze[end_x][end_y] |= (WALL_TOP >> end_dir);
1394 /* initialize search path */
1399 maze[end_x][end_y] |= SOLVER_VISIT;
1404 if ( maze[path[i].x][path[i].y] & START_SQUARE )
1407 /* Abort solve on expose - cheapo repaint strategy */
1408 if (check_events()) return;
1410 if (solve_delay) usleep (solve_delay);
1415 /* First visit this square. Which adjacent squares are open? */
1416 for(dir = WALL_TOP; dir & WALL_ANY; dir >>= 1)
1418 if(maze[path[i].x][path[i].y] & dir)
1421 y = path[i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1422 x = path[i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1424 if(maze[x][y] & SOLVER_VISIT)
1427 from = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1428 /* don't enter obvious dead ends */
1429 if(((maze[x][y] & WALL_ANY) | from) != WALL_ANY)
1431 if(!longdeadend_p(path[i].x, path[i].y, x, y, dir))
1436 draw_solid_square(x, y, from, sgc);
1437 maze[x][y] |= SOLVER_VISIT;
1442 ways = path[i].ways;
1443 /* ways now has a bitmask of open paths. */
1450 x = path[i].x - start_x;
1451 y = path[i].y - start_y;
1453 if(abs(y) <= abs(x))
1454 dir = (x > 0) ? WALL_LEFT : WALL_RIGHT;
1456 dir = (y > 0) ? WALL_TOP : WALL_BOTTOM;
1466 dir = (y > 0) ? WALL_TOP : WALL_BOTTOM; break;
1469 dir = (x > 0) ? WALL_LEFT : WALL_RIGHT;
1477 dir = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1492 else if(ways&WALL_LEFT)
1494 else if(ways&WALL_BOTTOM)
1496 else if(ways&WALL_RIGHT)
1502 ways &= ~dir; /* tried this one */
1504 y = path[i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1505 x = path[i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1507 /* advance in direction dir */
1509 path[i].ways = ways;
1510 draw_solid_square(path[i].x, path[i].y, dir, tgc);
1517 maze[x][y] |= SOLVER_VISIT;
1523 printf("Unsolvable maze.\n");
1527 if(!bt && !ignorant_p)
1528 find_dead_regions();
1530 from = path[i-1].dir;
1531 from = (from << 2 & WALL_ANY) | (from >> 2 & WALL_ANY);
1533 draw_solid_square(path[i].x, path[i].y, from, cgc);
1540 enter_square (int n) /* move into a neighboring square */
1542 draw_solid_square( (int)path[n].x, (int)path[n].y,
1543 (int)path[n].dir, tgc);
1546 switch (path[n].dir) {
1547 case 0: path[n+1].x = path[n].x;
1548 path[n+1].y = path[n].y - 1;
1550 case 1: path[n+1].x = path[n].x + 1;
1551 path[n+1].y = path[n].y;
1553 case 2: path[n+1].x = path[n].x;
1554 path[n+1].y = path[n].y + 1;
1556 case 3: path[n+1].x = path[n].x - 1;
1557 path[n+1].y = path[n].y;
1565 * jmr additions for Jamie Zawinski's <jwz@jwz.org> screensaver stuff,
1566 * note that the code above this has probably been hacked about in some
1570 char *progclass = "Maze";
1572 char *defaults[] = {
1573 ".background: black",
1574 ".foreground: white",
1576 "*solveDelay: 5000",
1577 "*preDelay: 2000000",
1578 "*postDelay: 4000000",
1579 "*liveColor: green",
1581 "*skipColor: orange",
1582 "*surroundColor: slateblue",
1590 XrmOptionDescRec options[] = {
1591 { "-ignorant", ".ignorant", XrmoptionNoArg, "True" },
1592 { "-no-ignorant", ".ignorant", XrmoptionNoArg, "False" },
1593 { "-grid-size", ".gridSize", XrmoptionSepArg, 0 },
1594 { "-solve-delay", ".solveDelay", XrmoptionSepArg, 0 },
1595 { "-pre-delay", ".preDelay", XrmoptionSepArg, 0 },
1596 { "-post-delay", ".postDelay", XrmoptionSepArg, 0 },
1597 { "-live-color", ".liveColor", XrmoptionSepArg, 0 },
1598 { "-dead-color", ".deadColor", XrmoptionSepArg, 0 },
1599 { "-skip-color", ".skipColor", XrmoptionSepArg, 0 },
1600 { "-surround-color", ".surroundColor",XrmoptionSepArg, 0 },
1601 { "-generator", ".generator", XrmoptionSepArg, 0 },
1602 { "-max-length", ".maxLength", XrmoptionSepArg, 0 },
1603 { "-bridge", ".bridge", XrmoptionNoArg, "True" },
1604 { "-no-bridge", ".bridge", XrmoptionNoArg, "False" },
1608 #ifdef XSCREENSAVER_LOGO
1609 extern void xscreensaver_logo (Display *,Drawable,Colormap, Bool next_frame_p);
1613 screenhack(Display *display, Window window)
1616 int size, root, generator, this_gen;
1617 XWindowAttributes xgwa;
1618 unsigned long bg, fg, pfg, pbg, sfg, ufg;
1620 size = get_integer_resource ("gridSize", "Dimension");
1621 root = get_boolean_resource("root", "Boolean");
1622 solve_delay = get_integer_resource ("solveDelay", "Integer");
1623 pre_solve_delay = get_integer_resource ("preDelay", "Integer");
1624 post_solve_delay = get_integer_resource ("postDelay", "Integer");
1625 generator = get_integer_resource("generator", "Integer");
1626 max_length = get_integer_resource("maxLength", "Integer");
1627 bridge_p = get_boolean_resource("bridge", "Boolean");
1628 ignorant_p = get_boolean_resource("ignorant", "Boolean");
1630 if (size < 2) size = 7 + (random () % 30);
1631 grid_width = grid_height = size;
1632 bw = (size > 6 ? 3 : (size-1)/2);
1634 dpy = display; win = window; /* the maze stuff uses global variables */
1636 XGetWindowAttributes (dpy, win, &xgwa);
1641 set_maze_sizes (xgwa.width, xgwa.height);
1645 XWindowAttributes xgwa;
1646 XGetWindowAttributes (dpy, window, &xgwa);
1647 XSelectInput (dpy, win,
1648 xgwa.your_event_mask | ExposureMask |
1649 ButtonPressMask |StructureNotifyMask);
1652 gc = XCreateGC(dpy, win, 0, 0);
1653 cgc = XCreateGC(dpy, win, 0, 0);
1654 tgc = XCreateGC(dpy, win, 0, 0);
1655 sgc = XCreateGC(dpy, win, 0, 0);
1656 ugc = XCreateGC(dpy, win, 0, 0);
1657 logo_gc = XCreateGC(dpy, win, 0, 0);
1658 erase_gc = XCreateGC(dpy, win, 0, 0);
1660 gray = XCreateBitmapFromData (dpy,win,gray1_bits,gray1_width,gray1_height);
1662 bg = get_pixel_resource ("background","Background", dpy, xgwa.colormap);
1663 fg = get_pixel_resource ("foreground","Foreground", dpy, xgwa.colormap);
1664 pfg = get_pixel_resource ("liveColor", "Foreground", dpy, xgwa.colormap);
1665 pbg = get_pixel_resource ("deadColor", "Foreground", dpy, xgwa.colormap);
1666 sfg = get_pixel_resource ("skipColor", "Foreground", dpy, xgwa.colormap);
1667 ufg = get_pixel_resource ("surroundColor", "Foreground", dpy, xgwa.colormap);
1669 XSetForeground (dpy, gc, fg);
1670 XSetBackground (dpy, gc, bg);
1671 XSetForeground (dpy, cgc, pbg);
1672 XSetBackground (dpy, cgc, bg);
1673 XSetForeground (dpy, tgc, pfg);
1674 XSetBackground (dpy, tgc, bg);
1675 XSetForeground (dpy, sgc, sfg);
1676 XSetBackground (dpy, sgc, bg);
1677 XSetForeground (dpy, ugc, ufg);
1678 XSetBackground (dpy, ugc, bg);
1679 XSetForeground (dpy, logo_gc, fg);
1680 XSetBackground (dpy, logo_gc, bg);
1681 XSetForeground (dpy, erase_gc, bg);
1682 XSetBackground (dpy, erase_gc, bg);
1684 XSetStipple (dpy, cgc, gray);
1685 XSetFillStyle (dpy, cgc, FillOpaqueStippled);
1686 XSetStipple (dpy, sgc, gray);
1687 XSetFillStyle (dpy, sgc, FillOpaqueStippled);
1688 XSetStipple (dpy, ugc, gray);
1689 XSetFillStyle (dpy, ugc, FillOpaqueStippled);
1691 #ifdef XSCREENSAVER_LOGO
1694 /* round up to grid size */
1695 w = ((logo_width / grid_width) + 1) * grid_width;
1696 h = ((logo_height / grid_height) + 1) * grid_height;
1697 logo_map = XCreatePixmap (dpy, win, w, h, xgwa.depth);
1698 xscreensaver_logo (dpy, logo_map, xgwa.colormap, False);
1701 if (!(logo_map = XCreateBitmapFromData (dpy, win, logo_bits,
1702 logo_width, logo_height)))
1704 fprintf (stderr, "Can't create logo pixmap\n");
1708 XMapRaised(dpy, win);
1712 sync_p = !(random() % 10);
1714 while (1) { /* primary execution loop [ rhess ] */
1715 if (check_events()) continue ;
1716 if (restart || stop) goto pop;
1722 XClearWindow(dpy, win);
1726 this_gen = generator;
1727 if(this_gen<0 || this_gen>2)
1728 this_gen = random()%3;
1745 usleep (pre_solve_delay);
1752 usleep (post_solve_delay);
1754 erase_full_window(display, window);
1763 static XWindowAttributes wattr;
1767 XGetWindowAttributes (dpy, win, &wattr);
1768 set_maze_sizes (wattr.width, wattr.height);
1769 XClearWindow (dpy, win);
1771 sync_p = !(random() % 10);