1 /******************************************************************************
4 * modified: [ 6-28-98 ] Zack Weinberg <zack@rabi.phys.columbia.edu>
6 * Made the maze-solver somewhat more intelligent. There are
9 * - Straight-line lookahead: the solver does not enter dead-end
10 * corridors. This is a win with all maze generators.
12 * - First order direction choice: the solver knows where the
13 * exit is in relation to itself, and will try paths leading in
14 * that direction first. This is a major win on maze generator 1
15 * which tends to offer direct routes to the exit.
17 * - Dead region elimination: the solver already has a map of
18 * all squares visited. Whenever it starts to backtrack, it
19 * consults this map and marks off all squares that cannot be
20 * reached from the exit without crossing a square already
21 * visited. Those squares can never contribute to the path to
22 * the exit, so it doesn't bother checking them. This helps a
23 * lot with maze generator 2 and somewhat less with generator 1.
25 * Further improvements would require knowledge of the wall map
26 * as well as the position of the exit and the squares visited.
27 * I would consider that to be cheating. Generator 0 makes
28 * mazes which are remarkably difficult to solve mechanically --
29 * even with these optimizations the solver generally must visit
30 * at least two-thirds of the squares. This is partially
31 * because generator 0's mazes have longer paths to the exit.
33 * modified: [ 4-10-97 ] Johannes Keukelaar <johannes@nada.kth.se>
34 * Added multiple maze creators. Robustified solver.
35 * Added bridge option.
36 * modified: [ 8-11-95 ] Ed James <james@mml.mmc.com>
37 * added fill of dead-end box to solve_maze while loop.
38 * modified: [ 3-7-93 ] Jamie Zawinski <jwz@netscape.com>
39 * added the XRoger logo, cleaned up resources, made
40 * grid size a parameter.
41 * modified: [ 3-3-93 ] Jim Randell <jmr@mddjmr.fc.hp.com>
42 * Added the colour stuff and integrated it with jwz's
43 * screenhack stuff. There's still some work that could
44 * be done on this, particularly allowing a resource to
45 * specify how big the squares are.
46 * modified: [ 10-4-88 ] Richard Hess ...!uunet!cimshop!rhess
47 * [ Revised primary execution loop within main()...
48 * [ Extended X event handler, check_events()...
49 * modified: [ 1-29-88 ] Dave Lemke lemke@sun.com
51 * [ Note the word "hacked" -- this is extremely ugly, but at
52 * [ least it does the job. NOT a good programming example
54 * original: [ 6/21/85 ] Martin Weiss Sun Microsystems [ SunView ]
56 ******************************************************************************
57 Copyright 1988 by Sun Microsystems, Inc. Mountain View, CA.
61 Permission to use, copy, modify, and distribute this software and its
62 documentation for any purpose and without fee is hereby granted,
63 provided that the above copyright notice appear in all copies and that
64 both that copyright notice and this permission notice appear in
65 supporting documentation, and that the names of Sun or MIT not be
66 used in advertising or publicity pertaining to distribution of the
67 software without specific prior written permission. Sun and M.I.T.
68 make no representations about the suitability of this software for
69 any purpose. It is provided "as is" without any express or implied warranty.
71 SUN DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
72 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
73 PURPOSE. IN NO EVENT SHALL SUN BE LIABLE FOR ANY SPECIAL, INDIRECT
74 OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
75 OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
76 OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE
77 OR PERFORMANCE OF THIS SOFTWARE.
78 *****************************************************************************/
80 #include "screenhack.h"
85 static int solve_delay, pre_solve_delay, post_solve_delay;
89 #include <X11/Xutil.h>
91 # include <X11/bitmaps/gray1>
93 # include "sys$common:[decw$include.bitmaps]gray1.xbm"
96 #define MAX_MAZE_SIZE_X 500
97 #define MAX_MAZE_SIZE_Y 500
99 #define MOVE_LIST_SIZE (MAX_MAZE_SIZE_X * MAX_MAZE_SIZE_Y)
101 #define NOT_DEAD 0x8000
102 #define SOLVER_VISIT 0x4000
103 #define START_SQUARE 0x2000
104 #define END_SQUARE 0x1000
107 #define WALL_RIGHT 0x4
108 #define WALL_BOTTOM 0x2
109 #define WALL_LEFT 0x1
112 #define DOOR_IN_TOP 0x800
113 #define DOOR_IN_RIGHT 0x400
114 #define DOOR_IN_BOTTOM 0x200
115 #define DOOR_IN_LEFT 0x100
116 #define DOOR_IN_ANY 0xF00
118 #define DOOR_OUT_TOP 0x80
119 #define DOOR_OUT_RIGHT 0x40
120 #define DOOR_OUT_BOTTOM 0x20
121 #define DOOR_OUT_LEFT 0x10
127 #define get_random(x) (random() % (x))
130 static int logo_x, logo_y;
133 # define logo_width 128
134 # define logo_height 128
136 # include <X11/bitmaps/xlogo64>
137 # define logo_width xlogo64_width
138 # define logo_height xlogo64_height
139 # define logo_bits xlogo64_bits
142 static unsigned short maze[MAX_MAZE_SIZE_X][MAX_MAZE_SIZE_Y];
147 unsigned char dir, ways;
148 } move_list[MOVE_LIST_SIZE], save_path[MOVE_LIST_SIZE], path[MOVE_LIST_SIZE];
150 static int maze_size_x, maze_size_y;
151 static int sqnum, cur_sq_x, cur_sq_y, path_length;
152 static int start_x, start_y, start_dir, end_x, end_y, end_dir;
153 static int grid_width, grid_height;
158 static GC gc, cgc, tgc, sgc, ugc, logo_gc, erase_gc;
159 static Pixmap logo_map;
161 static int x = 0, y = 0, restart = 0, stop = 1, state = 1, max_length;
162 static int sync_p, bridge_p;
165 check_events (void) /* X event handler [ rhess ] */
174 switch (e.xbutton.button) {
180 if (state == 5) state = 4 ;
193 case ConfigureNotify:
198 XClearWindow (dpy, win);
212 set_maze_sizes (int width, int height)
214 maze_size_x = width / grid_width;
215 maze_size_y = height / grid_height;
220 initialize_maze (void) /* draw the surrounding wall and start/end squares */
222 register int i, j, wall;
223 int logow = 1 + logo_width / grid_width;
224 int logoh = 1 + logo_height / grid_height;
226 /* initialize all squares */
227 for ( i=0; i<maze_size_x; i++) {
228 for ( j=0; j<maze_size_y; j++) {
234 for ( i=0; i<maze_size_x; i++ ) {
235 maze[i][0] |= WALL_TOP;
239 for ( j=0; j<maze_size_y; j++ ) {
240 maze[maze_size_x-1][j] |= WALL_RIGHT;
244 for ( i=0; i<maze_size_x; i++ ) {
245 maze[i][maze_size_y-1] |= WALL_BOTTOM;
249 for ( j=0; j<maze_size_y; j++ ) {
250 maze[0][j] |= WALL_LEFT;
253 /* set start square */
254 wall = get_random(4);
257 i = get_random(maze_size_x);
262 j = get_random(maze_size_y);
265 i = get_random(maze_size_x);
270 j = get_random(maze_size_y);
273 maze[i][j] |= START_SQUARE;
274 maze[i][j] |= ( DOOR_IN_TOP >> wall );
275 maze[i][j] &= ~( WALL_TOP >> wall );
287 i = get_random(maze_size_x);
292 j = get_random(maze_size_y);
295 i = get_random(maze_size_x);
300 j = get_random(maze_size_y);
303 maze[i][j] |= END_SQUARE;
304 maze[i][j] |= ( DOOR_OUT_TOP >> wall );
305 maze[i][j] &= ~( WALL_TOP >> wall );
311 if ((maze_size_x-logow >= 6) && (maze_size_y-logoh >= 6))
313 /* not closer than 3 grid units from a wall */
314 logo_x = get_random (maze_size_x - logow - 5) + 3;
315 logo_y = get_random (maze_size_y - logoh - 5) + 3;
316 for (i=0; i<logow; i++)
317 for (j=0; j<logoh; j++)
318 maze[logo_x + i][logo_y + j] |= DOOR_IN_TOP;
321 logo_y = logo_x = -1;
324 static int choose_door (void);
325 static int backup (void);
326 static void draw_wall (int, int, int, GC);
327 static void draw_solid_square (int, int, int, GC);
328 /*static void enter_square (int);*/
329 static void build_wall (int, int, int);
330 /*static void break_wall (int, int, int);*/
332 static void join_sets(int, int);
334 /* For set_create_maze. */
335 /* The sets that our squares are in. */
336 static int *sets = 0;
337 /* The `list' of hedges. */
338 static int *hedges = 0;
342 /* Initialise the sets. */
350 sets = (int *)malloc(maze_size_x*maze_size_y*sizeof(int));
353 for(i = 0; i < maze_size_x*maze_size_y; i++)
360 hedges = (int *)malloc(maze_size_x*maze_size_y*2*sizeof(int));
363 for(i = 0; i < maze_size_x*maze_size_y*2; i++)
367 /* Mask out outside walls. */
368 for(i = 0; i < maze_size_y; i++)
370 hedges[2*((maze_size_x)*i+maze_size_x-1)+1] = -1;
372 for(i = 0; i < maze_size_x; i++)
374 hedges[2*((maze_size_y-1)*maze_size_x+i)] = -1;
376 /* Mask out a possible logo. */
379 int logow = 1 + logo_width / grid_width;
380 int logoh = 1 + logo_height / grid_height;
381 int bridge_dir, bridge_c;
383 if(bridge_p && logoh>=3 && logow>=3)
385 bridge_dir = 1+random()%2;
388 bridge_c = logo_y+random()%(logoh-2)+1;
392 bridge_c = logo_x+random()%(logow-2)+1;
401 for(x = logo_x; x < logo_x+logow; x++)
402 for(y = logo_y; y < logo_y+logoh; y++)
404 /* I should check for the bridge here, except that I join the
405 * bridge together below.
407 hedges[2*(x+maze_size_x*y)+1] = -1;
408 hedges[2*(x+maze_size_x*y)] = -1;
410 for(x = logo_x; x < logo_x+logow; x++)
412 if(!(bridge_dir==2 && x==bridge_c))
414 build_wall(x, logo_y, 0);
415 build_wall(x, logo_y+logoh, 0);
417 hedges[2*(x+maze_size_x*(logo_y-1))] = -1;
420 build_wall(x, bridge_c, 0);
421 build_wall(x, bridge_c, 2);
424 for(y = logo_y; y < logo_y+logoh; y++)
426 if(!(bridge_dir==1 && y==bridge_c))
428 build_wall(logo_x, y, 3);
429 build_wall(logo_x+logow, y, 3);
431 hedges[2*(logo_x-1+maze_size_x*y)+1] = -1;
434 build_wall(bridge_c, y, 1);
435 build_wall(bridge_c, y, 3);
438 /* Join the whole bridge together. */
445 for(i = logo_x; i < logo_x+logow+1; i++)
446 join_sets(x+y*maze_size_x, i+y*maze_size_x);
452 for(i = logo_y; i < logo_y+logoh+1; i++)
453 join_sets(x+y*maze_size_x, x+i*maze_size_x);
458 for(i = 0; i < maze_size_x*maze_size_y*2; i++)
461 r = random()%(maze_size_x*maze_size_y*2);
462 hedges[i] = hedges[r];
467 /* Get the representative of a set. */
477 s = get_set(sets[num]);
483 /* Join two sets together. */
485 join_sets(num1, num2)
499 /* Exitialise the sets. */
512 /* Temporary hack. */
514 show_set(int num, GC gc)
520 for(x = 0; x < maze_size_x; x++)
521 for(y = 0; y < maze_size_y; y++)
523 if(get_set(x+y*maze_size_x)==set)
525 XFillRectangle(dpy, win, gc, border_x + bw + grid_width * x,
526 border_y + bw + grid_height * y,
527 grid_width-2*bw , grid_height-2*bw);
533 /* Second alternative maze creator: Put each square in the maze in a
534 * separate set. Also, make a list of all the hedges. Randomize that list.
535 * Walk through the list. If, for a certain hedge, the two squares on both
536 * sides of it are in different sets, union the sets and remove the hedge.
537 * Continue until all hedges have been processed or only one set remains.
540 set_create_maze(void)
542 int i, h, x, y, dir, v, w;
548 /* Do almost all the setup. */
551 /* Start running through the hedges. */
552 for(i = 0; i < 2*maze_size_x*maze_size_y; i++)
556 /* This one is in the logo or outside border. */
561 x = (h>>1)%maze_size_x;
562 y = (h>>1)/maze_size_x;
577 show_set(x+y*maze_size_x, logo_gc);
578 show_set(v+w*maze_size_x, tgc);
580 if(get_set(x+y*maze_size_x)!=get_set(v+w*maze_size_x))
585 join_sets(x+y*maze_size_x, v+w*maze_size_x);
586 /* Don't draw the wall. */
593 /* Don't join the sets. */
594 build_wall(x, y, dir);
604 show_set(x+y*maze_size_x, erase_gc);
605 show_set(v+w*maze_size_x, erase_gc);
609 /* Free some memory. */
613 /* First alternative maze creator: Pick a random, empty corner in the maze.
614 * Pick a random direction. Draw a wall in that direction, from that corner
615 * until we hit a wall. Option: Only draw the wall if it's going to be
616 * shorter than a certain length. Otherwise we get lots of long walls.
619 alt_create_maze(void)
623 int i, j, height, width, open_corners, k, dir, x, y;
625 height = maze_size_y+1;
626 width = maze_size_x+1;
628 /* Allocate and clear some mem. */
629 corners = (char *)calloc(height*width, 1);
633 /* Set up the indexing array. */
634 c_idx = (int *)malloc(sizeof(int)*height*width);
640 for(i = 0; i < height*width; i++)
642 for(i = 0; i < height*width; i++)
645 k = random()%(height*width);
650 /* Set up some initial walls. */
652 for(i = 0; i < width; i++)
655 corners[i+width*(height-1)] = 1;
657 for(i = 0; i < height; i++)
659 corners[i*width] = 1;
660 corners[i*width+width-1] = 1;
662 /* Walls around logo. In fact, inside the logo, too. */
663 /* Also draw the walls. */
666 int logow = 1 + logo_width / grid_width;
667 int logoh = 1 + logo_height / grid_height;
668 int bridge_dir, bridge_c;
670 if(bridge_p && logoh>=3 && logow>=3)
672 bridge_dir = 1+random()%2;
675 bridge_c = logo_y+random()%(logoh-2)+1;
679 bridge_c = logo_x+random()%(logow-2)+1;
687 for(i = logo_x; i <= logo_x + logow; i++)
689 for(j = logo_y; j <= logo_y + logoh; j++)
691 corners[i+width*j] = 1;
694 for(x = logo_x; x < logo_x+logow; x++)
696 if(!(bridge_dir==2 && x==bridge_c))
698 build_wall(x, logo_y, 0);
699 build_wall(x, logo_y+logoh, 0);
703 build_wall(x, bridge_c, 0);
704 build_wall(x, bridge_c, 2);
707 for(y = logo_y; y < logo_y+logoh; y++)
709 if(!(bridge_dir==1 && y==bridge_c))
711 build_wall(logo_x, y, 3);
712 build_wall(logo_x+logow, y, 3);
716 build_wall(bridge_c, y, 1);
717 build_wall(bridge_c, y, 3);
720 /* Connect one wall of the logo with an outside wall. */
722 dir = (bridge_dir+1)%4;
728 x = logo_x+(random()%(logow+1));
733 y = logo_y+(random()%(logoh+1));
736 x = logo_x+(random()%(logow+1));
741 y = logo_y+(random()%(logoh+1));
746 corners[x+width*y] = 1;
750 build_wall(x-1, y-1, 1);
762 build_wall(x-1, y-1, 2);
767 while(!corners[x+width*y]);
774 x = logo_x+(random()%(logow+1));
779 y = logo_y+(random()%(logoh+1));
782 x = logo_x+(random()%(logow+1));
787 y = logo_y+(random()%(logoh+1));
792 corners[x+width*y] = 1;
796 build_wall(x-1, y-1, 1);
808 build_wall(x-1, y-1, 2);
813 while(!corners[x+width*y]);
817 /* Count open gridpoints. */
819 for(i = 0; i < width; i++)
820 for(j = 0; j < height; j++)
821 if(!corners[i+width*j])
824 /* Now do actual maze generation. */
825 while(open_corners>0)
827 for(i = 0; i < width*height; i++)
829 if(!corners[c_idx[i]])
833 /* Choose a random direction. */
837 /* Measure the length of the wall we'd draw. */
838 while(!corners[x+width*y])
863 /* Draw a wall until we hit something. */
864 while(!corners[x+width*y])
867 corners[x+width*y] = 1;
871 build_wall(x-1, y-1, 1);
883 build_wall(x-1, y-1, 2);
893 /* Free some memory we used. */
898 /* The original maze creator. Start somewhere. Take a step in a random
899 * direction. Keep doing this until we hit a wall. Then, backtrack until
900 * we find a point where we can go in another direction.
903 create_maze (void) /* create a maze layout given the initialized maze */
905 register int i, newdoor = 0;
906 int logow = 1 + logo_width / grid_width;
907 int logoh = 1 + logo_height / grid_height;
909 /* Maybe we should make a bridge? */
910 if(bridge_p && logo_x>=0 && logow>=3 && logoh>=3)
912 int bridge_dir, bridge_c;
914 bridge_dir = 1+random()%2;
918 bridge_c = logo_y+random()%(logoh-2)+1;
920 bridge_c = logo_y+random()%logoh;
925 bridge_c = logo_x+random()%(logow-2)+1;
927 bridge_c = logo_x+random()%logow;
932 for(i = logo_x; i < logo_x+logow; i++)
934 maze[i][bridge_c] &= ~DOOR_IN_TOP;
939 for(i = logo_y; i < logo_y+logoh; i++)
941 maze[bridge_c][i] &= ~DOOR_IN_TOP;
947 move_list[sqnum].x = cur_sq_x;
948 move_list[sqnum].y = cur_sq_y;
949 move_list[sqnum].dir = newdoor;
950 while ( ( newdoor = choose_door() ) == -1 ) { /* pick a door */
951 if ( backup() == -1 ) { /* no more doors ... backup */
952 return; /* done ... return */
956 /* mark the out door */
957 maze[cur_sq_x][cur_sq_y] |= ( DOOR_OUT_TOP >> newdoor );
971 /* mark the in door */
972 maze[cur_sq_x][cur_sq_y] |= ( DOOR_IN_TOP >> ((newdoor+2)%4) );
974 /* if end square set path length and save path */
975 if ( maze[cur_sq_x][cur_sq_y] & END_SQUARE ) {
977 for ( i=0; i<path_length; i++) {
978 save_path[i].x = move_list[i].x;
979 save_path[i].y = move_list[i].y;
980 save_path[i].dir = move_list[i].dir;
990 choose_door (void) /* pick a new path */
993 register int num_candidates;
998 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_TOP )
1000 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_TOP )
1002 if ( maze[cur_sq_x][cur_sq_y] & WALL_TOP )
1004 if ( maze[cur_sq_x][cur_sq_y - 1] & DOOR_IN_ANY ) {
1005 maze[cur_sq_x][cur_sq_y] |= WALL_TOP;
1006 maze[cur_sq_x][cur_sq_y - 1] |= WALL_BOTTOM;
1007 draw_wall(cur_sq_x, cur_sq_y, 0, gc);
1010 candidates[num_candidates++] = 0;
1014 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_RIGHT )
1016 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_RIGHT )
1018 if ( maze[cur_sq_x][cur_sq_y] & WALL_RIGHT )
1020 if ( maze[cur_sq_x + 1][cur_sq_y] & DOOR_IN_ANY ) {
1021 maze[cur_sq_x][cur_sq_y] |= WALL_RIGHT;
1022 maze[cur_sq_x + 1][cur_sq_y] |= WALL_LEFT;
1023 draw_wall(cur_sq_x, cur_sq_y, 1, gc);
1026 candidates[num_candidates++] = 1;
1030 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_BOTTOM )
1032 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_BOTTOM )
1034 if ( maze[cur_sq_x][cur_sq_y] & WALL_BOTTOM )
1036 if ( maze[cur_sq_x][cur_sq_y + 1] & DOOR_IN_ANY ) {
1037 maze[cur_sq_x][cur_sq_y] |= WALL_BOTTOM;
1038 maze[cur_sq_x][cur_sq_y + 1] |= WALL_TOP;
1039 draw_wall(cur_sq_x, cur_sq_y, 2, gc);
1042 candidates[num_candidates++] = 2;
1046 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_LEFT )
1048 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_LEFT )
1050 if ( maze[cur_sq_x][cur_sq_y] & WALL_LEFT )
1052 if ( maze[cur_sq_x - 1][cur_sq_y] & DOOR_IN_ANY ) {
1053 maze[cur_sq_x][cur_sq_y] |= WALL_LEFT;
1054 maze[cur_sq_x - 1][cur_sq_y] |= WALL_RIGHT;
1055 draw_wall(cur_sq_x, cur_sq_y, 3, gc);
1058 candidates[num_candidates++] = 3;
1061 if (num_candidates == 0)
1063 if (num_candidates == 1)
1064 return ( candidates[0] );
1065 return ( candidates[ get_random(num_candidates) ] );
1071 backup (void) /* back up a move */
1074 cur_sq_x = move_list[sqnum].x;
1075 cur_sq_y = move_list[sqnum].y;
1081 draw_maze_border (void) /* draw the maze outline */
1086 for ( i=0; i<maze_size_x; i++) {
1087 if ( maze[i][0] & WALL_TOP ) {
1088 XDrawLine(dpy, win, gc,
1089 border_x + grid_width * i,
1091 border_x + grid_width * (i+1) - 1,
1094 if ((maze[i][maze_size_y - 1] & WALL_BOTTOM)) {
1095 XDrawLine(dpy, win, gc,
1096 border_x + grid_width * i,
1097 border_y + grid_height * (maze_size_y) - 1,
1098 border_x + grid_width * (i+1) - 1,
1099 border_y + grid_height * (maze_size_y) - 1);
1102 for ( j=0; j<maze_size_y; j++) {
1103 if ( maze[maze_size_x - 1][j] & WALL_RIGHT ) {
1104 XDrawLine(dpy, win, gc,
1105 border_x + grid_width * maze_size_x - 1,
1106 border_y + grid_height * j,
1107 border_x + grid_width * maze_size_x - 1,
1108 border_y + grid_height * (j+1) - 1);
1110 if ( maze[0][j] & WALL_LEFT ) {
1111 XDrawLine(dpy, win, gc,
1113 border_y + grid_height * j,
1115 border_y + grid_height * (j+1) - 1);
1123 unsigned int w, h, bw, d;
1124 XGetGeometry (dpy, logo_map, &r, &x, &y, &w, &h, &bw, &d);
1125 XCopyPlane (dpy, logo_map, win, logo_gc,
1127 border_x + 3 + grid_width * logo_x,
1128 border_y + 3 + grid_height * logo_y, 1);
1130 draw_solid_square (start_x, start_y, WALL_TOP >> start_dir, tgc);
1131 draw_solid_square (end_x, end_y, WALL_TOP >> end_dir, tgc);
1136 draw_wall(int i, int j, int dir, GC gc) /* draw a single wall */
1140 XDrawLine(dpy, win, gc,
1141 border_x + grid_width * i,
1142 border_y + grid_height * j,
1143 border_x + grid_width * (i+1),
1144 border_y + grid_height * j);
1147 XDrawLine(dpy, win, gc,
1148 border_x + grid_width * (i+1),
1149 border_y + grid_height * j,
1150 border_x + grid_width * (i+1),
1151 border_y + grid_height * (j+1));
1154 XDrawLine(dpy, win, gc,
1155 border_x + grid_width * i,
1156 border_y + grid_height * (j+1),
1157 border_x + grid_width * (i+1),
1158 border_y + grid_height * (j+1));
1161 XDrawLine(dpy, win, gc,
1162 border_x + grid_width * i,
1163 border_y + grid_height * j,
1164 border_x + grid_width * i,
1165 border_y + grid_height * (j+1));
1172 /* Actually build a wall. */
1174 build_wall(i, j, dir)
1177 /* Draw it on the screen. */
1178 draw_wall(i, j, dir, gc);
1179 /* Put it in the maze. */
1183 maze[i][j] |= WALL_TOP;
1185 maze[i][j-1] |= WALL_BOTTOM;
1188 maze[i][j] |= WALL_RIGHT;
1190 maze[i+1][j] |= WALL_LEFT;
1193 maze[i][j] |= WALL_BOTTOM;
1195 maze[i][j+1] |= WALL_TOP;
1198 maze[i][j] |= WALL_LEFT;
1200 maze[i-1][j] |= WALL_RIGHT;
1205 /* Break out a wall. */
1208 break_wall(i, j, dir)
1211 /* Draw it on the screen. */
1212 draw_wall(i, j, dir, erase_gc);
1213 /* Put it in the maze. */
1217 maze[i][j] &= ~WALL_TOP;
1219 maze[i][j-1] &= ~WALL_BOTTOM;
1222 maze[i][j] &= ~WALL_RIGHT;
1224 maze[i+1][j] &= ~WALL_LEFT;
1227 maze[i][j] &= ~WALL_BOTTOM;
1229 maze[i][j+1] &= ~WALL_BOTTOM;
1232 maze[i][j] &= ~WALL_LEFT;
1234 maze[i-1][j] &= ~WALL_RIGHT;
1242 draw_solid_square(int i, int j, /* draw a solid square in a square */
1247 XFillRectangle(dpy, win, gc,
1248 border_x + bw + grid_width * i,
1249 border_y - bw + grid_height * j,
1250 grid_width - (bw+bw), grid_height);
1253 XFillRectangle(dpy, win, gc,
1254 border_x + bw + grid_width * i,
1255 border_y + bw + grid_height * j,
1256 grid_width, grid_height - (bw+bw));
1259 XFillRectangle(dpy, win, gc,
1260 border_x + bw + grid_width * i,
1261 border_y + bw + grid_height * j,
1262 grid_width - (bw+bw), grid_height);
1265 XFillRectangle(dpy, win, gc,
1266 border_x - bw + grid_width * i,
1267 border_y + bw + grid_height * j,
1268 grid_width, grid_height - (bw+bw));
1275 longdeadend_p(int x1, int y1, int x2, int y2, int endwall)
1277 int dx = x2 - x1, dy = y2 - y1;
1280 sidewalls = endwall | (endwall >> 2 | endwall << 2);
1281 sidewalls = ~sidewalls & WALL_ANY;
1283 while((maze[x2][y2] & WALL_ANY) == sidewalls)
1289 if((maze[x2][y2] & WALL_ANY) == (sidewalls | endwall))
1291 endwall = (endwall >> 2 | endwall << 2) & WALL_ANY;
1292 while(x1 != x2 || y1 != y2)
1296 draw_solid_square(x1, y1, endwall, sgc);
1297 maze[x1][y1] |= SOLVER_VISIT;
1305 /* Find all dead regions -- areas from which the goal cannot be reached --
1306 and mark them visited. */
1308 find_dead_regions(void)
1312 /* Find all not SOLVER_VISIT squares bordering NOT_DEAD squares
1313 and mark them NOT_DEAD also. Repeat until no more such squares. */
1314 maze[start_x][start_y] |= NOT_DEAD;
1319 for(x = 0; x < maze_size_x; x++)
1320 for(y = 0; y < maze_size_y; y++)
1321 if(!(maze[x][y] & (SOLVER_VISIT | NOT_DEAD))
1322 && ( (x && (maze[x-1][y] & NOT_DEAD))
1323 || (y && (maze[x][y-1] & NOT_DEAD))))
1326 maze[x][y] |= NOT_DEAD;
1328 for(x = maze_size_x-1; x >= 0; x--)
1329 for(y = maze_size_y-1; y >= 0; y--)
1330 if(!(maze[x][y] & (SOLVER_VISIT | NOT_DEAD))
1331 && ( (x != maze_size_x-1 && (maze[x+1][y] & NOT_DEAD))
1332 || (y != maze_size_y-1 && (maze[x][y+1] & NOT_DEAD))))
1335 maze[x][y] |= NOT_DEAD;
1340 for (y = 0; y < maze_size_y; y++)
1341 for (x = 0; x < maze_size_x; x++)
1343 if (maze[x][y] & NOT_DEAD)
1344 maze[x][y] &= ~NOT_DEAD;
1345 else if (!(maze[x][y] & SOLVER_VISIT))
1347 maze[x][y] |= SOLVER_VISIT;
1348 if((x < logo_x || x > logo_x + logo_width / grid_width) ||
1349 (y < logo_y || y > logo_y + logo_height / grid_height))
1351 if (!maze[x][y] & WALL_ANY)
1352 XFillRectangle(dpy, win, ugc,
1353 border_x + bw + grid_width * x,
1354 border_y + bw + grid_height * y,
1355 grid_width - (bw+bw), grid_height - (bw+bw));
1358 if (! (maze[x][y] & WALL_LEFT))
1359 draw_solid_square(x, y, WALL_LEFT, ugc);
1360 if (! (maze[x][y] & WALL_RIGHT))
1361 draw_solid_square(x, y, WALL_RIGHT, ugc);
1362 if (! (maze[x][y] & WALL_TOP))
1363 draw_solid_square(x, y, WALL_TOP, ugc);
1364 if (! (maze[x][y] & WALL_BOTTOM))
1365 draw_solid_square(x, y, WALL_BOTTOM, ugc);
1374 solve_maze (void) /* solve it with graphical feedback */
1376 int i, dir, from, x, y, ways, bt;
1378 /* plug up the surrounding wall */
1379 maze[end_x][end_y] |= (WALL_TOP >> end_dir);
1381 /* initialize search path */
1386 maze[end_x][end_y] |= SOLVER_VISIT;
1391 if ( maze[path[i].x][path[i].y] & START_SQUARE )
1394 /* Abort solve on expose - cheapo repaint strategy */
1395 if (check_events()) return;
1397 if (solve_delay) usleep (solve_delay);
1402 /* First visit this square. Which adjacent squares are open? */
1403 for(dir = WALL_TOP; dir & WALL_ANY; dir >>= 1)
1405 if(maze[path[i].x][path[i].y] & dir)
1408 y = path[i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1409 x = path[i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1411 if(maze[x][y] & SOLVER_VISIT)
1414 from = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1415 /* don't enter obvious dead ends */
1416 if(((maze[x][y] & WALL_ANY) | from) != WALL_ANY)
1418 if(!longdeadend_p(path[i].x, path[i].y, x, y, dir))
1423 draw_solid_square(x, y, from, sgc);
1424 maze[x][y] |= SOLVER_VISIT;
1429 ways = path[i].ways;
1430 /* ways now has a bitmask of open paths. */
1435 x = path[i].x - start_x;
1436 y = path[i].y - start_y;
1438 if(abs(y) <= abs(x))
1439 dir = (x > 0) ? WALL_LEFT : WALL_RIGHT;
1441 dir = (y > 0) ? WALL_TOP : WALL_BOTTOM;
1451 dir = (y > 0) ? WALL_TOP : WALL_BOTTOM; break;
1454 dir = (x > 0) ? WALL_LEFT : WALL_RIGHT;
1462 dir = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1473 ways &= ~dir; /* tried this one */
1475 y = path[i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1476 x = path[i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1478 /* advance in direction dir */
1480 path[i].ways = ways;
1481 draw_solid_square(path[i].x, path[i].y, dir, tgc);
1488 maze[x][y] |= SOLVER_VISIT;
1494 printf("Unsolvable maze.\n");
1499 find_dead_regions();
1501 from = path[i-1].dir;
1502 from = (from << 2 & WALL_ANY) | (from >> 2 & WALL_ANY);
1504 draw_solid_square(path[i].x, path[i].y, from, cgc);
1511 enter_square (int n) /* move into a neighboring square */
1513 draw_solid_square( (int)path[n].x, (int)path[n].y,
1514 (int)path[n].dir, tgc);
1517 switch (path[n].dir) {
1518 case 0: path[n+1].x = path[n].x;
1519 path[n+1].y = path[n].y - 1;
1521 case 1: path[n+1].x = path[n].x + 1;
1522 path[n+1].y = path[n].y;
1524 case 2: path[n+1].x = path[n].x;
1525 path[n+1].y = path[n].y + 1;
1527 case 3: path[n+1].x = path[n].x - 1;
1528 path[n+1].y = path[n].y;
1536 * jmr additions for Jamie Zawinski's <jwz@netscape.com> screensaver stuff,
1537 * note that the code above this has probably been hacked about in some
1541 char *progclass = "Maze";
1543 char *defaults[] = {
1544 ".background: black",
1545 ".foreground: white",
1547 "*solveDelay: 5000",
1548 "*preDelay: 2000000",
1549 "*postDelay: 4000000",
1550 "*liveColor: green",
1552 "*skipColor: orange",
1553 "*surroundColor: slateblue",
1564 XrmOptionDescRec options[] = {
1565 { "-grid-size", ".gridSize", XrmoptionSepArg, 0 },
1566 { "-solve-delay", ".solveDelay", XrmoptionSepArg, 0 },
1567 { "-pre-delay", ".preDelay", XrmoptionSepArg, 0 },
1568 { "-post-delay", ".postDelay", XrmoptionSepArg, 0 },
1569 { "-live-color", ".liveColor", XrmoptionSepArg, 0 },
1570 { "-dead-color", ".deadColor", XrmoptionSepArg, 0 },
1571 { "-skip-color", ".skipColor", XrmoptionSepArg, 0 },
1572 { "-surround-color", ".surroundColor",XrmoptionSepArg, 0 },
1573 { "-generator", ".generator", XrmoptionSepArg, 0 },
1574 { "-max-length", ".maxLength", XrmoptionSepArg, 0 },
1575 { "-bridge", ".bridge", XrmoptionNoArg, "True" },
1576 { "-no-bridge", ".bridge", XrmoptionNoArg, "False" },
1581 extern void skull (Display *, Window, GC, GC, int, int, int, int);
1585 screenhack(Display *display, Window window)
1588 int size, root, generator, this_gen;
1589 XWindowAttributes xgwa;
1590 unsigned long bg, fg, pfg, pbg, lfg, sfg, ufg;
1592 size = get_integer_resource ("gridSize", "Dimension");
1593 root = get_boolean_resource("root", "Boolean");
1594 solve_delay = get_integer_resource ("solveDelay", "Integer");
1595 pre_solve_delay = get_integer_resource ("preDelay", "Integer");
1596 post_solve_delay = get_integer_resource ("postDelay", "Integer");
1597 generator = get_integer_resource("generator", "Integer");
1598 max_length = get_integer_resource("maxLength", "Integer");
1599 bridge_p = get_boolean_resource("bridge", "Boolean");
1601 if (size < 2) size = 7 + (random () % 30);
1602 grid_width = grid_height = size;
1603 bw = (size > 6 ? 3 : (size-1)/2);
1605 dpy = display; win = window; /* the maze stuff uses global variables */
1607 XGetWindowAttributes (dpy, win, &xgwa);
1612 set_maze_sizes (xgwa.width, xgwa.height);
1615 XSelectInput (dpy, win, ExposureMask|ButtonPressMask|StructureNotifyMask);
1617 gc = XCreateGC(dpy, win, 0, 0);
1618 cgc = XCreateGC(dpy, win, 0, 0);
1619 tgc = XCreateGC(dpy, win, 0, 0);
1620 sgc = XCreateGC(dpy, win, 0, 0);
1621 ugc = XCreateGC(dpy, win, 0, 0);
1622 logo_gc = XCreateGC(dpy, win, 0, 0);
1623 erase_gc = XCreateGC(dpy, win, 0, 0);
1625 gray = XCreateBitmapFromData (dpy,win,gray1_bits,gray1_width,gray1_height);
1627 bg = get_pixel_resource ("background","Background", dpy, xgwa.colormap);
1628 fg = get_pixel_resource ("foreground","Foreground", dpy, xgwa.colormap);
1629 lfg = get_pixel_resource ("logoColor", "Foreground", dpy, xgwa.colormap);
1630 pfg = get_pixel_resource ("liveColor", "Foreground", dpy, xgwa.colormap);
1631 pbg = get_pixel_resource ("deadColor", "Foreground", dpy, xgwa.colormap);
1632 sfg = get_pixel_resource ("skipColor", "Foreground", dpy, xgwa.colormap);
1633 ufg = get_pixel_resource ("surroundColor", "Foreground", dpy, xgwa.colormap);
1634 if (mono_p) lfg = pfg = fg;
1637 lfg = ((bg == WhitePixel (dpy, DefaultScreen (dpy)))
1638 ? BlackPixel (dpy, DefaultScreen (dpy))
1639 : WhitePixel (dpy, DefaultScreen (dpy)));
1641 XSetForeground (dpy, gc, fg);
1642 XSetBackground (dpy, gc, bg);
1643 XSetForeground (dpy, cgc, pbg);
1644 XSetBackground (dpy, cgc, bg);
1645 XSetForeground (dpy, tgc, pfg);
1646 XSetBackground (dpy, tgc, bg);
1647 XSetForeground (dpy, sgc, sfg);
1648 XSetBackground (dpy, sgc, bg);
1649 XSetForeground (dpy, ugc, ufg);
1650 XSetBackground (dpy, ugc, bg);
1651 XSetForeground (dpy, logo_gc, lfg);
1652 XSetBackground (dpy, logo_gc, bg);
1653 XSetForeground (dpy, erase_gc, bg);
1654 XSetBackground (dpy, erase_gc, bg);
1656 XSetStipple (dpy, cgc, gray);
1657 XSetFillStyle (dpy, cgc, FillOpaqueStippled);
1658 XSetStipple (dpy, sgc, gray);
1659 XSetFillStyle (dpy, sgc, FillOpaqueStippled);
1660 XSetStipple (dpy, ugc, gray);
1661 XSetFillStyle (dpy, ugc, FillOpaqueStippled);
1667 GC draw_gc, erase_gc;
1668 /* round up to grid size */
1669 w = ((logo_width / grid_width) + 1) * grid_width;
1670 h = ((logo_height / grid_height) + 1) * grid_height;
1671 logo_map = XCreatePixmap (dpy, win, w, h, 1);
1672 gcv.foreground = 1L;
1673 draw_gc = XCreateGC (dpy, logo_map, GCForeground, &gcv);
1674 gcv.foreground = 0L;
1675 erase_gc= XCreateGC (dpy, logo_map, GCForeground, &gcv);
1676 XFillRectangle (dpy, logo_map, erase_gc, 0, 0, w, h);
1677 skull (dpy, logo_map, draw_gc, erase_gc, 5, 0, w-10, h-10);
1678 XFreeGC (dpy, draw_gc);
1679 XFreeGC (dpy, erase_gc);
1682 if (!(logo_map = XCreateBitmapFromData (dpy, win, logo_bits,
1683 logo_width, logo_height)))
1685 fprintf (stderr, "Can't create logo pixmap\n");
1689 XMapRaised(dpy, win);
1693 sync_p = !(random() % 10);
1695 while (1) { /* primary execution loop [ rhess ] */
1696 if (check_events()) continue ;
1697 if (restart || stop) goto pop;
1703 XClearWindow(dpy, win);
1707 this_gen = generator;
1708 if(this_gen<0 || this_gen>2)
1709 this_gen = random()%3;
1726 usleep (pre_solve_delay);
1733 usleep (post_solve_delay);
1735 erase_full_window(display, window);
1744 static XWindowAttributes wattr;
1748 XGetWindowAttributes (dpy, win, &wattr);
1749 set_maze_sizes (wattr.width, wattr.height);
1750 XClearWindow (dpy, win);
1752 sync_p = !(random() % 10);