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 ".background: black",
1328 ".foreground: white",
1330 "*solveDelay: 5000",
1331 "*preDelay: 2000000",
1332 "*postDelay: 4000000",
1333 "*liveColor: green",
1345 XrmOptionDescRec options[] = {
1346 { "-grid-size", ".gridSize", XrmoptionSepArg, 0 },
1347 { "-solve-delay", ".solveDelay", XrmoptionSepArg, 0 },
1348 { "-pre-delay", ".preDelay", XrmoptionSepArg, 0 },
1349 { "-post-delay", ".postDelay", XrmoptionSepArg, 0 },
1350 { "-live-color", ".liveColor", XrmoptionSepArg, 0 },
1351 { "-dead-color", ".deadColor", XrmoptionSepArg, 0 },
1352 { "-generator", ".generator", XrmoptionSepArg, 0 },
1353 { "-max-length", ".maxLength", XrmoptionSepArg, 0 },
1354 { "-bridge", ".bridge", XrmoptionNoArg, "True" },
1355 { "-no-bridge", ".bridge", XrmoptionNoArg, "False" },
1360 extern void skull (Display *, Window, GC, GC, int, int, int, int);
1364 screenhack(Display *display, Window window)
1367 int size, root, generator, this_gen;
1368 XWindowAttributes xgwa;
1369 unsigned long bg, fg, pfg, pbg, lfg;
1371 size = get_integer_resource ("gridSize", "Dimension");
1372 root = get_boolean_resource("root", "Boolean");
1373 solve_delay = get_integer_resource ("solveDelay", "Integer");
1374 pre_solve_delay = get_integer_resource ("preDelay", "Integer");
1375 post_solve_delay = get_integer_resource ("postDelay", "Integer");
1376 generator = get_integer_resource("generator", "Integer");
1377 max_length = get_integer_resource("maxLength", "Integer");
1378 bridge_p = get_boolean_resource("bridge", "Boolean");
1380 if (size < 2) size = 7 + (random () % 30);
1381 grid_width = grid_height = size;
1382 bw = (size > 6 ? 3 : (size-1)/2);
1384 dpy = display; win = window; /* the maze stuff uses global variables */
1386 XGetWindowAttributes (dpy, win, &xgwa);
1391 set_maze_sizes (xgwa.width, xgwa.height);
1394 XSelectInput (dpy, win, ExposureMask|ButtonPressMask|StructureNotifyMask);
1396 gc = XCreateGC(dpy, win, 0, 0);
1397 cgc = XCreateGC(dpy, win, 0, 0);
1398 tgc = XCreateGC(dpy,win,0,0);
1399 logo_gc = XCreateGC(dpy, win, 0, 0);
1400 erase_gc = XCreateGC(dpy, win, 0, 0);
1402 gray = XCreateBitmapFromData (dpy,win,gray1_bits,gray1_width,gray1_height);
1404 bg = get_pixel_resource ("background","Background", dpy, xgwa.colormap);
1405 fg = get_pixel_resource ("foreground","Foreground", dpy, xgwa.colormap);
1406 lfg = get_pixel_resource ("logoColor", "Foreground", dpy, xgwa.colormap);
1407 pfg = get_pixel_resource ("liveColor", "Foreground", dpy, xgwa.colormap);
1408 pbg = get_pixel_resource ("deadColor", "Foreground", dpy, xgwa.colormap);
1409 if (mono_p) lfg = pfg = fg;
1412 lfg = ((bg == WhitePixel (dpy, DefaultScreen (dpy)))
1413 ? BlackPixel (dpy, DefaultScreen (dpy))
1414 : WhitePixel (dpy, DefaultScreen (dpy)));
1416 XSetForeground (dpy, gc, fg);
1417 XSetBackground (dpy, gc, bg);
1418 XSetForeground (dpy, cgc, pbg);
1419 XSetBackground (dpy, cgc, bg);
1420 XSetForeground (dpy, tgc, pfg);
1421 XSetBackground (dpy, tgc, bg);
1422 XSetForeground (dpy, logo_gc, lfg);
1423 XSetBackground (dpy, logo_gc, bg);
1424 XSetForeground (dpy, erase_gc, bg);
1425 XSetBackground (dpy, erase_gc, bg);
1427 XSetStipple (dpy, cgc, gray);
1428 XSetFillStyle (dpy, cgc, FillOpaqueStippled);
1434 GC draw_gc, erase_gc;
1435 /* round up to grid size */
1436 w = ((logo_width / grid_width) + 1) * grid_width;
1437 h = ((logo_height / grid_height) + 1) * grid_height;
1438 logo_map = XCreatePixmap (dpy, win, w, h, 1);
1439 gcv.foreground = 1L;
1440 draw_gc = XCreateGC (dpy, logo_map, GCForeground, &gcv);
1441 gcv.foreground = 0L;
1442 erase_gc= XCreateGC (dpy, logo_map, GCForeground, &gcv);
1443 XFillRectangle (dpy, logo_map, erase_gc, 0, 0, w, h);
1444 skull (dpy, logo_map, draw_gc, erase_gc, 5, 0, w-10, h-10);
1445 XFreeGC (dpy, draw_gc);
1446 XFreeGC (dpy, erase_gc);
1449 if (!(logo_map = XCreateBitmapFromData (dpy, win, logo_bits,
1450 logo_width, logo_height)))
1452 fprintf (stderr, "Can't create logo pixmap\n");
1456 XMapRaised(dpy, win);
1460 sync_p = !(random() % 10);
1462 while (1) { /* primary execution loop [ rhess ] */
1463 if (check_events()) continue ;
1464 if (restart || stop) goto pop;
1470 XClearWindow(dpy, win);
1474 this_gen = generator;
1475 if(this_gen<0 || this_gen>2)
1476 this_gen = random()%3;
1493 usleep (pre_solve_delay);
1500 usleep (post_solve_delay);
1502 erase_full_window(display, window);
1511 static XWindowAttributes wattr;
1515 XGetWindowAttributes (dpy, win, &wattr);
1516 set_maze_sizes (wattr.width, wattr.height);
1517 XClearWindow (dpy, win);
1519 sync_p = !(random() % 10);