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"
55 static int solve_delay, pre_solve_delay, post_solve_delay;
59 #include <X11/Xutil.h>
61 # include <X11/bitmaps/gray1>
63 # include "sys$common:[decw$include.bitmaps]gray1.xbm"
66 #define MAX_MAZE_SIZE_X 500
67 #define MAX_MAZE_SIZE_Y 500
69 #define MOVE_LIST_SIZE (MAX_MAZE_SIZE_X * MAX_MAZE_SIZE_Y)
71 #define WALL_TOP 0x8000
72 #define WALL_RIGHT 0x4000
73 #define WALL_BOTTOM 0x2000
74 #define WALL_LEFT 0x1000
76 #define DOOR_IN_TOP 0x800
77 #define DOOR_IN_RIGHT 0x400
78 #define DOOR_IN_BOTTOM 0x200
79 #define DOOR_IN_LEFT 0x100
80 #define DOOR_IN_ANY 0xF00
82 #define DOOR_OUT_TOP 0x80
83 #define DOOR_OUT_RIGHT 0x40
84 #define DOOR_OUT_BOTTOM 0x20
85 #define DOOR_OUT_LEFT 0x10
87 #define SOLVER_VISIT 0x4
88 #define START_SQUARE 0x2
89 #define END_SQUARE 0x1
94 #define get_random(x) (random() % (x))
96 static int logo_x, logo_y;
99 # define logo_width 128
100 # define logo_height 128
102 # include <X11/bitmaps/xlogo64>
103 # define logo_width xlogo64_width
104 # define logo_height xlogo64_height
105 # define logo_bits xlogo64_bits
108 static unsigned short maze[MAX_MAZE_SIZE_X][MAX_MAZE_SIZE_Y];
114 } move_list[MOVE_LIST_SIZE], save_path[MOVE_LIST_SIZE], path[MOVE_LIST_SIZE];
116 static int maze_size_x, maze_size_y;
117 static int sqnum, cur_sq_x, cur_sq_y, path_length;
118 static int start_x, start_y, start_dir, end_x, end_y, end_dir;
119 static int grid_width, grid_height;
124 static GC gc, cgc, tgc, logo_gc, erase_gc;
125 static Pixmap logo_map;
127 static int x = 0, y = 0, restart = 0, stop = 1, state = 1, max_length;
128 static int sync_p, bridge_p;
131 check_events (void) /* X event handler [ rhess ] */
140 switch (e.xbutton.button) {
146 if (state == 5) state = 4 ;
159 case ConfigureNotify:
164 XClearWindow (dpy, win);
178 set_maze_sizes (int width, int height)
180 maze_size_x = width / grid_width;
181 maze_size_y = height / grid_height;
186 initialize_maze (void) /* draw the surrounding wall and start/end squares */
188 register int i, j, wall;
189 int logow = 1 + logo_width / grid_width;
190 int logoh = 1 + logo_height / grid_height;
192 /* initialize all squares */
193 for ( i=0; i<maze_size_x; i++) {
194 for ( j=0; j<maze_size_y; j++) {
200 for ( i=0; i<maze_size_x; i++ ) {
201 maze[i][0] |= WALL_TOP;
205 for ( j=0; j<maze_size_y; j++ ) {
206 maze[maze_size_x-1][j] |= WALL_RIGHT;
210 for ( i=0; i<maze_size_x; i++ ) {
211 maze[i][maze_size_y-1] |= WALL_BOTTOM;
215 for ( j=0; j<maze_size_y; j++ ) {
216 maze[0][j] |= WALL_LEFT;
219 /* set start square */
220 wall = get_random(4);
223 i = get_random(maze_size_x);
228 j = get_random(maze_size_y);
231 i = get_random(maze_size_x);
236 j = get_random(maze_size_y);
239 maze[i][j] |= START_SQUARE;
240 maze[i][j] |= ( DOOR_IN_TOP >> wall );
241 maze[i][j] &= ~( WALL_TOP >> wall );
253 i = get_random(maze_size_x);
258 j = get_random(maze_size_y);
261 i = get_random(maze_size_x);
266 j = get_random(maze_size_y);
269 maze[i][j] |= END_SQUARE;
270 maze[i][j] |= ( DOOR_OUT_TOP >> wall );
271 maze[i][j] &= ~( WALL_TOP >> wall );
277 if ((maze_size_x-logow >= 6) && (maze_size_y-logoh >= 6))
279 /* not closer than 3 grid units from a wall */
280 logo_x = get_random (maze_size_x - logow - 5) + 3;
281 logo_y = get_random (maze_size_y - logoh - 5) + 3;
282 for (i=0; i<logow; i++)
283 for (j=0; j<logoh; j++)
284 maze[logo_x + i][logo_y + j] |= DOOR_IN_TOP;
287 logo_y = logo_x = -1;
290 static int choose_door (void);
291 static int backup (void);
292 static void draw_wall (int, int, int, GC);
293 static void draw_solid_square (int, int, int, GC);
294 /*static void enter_square (int);*/
295 static void build_wall (int, int, int);
296 /*static void break_wall (int, int, int);*/
298 static void join_sets(int, int);
300 /* For set_create_maze. */
301 /* The sets that our squares are in. */
302 static int *sets = 0;
303 /* The `list' of hedges. */
304 static int *hedges = 0;
308 /* Initialise the sets. */
316 sets = (int *)malloc(maze_size_x*maze_size_y*sizeof(int));
319 for(i = 0; i < maze_size_x*maze_size_y; i++)
326 hedges = (int *)malloc(maze_size_x*maze_size_y*2*sizeof(int));
329 for(i = 0; i < maze_size_x*maze_size_y*2; i++)
333 /* Mask out outside walls. */
334 for(i = 0; i < maze_size_y; i++)
336 hedges[2*((maze_size_x)*i+maze_size_x-1)+1] = -1;
338 for(i = 0; i < maze_size_x; i++)
340 hedges[2*((maze_size_y-1)*maze_size_x+i)] = -1;
342 /* Mask out a possible logo. */
345 int logow = 1 + logo_width / grid_width;
346 int logoh = 1 + logo_height / grid_height;
347 int bridge_dir, bridge_c;
349 if(bridge_p && logoh>=3 && logow>=3)
351 bridge_dir = 1+random()%2;
354 bridge_c = logo_y+random()%(logoh-2)+1;
358 bridge_c = logo_x+random()%(logow-2)+1;
367 for(x = logo_x; x < logo_x+logow; x++)
368 for(y = logo_y; y < logo_y+logoh; y++)
370 /* I should check for the bridge here, except that I join the
371 * bridge together below.
373 hedges[2*(x+maze_size_x*y)+1] = -1;
374 hedges[2*(x+maze_size_x*y)] = -1;
376 for(x = logo_x; x < logo_x+logow; x++)
378 if(!(bridge_dir==2 && x==bridge_c))
380 build_wall(x, logo_y, 0);
381 build_wall(x, logo_y+logoh, 0);
383 hedges[2*(x+maze_size_x*(logo_y-1))] = -1;
386 build_wall(x, bridge_c, 0);
387 build_wall(x, bridge_c, 2);
390 for(y = logo_y; y < logo_y+logoh; y++)
392 if(!(bridge_dir==1 && y==bridge_c))
394 build_wall(logo_x, y, 3);
395 build_wall(logo_x+logow, y, 3);
397 hedges[2*(logo_x-1+maze_size_x*y)+1] = -1;
400 build_wall(bridge_c, y, 1);
401 build_wall(bridge_c, y, 3);
404 /* Join the whole bridge together. */
411 for(i = logo_x; i < logo_x+logow+1; i++)
412 join_sets(x+y*maze_size_x, i+y*maze_size_x);
418 for(i = logo_y; i < logo_y+logoh+1; i++)
419 join_sets(x+y*maze_size_x, x+i*maze_size_x);
424 for(i = 0; i < maze_size_x*maze_size_y*2; i++)
427 r = random()%(maze_size_x*maze_size_y*2);
428 hedges[i] = hedges[r];
433 /* Get the representative of a set. */
443 s = get_set(sets[num]);
449 /* Join two sets together. */
451 join_sets(num1, num2)
465 /* Exitialise the sets. */
478 /* Temporary hack. */
480 show_set(int num, GC gc)
486 for(x = 0; x < maze_size_x; x++)
487 for(y = 0; y < maze_size_y; y++)
489 if(get_set(x+y*maze_size_x)==set)
491 XFillRectangle(dpy, win, gc, border_x + bw + grid_width * x,
492 border_y + bw + grid_height * y,
493 grid_width-2*bw , grid_height-2*bw);
499 /* Second alternative maze creator: Put each square in the maze in a
500 * separate set. Also, make a list of all the hedges. Randomize that list.
501 * Walk through the list. If, for a certain hedge, the two squares on both
502 * sides of it are in different sets, union the sets and remove the hedge.
503 * Continue until all hedges have been processed or only one set remains.
506 set_create_maze(void)
508 int i, h, x, y, dir, v, w;
514 /* Do almost all the setup. */
517 /* Start running through the hedges. */
518 for(i = 0; i < 2*maze_size_x*maze_size_y; i++)
522 /* This one is in the logo or outside border. */
527 x = (h>>1)%maze_size_x;
528 y = (h>>1)/maze_size_x;
543 show_set(x+y*maze_size_x, logo_gc);
544 show_set(v+w*maze_size_x, tgc);
546 if(get_set(x+y*maze_size_x)!=get_set(v+w*maze_size_x))
551 join_sets(x+y*maze_size_x, v+w*maze_size_x);
552 /* Don't draw the wall. */
559 /* Don't join the sets. */
560 build_wall(x, y, dir);
570 show_set(x+y*maze_size_x, erase_gc);
571 show_set(v+w*maze_size_x, erase_gc);
575 /* Free some memory. */
579 /* First alternative maze creator: Pick a random, empty corner in the maze.
580 * Pick a random direction. Draw a wall in that direction, from that corner
581 * until we hit a wall. Option: Only draw the wall if it's going to be
582 * shorter than a certain length. Otherwise we get lots of long walls.
585 alt_create_maze(void)
589 int i, j, height, width, open_corners, k, dir, x, y;
591 height = maze_size_y+1;
592 width = maze_size_x+1;
594 /* Allocate and clear some mem. */
595 corners = (char *)calloc(height*width, 1);
599 /* Set up the indexing array. */
600 c_idx = (int *)malloc(sizeof(int)*height*width);
606 for(i = 0; i < height*width; i++)
608 for(i = 0; i < height*width; i++)
611 k = random()%(height*width);
616 /* Set up some initial walls. */
618 for(i = 0; i < width; i++)
621 corners[i+width*(height-1)] = 1;
623 for(i = 0; i < height; i++)
625 corners[i*width] = 1;
626 corners[i*width+width-1] = 1;
628 /* Walls around logo. In fact, inside the logo, too. */
629 /* Also draw the walls. */
632 int logow = 1 + logo_width / grid_width;
633 int logoh = 1 + logo_height / grid_height;
634 int bridge_dir, bridge_c;
636 if(bridge_p && logoh>=3 && logow>=3)
638 bridge_dir = 1+random()%2;
641 bridge_c = logo_y+random()%(logoh-2)+1;
645 bridge_c = logo_x+random()%(logow-2)+1;
653 for(i = logo_x; i <= logo_x + logow; i++)
655 for(j = logo_y; j <= logo_y + logoh; j++)
657 corners[i+width*j] = 1;
660 for(x = logo_x; x < logo_x+logow; x++)
662 if(!(bridge_dir==2 && x==bridge_c))
664 build_wall(x, logo_y, 0);
665 build_wall(x, logo_y+logoh, 0);
669 build_wall(x, bridge_c, 0);
670 build_wall(x, bridge_c, 2);
673 for(y = logo_y; y < logo_y+logoh; y++)
675 if(!(bridge_dir==1 && y==bridge_c))
677 build_wall(logo_x, y, 3);
678 build_wall(logo_x+logow, y, 3);
682 build_wall(bridge_c, y, 1);
683 build_wall(bridge_c, y, 3);
686 /* Connect one wall of the logo with an outside wall. */
688 dir = (bridge_dir+1)%4;
694 x = logo_x+(random()%(logow+1));
699 y = logo_y+(random()%(logoh+1));
702 x = logo_x+(random()%(logow+1));
707 y = logo_y+(random()%(logoh+1));
712 corners[x+width*y] = 1;
716 build_wall(x-1, y-1, 1);
728 build_wall(x-1, y-1, 2);
733 while(!corners[x+width*y]);
740 x = logo_x+(random()%(logow+1));
745 y = logo_y+(random()%(logoh+1));
748 x = logo_x+(random()%(logow+1));
753 y = logo_y+(random()%(logoh+1));
758 corners[x+width*y] = 1;
762 build_wall(x-1, y-1, 1);
774 build_wall(x-1, y-1, 2);
779 while(!corners[x+width*y]);
783 /* Count open gridpoints. */
785 for(i = 0; i < width; i++)
786 for(j = 0; j < height; j++)
787 if(!corners[i+width*j])
790 /* Now do actual maze generation. */
791 while(open_corners>0)
793 for(i = 0; i < width*height; i++)
795 if(!corners[c_idx[i]])
799 /* Choose a random direction. */
803 /* Measure the length of the wall we'd draw. */
804 while(!corners[x+width*y])
829 /* Draw a wall until we hit something. */
830 while(!corners[x+width*y])
833 corners[x+width*y] = 1;
837 build_wall(x-1, y-1, 1);
849 build_wall(x-1, y-1, 2);
859 /* Free some memory we used. */
864 /* The original maze creator. Start somewhere. Take a step in a random
865 * direction. Keep doing this until we hit a wall. Then, backtrack until
866 * we find a point where we can go in another direction.
869 create_maze (void) /* create a maze layout given the initialized maze */
871 register int i, newdoor = 0;
872 int logow = 1 + logo_width / grid_width;
873 int logoh = 1 + logo_height / grid_height;
875 /* Maybe we should make a bridge? */
876 if(bridge_p && logo_x>=0 && logow>=3 && logoh>=3)
878 int bridge_dir, bridge_c;
880 bridge_dir = 1+random()%2;
884 bridge_c = logo_y+random()%(logoh-2)+1;
886 bridge_c = logo_y+random()%logoh;
891 bridge_c = logo_x+random()%(logow-2)+1;
893 bridge_c = logo_x+random()%logow;
898 for(i = logo_x; i < logo_x+logow; i++)
900 maze[i][bridge_c] &= ~DOOR_IN_TOP;
905 for(i = logo_y; i < logo_y+logoh; i++)
907 maze[bridge_c][i] &= ~DOOR_IN_TOP;
913 move_list[sqnum].x = cur_sq_x;
914 move_list[sqnum].y = cur_sq_y;
915 move_list[sqnum].dir = newdoor;
916 while ( ( newdoor = choose_door() ) == -1 ) { /* pick a door */
917 if ( backup() == -1 ) { /* no more doors ... backup */
918 return; /* done ... return */
922 /* mark the out door */
923 maze[cur_sq_x][cur_sq_y] |= ( DOOR_OUT_TOP >> newdoor );
937 /* mark the in door */
938 maze[cur_sq_x][cur_sq_y] |= ( DOOR_IN_TOP >> ((newdoor+2)%4) );
940 /* if end square set path length and save path */
941 if ( maze[cur_sq_x][cur_sq_y] & END_SQUARE ) {
943 for ( i=0; i<path_length; i++) {
944 save_path[i].x = move_list[i].x;
945 save_path[i].y = move_list[i].y;
946 save_path[i].dir = move_list[i].dir;
956 choose_door (void) /* pick a new path */
959 register int num_candidates;
964 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_TOP )
966 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_TOP )
968 if ( maze[cur_sq_x][cur_sq_y] & WALL_TOP )
970 if ( maze[cur_sq_x][cur_sq_y - 1] & DOOR_IN_ANY ) {
971 maze[cur_sq_x][cur_sq_y] |= WALL_TOP;
972 maze[cur_sq_x][cur_sq_y - 1] |= WALL_BOTTOM;
973 draw_wall(cur_sq_x, cur_sq_y, 0, gc);
976 candidates[num_candidates++] = 0;
980 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_RIGHT )
982 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_RIGHT )
984 if ( maze[cur_sq_x][cur_sq_y] & WALL_RIGHT )
986 if ( maze[cur_sq_x + 1][cur_sq_y] & DOOR_IN_ANY ) {
987 maze[cur_sq_x][cur_sq_y] |= WALL_RIGHT;
988 maze[cur_sq_x + 1][cur_sq_y] |= WALL_LEFT;
989 draw_wall(cur_sq_x, cur_sq_y, 1, gc);
992 candidates[num_candidates++] = 1;
996 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_BOTTOM )
998 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_BOTTOM )
1000 if ( maze[cur_sq_x][cur_sq_y] & WALL_BOTTOM )
1002 if ( maze[cur_sq_x][cur_sq_y + 1] & DOOR_IN_ANY ) {
1003 maze[cur_sq_x][cur_sq_y] |= WALL_BOTTOM;
1004 maze[cur_sq_x][cur_sq_y + 1] |= WALL_TOP;
1005 draw_wall(cur_sq_x, cur_sq_y, 2, gc);
1008 candidates[num_candidates++] = 2;
1012 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_LEFT )
1014 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_LEFT )
1016 if ( maze[cur_sq_x][cur_sq_y] & WALL_LEFT )
1018 if ( maze[cur_sq_x - 1][cur_sq_y] & DOOR_IN_ANY ) {
1019 maze[cur_sq_x][cur_sq_y] |= WALL_LEFT;
1020 maze[cur_sq_x - 1][cur_sq_y] |= WALL_RIGHT;
1021 draw_wall(cur_sq_x, cur_sq_y, 3, gc);
1024 candidates[num_candidates++] = 3;
1027 if (num_candidates == 0)
1029 if (num_candidates == 1)
1030 return ( candidates[0] );
1031 return ( candidates[ get_random(num_candidates) ] );
1037 backup (void) /* back up a move */
1040 cur_sq_x = move_list[sqnum].x;
1041 cur_sq_y = move_list[sqnum].y;
1047 draw_maze_border (void) /* draw the maze outline */
1052 for ( i=0; i<maze_size_x; i++) {
1053 if ( maze[i][0] & WALL_TOP ) {
1054 XDrawLine(dpy, win, gc,
1055 border_x + grid_width * i,
1057 border_x + grid_width * (i+1) - 1,
1060 if ((maze[i][maze_size_y - 1] & WALL_BOTTOM)) {
1061 XDrawLine(dpy, win, gc,
1062 border_x + grid_width * i,
1063 border_y + grid_height * (maze_size_y) - 1,
1064 border_x + grid_width * (i+1) - 1,
1065 border_y + grid_height * (maze_size_y) - 1);
1068 for ( j=0; j<maze_size_y; j++) {
1069 if ( maze[maze_size_x - 1][j] & WALL_RIGHT ) {
1070 XDrawLine(dpy, win, gc,
1071 border_x + grid_width * maze_size_x - 1,
1072 border_y + grid_height * j,
1073 border_x + grid_width * maze_size_x - 1,
1074 border_y + grid_height * (j+1) - 1);
1076 if ( maze[0][j] & WALL_LEFT ) {
1077 XDrawLine(dpy, win, gc,
1079 border_y + grid_height * j,
1081 border_y + grid_height * (j+1) - 1);
1089 unsigned int w, h, bw, d;
1090 XGetGeometry (dpy, logo_map, &r, &x, &y, &w, &h, &bw, &d);
1091 XCopyPlane (dpy, logo_map, win, logo_gc,
1093 border_x + 3 + grid_width * logo_x,
1094 border_y + 3 + grid_height * logo_y, 1);
1096 draw_solid_square (start_x, start_y, start_dir, tgc);
1097 draw_solid_square (end_x, end_y, end_dir, tgc);
1102 draw_wall(int i, int j, int dir, GC gc) /* draw a single wall */
1106 XDrawLine(dpy, win, gc,
1107 border_x + grid_width * i,
1108 border_y + grid_height * j,
1109 border_x + grid_width * (i+1),
1110 border_y + grid_height * j);
1113 XDrawLine(dpy, win, gc,
1114 border_x + grid_width * (i+1),
1115 border_y + grid_height * j,
1116 border_x + grid_width * (i+1),
1117 border_y + grid_height * (j+1));
1120 XDrawLine(dpy, win, gc,
1121 border_x + grid_width * i,
1122 border_y + grid_height * (j+1),
1123 border_x + grid_width * (i+1),
1124 border_y + grid_height * (j+1));
1127 XDrawLine(dpy, win, gc,
1128 border_x + grid_width * i,
1129 border_y + grid_height * j,
1130 border_x + grid_width * i,
1131 border_y + grid_height * (j+1));
1138 /* Actually build a wall. */
1140 build_wall(i, j, dir)
1143 /* Draw it on the screen. */
1144 draw_wall(i, j, dir, gc);
1145 /* Put it in the maze. */
1149 maze[i][j] |= WALL_TOP;
1151 maze[i][j-1] |= WALL_BOTTOM;
1154 maze[i][j] |= WALL_RIGHT;
1156 maze[i+1][j] |= WALL_LEFT;
1159 maze[i][j] |= WALL_BOTTOM;
1161 maze[i][j+1] |= WALL_TOP;
1164 maze[i][j] |= WALL_LEFT;
1166 maze[i-1][j] |= WALL_RIGHT;
1171 /* Break out a wall. */
1174 break_wall(i, j, dir)
1177 /* Draw it on the screen. */
1178 draw_wall(i, j, dir, erase_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_BOTTOM;
1198 maze[i][j] &= ~WALL_LEFT;
1200 maze[i-1][j] &= ~WALL_RIGHT;
1208 draw_solid_square(int i, int j, /* draw a solid square in a square */
1212 case 0: XFillRectangle(dpy, win, gc,
1213 border_x + bw + grid_width * i,
1214 border_y - bw + grid_height * j,
1215 grid_width - (bw+bw), grid_height);
1217 case 1: XFillRectangle(dpy, win, gc,
1218 border_x + bw + grid_width * i,
1219 border_y + bw + grid_height * j,
1220 grid_width, grid_height - (bw+bw));
1222 case 2: XFillRectangle(dpy, win, gc,
1223 border_x + bw + grid_width * i,
1224 border_y + bw + grid_height * j,
1225 grid_width - (bw+bw), grid_height);
1227 case 3: XFillRectangle(dpy, win, gc,
1228 border_x - bw + grid_width * i,
1229 border_y + bw + grid_height * j,
1230 grid_width, grid_height - (bw+bw));
1238 solve_maze (void) /* solve it with graphical feedback */
1241 int step_x[4] = { 0, 1, 0, -1 };
1242 int step_y[4] = { -1, 0, 1, 0 };
1244 /* plug up the surrounding wall */
1245 maze[start_x][start_y] |= (WALL_TOP >> start_dir);
1246 maze[end_x][end_y] |= (WALL_TOP >> end_dir);
1248 /* initialize search path */
1253 maze[end_x][end_y] |= SOLVER_VISIT;
1257 if ( ++path[i].dir >= 4 ) {
1258 XFillRectangle(dpy, win, cgc,
1259 border_x + bw + grid_width * (int)(path[i].x),
1260 border_y + bw + grid_height * (int)(path[i].y),
1261 grid_width - (bw+bw), grid_height - (bw+bw));
1263 if(i<0) /* Can't solve this maze. */
1265 printf("Unsolvable maze.\n");
1268 draw_solid_square( (int)(path[i].x), (int)(path[i].y),
1269 (int)(path[i].dir), cgc);
1271 else if ( (! (maze[path[i].x][path[i].y] & (WALL_TOP >> path[i].dir))) &&
1272 (!( maze[path[i].x+step_x[path[i].dir]]
1273 [path[i].y+step_y[path[i].dir]]&SOLVER_VISIT)) ) {
1274 path[i+1].x = path[i].x+step_x[path[i].dir];
1275 path[i+1].y = path[i].y+step_y[path[i].dir];
1277 draw_solid_square(path[i].x, path[i].y, path[i].dir, tgc);
1279 maze[path[i].x][path[i].y] |= SOLVER_VISIT;
1280 if ( maze[path[i].x][path[i].y] & START_SQUARE ) {
1284 if (check_events()) return;
1285 /* Abort solve on expose - cheapo repaint strategy */
1286 if (solve_delay) usleep (solve_delay);
1293 enter_square (int n) /* move into a neighboring square */
1295 draw_solid_square( (int)path[n].x, (int)path[n].y,
1296 (int)path[n].dir, tgc);
1299 switch (path[n].dir) {
1300 case 0: path[n+1].x = path[n].x;
1301 path[n+1].y = path[n].y - 1;
1303 case 1: path[n+1].x = path[n].x + 1;
1304 path[n+1].y = path[n].y;
1306 case 2: path[n+1].x = path[n].x;
1307 path[n+1].y = path[n].y + 1;
1309 case 3: path[n+1].x = path[n].x - 1;
1310 path[n+1].y = path[n].y;
1318 * jmr additions for Jamie Zawinski's <jwz@netscape.com> screensaver stuff,
1319 * note that the code above this has probably been hacked about in some
1323 char *progclass = "Maze";
1325 char *defaults[] = {
1326 "Maze.background: black", /* to placate SGI */
1327 "Maze.foreground: white", /* to placate SGI */
1329 "*solveDelay: 5000",
1330 "*preDelay: 2000000",
1331 "*postDelay: 4000000",
1332 "*liveColor: green",
1344 XrmOptionDescRec options[] = {
1345 { "-grid-size", ".gridSize", XrmoptionSepArg, 0 },
1346 { "-solve-delay", ".solveDelay", XrmoptionSepArg, 0 },
1347 { "-pre-delay", ".preDelay", XrmoptionSepArg, 0 },
1348 { "-post-delay", ".postDelay", XrmoptionSepArg, 0 },
1349 { "-live-color", ".liveColor", XrmoptionSepArg, 0 },
1350 { "-dead-color", ".deadColor", XrmoptionSepArg, 0 },
1351 { "-generator", ".generator", XrmoptionSepArg, 0 },
1352 { "-max-length", ".maxLength", XrmoptionSepArg, 0 },
1353 { "-bridge", ".bridge", XrmoptionNoArg, "True" },
1354 { "-no-bridge", ".bridge", XrmoptionNoArg, "False" },
1359 extern void skull (Display *, Window, GC, GC, int, int, int, int);
1363 screenhack(Display *display, Window window)
1366 int size, root, generator, this_gen;
1367 XWindowAttributes xgwa;
1368 unsigned long bg, fg, pfg, pbg, lfg;
1370 size = get_integer_resource ("gridSize", "Dimension");
1371 root = get_boolean_resource("root", "Boolean");
1372 solve_delay = get_integer_resource ("solveDelay", "Integer");
1373 pre_solve_delay = get_integer_resource ("preDelay", "Integer");
1374 post_solve_delay = get_integer_resource ("postDelay", "Integer");
1375 generator = get_integer_resource("generator", "Integer");
1376 max_length = get_integer_resource("maxLength", "Integer");
1377 bridge_p = get_boolean_resource("bridge", "Boolean");
1379 if (size < 2) size = 7 + (random () % 30);
1380 grid_width = grid_height = size;
1381 bw = (size > 6 ? 3 : (size-1)/2);
1383 dpy = display; win = window; /* the maze stuff uses global variables */
1385 XGetWindowAttributes (dpy, win, &xgwa);
1390 set_maze_sizes (xgwa.width, xgwa.height);
1393 XSelectInput (dpy, win, ExposureMask|ButtonPressMask|StructureNotifyMask);
1395 gc = XCreateGC(dpy, win, 0, 0);
1396 cgc = XCreateGC(dpy, win, 0, 0);
1397 tgc = XCreateGC(dpy,win,0,0);
1398 logo_gc = XCreateGC(dpy, win, 0, 0);
1399 erase_gc = XCreateGC(dpy, win, 0, 0);
1401 gray = XCreateBitmapFromData (dpy,win,gray1_bits,gray1_width,gray1_height);
1403 bg = get_pixel_resource ("background","Background", dpy, xgwa.colormap);
1404 fg = get_pixel_resource ("foreground","Foreground", dpy, xgwa.colormap);
1405 lfg = get_pixel_resource ("logoColor", "Foreground", dpy, xgwa.colormap);
1406 pfg = get_pixel_resource ("liveColor", "Foreground", dpy, xgwa.colormap);
1407 pbg = get_pixel_resource ("deadColor", "Foreground", dpy, xgwa.colormap);
1408 if (mono_p) lfg = pfg = fg;
1411 lfg = ((bg == WhitePixel (dpy, DefaultScreen (dpy)))
1412 ? BlackPixel (dpy, DefaultScreen (dpy))
1413 : WhitePixel (dpy, DefaultScreen (dpy)));
1415 XSetForeground (dpy, gc, fg);
1416 XSetBackground (dpy, gc, bg);
1417 XSetForeground (dpy, cgc, pbg);
1418 XSetBackground (dpy, cgc, bg);
1419 XSetForeground (dpy, tgc, pfg);
1420 XSetBackground (dpy, tgc, bg);
1421 XSetForeground (dpy, logo_gc, lfg);
1422 XSetBackground (dpy, logo_gc, bg);
1423 XSetForeground (dpy, erase_gc, bg);
1424 XSetBackground (dpy, erase_gc, bg);
1426 XSetStipple (dpy, cgc, gray);
1427 XSetFillStyle (dpy, cgc, FillOpaqueStippled);
1433 GC draw_gc, erase_gc;
1434 /* round up to grid size */
1435 w = ((logo_width / grid_width) + 1) * grid_width;
1436 h = ((logo_height / grid_height) + 1) * grid_height;
1437 logo_map = XCreatePixmap (dpy, win, w, h, 1);
1438 gcv.foreground = 1L;
1439 draw_gc = XCreateGC (dpy, logo_map, GCForeground, &gcv);
1440 gcv.foreground = 0L;
1441 erase_gc= XCreateGC (dpy, logo_map, GCForeground, &gcv);
1442 XFillRectangle (dpy, logo_map, erase_gc, 0, 0, w, h);
1443 skull (dpy, logo_map, draw_gc, erase_gc, 5, 0, w-10, h-10);
1444 XFreeGC (dpy, draw_gc);
1445 XFreeGC (dpy, erase_gc);
1448 if (!(logo_map = XCreateBitmapFromData (dpy, win, logo_bits,
1449 logo_width, logo_height)))
1451 fprintf (stderr, "Can't create logo pixmap\n");
1455 XMapRaised(dpy, win);
1459 sync_p = !(random() % 10);
1461 while (1) { /* primary execution loop [ rhess ] */
1462 if (check_events()) continue ;
1463 if (restart || stop) goto pop;
1469 XClearWindow(dpy, win);
1473 this_gen = generator;
1474 if(this_gen<0 || this_gen>2)
1475 this_gen = random()%3;
1492 usleep (pre_solve_delay);
1499 usleep (post_solve_delay);
1509 static XWindowAttributes wattr;
1513 XGetWindowAttributes (dpy, win, &wattr);
1514 set_maze_sizes (wattr.width, wattr.height);
1515 XClearWindow (dpy, win);
1517 sync_p = !(random() % 10);