1 /******************************************************************************
4 * modified: [ 4-10-97 ] Johannes Keukelaar <johannes@nada.kth.se>
5 * Added multiple maze creators. Robustified solver.
7 * modified: [ 8-11-95 ] Ed James <james@mml.mmc.com>
8 * added fill of dead-end box to solve_maze while loop.
9 * modified: [ 3-7-93 ] Jamie Zawinski <jwz@netscape.com>
10 * added the XRoger logo, cleaned up resources, made
11 * grid size a parameter.
12 * modified: [ 3-3-93 ] Jim Randell <jmr@mddjmr.fc.hp.com>
13 * Added the colour stuff and integrated it with jwz's
14 * screenhack stuff. There's still some work that could
15 * be done on this, particularly allowing a resource to
16 * specify how big the squares are.
17 * modified: [ 10-4-88 ] Richard Hess ...!uunet!cimshop!rhess
18 * [ Revised primary execution loop within main()...
19 * [ Extended X event handler, check_events()...
20 * modified: [ 1-29-88 ] Dave Lemke lemke@sun.com
22 * [ Note the word "hacked" -- this is extremely ugly, but at
23 * [ least it does the job. NOT a good programming example
25 * original: [ 6/21/85 ] Martin Weiss Sun Microsystems [ SunView ]
27 ******************************************************************************
28 Copyright 1988 by Sun Microsystems, Inc. Mountain View, CA.
32 Permission to use, copy, modify, and distribute this software and its
33 documentation for any purpose and without fee is hereby granted,
34 provided that the above copyright notice appear in all copies and that
35 both that copyright notice and this permission notice appear in
36 supporting documentation, and that the names of Sun or MIT not be
37 used in advertising or publicity pertaining to distribution of the
38 software without specific prior written permission. Sun and M.I.T.
39 make no representations about the suitability of this software for
40 any purpose. It is provided "as is" without any express or implied warranty.
42 SUN DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
43 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
44 PURPOSE. IN NO EVENT SHALL SUN BE LIABLE FOR ANY SPECIAL, INDIRECT
45 OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
46 OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
47 OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE
48 OR PERFORMANCE OF THIS SOFTWARE.
49 *****************************************************************************/
51 #include "screenhack.h"
56 static int solve_delay, pre_solve_delay, post_solve_delay;
60 #include <X11/Xutil.h>
62 # include <X11/bitmaps/gray1>
64 # include "sys$common:[decw$include.bitmaps]gray1.xbm"
67 #define MAX_MAZE_SIZE_X 500
68 #define MAX_MAZE_SIZE_Y 500
70 #define MOVE_LIST_SIZE (MAX_MAZE_SIZE_X * MAX_MAZE_SIZE_Y)
72 #define WALL_TOP 0x8000
73 #define WALL_RIGHT 0x4000
74 #define WALL_BOTTOM 0x2000
75 #define WALL_LEFT 0x1000
77 #define DOOR_IN_TOP 0x800
78 #define DOOR_IN_RIGHT 0x400
79 #define DOOR_IN_BOTTOM 0x200
80 #define DOOR_IN_LEFT 0x100
81 #define DOOR_IN_ANY 0xF00
83 #define DOOR_OUT_TOP 0x80
84 #define DOOR_OUT_RIGHT 0x40
85 #define DOOR_OUT_BOTTOM 0x20
86 #define DOOR_OUT_LEFT 0x10
88 #define SOLVER_VISIT 0x4
89 #define START_SQUARE 0x2
90 #define END_SQUARE 0x1
95 #define get_random(x) (random() % (x))
97 static int logo_x, logo_y;
100 # define logo_width 128
101 # define logo_height 128
103 # include <X11/bitmaps/xlogo64>
104 # define logo_width xlogo64_width
105 # define logo_height xlogo64_height
106 # define logo_bits xlogo64_bits
109 static unsigned short maze[MAX_MAZE_SIZE_X][MAX_MAZE_SIZE_Y];
115 } move_list[MOVE_LIST_SIZE], save_path[MOVE_LIST_SIZE], path[MOVE_LIST_SIZE];
117 static int maze_size_x, maze_size_y;
118 static int sqnum, cur_sq_x, cur_sq_y, path_length;
119 static int start_x, start_y, start_dir, end_x, end_y, end_dir;
120 static int grid_width, grid_height;
125 static GC gc, cgc, tgc, logo_gc, erase_gc;
126 static Pixmap logo_map;
128 static int x = 0, y = 0, restart = 0, stop = 1, state = 1, max_length;
129 static int sync_p, bridge_p;
132 check_events (void) /* X event handler [ rhess ] */
141 switch (e.xbutton.button) {
147 if (state == 5) state = 4 ;
160 case ConfigureNotify:
165 XClearWindow (dpy, win);
179 set_maze_sizes (int width, int height)
181 maze_size_x = width / grid_width;
182 maze_size_y = height / grid_height;
187 initialize_maze (void) /* draw the surrounding wall and start/end squares */
189 register int i, j, wall;
190 int logow = 1 + logo_width / grid_width;
191 int logoh = 1 + logo_height / grid_height;
193 /* initialize all squares */
194 for ( i=0; i<maze_size_x; i++) {
195 for ( j=0; j<maze_size_y; j++) {
201 for ( i=0; i<maze_size_x; i++ ) {
202 maze[i][0] |= WALL_TOP;
206 for ( j=0; j<maze_size_y; j++ ) {
207 maze[maze_size_x-1][j] |= WALL_RIGHT;
211 for ( i=0; i<maze_size_x; i++ ) {
212 maze[i][maze_size_y-1] |= WALL_BOTTOM;
216 for ( j=0; j<maze_size_y; j++ ) {
217 maze[0][j] |= WALL_LEFT;
220 /* set start square */
221 wall = get_random(4);
224 i = get_random(maze_size_x);
229 j = get_random(maze_size_y);
232 i = get_random(maze_size_x);
237 j = get_random(maze_size_y);
240 maze[i][j] |= START_SQUARE;
241 maze[i][j] |= ( DOOR_IN_TOP >> wall );
242 maze[i][j] &= ~( WALL_TOP >> wall );
254 i = get_random(maze_size_x);
259 j = get_random(maze_size_y);
262 i = get_random(maze_size_x);
267 j = get_random(maze_size_y);
270 maze[i][j] |= END_SQUARE;
271 maze[i][j] |= ( DOOR_OUT_TOP >> wall );
272 maze[i][j] &= ~( WALL_TOP >> wall );
278 if ((maze_size_x-logow >= 6) && (maze_size_y-logoh >= 6))
280 /* not closer than 3 grid units from a wall */
281 logo_x = get_random (maze_size_x - logow - 5) + 3;
282 logo_y = get_random (maze_size_y - logoh - 5) + 3;
283 for (i=0; i<logow; i++)
284 for (j=0; j<logoh; j++)
285 maze[logo_x + i][logo_y + j] |= DOOR_IN_TOP;
288 logo_y = logo_x = -1;
291 static int choose_door (void);
292 static int backup (void);
293 static void draw_wall (int, int, int, GC);
294 static void draw_solid_square (int, int, int, GC);
295 /*static void enter_square (int);*/
296 static void build_wall (int, int, int);
297 /*static void break_wall (int, int, int);*/
299 static void join_sets(int, int);
301 /* For set_create_maze. */
302 /* The sets that our squares are in. */
303 static int *sets = 0;
304 /* The `list' of hedges. */
305 static int *hedges = 0;
309 /* Initialise the sets. */
317 sets = (int *)malloc(maze_size_x*maze_size_y*sizeof(int));
320 for(i = 0; i < maze_size_x*maze_size_y; i++)
327 hedges = (int *)malloc(maze_size_x*maze_size_y*2*sizeof(int));
330 for(i = 0; i < maze_size_x*maze_size_y*2; i++)
334 /* Mask out outside walls. */
335 for(i = 0; i < maze_size_y; i++)
337 hedges[2*((maze_size_x)*i+maze_size_x-1)+1] = -1;
339 for(i = 0; i < maze_size_x; i++)
341 hedges[2*((maze_size_y-1)*maze_size_x+i)] = -1;
343 /* Mask out a possible logo. */
346 int logow = 1 + logo_width / grid_width;
347 int logoh = 1 + logo_height / grid_height;
348 int bridge_dir, bridge_c;
350 if(bridge_p && logoh>=3 && logow>=3)
352 bridge_dir = 1+random()%2;
355 bridge_c = logo_y+random()%(logoh-2)+1;
359 bridge_c = logo_x+random()%(logow-2)+1;
368 for(x = logo_x; x < logo_x+logow; x++)
369 for(y = logo_y; y < logo_y+logoh; y++)
371 /* I should check for the bridge here, except that I join the
372 * bridge together below.
374 hedges[2*(x+maze_size_x*y)+1] = -1;
375 hedges[2*(x+maze_size_x*y)] = -1;
377 for(x = logo_x; x < logo_x+logow; x++)
379 if(!(bridge_dir==2 && x==bridge_c))
381 build_wall(x, logo_y, 0);
382 build_wall(x, logo_y+logoh, 0);
384 hedges[2*(x+maze_size_x*(logo_y-1))] = -1;
387 build_wall(x, bridge_c, 0);
388 build_wall(x, bridge_c, 2);
391 for(y = logo_y; y < logo_y+logoh; y++)
393 if(!(bridge_dir==1 && y==bridge_c))
395 build_wall(logo_x, y, 3);
396 build_wall(logo_x+logow, y, 3);
398 hedges[2*(logo_x-1+maze_size_x*y)+1] = -1;
401 build_wall(bridge_c, y, 1);
402 build_wall(bridge_c, y, 3);
405 /* Join the whole bridge together. */
412 for(i = logo_x; i < logo_x+logow+1; i++)
413 join_sets(x+y*maze_size_x, i+y*maze_size_x);
419 for(i = logo_y; i < logo_y+logoh+1; i++)
420 join_sets(x+y*maze_size_x, x+i*maze_size_x);
425 for(i = 0; i < maze_size_x*maze_size_y*2; i++)
428 r = random()%(maze_size_x*maze_size_y*2);
429 hedges[i] = hedges[r];
434 /* Get the representative of a set. */
444 s = get_set(sets[num]);
450 /* Join two sets together. */
452 join_sets(num1, num2)
466 /* Exitialise the sets. */
479 /* Temporary hack. */
481 show_set(int num, GC gc)
487 for(x = 0; x < maze_size_x; x++)
488 for(y = 0; y < maze_size_y; y++)
490 if(get_set(x+y*maze_size_x)==set)
492 XFillRectangle(dpy, win, gc, border_x + bw + grid_width * x,
493 border_y + bw + grid_height * y,
494 grid_width-2*bw , grid_height-2*bw);
500 /* Second alternative maze creator: Put each square in the maze in a
501 * separate set. Also, make a list of all the hedges. Randomize that list.
502 * Walk through the list. If, for a certain hedge, the two squares on both
503 * sides of it are in different sets, union the sets and remove the hedge.
504 * Continue until all hedges have been processed or only one set remains.
507 set_create_maze(void)
509 int i, h, x, y, dir, v, w;
515 /* Do almost all the setup. */
518 /* Start running through the hedges. */
519 for(i = 0; i < 2*maze_size_x*maze_size_y; i++)
523 /* This one is in the logo or outside border. */
528 x = (h>>1)%maze_size_x;
529 y = (h>>1)/maze_size_x;
544 show_set(x+y*maze_size_x, logo_gc);
545 show_set(v+w*maze_size_x, tgc);
547 if(get_set(x+y*maze_size_x)!=get_set(v+w*maze_size_x))
552 join_sets(x+y*maze_size_x, v+w*maze_size_x);
553 /* Don't draw the wall. */
560 /* Don't join the sets. */
561 build_wall(x, y, dir);
571 show_set(x+y*maze_size_x, erase_gc);
572 show_set(v+w*maze_size_x, erase_gc);
576 /* Free some memory. */
580 /* First alternative maze creator: Pick a random, empty corner in the maze.
581 * Pick a random direction. Draw a wall in that direction, from that corner
582 * until we hit a wall. Option: Only draw the wall if it's going to be
583 * shorter than a certain length. Otherwise we get lots of long walls.
586 alt_create_maze(void)
590 int i, j, height, width, open_corners, k, dir, x, y;
592 height = maze_size_y+1;
593 width = maze_size_x+1;
595 /* Allocate and clear some mem. */
596 corners = (char *)calloc(height*width, 1);
600 /* Set up the indexing array. */
601 c_idx = (int *)malloc(sizeof(int)*height*width);
607 for(i = 0; i < height*width; i++)
609 for(i = 0; i < height*width; i++)
612 k = random()%(height*width);
617 /* Set up some initial walls. */
619 for(i = 0; i < width; i++)
622 corners[i+width*(height-1)] = 1;
624 for(i = 0; i < height; i++)
626 corners[i*width] = 1;
627 corners[i*width+width-1] = 1;
629 /* Walls around logo. In fact, inside the logo, too. */
630 /* Also draw the walls. */
633 int logow = 1 + logo_width / grid_width;
634 int logoh = 1 + logo_height / grid_height;
635 int bridge_dir, bridge_c;
637 if(bridge_p && logoh>=3 && logow>=3)
639 bridge_dir = 1+random()%2;
642 bridge_c = logo_y+random()%(logoh-2)+1;
646 bridge_c = logo_x+random()%(logow-2)+1;
654 for(i = logo_x; i <= logo_x + logow; i++)
656 for(j = logo_y; j <= logo_y + logoh; j++)
658 corners[i+width*j] = 1;
661 for(x = logo_x; x < logo_x+logow; x++)
663 if(!(bridge_dir==2 && x==bridge_c))
665 build_wall(x, logo_y, 0);
666 build_wall(x, logo_y+logoh, 0);
670 build_wall(x, bridge_c, 0);
671 build_wall(x, bridge_c, 2);
674 for(y = logo_y; y < logo_y+logoh; y++)
676 if(!(bridge_dir==1 && y==bridge_c))
678 build_wall(logo_x, y, 3);
679 build_wall(logo_x+logow, y, 3);
683 build_wall(bridge_c, y, 1);
684 build_wall(bridge_c, y, 3);
687 /* Connect one wall of the logo with an outside wall. */
689 dir = (bridge_dir+1)%4;
695 x = logo_x+(random()%(logow+1));
700 y = logo_y+(random()%(logoh+1));
703 x = logo_x+(random()%(logow+1));
708 y = logo_y+(random()%(logoh+1));
713 corners[x+width*y] = 1;
717 build_wall(x-1, y-1, 1);
729 build_wall(x-1, y-1, 2);
734 while(!corners[x+width*y]);
741 x = logo_x+(random()%(logow+1));
746 y = logo_y+(random()%(logoh+1));
749 x = logo_x+(random()%(logow+1));
754 y = logo_y+(random()%(logoh+1));
759 corners[x+width*y] = 1;
763 build_wall(x-1, y-1, 1);
775 build_wall(x-1, y-1, 2);
780 while(!corners[x+width*y]);
784 /* Count open gridpoints. */
786 for(i = 0; i < width; i++)
787 for(j = 0; j < height; j++)
788 if(!corners[i+width*j])
791 /* Now do actual maze generation. */
792 while(open_corners>0)
794 for(i = 0; i < width*height; i++)
796 if(!corners[c_idx[i]])
800 /* Choose a random direction. */
804 /* Measure the length of the wall we'd draw. */
805 while(!corners[x+width*y])
830 /* Draw a wall until we hit something. */
831 while(!corners[x+width*y])
834 corners[x+width*y] = 1;
838 build_wall(x-1, y-1, 1);
850 build_wall(x-1, y-1, 2);
860 /* Free some memory we used. */
865 /* The original maze creator. Start somewhere. Take a step in a random
866 * direction. Keep doing this until we hit a wall. Then, backtrack until
867 * we find a point where we can go in another direction.
870 create_maze (void) /* create a maze layout given the initialized maze */
872 register int i, newdoor = 0;
873 int logow = 1 + logo_width / grid_width;
874 int logoh = 1 + logo_height / grid_height;
876 /* Maybe we should make a bridge? */
877 if(bridge_p && logo_x>=0 && logow>=3 && logoh>=3)
879 int bridge_dir, bridge_c;
881 bridge_dir = 1+random()%2;
885 bridge_c = logo_y+random()%(logoh-2)+1;
887 bridge_c = logo_y+random()%logoh;
892 bridge_c = logo_x+random()%(logow-2)+1;
894 bridge_c = logo_x+random()%logow;
899 for(i = logo_x; i < logo_x+logow; i++)
901 maze[i][bridge_c] &= ~DOOR_IN_TOP;
906 for(i = logo_y; i < logo_y+logoh; i++)
908 maze[bridge_c][i] &= ~DOOR_IN_TOP;
914 move_list[sqnum].x = cur_sq_x;
915 move_list[sqnum].y = cur_sq_y;
916 move_list[sqnum].dir = newdoor;
917 while ( ( newdoor = choose_door() ) == -1 ) { /* pick a door */
918 if ( backup() == -1 ) { /* no more doors ... backup */
919 return; /* done ... return */
923 /* mark the out door */
924 maze[cur_sq_x][cur_sq_y] |= ( DOOR_OUT_TOP >> newdoor );
938 /* mark the in door */
939 maze[cur_sq_x][cur_sq_y] |= ( DOOR_IN_TOP >> ((newdoor+2)%4) );
941 /* if end square set path length and save path */
942 if ( maze[cur_sq_x][cur_sq_y] & END_SQUARE ) {
944 for ( i=0; i<path_length; i++) {
945 save_path[i].x = move_list[i].x;
946 save_path[i].y = move_list[i].y;
947 save_path[i].dir = move_list[i].dir;
957 choose_door (void) /* pick a new path */
960 register int num_candidates;
965 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_TOP )
967 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_TOP )
969 if ( maze[cur_sq_x][cur_sq_y] & WALL_TOP )
971 if ( maze[cur_sq_x][cur_sq_y - 1] & DOOR_IN_ANY ) {
972 maze[cur_sq_x][cur_sq_y] |= WALL_TOP;
973 maze[cur_sq_x][cur_sq_y - 1] |= WALL_BOTTOM;
974 draw_wall(cur_sq_x, cur_sq_y, 0, gc);
977 candidates[num_candidates++] = 0;
981 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_RIGHT )
983 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_RIGHT )
985 if ( maze[cur_sq_x][cur_sq_y] & WALL_RIGHT )
987 if ( maze[cur_sq_x + 1][cur_sq_y] & DOOR_IN_ANY ) {
988 maze[cur_sq_x][cur_sq_y] |= WALL_RIGHT;
989 maze[cur_sq_x + 1][cur_sq_y] |= WALL_LEFT;
990 draw_wall(cur_sq_x, cur_sq_y, 1, gc);
993 candidates[num_candidates++] = 1;
997 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_BOTTOM )
999 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_BOTTOM )
1001 if ( maze[cur_sq_x][cur_sq_y] & WALL_BOTTOM )
1003 if ( maze[cur_sq_x][cur_sq_y + 1] & DOOR_IN_ANY ) {
1004 maze[cur_sq_x][cur_sq_y] |= WALL_BOTTOM;
1005 maze[cur_sq_x][cur_sq_y + 1] |= WALL_TOP;
1006 draw_wall(cur_sq_x, cur_sq_y, 2, gc);
1009 candidates[num_candidates++] = 2;
1013 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_LEFT )
1015 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_LEFT )
1017 if ( maze[cur_sq_x][cur_sq_y] & WALL_LEFT )
1019 if ( maze[cur_sq_x - 1][cur_sq_y] & DOOR_IN_ANY ) {
1020 maze[cur_sq_x][cur_sq_y] |= WALL_LEFT;
1021 maze[cur_sq_x - 1][cur_sq_y] |= WALL_RIGHT;
1022 draw_wall(cur_sq_x, cur_sq_y, 3, gc);
1025 candidates[num_candidates++] = 3;
1028 if (num_candidates == 0)
1030 if (num_candidates == 1)
1031 return ( candidates[0] );
1032 return ( candidates[ get_random(num_candidates) ] );
1038 backup (void) /* back up a move */
1041 cur_sq_x = move_list[sqnum].x;
1042 cur_sq_y = move_list[sqnum].y;
1048 draw_maze_border (void) /* draw the maze outline */
1053 for ( i=0; i<maze_size_x; i++) {
1054 if ( maze[i][0] & WALL_TOP ) {
1055 XDrawLine(dpy, win, gc,
1056 border_x + grid_width * i,
1058 border_x + grid_width * (i+1) - 1,
1061 if ((maze[i][maze_size_y - 1] & WALL_BOTTOM)) {
1062 XDrawLine(dpy, win, gc,
1063 border_x + grid_width * i,
1064 border_y + grid_height * (maze_size_y) - 1,
1065 border_x + grid_width * (i+1) - 1,
1066 border_y + grid_height * (maze_size_y) - 1);
1069 for ( j=0; j<maze_size_y; j++) {
1070 if ( maze[maze_size_x - 1][j] & WALL_RIGHT ) {
1071 XDrawLine(dpy, win, gc,
1072 border_x + grid_width * maze_size_x - 1,
1073 border_y + grid_height * j,
1074 border_x + grid_width * maze_size_x - 1,
1075 border_y + grid_height * (j+1) - 1);
1077 if ( maze[0][j] & WALL_LEFT ) {
1078 XDrawLine(dpy, win, gc,
1080 border_y + grid_height * j,
1082 border_y + grid_height * (j+1) - 1);
1090 unsigned int w, h, bw, d;
1091 XGetGeometry (dpy, logo_map, &r, &x, &y, &w, &h, &bw, &d);
1092 XCopyPlane (dpy, logo_map, win, logo_gc,
1094 border_x + 3 + grid_width * logo_x,
1095 border_y + 3 + grid_height * logo_y, 1);
1097 draw_solid_square (start_x, start_y, start_dir, tgc);
1098 draw_solid_square (end_x, end_y, end_dir, tgc);
1103 draw_wall(int i, int j, int dir, GC gc) /* draw a single wall */
1107 XDrawLine(dpy, win, gc,
1108 border_x + grid_width * i,
1109 border_y + grid_height * j,
1110 border_x + grid_width * (i+1),
1111 border_y + grid_height * j);
1114 XDrawLine(dpy, win, gc,
1115 border_x + grid_width * (i+1),
1116 border_y + grid_height * j,
1117 border_x + grid_width * (i+1),
1118 border_y + grid_height * (j+1));
1121 XDrawLine(dpy, win, gc,
1122 border_x + grid_width * i,
1123 border_y + grid_height * (j+1),
1124 border_x + grid_width * (i+1),
1125 border_y + grid_height * (j+1));
1128 XDrawLine(dpy, win, gc,
1129 border_x + grid_width * i,
1130 border_y + grid_height * j,
1131 border_x + grid_width * i,
1132 border_y + grid_height * (j+1));
1139 /* Actually build a wall. */
1141 build_wall(i, j, dir)
1144 /* Draw it on the screen. */
1145 draw_wall(i, j, dir, gc);
1146 /* Put it in the maze. */
1150 maze[i][j] |= WALL_TOP;
1152 maze[i][j-1] |= WALL_BOTTOM;
1155 maze[i][j] |= WALL_RIGHT;
1157 maze[i+1][j] |= WALL_LEFT;
1160 maze[i][j] |= WALL_BOTTOM;
1162 maze[i][j+1] |= WALL_TOP;
1165 maze[i][j] |= WALL_LEFT;
1167 maze[i-1][j] |= WALL_RIGHT;
1172 /* Break out a wall. */
1175 break_wall(i, j, dir)
1178 /* Draw it on the screen. */
1179 draw_wall(i, j, dir, erase_gc);
1180 /* Put it in the maze. */
1184 maze[i][j] &= ~WALL_TOP;
1186 maze[i][j-1] &= ~WALL_BOTTOM;
1189 maze[i][j] &= ~WALL_RIGHT;
1191 maze[i+1][j] &= ~WALL_LEFT;
1194 maze[i][j] &= ~WALL_BOTTOM;
1196 maze[i][j+1] &= ~WALL_BOTTOM;
1199 maze[i][j] &= ~WALL_LEFT;
1201 maze[i-1][j] &= ~WALL_RIGHT;
1209 draw_solid_square(int i, int j, /* draw a solid square in a square */
1213 case 0: XFillRectangle(dpy, win, gc,
1214 border_x + bw + grid_width * i,
1215 border_y - bw + grid_height * j,
1216 grid_width - (bw+bw), grid_height);
1218 case 1: XFillRectangle(dpy, win, gc,
1219 border_x + bw + grid_width * i,
1220 border_y + bw + grid_height * j,
1221 grid_width, grid_height - (bw+bw));
1223 case 2: XFillRectangle(dpy, win, gc,
1224 border_x + bw + grid_width * i,
1225 border_y + bw + grid_height * j,
1226 grid_width - (bw+bw), grid_height);
1228 case 3: XFillRectangle(dpy, win, gc,
1229 border_x - bw + grid_width * i,
1230 border_y + bw + grid_height * j,
1231 grid_width, grid_height - (bw+bw));
1239 solve_maze (void) /* solve it with graphical feedback */
1242 int step_x[4] = { 0, 1, 0, -1 };
1243 int step_y[4] = { -1, 0, 1, 0 };
1245 /* plug up the surrounding wall */
1246 maze[start_x][start_y] |= (WALL_TOP >> start_dir);
1247 maze[end_x][end_y] |= (WALL_TOP >> end_dir);
1249 /* initialize search path */
1254 maze[end_x][end_y] |= SOLVER_VISIT;
1258 if ( ++path[i].dir >= 4 ) {
1259 XFillRectangle(dpy, win, cgc,
1260 border_x + bw + grid_width * (int)(path[i].x),
1261 border_y + bw + grid_height * (int)(path[i].y),
1262 grid_width - (bw+bw), grid_height - (bw+bw));
1264 if(i<0) /* Can't solve this maze. */
1266 printf("Unsolvable maze.\n");
1269 draw_solid_square( (int)(path[i].x), (int)(path[i].y),
1270 (int)(path[i].dir), cgc);
1272 else if ( (! (maze[path[i].x][path[i].y] & (WALL_TOP >> path[i].dir))) &&
1273 (!( maze[path[i].x+step_x[path[i].dir]]
1274 [path[i].y+step_y[path[i].dir]]&SOLVER_VISIT)) ) {
1275 path[i+1].x = path[i].x+step_x[path[i].dir];
1276 path[i+1].y = path[i].y+step_y[path[i].dir];
1278 draw_solid_square(path[i].x, path[i].y, path[i].dir, tgc);
1280 maze[path[i].x][path[i].y] |= SOLVER_VISIT;
1281 if ( maze[path[i].x][path[i].y] & START_SQUARE ) {
1285 if (check_events()) return;
1286 /* Abort solve on expose - cheapo repaint strategy */
1287 if (solve_delay) usleep (solve_delay);
1294 enter_square (int n) /* move into a neighboring square */
1296 draw_solid_square( (int)path[n].x, (int)path[n].y,
1297 (int)path[n].dir, tgc);
1300 switch (path[n].dir) {
1301 case 0: path[n+1].x = path[n].x;
1302 path[n+1].y = path[n].y - 1;
1304 case 1: path[n+1].x = path[n].x + 1;
1305 path[n+1].y = path[n].y;
1307 case 2: path[n+1].x = path[n].x;
1308 path[n+1].y = path[n].y + 1;
1310 case 3: path[n+1].x = path[n].x - 1;
1311 path[n+1].y = path[n].y;
1319 * jmr additions for Jamie Zawinski's <jwz@netscape.com> screensaver stuff,
1320 * note that the code above this has probably been hacked about in some
1324 char *progclass = "Maze";
1326 char *defaults[] = {
1327 "Maze.background: black", /* to placate SGI */
1328 "Maze.foreground: white", /* to placate SGI */
1330 "*solveDelay: 5000",
1331 "*preDelay: 2000000",
1332 "*postDelay: 4000000",
1333 "*liveColor: green",
1347 XrmOptionDescRec options[] = {
1348 { "-grid-size", ".gridSize", XrmoptionSepArg, 0 },
1349 { "-solve-delay", ".solveDelay", XrmoptionSepArg, 0 },
1350 { "-pre-delay", ".preDelay", XrmoptionSepArg, 0 },
1351 { "-post-delay", ".postDelay", XrmoptionSepArg, 0 },
1352 { "-live-color", ".liveColor", XrmoptionSepArg, 0 },
1353 { "-dead-color", ".deadColor", XrmoptionSepArg, 0 },
1354 { "-generator", ".generator", XrmoptionSepArg, 0 },
1355 { "-max-length", ".maxLength", XrmoptionSepArg, 0 },
1356 { "-bridge", ".bridge", XrmoptionNoArg, "True" },
1357 { "-no-bridge", ".bridge", XrmoptionNoArg, "False" },
1362 extern void skull (Display *, Window, GC, GC, int, int, int, int);
1366 screenhack(Display *display, Window window)
1369 int size, root, generator, this_gen;
1370 XWindowAttributes xgwa;
1371 unsigned long bg, fg, pfg, pbg, lfg;
1373 size = get_integer_resource ("gridSize", "Dimension");
1374 root = get_boolean_resource("root", "Boolean");
1375 solve_delay = get_integer_resource ("solveDelay", "Integer");
1376 pre_solve_delay = get_integer_resource ("preDelay", "Integer");
1377 post_solve_delay = get_integer_resource ("postDelay", "Integer");
1378 generator = get_integer_resource("generator", "Integer");
1379 max_length = get_integer_resource("maxLength", "Integer");
1380 bridge_p = get_boolean_resource("bridge", "Boolean");
1382 if (size < 2) size = 7 + (random () % 30);
1383 grid_width = grid_height = size;
1384 bw = (size > 6 ? 3 : (size-1)/2);
1386 dpy = display; win = window; /* the maze stuff uses global variables */
1388 XGetWindowAttributes (dpy, win, &xgwa);
1393 set_maze_sizes (xgwa.width, xgwa.height);
1396 XSelectInput (dpy, win, ExposureMask|ButtonPressMask|StructureNotifyMask);
1398 gc = XCreateGC(dpy, win, 0, 0);
1399 cgc = XCreateGC(dpy, win, 0, 0);
1400 tgc = XCreateGC(dpy,win,0,0);
1401 logo_gc = XCreateGC(dpy, win, 0, 0);
1402 erase_gc = XCreateGC(dpy, win, 0, 0);
1404 gray = XCreateBitmapFromData (dpy,win,gray1_bits,gray1_width,gray1_height);
1406 bg = get_pixel_resource ("background","Background", dpy, xgwa.colormap);
1407 fg = get_pixel_resource ("foreground","Foreground", dpy, xgwa.colormap);
1408 lfg = get_pixel_resource ("logoColor", "Foreground", dpy, xgwa.colormap);
1409 pfg = get_pixel_resource ("liveColor", "Foreground", dpy, xgwa.colormap);
1410 pbg = get_pixel_resource ("deadColor", "Foreground", dpy, xgwa.colormap);
1411 if (mono_p) lfg = pfg = fg;
1414 lfg = ((bg == WhitePixel (dpy, DefaultScreen (dpy)))
1415 ? BlackPixel (dpy, DefaultScreen (dpy))
1416 : WhitePixel (dpy, DefaultScreen (dpy)));
1418 XSetForeground (dpy, gc, fg);
1419 XSetBackground (dpy, gc, bg);
1420 XSetForeground (dpy, cgc, pbg);
1421 XSetBackground (dpy, cgc, bg);
1422 XSetForeground (dpy, tgc, pfg);
1423 XSetBackground (dpy, tgc, bg);
1424 XSetForeground (dpy, logo_gc, lfg);
1425 XSetBackground (dpy, logo_gc, bg);
1426 XSetForeground (dpy, erase_gc, bg);
1427 XSetBackground (dpy, erase_gc, bg);
1429 XSetStipple (dpy, cgc, gray);
1430 XSetFillStyle (dpy, cgc, FillOpaqueStippled);
1436 GC draw_gc, erase_gc;
1437 /* round up to grid size */
1438 w = ((logo_width / grid_width) + 1) * grid_width;
1439 h = ((logo_height / grid_height) + 1) * grid_height;
1440 logo_map = XCreatePixmap (dpy, win, w, h, 1);
1441 gcv.foreground = 1L;
1442 draw_gc = XCreateGC (dpy, logo_map, GCForeground, &gcv);
1443 gcv.foreground = 0L;
1444 erase_gc= XCreateGC (dpy, logo_map, GCForeground, &gcv);
1445 XFillRectangle (dpy, logo_map, erase_gc, 0, 0, w, h);
1446 skull (dpy, logo_map, draw_gc, erase_gc, 5, 0, w-10, h-10);
1447 XFreeGC (dpy, draw_gc);
1448 XFreeGC (dpy, erase_gc);
1451 if (!(logo_map = XCreateBitmapFromData (dpy, win, logo_bits,
1452 logo_width, logo_height)))
1454 fprintf (stderr, "Can't create logo pixmap\n");
1458 XMapRaised(dpy, win);
1462 sync_p = !(random() % 10);
1464 while (1) { /* primary execution loop [ rhess ] */
1465 if (check_events()) continue ;
1466 if (restart || stop) goto pop;
1472 XClearWindow(dpy, win);
1476 this_gen = generator;
1477 if(this_gen<0 || this_gen>2)
1478 this_gen = random()%3;
1495 usleep (pre_solve_delay);
1502 usleep (post_solve_delay);
1504 erase_full_window(display, window);
1513 static XWindowAttributes wattr;
1517 XGetWindowAttributes (dpy, win, &wattr);
1518 set_maze_sizes (wattr.width, wattr.height);
1519 XClearWindow (dpy, win);
1521 sync_p = !(random() % 10);