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@jwz.org>
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);
205 screenhack_handle_event(dpy, &e);
215 set_maze_sizes (int width, int height)
217 maze_size_x = width / grid_width;
218 maze_size_y = height / grid_height;
223 initialize_maze (void) /* draw the surrounding wall and start/end squares */
225 register int i, j, wall;
226 int logow = 1 + logo_width / grid_width;
227 int logoh = 1 + logo_height / grid_height;
229 /* initialize all squares */
230 for ( i=0; i<maze_size_x; i++) {
231 for ( j=0; j<maze_size_y; j++) {
237 for ( i=0; i<maze_size_x; i++ ) {
238 maze[i][0] |= WALL_TOP;
242 for ( j=0; j<maze_size_y; j++ ) {
243 maze[maze_size_x-1][j] |= WALL_RIGHT;
247 for ( i=0; i<maze_size_x; i++ ) {
248 maze[i][maze_size_y-1] |= WALL_BOTTOM;
252 for ( j=0; j<maze_size_y; j++ ) {
253 maze[0][j] |= WALL_LEFT;
256 /* set start square */
257 wall = get_random(4);
260 i = get_random(maze_size_x);
265 j = get_random(maze_size_y);
268 i = get_random(maze_size_x);
273 j = get_random(maze_size_y);
276 maze[i][j] |= START_SQUARE;
277 maze[i][j] |= ( DOOR_IN_TOP >> wall );
278 maze[i][j] &= ~( WALL_TOP >> wall );
290 i = get_random(maze_size_x);
295 j = get_random(maze_size_y);
298 i = get_random(maze_size_x);
303 j = get_random(maze_size_y);
306 maze[i][j] |= END_SQUARE;
307 maze[i][j] |= ( DOOR_OUT_TOP >> wall );
308 maze[i][j] &= ~( WALL_TOP >> wall );
314 if ((maze_size_x-logow >= 6) && (maze_size_y-logoh >= 6))
316 /* not closer than 3 grid units from a wall */
317 logo_x = get_random (maze_size_x - logow - 5) + 3;
318 logo_y = get_random (maze_size_y - logoh - 5) + 3;
319 for (i=0; i<logow; i++)
320 for (j=0; j<logoh; j++)
321 maze[logo_x + i][logo_y + j] |= DOOR_IN_TOP;
324 logo_y = logo_x = -1;
327 static int choose_door (void);
328 static int backup (void);
329 static void draw_wall (int, int, int, GC);
330 static void draw_solid_square (int, int, int, GC);
331 /*static void enter_square (int);*/
332 static void build_wall (int, int, int);
333 /*static void break_wall (int, int, int);*/
335 static void join_sets(int, int);
337 /* For set_create_maze. */
338 /* The sets that our squares are in. */
339 static int *sets = 0;
340 /* The `list' of hedges. */
341 static int *hedges = 0;
345 /* Initialise the sets. */
353 sets = (int *)malloc(maze_size_x*maze_size_y*sizeof(int));
356 for(i = 0; i < maze_size_x*maze_size_y; i++)
363 hedges = (int *)malloc(maze_size_x*maze_size_y*2*sizeof(int));
366 for(i = 0; i < maze_size_x*maze_size_y*2; i++)
370 /* Mask out outside walls. */
371 for(i = 0; i < maze_size_y; i++)
373 hedges[2*((maze_size_x)*i+maze_size_x-1)+1] = -1;
375 for(i = 0; i < maze_size_x; i++)
377 hedges[2*((maze_size_y-1)*maze_size_x+i)] = -1;
379 /* Mask out a possible logo. */
382 int logow = 1 + logo_width / grid_width;
383 int logoh = 1 + logo_height / grid_height;
384 int bridge_dir, bridge_c;
386 if(bridge_p && logoh>=3 && logow>=3)
388 bridge_dir = 1+random()%2;
391 bridge_c = logo_y+random()%(logoh-2)+1;
395 bridge_c = logo_x+random()%(logow-2)+1;
404 for(x = logo_x; x < logo_x+logow; x++)
405 for(y = logo_y; y < logo_y+logoh; y++)
407 /* I should check for the bridge here, except that I join the
408 * bridge together below.
410 hedges[2*(x+maze_size_x*y)+1] = -1;
411 hedges[2*(x+maze_size_x*y)] = -1;
413 for(x = logo_x; x < logo_x+logow; x++)
415 if(!(bridge_dir==2 && x==bridge_c))
417 build_wall(x, logo_y, 0);
418 build_wall(x, logo_y+logoh, 0);
420 hedges[2*(x+maze_size_x*(logo_y-1))] = -1;
423 build_wall(x, bridge_c, 0);
424 build_wall(x, bridge_c, 2);
427 for(y = logo_y; y < logo_y+logoh; y++)
429 if(!(bridge_dir==1 && y==bridge_c))
431 build_wall(logo_x, y, 3);
432 build_wall(logo_x+logow, y, 3);
434 hedges[2*(logo_x-1+maze_size_x*y)+1] = -1;
437 build_wall(bridge_c, y, 1);
438 build_wall(bridge_c, y, 3);
441 /* Join the whole bridge together. */
448 for(i = logo_x; i < logo_x+logow+1; i++)
449 join_sets(x+y*maze_size_x, i+y*maze_size_x);
455 for(i = logo_y; i < logo_y+logoh+1; i++)
456 join_sets(x+y*maze_size_x, x+i*maze_size_x);
461 for(i = 0; i < maze_size_x*maze_size_y*2; i++)
464 r = random()%(maze_size_x*maze_size_y*2);
465 hedges[i] = hedges[r];
470 /* Get the representative of a set. */
480 s = get_set(sets[num]);
486 /* Join two sets together. */
488 join_sets(num1, num2)
502 /* Exitialise the sets. */
515 /* Temporary hack. */
517 show_set(int num, GC gc)
523 for(x = 0; x < maze_size_x; x++)
524 for(y = 0; y < maze_size_y; y++)
526 if(get_set(x+y*maze_size_x)==set)
528 XFillRectangle(dpy, win, gc, border_x + bw + grid_width * x,
529 border_y + bw + grid_height * y,
530 grid_width-2*bw , grid_height-2*bw);
536 /* Second alternative maze creator: Put each square in the maze in a
537 * separate set. Also, make a list of all the hedges. Randomize that list.
538 * Walk through the list. If, for a certain hedge, the two squares on both
539 * sides of it are in different sets, union the sets and remove the hedge.
540 * Continue until all hedges have been processed or only one set remains.
543 set_create_maze(void)
545 int i, h, x, y, dir, v, w;
551 /* Do almost all the setup. */
554 /* Start running through the hedges. */
555 for(i = 0; i < 2*maze_size_x*maze_size_y; i++)
559 /* This one is in the logo or outside border. */
564 x = (h>>1)%maze_size_x;
565 y = (h>>1)/maze_size_x;
580 show_set(x+y*maze_size_x, logo_gc);
581 show_set(v+w*maze_size_x, tgc);
583 if(get_set(x+y*maze_size_x)!=get_set(v+w*maze_size_x))
588 join_sets(x+y*maze_size_x, v+w*maze_size_x);
589 /* Don't draw the wall. */
596 /* Don't join the sets. */
597 build_wall(x, y, dir);
607 show_set(x+y*maze_size_x, erase_gc);
608 show_set(v+w*maze_size_x, erase_gc);
612 /* Free some memory. */
616 /* First alternative maze creator: Pick a random, empty corner in the maze.
617 * Pick a random direction. Draw a wall in that direction, from that corner
618 * until we hit a wall. Option: Only draw the wall if it's going to be
619 * shorter than a certain length. Otherwise we get lots of long walls.
622 alt_create_maze(void)
626 int i, j, height, width, open_corners, k, dir, x, y;
628 height = maze_size_y+1;
629 width = maze_size_x+1;
631 /* Allocate and clear some mem. */
632 corners = (char *)calloc(height*width, 1);
636 /* Set up the indexing array. */
637 c_idx = (int *)malloc(sizeof(int)*height*width);
643 for(i = 0; i < height*width; i++)
645 for(i = 0; i < height*width; i++)
648 k = random()%(height*width);
653 /* Set up some initial walls. */
655 for(i = 0; i < width; i++)
658 corners[i+width*(height-1)] = 1;
660 for(i = 0; i < height; i++)
662 corners[i*width] = 1;
663 corners[i*width+width-1] = 1;
665 /* Walls around logo. In fact, inside the logo, too. */
666 /* Also draw the walls. */
669 int logow = 1 + logo_width / grid_width;
670 int logoh = 1 + logo_height / grid_height;
671 int bridge_dir, bridge_c;
673 if(bridge_p && logoh>=3 && logow>=3)
675 bridge_dir = 1+random()%2;
678 bridge_c = logo_y+random()%(logoh-2)+1;
682 bridge_c = logo_x+random()%(logow-2)+1;
690 for(i = logo_x; i <= logo_x + logow; i++)
692 for(j = logo_y; j <= logo_y + logoh; j++)
694 corners[i+width*j] = 1;
697 for(x = logo_x; x < logo_x+logow; x++)
699 if(!(bridge_dir==2 && x==bridge_c))
701 build_wall(x, logo_y, 0);
702 build_wall(x, logo_y+logoh, 0);
706 build_wall(x, bridge_c, 0);
707 build_wall(x, bridge_c, 2);
710 for(y = logo_y; y < logo_y+logoh; y++)
712 if(!(bridge_dir==1 && y==bridge_c))
714 build_wall(logo_x, y, 3);
715 build_wall(logo_x+logow, y, 3);
719 build_wall(bridge_c, y, 1);
720 build_wall(bridge_c, y, 3);
723 /* Connect one wall of the logo with an outside wall. */
725 dir = (bridge_dir+1)%4;
731 x = logo_x+(random()%(logow+1));
736 y = logo_y+(random()%(logoh+1));
739 x = logo_x+(random()%(logow+1));
744 y = logo_y+(random()%(logoh+1));
749 corners[x+width*y] = 1;
753 build_wall(x-1, y-1, 1);
765 build_wall(x-1, y-1, 2);
770 while(!corners[x+width*y]);
777 x = logo_x+(random()%(logow+1));
782 y = logo_y+(random()%(logoh+1));
785 x = logo_x+(random()%(logow+1));
790 y = logo_y+(random()%(logoh+1));
795 corners[x+width*y] = 1;
799 build_wall(x-1, y-1, 1);
811 build_wall(x-1, y-1, 2);
816 while(!corners[x+width*y]);
820 /* Count open gridpoints. */
822 for(i = 0; i < width; i++)
823 for(j = 0; j < height; j++)
824 if(!corners[i+width*j])
827 /* Now do actual maze generation. */
828 while(open_corners>0)
830 for(i = 0; i < width*height; i++)
832 if(!corners[c_idx[i]])
836 /* Choose a random direction. */
840 /* Measure the length of the wall we'd draw. */
841 while(!corners[x+width*y])
866 /* Draw a wall until we hit something. */
867 while(!corners[x+width*y])
870 corners[x+width*y] = 1;
874 build_wall(x-1, y-1, 1);
886 build_wall(x-1, y-1, 2);
896 /* Free some memory we used. */
901 /* The original maze creator. Start somewhere. Take a step in a random
902 * direction. Keep doing this until we hit a wall. Then, backtrack until
903 * we find a point where we can go in another direction.
906 create_maze (void) /* create a maze layout given the initialized maze */
908 register int i, newdoor = 0;
909 int logow = 1 + logo_width / grid_width;
910 int logoh = 1 + logo_height / grid_height;
912 /* Maybe we should make a bridge? */
913 if(bridge_p && logo_x>=0 && logow>=3 && logoh>=3)
915 int bridge_dir, bridge_c;
917 bridge_dir = 1+random()%2;
921 bridge_c = logo_y+random()%(logoh-2)+1;
923 bridge_c = logo_y+random()%logoh;
928 bridge_c = logo_x+random()%(logow-2)+1;
930 bridge_c = logo_x+random()%logow;
935 for(i = logo_x; i < logo_x+logow; i++)
937 maze[i][bridge_c] &= ~DOOR_IN_TOP;
942 for(i = logo_y; i < logo_y+logoh; i++)
944 maze[bridge_c][i] &= ~DOOR_IN_TOP;
950 move_list[sqnum].x = cur_sq_x;
951 move_list[sqnum].y = cur_sq_y;
952 move_list[sqnum].dir = newdoor;
953 while ( ( newdoor = choose_door() ) == -1 ) { /* pick a door */
954 if ( backup() == -1 ) { /* no more doors ... backup */
955 return; /* done ... return */
959 /* mark the out door */
960 maze[cur_sq_x][cur_sq_y] |= ( DOOR_OUT_TOP >> newdoor );
974 /* mark the in door */
975 maze[cur_sq_x][cur_sq_y] |= ( DOOR_IN_TOP >> ((newdoor+2)%4) );
977 /* if end square set path length and save path */
978 if ( maze[cur_sq_x][cur_sq_y] & END_SQUARE ) {
980 for ( i=0; i<path_length; i++) {
981 save_path[i].x = move_list[i].x;
982 save_path[i].y = move_list[i].y;
983 save_path[i].dir = move_list[i].dir;
993 choose_door (void) /* pick a new path */
996 register int num_candidates;
1001 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_TOP )
1003 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_TOP )
1005 if ( maze[cur_sq_x][cur_sq_y] & WALL_TOP )
1007 if ( maze[cur_sq_x][cur_sq_y - 1] & DOOR_IN_ANY ) {
1008 maze[cur_sq_x][cur_sq_y] |= WALL_TOP;
1009 maze[cur_sq_x][cur_sq_y - 1] |= WALL_BOTTOM;
1010 draw_wall(cur_sq_x, cur_sq_y, 0, gc);
1013 candidates[num_candidates++] = 0;
1017 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_RIGHT )
1019 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_RIGHT )
1021 if ( maze[cur_sq_x][cur_sq_y] & WALL_RIGHT )
1023 if ( maze[cur_sq_x + 1][cur_sq_y] & DOOR_IN_ANY ) {
1024 maze[cur_sq_x][cur_sq_y] |= WALL_RIGHT;
1025 maze[cur_sq_x + 1][cur_sq_y] |= WALL_LEFT;
1026 draw_wall(cur_sq_x, cur_sq_y, 1, gc);
1029 candidates[num_candidates++] = 1;
1033 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_BOTTOM )
1035 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_BOTTOM )
1037 if ( maze[cur_sq_x][cur_sq_y] & WALL_BOTTOM )
1039 if ( maze[cur_sq_x][cur_sq_y + 1] & DOOR_IN_ANY ) {
1040 maze[cur_sq_x][cur_sq_y] |= WALL_BOTTOM;
1041 maze[cur_sq_x][cur_sq_y + 1] |= WALL_TOP;
1042 draw_wall(cur_sq_x, cur_sq_y, 2, gc);
1045 candidates[num_candidates++] = 2;
1049 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_LEFT )
1051 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_LEFT )
1053 if ( maze[cur_sq_x][cur_sq_y] & WALL_LEFT )
1055 if ( maze[cur_sq_x - 1][cur_sq_y] & DOOR_IN_ANY ) {
1056 maze[cur_sq_x][cur_sq_y] |= WALL_LEFT;
1057 maze[cur_sq_x - 1][cur_sq_y] |= WALL_RIGHT;
1058 draw_wall(cur_sq_x, cur_sq_y, 3, gc);
1061 candidates[num_candidates++] = 3;
1064 if (num_candidates == 0)
1066 if (num_candidates == 1)
1067 return ( candidates[0] );
1068 return ( candidates[ get_random(num_candidates) ] );
1074 backup (void) /* back up a move */
1077 cur_sq_x = move_list[sqnum].x;
1078 cur_sq_y = move_list[sqnum].y;
1084 draw_maze_border (void) /* draw the maze outline */
1089 for ( i=0; i<maze_size_x; i++) {
1090 if ( maze[i][0] & WALL_TOP ) {
1091 XDrawLine(dpy, win, gc,
1092 border_x + grid_width * i,
1094 border_x + grid_width * (i+1) - 1,
1097 if ((maze[i][maze_size_y - 1] & WALL_BOTTOM)) {
1098 XDrawLine(dpy, win, gc,
1099 border_x + grid_width * i,
1100 border_y + grid_height * (maze_size_y) - 1,
1101 border_x + grid_width * (i+1) - 1,
1102 border_y + grid_height * (maze_size_y) - 1);
1105 for ( j=0; j<maze_size_y; j++) {
1106 if ( maze[maze_size_x - 1][j] & WALL_RIGHT ) {
1107 XDrawLine(dpy, win, gc,
1108 border_x + grid_width * maze_size_x - 1,
1109 border_y + grid_height * j,
1110 border_x + grid_width * maze_size_x - 1,
1111 border_y + grid_height * (j+1) - 1);
1113 if ( maze[0][j] & WALL_LEFT ) {
1114 XDrawLine(dpy, win, gc,
1116 border_y + grid_height * j,
1118 border_y + grid_height * (j+1) - 1);
1126 unsigned int w, h, bw, d;
1127 XGetGeometry (dpy, logo_map, &r, &x, &y, &w, &h, &bw, &d);
1128 XCopyPlane (dpy, logo_map, win, logo_gc,
1130 border_x + 3 + grid_width * logo_x,
1131 border_y + 3 + grid_height * logo_y, 1);
1133 draw_solid_square (start_x, start_y, WALL_TOP >> start_dir, tgc);
1134 draw_solid_square (end_x, end_y, WALL_TOP >> end_dir, tgc);
1139 draw_wall(int i, int j, int dir, GC gc) /* draw a single wall */
1143 XDrawLine(dpy, win, gc,
1144 border_x + grid_width * i,
1145 border_y + grid_height * j,
1146 border_x + grid_width * (i+1),
1147 border_y + grid_height * j);
1150 XDrawLine(dpy, win, gc,
1151 border_x + grid_width * (i+1),
1152 border_y + grid_height * j,
1153 border_x + grid_width * (i+1),
1154 border_y + grid_height * (j+1));
1157 XDrawLine(dpy, win, gc,
1158 border_x + grid_width * i,
1159 border_y + grid_height * (j+1),
1160 border_x + grid_width * (i+1),
1161 border_y + grid_height * (j+1));
1164 XDrawLine(dpy, win, gc,
1165 border_x + grid_width * i,
1166 border_y + grid_height * j,
1167 border_x + grid_width * i,
1168 border_y + grid_height * (j+1));
1175 /* Actually build a wall. */
1177 build_wall(i, j, dir)
1180 /* Draw it on the screen. */
1181 draw_wall(i, j, dir, gc);
1182 /* Put it in the maze. */
1186 maze[i][j] |= WALL_TOP;
1188 maze[i][j-1] |= WALL_BOTTOM;
1191 maze[i][j] |= WALL_RIGHT;
1193 maze[i+1][j] |= WALL_LEFT;
1196 maze[i][j] |= WALL_BOTTOM;
1198 maze[i][j+1] |= WALL_TOP;
1201 maze[i][j] |= WALL_LEFT;
1203 maze[i-1][j] |= WALL_RIGHT;
1208 /* Break out a wall. */
1211 break_wall(i, j, dir)
1214 /* Draw it on the screen. */
1215 draw_wall(i, j, dir, erase_gc);
1216 /* Put it in the maze. */
1220 maze[i][j] &= ~WALL_TOP;
1222 maze[i][j-1] &= ~WALL_BOTTOM;
1225 maze[i][j] &= ~WALL_RIGHT;
1227 maze[i+1][j] &= ~WALL_LEFT;
1230 maze[i][j] &= ~WALL_BOTTOM;
1232 maze[i][j+1] &= ~WALL_BOTTOM;
1235 maze[i][j] &= ~WALL_LEFT;
1237 maze[i-1][j] &= ~WALL_RIGHT;
1245 draw_solid_square(int i, int j, /* draw a solid square in a square */
1250 XFillRectangle(dpy, win, gc,
1251 border_x + bw + grid_width * i,
1252 border_y - bw + grid_height * j,
1253 grid_width - (bw+bw), grid_height);
1256 XFillRectangle(dpy, win, gc,
1257 border_x + bw + grid_width * i,
1258 border_y + bw + grid_height * j,
1259 grid_width, grid_height - (bw+bw));
1262 XFillRectangle(dpy, win, gc,
1263 border_x + bw + grid_width * i,
1264 border_y + bw + grid_height * j,
1265 grid_width - (bw+bw), grid_height);
1268 XFillRectangle(dpy, win, gc,
1269 border_x - bw + grid_width * i,
1270 border_y + bw + grid_height * j,
1271 grid_width, grid_height - (bw+bw));
1278 longdeadend_p(int x1, int y1, int x2, int y2, int endwall)
1280 int dx = x2 - x1, dy = y2 - y1;
1283 sidewalls = endwall | (endwall >> 2 | endwall << 2);
1284 sidewalls = ~sidewalls & WALL_ANY;
1286 while((maze[x2][y2] & WALL_ANY) == sidewalls)
1292 if((maze[x2][y2] & WALL_ANY) == (sidewalls | endwall))
1294 endwall = (endwall >> 2 | endwall << 2) & WALL_ANY;
1295 while(x1 != x2 || y1 != y2)
1299 draw_solid_square(x1, y1, endwall, sgc);
1300 maze[x1][y1] |= SOLVER_VISIT;
1308 /* Find all dead regions -- areas from which the goal cannot be reached --
1309 and mark them visited. */
1311 find_dead_regions(void)
1315 /* Find all not SOLVER_VISIT squares bordering NOT_DEAD squares
1316 and mark them NOT_DEAD also. Repeat until no more such squares. */
1317 maze[start_x][start_y] |= NOT_DEAD;
1322 for(x = 0; x < maze_size_x; x++)
1323 for(y = 0; y < maze_size_y; y++)
1324 if(!(maze[x][y] & (SOLVER_VISIT | NOT_DEAD))
1325 && ( (x && (maze[x-1][y] & NOT_DEAD))
1326 || (y && (maze[x][y-1] & NOT_DEAD))))
1329 maze[x][y] |= NOT_DEAD;
1331 for(x = maze_size_x-1; x >= 0; x--)
1332 for(y = maze_size_y-1; y >= 0; y--)
1333 if(!(maze[x][y] & (SOLVER_VISIT | NOT_DEAD))
1334 && ( (x != maze_size_x-1 && (maze[x+1][y] & NOT_DEAD))
1335 || (y != maze_size_y-1 && (maze[x][y+1] & NOT_DEAD))))
1338 maze[x][y] |= NOT_DEAD;
1343 for (y = 0; y < maze_size_y; y++)
1344 for (x = 0; x < maze_size_x; x++)
1346 if (maze[x][y] & NOT_DEAD)
1347 maze[x][y] &= ~NOT_DEAD;
1348 else if (!(maze[x][y] & SOLVER_VISIT))
1350 maze[x][y] |= SOLVER_VISIT;
1351 if((x < logo_x || x > logo_x + logo_width / grid_width) ||
1352 (y < logo_y || y > logo_y + logo_height / grid_height))
1354 if (!maze[x][y] & WALL_ANY)
1355 XFillRectangle(dpy, win, ugc,
1356 border_x + bw + grid_width * x,
1357 border_y + bw + grid_height * y,
1358 grid_width - (bw+bw), grid_height - (bw+bw));
1361 if (! (maze[x][y] & WALL_LEFT))
1362 draw_solid_square(x, y, WALL_LEFT, ugc);
1363 if (! (maze[x][y] & WALL_RIGHT))
1364 draw_solid_square(x, y, WALL_RIGHT, ugc);
1365 if (! (maze[x][y] & WALL_TOP))
1366 draw_solid_square(x, y, WALL_TOP, ugc);
1367 if (! (maze[x][y] & WALL_BOTTOM))
1368 draw_solid_square(x, y, WALL_BOTTOM, ugc);
1377 solve_maze (void) /* solve it with graphical feedback */
1379 int i, dir, from, x, y, ways, bt = 0;
1381 /* plug up the surrounding wall */
1382 maze[end_x][end_y] |= (WALL_TOP >> end_dir);
1384 /* initialize search path */
1389 maze[end_x][end_y] |= SOLVER_VISIT;
1394 if ( maze[path[i].x][path[i].y] & START_SQUARE )
1397 /* Abort solve on expose - cheapo repaint strategy */
1398 if (check_events()) return;
1400 if (solve_delay) usleep (solve_delay);
1405 /* First visit this square. Which adjacent squares are open? */
1406 for(dir = WALL_TOP; dir & WALL_ANY; dir >>= 1)
1408 if(maze[path[i].x][path[i].y] & dir)
1411 y = path[i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1412 x = path[i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1414 if(maze[x][y] & SOLVER_VISIT)
1417 from = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1418 /* don't enter obvious dead ends */
1419 if(((maze[x][y] & WALL_ANY) | from) != WALL_ANY)
1421 if(!longdeadend_p(path[i].x, path[i].y, x, y, dir))
1426 draw_solid_square(x, y, from, sgc);
1427 maze[x][y] |= SOLVER_VISIT;
1432 ways = path[i].ways;
1433 /* ways now has a bitmask of open paths. */
1438 x = path[i].x - start_x;
1439 y = path[i].y - start_y;
1441 if(abs(y) <= abs(x))
1442 dir = (x > 0) ? WALL_LEFT : WALL_RIGHT;
1444 dir = (y > 0) ? WALL_TOP : WALL_BOTTOM;
1454 dir = (y > 0) ? WALL_TOP : WALL_BOTTOM; break;
1457 dir = (x > 0) ? WALL_LEFT : WALL_RIGHT;
1465 dir = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1476 ways &= ~dir; /* tried this one */
1478 y = path[i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1479 x = path[i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1481 /* advance in direction dir */
1483 path[i].ways = ways;
1484 draw_solid_square(path[i].x, path[i].y, dir, tgc);
1491 maze[x][y] |= SOLVER_VISIT;
1497 printf("Unsolvable maze.\n");
1502 find_dead_regions();
1504 from = path[i-1].dir;
1505 from = (from << 2 & WALL_ANY) | (from >> 2 & WALL_ANY);
1507 draw_solid_square(path[i].x, path[i].y, from, cgc);
1514 enter_square (int n) /* move into a neighboring square */
1516 draw_solid_square( (int)path[n].x, (int)path[n].y,
1517 (int)path[n].dir, tgc);
1520 switch (path[n].dir) {
1521 case 0: path[n+1].x = path[n].x;
1522 path[n+1].y = path[n].y - 1;
1524 case 1: path[n+1].x = path[n].x + 1;
1525 path[n+1].y = path[n].y;
1527 case 2: path[n+1].x = path[n].x;
1528 path[n+1].y = path[n].y + 1;
1530 case 3: path[n+1].x = path[n].x - 1;
1531 path[n+1].y = path[n].y;
1539 * jmr additions for Jamie Zawinski's <jwz@jwz.org> screensaver stuff,
1540 * note that the code above this has probably been hacked about in some
1544 char *progclass = "Maze";
1546 char *defaults[] = {
1547 ".background: black",
1548 ".foreground: white",
1550 "*solveDelay: 5000",
1551 "*preDelay: 2000000",
1552 "*postDelay: 4000000",
1553 "*liveColor: green",
1555 "*skipColor: orange",
1556 "*surroundColor: slateblue",
1567 XrmOptionDescRec options[] = {
1568 { "-grid-size", ".gridSize", XrmoptionSepArg, 0 },
1569 { "-solve-delay", ".solveDelay", XrmoptionSepArg, 0 },
1570 { "-pre-delay", ".preDelay", XrmoptionSepArg, 0 },
1571 { "-post-delay", ".postDelay", XrmoptionSepArg, 0 },
1572 { "-live-color", ".liveColor", XrmoptionSepArg, 0 },
1573 { "-dead-color", ".deadColor", XrmoptionSepArg, 0 },
1574 { "-skip-color", ".skipColor", XrmoptionSepArg, 0 },
1575 { "-surround-color", ".surroundColor",XrmoptionSepArg, 0 },
1576 { "-generator", ".generator", XrmoptionSepArg, 0 },
1577 { "-max-length", ".maxLength", XrmoptionSepArg, 0 },
1578 { "-bridge", ".bridge", XrmoptionNoArg, "True" },
1579 { "-no-bridge", ".bridge", XrmoptionNoArg, "False" },
1584 extern void skull (Display *, Window, GC, GC, int, int, int, int);
1588 screenhack(Display *display, Window window)
1591 int size, root, generator, this_gen;
1592 XWindowAttributes xgwa;
1593 unsigned long bg, fg, pfg, pbg, lfg, sfg, ufg;
1595 size = get_integer_resource ("gridSize", "Dimension");
1596 root = get_boolean_resource("root", "Boolean");
1597 solve_delay = get_integer_resource ("solveDelay", "Integer");
1598 pre_solve_delay = get_integer_resource ("preDelay", "Integer");
1599 post_solve_delay = get_integer_resource ("postDelay", "Integer");
1600 generator = get_integer_resource("generator", "Integer");
1601 max_length = get_integer_resource("maxLength", "Integer");
1602 bridge_p = get_boolean_resource("bridge", "Boolean");
1604 if (size < 2) size = 7 + (random () % 30);
1605 grid_width = grid_height = size;
1606 bw = (size > 6 ? 3 : (size-1)/2);
1608 dpy = display; win = window; /* the maze stuff uses global variables */
1610 XGetWindowAttributes (dpy, win, &xgwa);
1615 set_maze_sizes (xgwa.width, xgwa.height);
1619 XWindowAttributes xgwa;
1620 XGetWindowAttributes (dpy, window, &xgwa);
1621 XSelectInput (dpy, win,
1622 xgwa.your_event_mask | ExposureMask |
1623 ButtonPressMask |StructureNotifyMask);
1626 gc = XCreateGC(dpy, win, 0, 0);
1627 cgc = XCreateGC(dpy, win, 0, 0);
1628 tgc = XCreateGC(dpy, win, 0, 0);
1629 sgc = XCreateGC(dpy, win, 0, 0);
1630 ugc = XCreateGC(dpy, win, 0, 0);
1631 logo_gc = XCreateGC(dpy, win, 0, 0);
1632 erase_gc = XCreateGC(dpy, win, 0, 0);
1634 gray = XCreateBitmapFromData (dpy,win,gray1_bits,gray1_width,gray1_height);
1636 bg = get_pixel_resource ("background","Background", dpy, xgwa.colormap);
1637 fg = get_pixel_resource ("foreground","Foreground", dpy, xgwa.colormap);
1638 lfg = get_pixel_resource ("logoColor", "Foreground", dpy, xgwa.colormap);
1639 pfg = get_pixel_resource ("liveColor", "Foreground", dpy, xgwa.colormap);
1640 pbg = get_pixel_resource ("deadColor", "Foreground", dpy, xgwa.colormap);
1641 sfg = get_pixel_resource ("skipColor", "Foreground", dpy, xgwa.colormap);
1642 ufg = get_pixel_resource ("surroundColor", "Foreground", dpy, xgwa.colormap);
1643 if (mono_p) lfg = pfg = fg;
1646 lfg = ((bg == WhitePixel (dpy, DefaultScreen (dpy)))
1647 ? BlackPixel (dpy, DefaultScreen (dpy))
1648 : WhitePixel (dpy, DefaultScreen (dpy)));
1650 XSetForeground (dpy, gc, fg);
1651 XSetBackground (dpy, gc, bg);
1652 XSetForeground (dpy, cgc, pbg);
1653 XSetBackground (dpy, cgc, bg);
1654 XSetForeground (dpy, tgc, pfg);
1655 XSetBackground (dpy, tgc, bg);
1656 XSetForeground (dpy, sgc, sfg);
1657 XSetBackground (dpy, sgc, bg);
1658 XSetForeground (dpy, ugc, ufg);
1659 XSetBackground (dpy, ugc, bg);
1660 XSetForeground (dpy, logo_gc, lfg);
1661 XSetBackground (dpy, logo_gc, bg);
1662 XSetForeground (dpy, erase_gc, bg);
1663 XSetBackground (dpy, erase_gc, bg);
1665 XSetStipple (dpy, cgc, gray);
1666 XSetFillStyle (dpy, cgc, FillOpaqueStippled);
1667 XSetStipple (dpy, sgc, gray);
1668 XSetFillStyle (dpy, sgc, FillOpaqueStippled);
1669 XSetStipple (dpy, ugc, gray);
1670 XSetFillStyle (dpy, ugc, FillOpaqueStippled);
1676 GC draw_gc, erase_gc;
1677 /* round up to grid size */
1678 w = ((logo_width / grid_width) + 1) * grid_width;
1679 h = ((logo_height / grid_height) + 1) * grid_height;
1680 logo_map = XCreatePixmap (dpy, win, w, h, 1);
1681 gcv.foreground = 1L;
1682 draw_gc = XCreateGC (dpy, logo_map, GCForeground, &gcv);
1683 gcv.foreground = 0L;
1684 erase_gc= XCreateGC (dpy, logo_map, GCForeground, &gcv);
1685 XFillRectangle (dpy, logo_map, erase_gc, 0, 0, w, h);
1686 skull (dpy, logo_map, draw_gc, erase_gc, 5, 0, w-10, h-10);
1687 XFreeGC (dpy, draw_gc);
1688 XFreeGC (dpy, erase_gc);
1691 if (!(logo_map = XCreateBitmapFromData (dpy, win, logo_bits,
1692 logo_width, logo_height)))
1694 fprintf (stderr, "Can't create logo pixmap\n");
1698 XMapRaised(dpy, win);
1702 sync_p = !(random() % 10);
1704 while (1) { /* primary execution loop [ rhess ] */
1705 if (check_events()) continue ;
1706 if (restart || stop) goto pop;
1712 XClearWindow(dpy, win);
1716 this_gen = generator;
1717 if(this_gen<0 || this_gen>2)
1718 this_gen = random()%3;
1735 usleep (pre_solve_delay);
1742 usleep (post_solve_delay);
1744 erase_full_window(display, window);
1753 static XWindowAttributes wattr;
1757 XGetWindowAttributes (dpy, win, &wattr);
1758 set_maze_sizes (wattr.width, wattr.height);
1759 XClearWindow (dpy, win);
1761 sync_p = !(random() % 10);