1 /******************************************************************************
4 * modified: [ 1-04-00 ] Johannes Keukelaar <johannes@nada.kth.se>
5 * Added -ignorant option (not the default) to remove knowlege
6 * of the direction in which the exit lies.
8 * modified: [ 6-28-98 ] Zack Weinberg <zack@rabi.phys.columbia.edu>
10 * Made the maze-solver somewhat more intelligent. There are
11 * three optimizations:
13 * - Straight-line lookahead: the solver does not enter dead-end
14 * corridors. This is a win with all maze generators.
16 * - First order direction choice: the solver knows where the
17 * exit is in relation to itself, and will try paths leading in
18 * that direction first. This is a major win on maze generator 1
19 * which tends to offer direct routes to the exit.
21 * - Dead region elimination: the solver already has a map of
22 * all squares visited. Whenever it starts to backtrack, it
23 * consults this map and marks off all squares that cannot be
24 * reached from the exit without crossing a square already
25 * visited. Those squares can never contribute to the path to
26 * the exit, so it doesn't bother checking them. This helps a
27 * lot with maze generator 2 and somewhat less with generator 1.
29 * Further improvements would require knowledge of the wall map
30 * as well as the position of the exit and the squares visited.
31 * I would consider that to be cheating. Generator 0 makes
32 * mazes which are remarkably difficult to solve mechanically --
33 * even with these optimizations the solver generally must visit
34 * at least two-thirds of the squares. This is partially
35 * because generator 0's mazes have longer paths to the exit.
37 * modified: [ 4-10-97 ] Johannes Keukelaar <johannes@nada.kth.se>
38 * Added multiple maze creators. Robustified solver.
39 * Added bridge option.
40 * modified: [ 8-11-95 ] Ed James <james@mml.mmc.com>
41 * added fill of dead-end box to solve_maze while loop.
42 * modified: [ 3-7-93 ] Jamie Zawinski <jwz@jwz.org>
43 * added the XRoger logo, cleaned up resources, made
44 * grid size a parameter.
45 * modified: [ 3-3-93 ] Jim Randell <jmr@mddjmr.fc.hp.com>
46 * Added the colour stuff and integrated it with jwz's
47 * screenhack stuff. There's still some work that could
48 * be done on this, particularly allowing a resource to
49 * specify how big the squares are.
50 * modified: [ 10-4-88 ] Richard Hess ...!uunet!cimshop!rhess
51 * [ Revised primary execution loop within main()...
52 * [ Extended X event handler, check_events()...
53 * modified: [ 1-29-88 ] Dave Lemke lemke@sun.com
55 * [ Note the word "hacked" -- this is extremely ugly, but at
56 * [ least it does the job. NOT a good programming example
58 * original: [ 6/21/85 ] Martin Weiss Sun Microsystems [ SunView ]
60 ******************************************************************************
61 Copyright 1988 by Sun Microsystems, Inc. Mountain View, CA.
65 Permission to use, copy, modify, and distribute this software and its
66 documentation for any purpose and without fee is hereby granted,
67 provided that the above copyright notice appear in all copies and that
68 both that copyright notice and this permission notice appear in
69 supporting documentation, and that the names of Sun or MIT not be
70 used in advertising or publicity pertaining to distribution of the
71 software without specific prior written permission. Sun and M.I.T.
72 make no representations about the suitability of this software for
73 any purpose. It is provided "as is" without any express or implied warranty.
75 SUN DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
76 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
77 PURPOSE. IN NO EVENT SHALL SUN BE LIABLE FOR ANY SPECIAL, INDIRECT
78 OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
79 OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
80 OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE
81 OR PERFORMANCE OF THIS SOFTWARE.
82 *****************************************************************************/
84 #include "screenhack.h"
89 static int solve_delay, pre_solve_delay, post_solve_delay;
93 #include <X11/Xutil.h>
95 # include <X11/bitmaps/gray1>
97 # include "sys$common:[decw$include.bitmaps]gray1.xbm"
100 #define MAX_MAZE_SIZE_X 500
101 #define MAX_MAZE_SIZE_Y 500
103 #define MOVE_LIST_SIZE (MAX_MAZE_SIZE_X * MAX_MAZE_SIZE_Y)
105 #define NOT_DEAD 0x8000
106 #define SOLVER_VISIT 0x4000
107 #define START_SQUARE 0x2000
108 #define END_SQUARE 0x1000
111 #define WALL_RIGHT 0x4
112 #define WALL_BOTTOM 0x2
113 #define WALL_LEFT 0x1
116 #define DOOR_IN_TOP 0x800
117 #define DOOR_IN_RIGHT 0x400
118 #define DOOR_IN_BOTTOM 0x200
119 #define DOOR_IN_LEFT 0x100
120 #define DOOR_IN_ANY 0xF00
122 #define DOOR_OUT_TOP 0x80
123 #define DOOR_OUT_RIGHT 0x40
124 #define DOOR_OUT_BOTTOM 0x20
125 #define DOOR_OUT_LEFT 0x10
131 #define get_random(x) (random() % (x))
134 static int logo_x, logo_y;
137 # define logo_width 128
138 # define logo_height 128
140 # include <X11/bitmaps/xlogo64>
141 # define logo_width xlogo64_width
142 # define logo_height xlogo64_height
143 # define logo_bits xlogo64_bits
146 static unsigned short maze[MAX_MAZE_SIZE_X][MAX_MAZE_SIZE_Y];
151 unsigned char dir, ways;
152 } move_list[MOVE_LIST_SIZE], save_path[MOVE_LIST_SIZE], path[MOVE_LIST_SIZE];
154 static int maze_size_x, maze_size_y;
155 static int sqnum, cur_sq_x, cur_sq_y, path_length;
156 static int start_x, start_y, start_dir, end_x, end_y, end_dir;
157 static int grid_width, grid_height;
162 static GC gc, cgc, tgc, sgc, ugc, logo_gc, erase_gc;
163 static Pixmap logo_map;
165 static int x = 0, y = 0, restart = 0, stop = 1, state = 1, max_length;
166 static int sync_p, bridge_p, ignorant_p;
169 check_events (void) /* X event handler [ rhess ] */
178 switch (e.xbutton.button) {
184 if (state == 5) state = 4 ;
197 case ConfigureNotify:
202 XClearWindow (dpy, win);
209 screenhack_handle_event(dpy, &e);
219 set_maze_sizes (int width, int height)
221 maze_size_x = width / grid_width;
222 maze_size_y = height / grid_height;
227 initialize_maze (void) /* draw the surrounding wall and start/end squares */
229 register int i, j, wall;
230 int logow = 1 + logo_width / grid_width;
231 int logoh = 1 + logo_height / grid_height;
233 /* initialize all squares */
234 for ( i=0; i<maze_size_x; i++) {
235 for ( j=0; j<maze_size_y; j++) {
241 for ( i=0; i<maze_size_x; i++ ) {
242 maze[i][0] |= WALL_TOP;
246 for ( j=0; j<maze_size_y; j++ ) {
247 maze[maze_size_x-1][j] |= WALL_RIGHT;
251 for ( i=0; i<maze_size_x; i++ ) {
252 maze[i][maze_size_y-1] |= WALL_BOTTOM;
256 for ( j=0; j<maze_size_y; j++ ) {
257 maze[0][j] |= WALL_LEFT;
260 /* set start square */
261 wall = get_random(4);
264 i = get_random(maze_size_x);
269 j = get_random(maze_size_y);
272 i = get_random(maze_size_x);
277 j = get_random(maze_size_y);
280 maze[i][j] |= START_SQUARE;
281 maze[i][j] |= ( DOOR_IN_TOP >> wall );
282 maze[i][j] &= ~( WALL_TOP >> wall );
294 i = get_random(maze_size_x);
299 j = get_random(maze_size_y);
302 i = get_random(maze_size_x);
307 j = get_random(maze_size_y);
310 maze[i][j] |= END_SQUARE;
311 maze[i][j] |= ( DOOR_OUT_TOP >> wall );
312 maze[i][j] &= ~( WALL_TOP >> wall );
318 if ((maze_size_x-logow >= 6) && (maze_size_y-logoh >= 6))
320 /* not closer than 3 grid units from a wall */
321 logo_x = get_random (maze_size_x - logow - 5) + 3;
322 logo_y = get_random (maze_size_y - logoh - 5) + 3;
323 for (i=0; i<logow; i++)
324 for (j=0; j<logoh; j++)
325 maze[logo_x + i][logo_y + j] |= DOOR_IN_TOP;
328 logo_y = logo_x = -1;
331 static int choose_door (void);
332 static int backup (void);
333 static void draw_wall (int, int, int, GC);
334 static void draw_solid_square (int, int, int, GC);
335 /*static void enter_square (int);*/
336 static void build_wall (int, int, int);
337 /*static void break_wall (int, int, int);*/
339 static void join_sets(int, int);
341 /* For set_create_maze. */
342 /* The sets that our squares are in. */
343 static int *sets = 0;
344 /* The `list' of hedges. */
345 static int *hedges = 0;
349 /* Initialise the sets. */
357 sets = (int *)malloc(maze_size_x*maze_size_y*sizeof(int));
360 for(i = 0; i < maze_size_x*maze_size_y; i++)
367 hedges = (int *)malloc(maze_size_x*maze_size_y*2*sizeof(int));
370 for(i = 0; i < maze_size_x*maze_size_y*2; i++)
374 /* Mask out outside walls. */
375 for(i = 0; i < maze_size_y; i++)
377 hedges[2*((maze_size_x)*i+maze_size_x-1)+1] = -1;
379 for(i = 0; i < maze_size_x; i++)
381 hedges[2*((maze_size_y-1)*maze_size_x+i)] = -1;
383 /* Mask out a possible logo. */
386 int logow = 1 + logo_width / grid_width;
387 int logoh = 1 + logo_height / grid_height;
388 int bridge_dir, bridge_c;
390 if(bridge_p && logoh>=3 && logow>=3)
392 bridge_dir = 1+random()%2;
395 bridge_c = logo_y+random()%(logoh-2)+1;
399 bridge_c = logo_x+random()%(logow-2)+1;
408 for(x = logo_x; x < logo_x+logow; x++)
409 for(y = logo_y; y < logo_y+logoh; y++)
411 /* I should check for the bridge here, except that I join the
412 * bridge together below.
414 hedges[2*(x+maze_size_x*y)+1] = -1;
415 hedges[2*(x+maze_size_x*y)] = -1;
417 for(x = logo_x; x < logo_x+logow; x++)
419 if(!(bridge_dir==2 && x==bridge_c))
421 build_wall(x, logo_y, 0);
422 build_wall(x, logo_y+logoh, 0);
424 hedges[2*(x+maze_size_x*(logo_y-1))] = -1;
427 build_wall(x, bridge_c, 0);
428 build_wall(x, bridge_c, 2);
431 for(y = logo_y; y < logo_y+logoh; y++)
433 if(!(bridge_dir==1 && y==bridge_c))
435 build_wall(logo_x, y, 3);
436 build_wall(logo_x+logow, y, 3);
438 hedges[2*(logo_x-1+maze_size_x*y)+1] = -1;
441 build_wall(bridge_c, y, 1);
442 build_wall(bridge_c, y, 3);
445 /* Join the whole bridge together. */
452 for(i = logo_x; i < logo_x+logow+1; i++)
453 join_sets(x+y*maze_size_x, i+y*maze_size_x);
459 for(i = logo_y; i < logo_y+logoh+1; i++)
460 join_sets(x+y*maze_size_x, x+i*maze_size_x);
465 for(i = 0; i < maze_size_x*maze_size_y*2; i++)
468 r = random()%(maze_size_x*maze_size_y*2);
469 hedges[i] = hedges[r];
474 /* Get the representative of a set. */
484 s = get_set(sets[num]);
490 /* Join two sets together. */
492 join_sets(num1, num2)
506 /* Exitialise the sets. */
519 /* Temporary hack. */
521 show_set(int num, GC gc)
527 for(x = 0; x < maze_size_x; x++)
528 for(y = 0; y < maze_size_y; y++)
530 if(get_set(x+y*maze_size_x)==set)
532 XFillRectangle(dpy, win, gc, border_x + bw + grid_width * x,
533 border_y + bw + grid_height * y,
534 grid_width-2*bw , grid_height-2*bw);
540 /* Second alternative maze creator: Put each square in the maze in a
541 * separate set. Also, make a list of all the hedges. Randomize that list.
542 * Walk through the list. If, for a certain hedge, the two squares on both
543 * sides of it are in different sets, union the sets and remove the hedge.
544 * Continue until all hedges have been processed or only one set remains.
547 set_create_maze(void)
549 int i, h, x, y, dir, v, w;
555 /* Do almost all the setup. */
558 /* Start running through the hedges. */
559 for(i = 0; i < 2*maze_size_x*maze_size_y; i++)
563 /* This one is in the logo or outside border. */
568 x = (h>>1)%maze_size_x;
569 y = (h>>1)/maze_size_x;
584 show_set(x+y*maze_size_x, logo_gc);
585 show_set(v+w*maze_size_x, tgc);
587 if(get_set(x+y*maze_size_x)!=get_set(v+w*maze_size_x))
592 join_sets(x+y*maze_size_x, v+w*maze_size_x);
593 /* Don't draw the wall. */
600 /* Don't join the sets. */
601 build_wall(x, y, dir);
611 show_set(x+y*maze_size_x, erase_gc);
612 show_set(v+w*maze_size_x, erase_gc);
616 /* Free some memory. */
620 /* First alternative maze creator: Pick a random, empty corner in the maze.
621 * Pick a random direction. Draw a wall in that direction, from that corner
622 * until we hit a wall. Option: Only draw the wall if it's going to be
623 * shorter than a certain length. Otherwise we get lots of long walls.
626 alt_create_maze(void)
630 int i, j, height, width, open_corners, k, dir, x, y;
632 height = maze_size_y+1;
633 width = maze_size_x+1;
635 /* Allocate and clear some mem. */
636 corners = (char *)calloc(height*width, 1);
640 /* Set up the indexing array. */
641 c_idx = (int *)malloc(sizeof(int)*height*width);
647 for(i = 0; i < height*width; i++)
649 for(i = 0; i < height*width; i++)
652 k = random()%(height*width);
657 /* Set up some initial walls. */
659 for(i = 0; i < width; i++)
662 corners[i+width*(height-1)] = 1;
664 for(i = 0; i < height; i++)
666 corners[i*width] = 1;
667 corners[i*width+width-1] = 1;
669 /* Walls around logo. In fact, inside the logo, too. */
670 /* Also draw the walls. */
673 int logow = 1 + logo_width / grid_width;
674 int logoh = 1 + logo_height / grid_height;
675 int bridge_dir, bridge_c;
677 if(bridge_p && logoh>=3 && logow>=3)
679 bridge_dir = 1+random()%2;
682 bridge_c = logo_y+random()%(logoh-2)+1;
686 bridge_c = logo_x+random()%(logow-2)+1;
694 for(i = logo_x; i <= logo_x + logow; i++)
696 for(j = logo_y; j <= logo_y + logoh; j++)
698 corners[i+width*j] = 1;
701 for(x = logo_x; x < logo_x+logow; x++)
703 if(!(bridge_dir==2 && x==bridge_c))
705 build_wall(x, logo_y, 0);
706 build_wall(x, logo_y+logoh, 0);
710 build_wall(x, bridge_c, 0);
711 build_wall(x, bridge_c, 2);
714 for(y = logo_y; y < logo_y+logoh; y++)
716 if(!(bridge_dir==1 && y==bridge_c))
718 build_wall(logo_x, y, 3);
719 build_wall(logo_x+logow, y, 3);
723 build_wall(bridge_c, y, 1);
724 build_wall(bridge_c, y, 3);
727 /* Connect one wall of the logo with an outside wall. */
729 dir = (bridge_dir+1)%4;
735 x = logo_x+(random()%(logow+1));
740 y = logo_y+(random()%(logoh+1));
743 x = logo_x+(random()%(logow+1));
748 y = logo_y+(random()%(logoh+1));
753 corners[x+width*y] = 1;
757 build_wall(x-1, y-1, 1);
769 build_wall(x-1, y-1, 2);
774 while(!corners[x+width*y]);
781 x = logo_x+(random()%(logow+1));
786 y = logo_y+(random()%(logoh+1));
789 x = logo_x+(random()%(logow+1));
794 y = logo_y+(random()%(logoh+1));
799 corners[x+width*y] = 1;
803 build_wall(x-1, y-1, 1);
815 build_wall(x-1, y-1, 2);
820 while(!corners[x+width*y]);
824 /* Count open gridpoints. */
826 for(i = 0; i < width; i++)
827 for(j = 0; j < height; j++)
828 if(!corners[i+width*j])
831 /* Now do actual maze generation. */
832 while(open_corners>0)
834 for(i = 0; i < width*height; i++)
836 if(!corners[c_idx[i]])
840 /* Choose a random direction. */
844 /* Measure the length of the wall we'd draw. */
845 while(!corners[x+width*y])
870 /* Draw a wall until we hit something. */
871 while(!corners[x+width*y])
874 corners[x+width*y] = 1;
878 build_wall(x-1, y-1, 1);
890 build_wall(x-1, y-1, 2);
900 /* Free some memory we used. */
905 /* The original maze creator. Start somewhere. Take a step in a random
906 * direction. Keep doing this until we hit a wall. Then, backtrack until
907 * we find a point where we can go in another direction.
910 create_maze (void) /* create a maze layout given the initialized maze */
912 register int i, newdoor = 0;
913 int logow = 1 + logo_width / grid_width;
914 int logoh = 1 + logo_height / grid_height;
916 /* Maybe we should make a bridge? */
917 if(bridge_p && logo_x>=0 && logow>=3 && logoh>=3)
919 int bridge_dir, bridge_c;
921 bridge_dir = 1+random()%2;
925 bridge_c = logo_y+random()%(logoh-2)+1;
927 bridge_c = logo_y+random()%logoh;
932 bridge_c = logo_x+random()%(logow-2)+1;
934 bridge_c = logo_x+random()%logow;
939 for(i = logo_x; i < logo_x+logow; i++)
941 maze[i][bridge_c] &= ~DOOR_IN_TOP;
946 for(i = logo_y; i < logo_y+logoh; i++)
948 maze[bridge_c][i] &= ~DOOR_IN_TOP;
954 move_list[sqnum].x = cur_sq_x;
955 move_list[sqnum].y = cur_sq_y;
956 move_list[sqnum].dir = newdoor;
957 while ( ( newdoor = choose_door() ) == -1 ) { /* pick a door */
958 if ( backup() == -1 ) { /* no more doors ... backup */
959 return; /* done ... return */
963 /* mark the out door */
964 maze[cur_sq_x][cur_sq_y] |= ( DOOR_OUT_TOP >> newdoor );
978 /* mark the in door */
979 maze[cur_sq_x][cur_sq_y] |= ( DOOR_IN_TOP >> ((newdoor+2)%4) );
981 /* if end square set path length and save path */
982 if ( maze[cur_sq_x][cur_sq_y] & END_SQUARE ) {
984 for ( i=0; i<path_length; i++) {
985 save_path[i].x = move_list[i].x;
986 save_path[i].y = move_list[i].y;
987 save_path[i].dir = move_list[i].dir;
997 choose_door (void) /* pick a new path */
1000 register int num_candidates;
1005 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_TOP )
1007 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_TOP )
1009 if ( maze[cur_sq_x][cur_sq_y] & WALL_TOP )
1011 if ( maze[cur_sq_x][cur_sq_y - 1] & DOOR_IN_ANY ) {
1012 maze[cur_sq_x][cur_sq_y] |= WALL_TOP;
1013 maze[cur_sq_x][cur_sq_y - 1] |= WALL_BOTTOM;
1014 draw_wall(cur_sq_x, cur_sq_y, 0, gc);
1017 candidates[num_candidates++] = 0;
1021 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_RIGHT )
1023 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_RIGHT )
1025 if ( maze[cur_sq_x][cur_sq_y] & WALL_RIGHT )
1027 if ( maze[cur_sq_x + 1][cur_sq_y] & DOOR_IN_ANY ) {
1028 maze[cur_sq_x][cur_sq_y] |= WALL_RIGHT;
1029 maze[cur_sq_x + 1][cur_sq_y] |= WALL_LEFT;
1030 draw_wall(cur_sq_x, cur_sq_y, 1, gc);
1033 candidates[num_candidates++] = 1;
1037 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_BOTTOM )
1039 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_BOTTOM )
1041 if ( maze[cur_sq_x][cur_sq_y] & WALL_BOTTOM )
1043 if ( maze[cur_sq_x][cur_sq_y + 1] & DOOR_IN_ANY ) {
1044 maze[cur_sq_x][cur_sq_y] |= WALL_BOTTOM;
1045 maze[cur_sq_x][cur_sq_y + 1] |= WALL_TOP;
1046 draw_wall(cur_sq_x, cur_sq_y, 2, gc);
1049 candidates[num_candidates++] = 2;
1053 if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_LEFT )
1055 if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_LEFT )
1057 if ( maze[cur_sq_x][cur_sq_y] & WALL_LEFT )
1059 if ( maze[cur_sq_x - 1][cur_sq_y] & DOOR_IN_ANY ) {
1060 maze[cur_sq_x][cur_sq_y] |= WALL_LEFT;
1061 maze[cur_sq_x - 1][cur_sq_y] |= WALL_RIGHT;
1062 draw_wall(cur_sq_x, cur_sq_y, 3, gc);
1065 candidates[num_candidates++] = 3;
1068 if (num_candidates == 0)
1070 if (num_candidates == 1)
1071 return ( candidates[0] );
1072 return ( candidates[ get_random(num_candidates) ] );
1078 backup (void) /* back up a move */
1081 cur_sq_x = move_list[sqnum].x;
1082 cur_sq_y = move_list[sqnum].y;
1088 draw_maze_border (void) /* draw the maze outline */
1093 for ( i=0; i<maze_size_x; i++) {
1094 if ( maze[i][0] & WALL_TOP ) {
1095 XDrawLine(dpy, win, gc,
1096 border_x + grid_width * i,
1098 border_x + grid_width * (i+1) - 1,
1101 if ((maze[i][maze_size_y - 1] & WALL_BOTTOM)) {
1102 XDrawLine(dpy, win, gc,
1103 border_x + grid_width * i,
1104 border_y + grid_height * (maze_size_y) - 1,
1105 border_x + grid_width * (i+1) - 1,
1106 border_y + grid_height * (maze_size_y) - 1);
1109 for ( j=0; j<maze_size_y; j++) {
1110 if ( maze[maze_size_x - 1][j] & WALL_RIGHT ) {
1111 XDrawLine(dpy, win, gc,
1112 border_x + grid_width * maze_size_x - 1,
1113 border_y + grid_height * j,
1114 border_x + grid_width * maze_size_x - 1,
1115 border_y + grid_height * (j+1) - 1);
1117 if ( maze[0][j] & WALL_LEFT ) {
1118 XDrawLine(dpy, win, gc,
1120 border_y + grid_height * j,
1122 border_y + grid_height * (j+1) - 1);
1130 unsigned int w, h, bw, d;
1131 XGetGeometry (dpy, logo_map, &r, &x, &y, &w, &h, &bw, &d);
1132 XCopyPlane (dpy, logo_map, win, logo_gc,
1134 border_x + 3 + grid_width * logo_x,
1135 border_y + 3 + grid_height * logo_y, 1);
1137 draw_solid_square (start_x, start_y, WALL_TOP >> start_dir, tgc);
1138 draw_solid_square (end_x, end_y, WALL_TOP >> end_dir, tgc);
1143 draw_wall(int i, int j, int dir, GC gc) /* draw a single wall */
1147 XDrawLine(dpy, win, gc,
1148 border_x + grid_width * i,
1149 border_y + grid_height * j,
1150 border_x + grid_width * (i+1),
1151 border_y + grid_height * j);
1154 XDrawLine(dpy, win, gc,
1155 border_x + grid_width * (i+1),
1156 border_y + grid_height * j,
1157 border_x + grid_width * (i+1),
1158 border_y + grid_height * (j+1));
1161 XDrawLine(dpy, win, gc,
1162 border_x + grid_width * i,
1163 border_y + grid_height * (j+1),
1164 border_x + grid_width * (i+1),
1165 border_y + grid_height * (j+1));
1168 XDrawLine(dpy, win, gc,
1169 border_x + grid_width * i,
1170 border_y + grid_height * j,
1171 border_x + grid_width * i,
1172 border_y + grid_height * (j+1));
1179 /* Actually build a wall. */
1181 build_wall(i, j, dir)
1184 /* Draw it on the screen. */
1185 draw_wall(i, j, dir, gc);
1186 /* Put it in the maze. */
1190 maze[i][j] |= WALL_TOP;
1192 maze[i][j-1] |= WALL_BOTTOM;
1195 maze[i][j] |= WALL_RIGHT;
1197 maze[i+1][j] |= WALL_LEFT;
1200 maze[i][j] |= WALL_BOTTOM;
1202 maze[i][j+1] |= WALL_TOP;
1205 maze[i][j] |= WALL_LEFT;
1207 maze[i-1][j] |= WALL_RIGHT;
1212 /* Break out a wall. */
1215 break_wall(i, j, dir)
1218 /* Draw it on the screen. */
1219 draw_wall(i, j, dir, erase_gc);
1220 /* Put it in the maze. */
1224 maze[i][j] &= ~WALL_TOP;
1226 maze[i][j-1] &= ~WALL_BOTTOM;
1229 maze[i][j] &= ~WALL_RIGHT;
1231 maze[i+1][j] &= ~WALL_LEFT;
1234 maze[i][j] &= ~WALL_BOTTOM;
1236 maze[i][j+1] &= ~WALL_BOTTOM;
1239 maze[i][j] &= ~WALL_LEFT;
1241 maze[i-1][j] &= ~WALL_RIGHT;
1249 draw_solid_square(int i, int j, /* draw a solid square in a square */
1254 XFillRectangle(dpy, win, gc,
1255 border_x + bw + grid_width * i,
1256 border_y - bw + grid_height * j,
1257 grid_width - (bw+bw), grid_height);
1260 XFillRectangle(dpy, win, gc,
1261 border_x + bw + grid_width * i,
1262 border_y + bw + grid_height * j,
1263 grid_width, grid_height - (bw+bw));
1266 XFillRectangle(dpy, win, gc,
1267 border_x + bw + grid_width * i,
1268 border_y + bw + grid_height * j,
1269 grid_width - (bw+bw), grid_height);
1272 XFillRectangle(dpy, win, gc,
1273 border_x - bw + grid_width * i,
1274 border_y + bw + grid_height * j,
1275 grid_width, grid_height - (bw+bw));
1282 longdeadend_p(int x1, int y1, int x2, int y2, int endwall)
1284 int dx = x2 - x1, dy = y2 - y1;
1287 sidewalls = endwall | (endwall >> 2 | endwall << 2);
1288 sidewalls = ~sidewalls & WALL_ANY;
1290 while((maze[x2][y2] & WALL_ANY) == sidewalls)
1296 if((maze[x2][y2] & WALL_ANY) == (sidewalls | endwall))
1298 endwall = (endwall >> 2 | endwall << 2) & WALL_ANY;
1299 while(x1 != x2 || y1 != y2)
1303 draw_solid_square(x1, y1, endwall, sgc);
1304 maze[x1][y1] |= SOLVER_VISIT;
1312 /* Find all dead regions -- areas from which the goal cannot be reached --
1313 and mark them visited. */
1315 find_dead_regions(void)
1319 /* Find all not SOLVER_VISIT squares bordering NOT_DEAD squares
1320 and mark them NOT_DEAD also. Repeat until no more such squares. */
1321 maze[start_x][start_y] |= NOT_DEAD;
1326 for(x = 0; x < maze_size_x; x++)
1327 for(y = 0; y < maze_size_y; y++)
1328 if(!(maze[x][y] & (SOLVER_VISIT | NOT_DEAD))
1329 && ( (x && (maze[x-1][y] & NOT_DEAD))
1330 || (y && (maze[x][y-1] & NOT_DEAD))))
1333 maze[x][y] |= NOT_DEAD;
1335 for(x = maze_size_x-1; x >= 0; x--)
1336 for(y = maze_size_y-1; y >= 0; y--)
1337 if(!(maze[x][y] & (SOLVER_VISIT | NOT_DEAD))
1338 && ( (x != maze_size_x-1 && (maze[x+1][y] & NOT_DEAD))
1339 || (y != maze_size_y-1 && (maze[x][y+1] & NOT_DEAD))))
1342 maze[x][y] |= NOT_DEAD;
1347 for (y = 0; y < maze_size_y; y++)
1348 for (x = 0; x < maze_size_x; x++)
1350 if (maze[x][y] & NOT_DEAD)
1351 maze[x][y] &= ~NOT_DEAD;
1352 else if (!(maze[x][y] & SOLVER_VISIT))
1354 maze[x][y] |= SOLVER_VISIT;
1355 if((x < logo_x || x > logo_x + logo_width / grid_width) ||
1356 (y < logo_y || y > logo_y + logo_height / grid_height))
1358 if (!maze[x][y] & WALL_ANY)
1359 XFillRectangle(dpy, win, ugc,
1360 border_x + bw + grid_width * x,
1361 border_y + bw + grid_height * y,
1362 grid_width - (bw+bw), grid_height - (bw+bw));
1365 if (! (maze[x][y] & WALL_LEFT))
1366 draw_solid_square(x, y, WALL_LEFT, ugc);
1367 if (! (maze[x][y] & WALL_RIGHT))
1368 draw_solid_square(x, y, WALL_RIGHT, ugc);
1369 if (! (maze[x][y] & WALL_TOP))
1370 draw_solid_square(x, y, WALL_TOP, ugc);
1371 if (! (maze[x][y] & WALL_BOTTOM))
1372 draw_solid_square(x, y, WALL_BOTTOM, ugc);
1381 solve_maze (void) /* solve it with graphical feedback */
1383 int i, dir, from, x, y, ways, bt = 0;
1385 /* plug up the surrounding wall */
1386 maze[end_x][end_y] |= (WALL_TOP >> end_dir);
1388 /* initialize search path */
1393 maze[end_x][end_y] |= SOLVER_VISIT;
1398 if ( maze[path[i].x][path[i].y] & START_SQUARE )
1401 /* Abort solve on expose - cheapo repaint strategy */
1402 if (check_events()) return;
1404 if (solve_delay) usleep (solve_delay);
1409 /* First visit this square. Which adjacent squares are open? */
1410 for(dir = WALL_TOP; dir & WALL_ANY; dir >>= 1)
1412 if(maze[path[i].x][path[i].y] & dir)
1415 y = path[i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1416 x = path[i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1418 if(maze[x][y] & SOLVER_VISIT)
1421 from = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1422 /* don't enter obvious dead ends */
1423 if(((maze[x][y] & WALL_ANY) | from) != WALL_ANY)
1425 if(!longdeadend_p(path[i].x, path[i].y, x, y, dir))
1430 draw_solid_square(x, y, from, sgc);
1431 maze[x][y] |= SOLVER_VISIT;
1436 ways = path[i].ways;
1437 /* ways now has a bitmask of open paths. */
1444 x = path[i].x - start_x;
1445 y = path[i].y - start_y;
1447 if(abs(y) <= abs(x))
1448 dir = (x > 0) ? WALL_LEFT : WALL_RIGHT;
1450 dir = (y > 0) ? WALL_TOP : WALL_BOTTOM;
1460 dir = (y > 0) ? WALL_TOP : WALL_BOTTOM; break;
1463 dir = (x > 0) ? WALL_LEFT : WALL_RIGHT;
1471 dir = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1486 else if(ways&WALL_LEFT)
1488 else if(ways&WALL_BOTTOM)
1490 else if(ways&WALL_RIGHT)
1496 ways &= ~dir; /* tried this one */
1498 y = path[i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1499 x = path[i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1501 /* advance in direction dir */
1503 path[i].ways = ways;
1504 draw_solid_square(path[i].x, path[i].y, dir, tgc);
1511 maze[x][y] |= SOLVER_VISIT;
1517 printf("Unsolvable maze.\n");
1521 if(!bt && !ignorant_p)
1522 find_dead_regions();
1524 from = path[i-1].dir;
1525 from = (from << 2 & WALL_ANY) | (from >> 2 & WALL_ANY);
1527 draw_solid_square(path[i].x, path[i].y, from, cgc);
1534 enter_square (int n) /* move into a neighboring square */
1536 draw_solid_square( (int)path[n].x, (int)path[n].y,
1537 (int)path[n].dir, tgc);
1540 switch (path[n].dir) {
1541 case 0: path[n+1].x = path[n].x;
1542 path[n+1].y = path[n].y - 1;
1544 case 1: path[n+1].x = path[n].x + 1;
1545 path[n+1].y = path[n].y;
1547 case 2: path[n+1].x = path[n].x;
1548 path[n+1].y = path[n].y + 1;
1550 case 3: path[n+1].x = path[n].x - 1;
1551 path[n+1].y = path[n].y;
1559 * jmr additions for Jamie Zawinski's <jwz@jwz.org> screensaver stuff,
1560 * note that the code above this has probably been hacked about in some
1564 char *progclass = "Maze";
1566 char *defaults[] = {
1567 ".background: black",
1568 ".foreground: white",
1570 "*solveDelay: 5000",
1571 "*preDelay: 2000000",
1572 "*postDelay: 4000000",
1573 "*liveColor: green",
1575 "*skipColor: orange",
1576 "*surroundColor: slateblue",
1587 XrmOptionDescRec options[] = {
1588 { "-ignorant", ".ignorant", XrmoptionNoArg, "True" },
1589 { "-no-ignorant", ".ignorant", XrmoptionNoArg, "False" },
1590 { "-grid-size", ".gridSize", XrmoptionSepArg, 0 },
1591 { "-solve-delay", ".solveDelay", XrmoptionSepArg, 0 },
1592 { "-pre-delay", ".preDelay", XrmoptionSepArg, 0 },
1593 { "-post-delay", ".postDelay", XrmoptionSepArg, 0 },
1594 { "-live-color", ".liveColor", XrmoptionSepArg, 0 },
1595 { "-dead-color", ".deadColor", XrmoptionSepArg, 0 },
1596 { "-skip-color", ".skipColor", XrmoptionSepArg, 0 },
1597 { "-surround-color", ".surroundColor",XrmoptionSepArg, 0 },
1598 { "-generator", ".generator", XrmoptionSepArg, 0 },
1599 { "-max-length", ".maxLength", XrmoptionSepArg, 0 },
1600 { "-bridge", ".bridge", XrmoptionNoArg, "True" },
1601 { "-no-bridge", ".bridge", XrmoptionNoArg, "False" },
1606 extern void skull (Display *, Window, GC, GC, int, int, int, int);
1610 screenhack(Display *display, Window window)
1613 int size, root, generator, this_gen;
1614 XWindowAttributes xgwa;
1615 unsigned long bg, fg, pfg, pbg, lfg, sfg, ufg;
1617 size = get_integer_resource ("gridSize", "Dimension");
1618 root = get_boolean_resource("root", "Boolean");
1619 solve_delay = get_integer_resource ("solveDelay", "Integer");
1620 pre_solve_delay = get_integer_resource ("preDelay", "Integer");
1621 post_solve_delay = get_integer_resource ("postDelay", "Integer");
1622 generator = get_integer_resource("generator", "Integer");
1623 max_length = get_integer_resource("maxLength", "Integer");
1624 bridge_p = get_boolean_resource("bridge", "Boolean");
1625 ignorant_p = get_boolean_resource("ignorant", "Boolean");
1627 if (size < 2) size = 7 + (random () % 30);
1628 grid_width = grid_height = size;
1629 bw = (size > 6 ? 3 : (size-1)/2);
1631 dpy = display; win = window; /* the maze stuff uses global variables */
1633 XGetWindowAttributes (dpy, win, &xgwa);
1638 set_maze_sizes (xgwa.width, xgwa.height);
1642 XWindowAttributes xgwa;
1643 XGetWindowAttributes (dpy, window, &xgwa);
1644 XSelectInput (dpy, win,
1645 xgwa.your_event_mask | ExposureMask |
1646 ButtonPressMask |StructureNotifyMask);
1649 gc = XCreateGC(dpy, win, 0, 0);
1650 cgc = XCreateGC(dpy, win, 0, 0);
1651 tgc = XCreateGC(dpy, win, 0, 0);
1652 sgc = XCreateGC(dpy, win, 0, 0);
1653 ugc = XCreateGC(dpy, win, 0, 0);
1654 logo_gc = XCreateGC(dpy, win, 0, 0);
1655 erase_gc = XCreateGC(dpy, win, 0, 0);
1657 gray = XCreateBitmapFromData (dpy,win,gray1_bits,gray1_width,gray1_height);
1659 bg = get_pixel_resource ("background","Background", dpy, xgwa.colormap);
1660 fg = get_pixel_resource ("foreground","Foreground", dpy, xgwa.colormap);
1661 lfg = get_pixel_resource ("logoColor", "Foreground", dpy, xgwa.colormap);
1662 pfg = get_pixel_resource ("liveColor", "Foreground", dpy, xgwa.colormap);
1663 pbg = get_pixel_resource ("deadColor", "Foreground", dpy, xgwa.colormap);
1664 sfg = get_pixel_resource ("skipColor", "Foreground", dpy, xgwa.colormap);
1665 ufg = get_pixel_resource ("surroundColor", "Foreground", dpy, xgwa.colormap);
1666 if (mono_p) lfg = pfg = fg;
1669 lfg = ((bg == WhitePixel (dpy, DefaultScreen (dpy)))
1670 ? BlackPixel (dpy, DefaultScreen (dpy))
1671 : WhitePixel (dpy, DefaultScreen (dpy)));
1673 XSetForeground (dpy, gc, fg);
1674 XSetBackground (dpy, gc, bg);
1675 XSetForeground (dpy, cgc, pbg);
1676 XSetBackground (dpy, cgc, bg);
1677 XSetForeground (dpy, tgc, pfg);
1678 XSetBackground (dpy, tgc, bg);
1679 XSetForeground (dpy, sgc, sfg);
1680 XSetBackground (dpy, sgc, bg);
1681 XSetForeground (dpy, ugc, ufg);
1682 XSetBackground (dpy, ugc, bg);
1683 XSetForeground (dpy, logo_gc, lfg);
1684 XSetBackground (dpy, logo_gc, bg);
1685 XSetForeground (dpy, erase_gc, bg);
1686 XSetBackground (dpy, erase_gc, bg);
1688 XSetStipple (dpy, cgc, gray);
1689 XSetFillStyle (dpy, cgc, FillOpaqueStippled);
1690 XSetStipple (dpy, sgc, gray);
1691 XSetFillStyle (dpy, sgc, FillOpaqueStippled);
1692 XSetStipple (dpy, ugc, gray);
1693 XSetFillStyle (dpy, ugc, FillOpaqueStippled);
1699 GC draw_gc, erase_gc;
1700 /* round up to grid size */
1701 w = ((logo_width / grid_width) + 1) * grid_width;
1702 h = ((logo_height / grid_height) + 1) * grid_height;
1703 logo_map = XCreatePixmap (dpy, win, w, h, 1);
1704 gcv.foreground = 1L;
1705 draw_gc = XCreateGC (dpy, logo_map, GCForeground, &gcv);
1706 gcv.foreground = 0L;
1707 erase_gc= XCreateGC (dpy, logo_map, GCForeground, &gcv);
1708 XFillRectangle (dpy, logo_map, erase_gc, 0, 0, w, h);
1709 skull (dpy, logo_map, draw_gc, erase_gc, 5, 0, w-10, h-10);
1710 XFreeGC (dpy, draw_gc);
1711 XFreeGC (dpy, erase_gc);
1714 if (!(logo_map = XCreateBitmapFromData (dpy, win, logo_bits,
1715 logo_width, logo_height)))
1717 fprintf (stderr, "Can't create logo pixmap\n");
1721 XMapRaised(dpy, win);
1725 sync_p = !(random() % 10);
1727 while (1) { /* primary execution loop [ rhess ] */
1728 if (check_events()) continue ;
1729 if (restart || stop) goto pop;
1735 XClearWindow(dpy, win);
1739 this_gen = generator;
1740 if(this_gen<0 || this_gen>2)
1741 this_gen = random()%3;
1758 usleep (pre_solve_delay);
1765 usleep (post_solve_delay);
1767 erase_full_window(display, window);
1776 static XWindowAttributes wattr;
1780 XGetWindowAttributes (dpy, win, &wattr);
1781 set_maze_sizes (wattr.width, wattr.height);
1782 XClearWindow (dpy, win);
1784 sync_p = !(random() % 10);