1 /******************************************************************************
4 * modified: [ 13-08-08 ] Jamie Zawinski <jwz@jwz.org>
5 * Removed the bridge option: it didn't look good, and it made
6 * the code a lot harder to understand.
7 * Made the maze stay out of the area used for the -fps display.
8 * Cleaned up and commented.
10 * modified: [ 1-04-00 ] Johannes Keukelaar <johannes@nada.kth.se>
11 * Added -ignorant option (not the default) to remove knowlege
12 * of the direction in which the exit lies.
14 * modified: [ 6-28-98 ] Zack Weinberg <zack@rabi.phys.columbia.edu>
16 * Made the maze-solver somewhat more intelligent. There are
17 * three optimizations:
19 * - Straight-line lookahead: the solver does not enter dead-end
20 * corridors. This is a win with all maze generators.
22 * - First order direction choice: the solver knows where the
23 * exit is in relation to itself, and will try paths leading in
24 * that direction first. This is a major win on maze generator 1
25 * which tends to offer direct routes to the exit.
27 * - Dead region elimination: the solver already has a map of
28 * all squares visited. Whenever it starts to backtrack, it
29 * consults this map and marks off all squares that cannot be
30 * reached from the exit without crossing a square already
31 * visited. Those squares can never contribute to the path to
32 * the exit, so it doesn't bother checking them. This helps a
33 * lot with maze generator 2 and somewhat less with generator 1.
35 * Further improvements would require knowledge of the wall map
36 * as well as the position of the exit and the squares visited.
37 * I would consider that to be cheating. Generator 0 makes
38 * mazes which are remarkably difficult to solve mechanically --
39 * even with these optimizations the solver generally must visit
40 * at least two-thirds of the squares. This is partially
41 * because generator 0's mazes have longer paths to the exit.
43 * modified: [ 4-10-97 ] Johannes Keukelaar <johannes@nada.kth.se>
44 * Added multiple maze creators. Robustified solver.
45 * Added bridge option.
46 * modified: [ 8-11-95 ] Ed James <james@mml.mmc.com>
47 * added fill of dead-end box to solve_maze while loop.
48 * modified: [ 3-7-93 ] Jamie Zawinski <jwz@jwz.org>
49 * added the XRoger logo, cleaned up resources, made
50 * grid size a parameter.
51 * modified: [ 3-3-93 ] Jim Randell <jmr@mddjmr.fc.hp.com>
52 * Added the colour stuff and integrated it with jwz's
53 * screenhack stuff. There's still some work that could
54 * be done on this, particularly allowing a resource to
55 * specify how big the squares are.
56 * modified: [ 10-4-88 ] Richard Hess ...!uunet!cimshop!rhess
57 * [ Revised primary execution loop within main()...
58 * [ Extended X event handler, check_events()...
59 * modified: [ 1-29-88 ] Dave Lemke lemke@sun.com
61 * [ Note the word "hacked" -- this is extremely ugly, but at
62 * [ least it does the job. NOT a good programming example
64 * original: [ 6/21/85 ] Martin Weiss Sun Microsystems [ SunView ]
66 ******************************************************************************
67 Copyright 1988 by Sun Microsystems, Inc. Mountain View, CA.
71 Permission to use, copy, modify, and distribute this software and its
72 documentation for any purpose and without fee is hereby granted,
73 provided that the above copyright notice appear in all copies and that
74 both that copyright notice and this permission notice appear in
75 supporting documentation, and that the names of Sun or MIT not be
76 used in advertising or publicity pertaining to distribution of the
77 software without specific prior written permission. Sun and M.I.T.
78 make no representations about the suitability of this software for
79 any purpose. It is provided "as is" without any express or implied warranty.
81 SUN DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
82 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
83 PURPOSE. IN NO EVENT SHALL SUN BE LIABLE FOR ANY SPECIAL, INDIRECT
84 OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
85 OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
86 OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE
87 OR PERFORMANCE OF THIS SOFTWARE.
88 *****************************************************************************/
90 #include "screenhack.h"
92 #include "ximage-loader.h"
93 #include "images/gen/logo-50_png.h"
94 #include "images/gen/logo-180_png.h"
98 /* #include <X11/bitmaps/gray1> */
100 #define gray1_width 2
101 #define gray1_height 2
102 static const char gray1_bits[] = { 0x01, 0x02 };
105 #define MAX_MAZE_SIZE_X 1000
106 #define MAX_MAZE_SIZE_Y 1000
108 #define MOVE_LIST_SIZE (MAX_MAZE_SIZE_X * MAX_MAZE_SIZE_Y)
110 #define NOT_DEAD 0x8000
111 #define SOLVER_VISIT 0x4000
112 #define START_SQUARE 0x2000
113 #define END_SQUARE 0x1000
116 #define WALL_RIGHT 0x4
117 #define WALL_BOTTOM 0x2
118 #define WALL_LEFT 0x1
121 #define DOOR_IN_TOP 0x800
122 #define DOOR_IN_RIGHT 0x400
123 #define DOOR_IN_BOTTOM 0x200
124 #define DOOR_IN_LEFT 0x100
125 #define DOOR_IN_ANY 0xF00
127 #define DOOR_OUT_TOP 0x80
128 #define DOOR_OUT_RIGHT 0x40
129 #define DOOR_OUT_BOTTOM 0x20
130 #define DOOR_OUT_LEFT 0x10
136 #define get_random(x) (random() % (x))
139 struct move_list_struct {
142 unsigned char dir, ways;
155 GC gc, cgc, tgc, sgc, ugc, logo_gc, erase_gc;
158 int logo_x, logo_y; /* in grid cells (or -1) */
159 int logo_width, logo_height; /* in pixels */
160 int fps_width, fps_height; /* in pixels */
162 int solve_delay, pre_solve_delay, post_solve_delay;
164 unsigned short maze[MAX_MAZE_SIZE_X][MAX_MAZE_SIZE_Y];
166 struct move_list_struct move_list[MOVE_LIST_SIZE];
167 struct move_list_struct save_path[MOVE_LIST_SIZE];
168 struct move_list_struct path[MOVE_LIST_SIZE];
170 int maze_size_x, maze_size_y;
171 int sqnum, cur_sq_x, cur_sq_y, path_length;
172 int start_x, start_y, start_dir, end_x, end_y, end_dir;
173 int grid_width, grid_height;
176 int x, y, restart, stop, state, max_length;
177 int sync_p, sync_tick;
180 struct solve_state *solve_state;
182 int *sets; /* The sets that our squares are in. */
183 int *hedges; /* The `list' of hedges. */
187 eraser_state *eraser;
195 static void draw_wall (struct state *, int, int, int, GC);
196 static void draw_solid_square (struct state *, int, int, int, GC);
197 static void build_wall (struct state *, int, int, int);
201 set_maze_sizes (struct state *st, int width, int height)
203 st->maze_size_x = width / st->grid_width;
204 st->maze_size_y = height / st->grid_height;
206 if (st->maze_size_x < 4) st->maze_size_x = 4;
207 if (st->maze_size_y < 4) st->maze_size_y = 4;
211 /* Resets the maze grid, picks the starting and ending points,
212 and the position of the logo, if any.
215 initialize_maze (struct state *st)
219 int logow = 1 + st->logo_width / st->grid_width;
220 int logoh = 1 + st->logo_height / st->grid_height;
224 /* This can happen if the window is really small. Let's not sweat it. */
225 if (++retry_count > 100) return;
228 /* initialize all squares */
229 for ( i=0; i<st->maze_size_x; i++) {
230 for ( j=0; j<st->maze_size_y; j++) {
236 for ( i=0; i<st->maze_size_x; i++ ) {
237 st->maze[i][0] |= WALL_TOP;
241 for ( j=0; j<st->maze_size_y; j++ ) {
242 st->maze[st->maze_size_x-1][j] |= WALL_RIGHT;
246 for ( i=0; i<st->maze_size_x; i++ ) {
247 st->maze[i][st->maze_size_y-1] |= WALL_BOTTOM;
251 for ( j=0; j<st->maze_size_y; j++ ) {
252 st->maze[0][j] |= WALL_LEFT;
255 /* set start square */
256 wall = get_random(4);
259 i = get_random(st->maze_size_x);
263 i = st->maze_size_x - 1;
264 j = get_random(st->maze_size_y);
267 i = get_random(st->maze_size_x);
268 j = st->maze_size_y - 1;
272 j = get_random(st->maze_size_y);
275 st->maze[i][j] |= START_SQUARE;
276 st->maze[i][j] |= ( DOOR_IN_TOP >> wall );
277 st->maze[i][j] &= ~( WALL_TOP >> wall );
282 st->start_dir = wall;
289 i = get_random(st->maze_size_x);
293 i = st->maze_size_x - 1;
294 j = get_random(st->maze_size_y);
297 i = get_random(st->maze_size_x);
298 j = st->maze_size_y - 1;
302 j = get_random(st->maze_size_y);
305 st->maze[i][j] |= END_SQUARE;
306 st->maze[i][j] |= ( DOOR_OUT_TOP >> wall );
307 st->maze[i][j] &= ~( WALL_TOP >> wall );
313 if ((st->maze_size_x-logow >= 6) && (st->maze_size_y-logoh >= 6))
315 /* not closer than 3 grid units from a wall, to ensure that it
316 won't overlap the entrance or exit. */
317 st->logo_x = get_random (st->maze_size_x - logow - 5) + 3;
318 st->logo_y = get_random (st->maze_size_y - logoh - 5) + 3;
319 for (i=0; i<logow; i++)
320 for (j=0; j<logoh; j++)
321 /* mark as having doors to prevent these cells being used in maze. */
322 st->maze[st->logo_x + i][st->logo_y + j] |= DOOR_IN_ANY;
325 st->logo_y = st->logo_x = -1;
327 /* mask out the fps area */
328 if (st->fps_width > 0)
330 int fpsw = 1 + st->fps_width / st->grid_width;
331 int fpsh = 1 + st->fps_height / st->grid_width;
333 /* if the chosen logo position overlapped the fps area, try again! */
334 if (st->logo_x < fpsw+3 && st->logo_y+logoh > st->maze_size_y-fpsh-4)
337 /* if the start or end point is inside the fps area, try again! */
338 if ((st->start_x <= fpsw && st->start_y >= st->maze_size_y-fpsh-1) ||
339 (st->end_x <= fpsw && st->end_y >= st->maze_size_y-fpsh-1))
342 for (i=0; i<fpsw; i++)
343 for (j=0; j<fpsh; j++) {
344 /* mark as having doors to prevent these cells being used in maze.
345 mark as visit to prevent it being colored "unreachable". */
346 st->maze[i][st->maze_size_y - j - 1] |= DOOR_IN_ANY|SOLVER_VISIT;
347 /* take off left/bottom wall or the FPS text overlaps it */
348 st->maze[i][st->maze_size_y - j - 1] &= ~(WALL_BOTTOM|WALL_LEFT);
354 /****************************************************************************
355 Generator 2: Set-based maze generator.
357 Put each square in the maze in a separate set. Also, make a list of all the
358 hedges. Randomize that list. Walk through the list. If, for a certain
359 hedge, the two squares on both sides of it are in different sets, union the
360 sets and remove the hedge. Continue until all hedges have been processed or
361 only one set remains.
363 This is essentially the "Kruskal" algorithm.
365 ****************************************************************************/
367 static void mask_out_set_rect(struct state *st, int x, int y, int w, int h);
369 /* Initialise the sets. */
371 init_sets(struct state *st)
377 st->sets = (int *)malloc(st->maze_size_x*st->maze_size_y*sizeof(int));
380 for(i = 0; i < st->maze_size_x*st->maze_size_y; i++)
387 st->hedges = (int *)malloc(st->maze_size_x*st->maze_size_y*2*sizeof(int));
390 for(i = 0; i < st->maze_size_x*st->maze_size_y*2; i++)
394 /* Mask out outside walls. */
395 for(i = 0; i < st->maze_size_y; i++)
397 st->hedges[2*((st->maze_size_x)*i+st->maze_size_x-1)+1] = -1;
399 for(i = 0; i < st->maze_size_x; i++)
401 st->hedges[2*((st->maze_size_y-1)*st->maze_size_x+i)] = -1;
404 /* Mask out the logo area. */
407 int logow = 1 + st->logo_width / st->grid_width;
408 int logoh = 1 + st->logo_height / st->grid_height;
409 mask_out_set_rect(st, st->logo_x, st->logo_y, logow, logoh);
412 /* Mask out the FPS area. */
413 if(st->fps_width > 0)
415 int fpsw = 1 + st->fps_width / st->grid_width;
416 int fpsh = 1 + st->fps_height / st->grid_height;
417 mask_out_set_rect(st, 0, st->maze_size_y-fpsh, fpsw, fpsh);
420 for(i = 0; i < st->maze_size_x*st->maze_size_y*2; i++)
423 r = random()%(st->maze_size_x*st->maze_size_y*2);
424 st->hedges[i] = st->hedges[r];
429 /* Get the representative of a set. */
431 get_set(struct state *st, int num)
435 if(st->sets[num]==num)
439 s = get_set(st, st->sets[num]);
445 /* Join two sets together. */
447 join_sets(struct state *st, int num1, int num2)
451 s1 = get_set(st, num1);
452 s2 = get_set(st, num2);
460 /* Exitialise the sets. */
462 exit_sets(struct state *st)
474 set_create_maze(struct state *st)
476 int i, h, xx, yy, dir, v, w;
478 /* Do almost all the setup. */
481 /* Start running through the hedges. */
482 for(i = 0; i < 2*st->maze_size_x*st->maze_size_y; i++)
486 /* This one is in the logo or outside border. */
491 xx = (h>>1)%st->maze_size_x;
492 yy = (h>>1)/st->maze_size_x;
506 if(get_set(st, xx+yy*st->maze_size_x)!=get_set(st, v+w*st->maze_size_x))
508 join_sets(st, xx+yy*st->maze_size_x, v+w*st->maze_size_x);
509 /* Don't draw the wall. */
513 /* Don't join the sets. */
514 build_wall(st, xx, yy, dir);
518 /* Free some memory. */
522 /* mark a rectangle as being unavailable for usage in the maze */
524 mask_out_set_rect(struct state *st, int x, int y, int w, int h)
527 for(xx = x; xx < x+w; xx++)
528 for(yy = y; yy < y+h; yy++)
530 st->hedges[2*(xx+st->maze_size_x*yy)+1] = -1;
531 st->hedges[2*(xx+st->maze_size_x*yy)] = -1;
533 for(xx = x; xx < x+w; xx++)
535 build_wall(st, xx, y, 0);
536 build_wall(st, xx, y+h, 0);
537 st->hedges[2*(xx+st->maze_size_x*(y-1))] = -1;
539 for(yy = y; yy < y+h; yy++)
541 build_wall(st, x, yy, 3);
542 build_wall(st, x+w, yy, 3);
543 st->hedges[2*(x-1+st->maze_size_x*yy)+1] = -1;
548 /****************************************************************************
549 Generator 1: Wall-building maze generator.
551 Pick a random, empty corner in the maze. Pick a random direction. Draw a
552 wall in that direction, from that corner until we hit a wall. Option: Only
553 draw the wall if it's going to be shorter than a certain length. Otherwise
554 we get lots of long walls.
556 This is essentially the "Prim" algorithm.
557 ****************************************************************************/
559 static void alt_mask_out_rect(struct state *st, char *corners,
560 int x, int y, int w, int h);
563 alt_create_maze(struct state *st)
567 int i, j, height, width, open_corners, k, dir, xx, yy;
569 height = st->maze_size_y+1;
570 width = st->maze_size_x+1;
572 /* Allocate and clear some mem. */
573 corners = (char *)calloc(height*width, 1);
577 /* Set up the indexing array. */
578 c_idx = (int *)malloc(sizeof(int)*height*width);
584 for(i = 0; i < height*width; i++)
586 for(i = 0; i < height*width; i++)
589 k = random()%(height*width);
594 /* Set up some initial walls. */
596 for(i = 0; i < width; i++)
599 corners[i+width*(height-1)] = 1;
601 for(i = 0; i < height; i++)
603 corners[i*width] = 1;
604 corners[i*width+width-1] = 1;
607 /* mask out the logo area */
610 int logow = 1 + st->logo_width / st->grid_width;
611 int logoh = 1 + st->logo_height / st->grid_height;
612 alt_mask_out_rect (st, corners, st->logo_x, st->logo_y, logow, logoh);
615 /* mask out the FPS area */
618 int fpsw = 1 + st->fps_width / st->grid_width;
619 int fpsh = 1 + st->fps_height / st->grid_height;
620 alt_mask_out_rect (st, corners, 0, st->maze_size_y-fpsh, fpsw, fpsh);
623 /* Count open gridpoints. */
625 for(i = 0; i < width; i++)
626 for(j = 0; j < height; j++)
627 if(!corners[i+width*j])
630 /* Now do actual maze generation. */
631 while(open_corners>0)
633 for(i = 0; i < width*height; i++)
635 if(!corners[c_idx[i]])
639 /* Choose a random direction. */
643 /* Measure the length of the wall we'd draw. */
644 while(!corners[xx+width*yy])
664 if(k<=st->max_length)
669 /* Draw a wall until we hit something. */
670 while(!corners[xx+width*yy])
673 corners[xx+width*yy] = 1;
677 build_wall(st, xx-1, yy-1, 1);
681 build_wall(st, xx, yy, 0);
685 build_wall(st, xx, yy, 3);
689 build_wall(st, xx-1, yy-1, 2);
699 /* Free some memory we used. */
705 /* mark a rectangle as being unavailable for usage in the maze */
707 alt_mask_out_rect(struct state *st, char *corners, int x, int y, int w, int h)
710 int mazew = st->maze_size_x+1;
712 for(i = x; i <= x+w; i++)
713 for(j = y; j <= y+h; j++)
714 corners[i+mazew*j] = 1;
716 for(xx = x; xx < x+w; xx++)
718 build_wall(st, xx, y, 0);
719 if (y+h < st->maze_size_y)
720 build_wall(st, xx, y+h, 0);
722 for(yy = y; yy < y+h; yy++)
725 build_wall(st, x, yy, 3);
726 build_wall(st, x+w, yy, 3);
731 /****************************************************************************
732 Generator 0: The original maze generator.
734 Start somewhere. Take a step in a random direction. Keep doing this until
735 we hit a wall. Then, backtrack until we find a point where we can go in
738 This is essentially the "depth-first recursive backtracker" algorithm.
739 ****************************************************************************/
741 static int choose_door (struct state *st);
742 static int backup (struct state *st);
745 create_maze (struct state *st) /* create a maze layout given the initialized maze */
750 st->move_list[st->sqnum].x = st->cur_sq_x;
751 st->move_list[st->sqnum].y = st->cur_sq_y;
752 st->move_list[st->sqnum].dir = newdoor;
753 while ( ( newdoor = choose_door(st) ) == -1 ) { /* pick a door */
754 if ( backup(st) == -1 ) { /* no more doors ... backup */
755 return; /* done ... return */
759 /* mark the out door */
760 st->maze[st->cur_sq_x][st->cur_sq_y] |= ( DOOR_OUT_TOP >> newdoor );
763 case 0: st->cur_sq_y--;
765 case 1: st->cur_sq_x++;
767 case 2: st->cur_sq_y++;
769 case 3: st->cur_sq_x--;
774 /* mark the in door */
775 st->maze[st->cur_sq_x][st->cur_sq_y] |= ( DOOR_IN_TOP >> ((newdoor+2)%4) );
777 /* if end square set path length and save path */
778 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & END_SQUARE ) {
779 st->path_length = st->sqnum;
780 for ( i=0; i<st->path_length; i++) {
781 st->save_path[i].x = st->move_list[i].x;
782 st->save_path[i].y = st->move_list[i].y;
783 st->save_path[i].dir = st->move_list[i].dir;
793 choose_door (struct state *st) /* pick a new path */
801 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_TOP )
803 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_TOP )
805 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_TOP )
807 if ( st->maze[st->cur_sq_x][st->cur_sq_y - 1] & DOOR_IN_ANY ) {
808 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_TOP;
809 st->maze[st->cur_sq_x][st->cur_sq_y - 1] |= WALL_BOTTOM;
810 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 0, st->gc);
813 candidates[num_candidates++] = 0;
817 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_RIGHT )
819 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_RIGHT )
821 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_RIGHT )
823 if ( st->maze[st->cur_sq_x + 1][st->cur_sq_y] & DOOR_IN_ANY ) {
824 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_RIGHT;
825 st->maze[st->cur_sq_x + 1][st->cur_sq_y] |= WALL_LEFT;
826 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 1, st->gc);
829 candidates[num_candidates++] = 1;
833 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_BOTTOM )
835 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_BOTTOM )
837 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_BOTTOM )
839 if ( st->maze[st->cur_sq_x][st->cur_sq_y + 1] & DOOR_IN_ANY ) {
840 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_BOTTOM;
841 st->maze[st->cur_sq_x][st->cur_sq_y + 1] |= WALL_TOP;
842 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 2, st->gc);
845 candidates[num_candidates++] = 2;
849 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_LEFT )
851 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_LEFT )
853 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_LEFT )
855 if ( st->maze[st->cur_sq_x - 1][st->cur_sq_y] & DOOR_IN_ANY ) {
856 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_LEFT;
857 st->maze[st->cur_sq_x - 1][st->cur_sq_y] |= WALL_RIGHT;
858 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 3, st->gc);
861 candidates[num_candidates++] = 3;
864 if (num_candidates == 0)
866 if (num_candidates == 1)
867 return ( candidates[0] );
868 return ( candidates[ get_random(num_candidates) ] );
874 backup (struct state *st) /* back up a move */
877 if (st->sqnum >= 0) {
878 st->cur_sq_x = st->move_list[st->sqnum].x;
879 st->cur_sq_y = st->move_list[st->sqnum].y;
881 return ( st->sqnum );
885 /****************************************************************************
887 ****************************************************************************/
889 /* draws the maze outline, and the logo */
891 draw_maze_border (struct state *st)
895 for ( i=0; i<st->maze_size_x; i++) {
896 if ( st->maze[i][0] & WALL_TOP ) {
897 XDrawLine(st->dpy, st->window, st->gc,
898 border_x + st->grid_width * i,
900 border_x + st->grid_width * (i+1) - 1,
903 if ((st->maze[i][st->maze_size_y - 1] & WALL_BOTTOM)) {
904 XDrawLine(st->dpy, st->window, st->gc,
905 border_x + st->grid_width * i,
906 border_y + st->grid_height * (st->maze_size_y) - 1,
907 border_x + st->grid_width * (i+1) - 1,
908 border_y + st->grid_height * (st->maze_size_y) - 1);
911 for ( j=0; j<st->maze_size_y; j++) {
912 if ( st->maze[st->maze_size_x - 1][j] & WALL_RIGHT ) {
913 XDrawLine(st->dpy, st->window, st->gc,
914 border_x + st->grid_width * st->maze_size_x - 1,
915 border_y + st->grid_height * j,
916 border_x + st->grid_width * st->maze_size_x - 1,
917 border_y + st->grid_height * (j+1) - 1);
919 if ( st->maze[0][j] & WALL_LEFT ) {
920 XDrawLine(st->dpy, st->window, st->gc,
922 border_y + st->grid_height * j,
924 border_y + st->grid_height * (j+1) - 1);
928 if (st->logo_x != -1)
932 unsigned int w, h, bbw, d;
934 /* round up to grid size */
935 int ww = ((st->logo_width / st->grid_width) + 1) * st->grid_width;
936 int hh = ((st->logo_height / st->grid_height) + 1) * st->grid_height;
939 XGetGeometry (st->dpy, st->logo_map, &r, &xx, &yy, &w, &h, &bbw, &d);
941 /* kludge: if the logo "hole" is around the same size as the logo,
942 don't center it (since the xscreensaver logo image is a little
943 off center... But do center it if the hole/gridsize is large. */
944 if (ww < st->logo_width + 5) ww = w;
945 if (hh < st->logo_height + 5) hh = h;
948 lx = border_x + 3 + st->grid_width * st->logo_x + ((ww - w) / 2);
949 ly = border_y + 3 + st->grid_height * st->logo_y + ((hh - h) / 2);
951 /* Fill the background of the logo box with the "unreachable" color */
952 XFillRectangle (st->dpy, st->window, st->ugc,
953 border_x + 3 + st->grid_width * st->logo_x,
954 border_y + 3 + st->grid_height * st->logo_y,
957 XSetClipOrigin (st->dpy, st->logo_gc, lx, ly);
959 XCopyPlane (st->dpy, st->logo_map, st->window, st->logo_gc,
960 0, 0, w, h, lx, ly, 1);
962 XCopyArea (st->dpy, st->logo_map, st->window, st->logo_gc,
965 draw_solid_square (st, st->start_x, st->start_y, WALL_TOP >> st->start_dir, st->tgc);
966 draw_solid_square (st, st->end_x, st->end_y, WALL_TOP >> st->end_dir, st->tgc);
970 /* Mark the maze grid as having a wall at the given coordinate,
971 and draw that wall on the screen. */
973 build_wall(struct state *st, int i, int j, int dir)
975 /* Draw it on the screen. */
976 draw_wall(st, i, j, dir, st->gc);
977 /* Put it in the maze. */
981 st->maze[i][j] |= WALL_TOP;
983 st->maze[i][j-1] |= WALL_BOTTOM;
986 st->maze[i][j] |= WALL_RIGHT;
987 if(i<st->maze_size_x-1)
988 st->maze[i+1][j] |= WALL_LEFT;
991 st->maze[i][j] |= WALL_BOTTOM;
992 if(j<st->maze_size_y-1)
993 st->maze[i][j+1] |= WALL_TOP;
996 st->maze[i][j] |= WALL_LEFT;
998 st->maze[i-1][j] |= WALL_RIGHT;
1005 draw_wall(struct state *st, int i, int j, int dir, GC with_gc) /* draw a single wall */
1009 XDrawLine(st->dpy, st->window, with_gc,
1010 border_x + st->grid_width * i,
1011 border_y + st->grid_height * j,
1012 border_x + st->grid_width * (i+1),
1013 border_y + st->grid_height * j);
1016 XDrawLine(st->dpy, st->window, with_gc,
1017 border_x + st->grid_width * (i+1),
1018 border_y + st->grid_height * j,
1019 border_x + st->grid_width * (i+1),
1020 border_y + st->grid_height * (j+1));
1023 XDrawLine(st->dpy, st->window, with_gc,
1024 border_x + st->grid_width * i,
1025 border_y + st->grid_height * (j+1),
1026 border_x + st->grid_width * (i+1),
1027 border_y + st->grid_height * (j+1));
1030 XDrawLine(st->dpy, st->window, with_gc,
1031 border_x + st->grid_width * i,
1032 border_y + st->grid_height * j,
1033 border_x + st->grid_width * i,
1034 border_y + st->grid_height * (j+1));
1039 /* too slow if we sync on every wall, so only sync about ten times
1040 during the maze-creation process.
1043 if (st->sync_tick <= 0) {
1044 XSync(st->dpy, False);
1045 st->sync_tick = st->maze_size_x * st->maze_size_x / 10;
1052 draw_solid_square(struct state *st,
1054 int dir, GC with_gc)
1058 XFillRectangle(st->dpy, st->window, with_gc,
1059 border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1060 border_y - st->bw-(st->bw==0?1:0) + st->grid_height * j,
1061 st->grid_width - (st->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
1064 XFillRectangle(st->dpy, st->window, with_gc,
1065 border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1066 border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1067 st->grid_width, st->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
1070 XFillRectangle(st->dpy, st->window, with_gc,
1071 border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1072 border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1073 st->grid_width - (st->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
1076 XFillRectangle(st->dpy, st->window, with_gc,
1077 border_x - st->bw-(st->bw==0?1:0) + st->grid_width * i,
1078 border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1079 st->grid_width, st->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
1084 /****************************************************************************
1086 ****************************************************************************/
1089 longdeadend_p(struct state *st, int x1, int y1, int x2, int y2, int endwall)
1091 int dx = x2 - x1, dy = y2 - y1;
1094 sidewalls = endwall | (endwall >> 2 | endwall << 2);
1095 sidewalls = ~sidewalls & WALL_ANY;
1097 while((st->maze[x2][y2] & WALL_ANY) == sidewalls)
1099 if (x2 + dx < 0 || x2 + dx >= st->maze_size_x ||
1100 y2 + dy < 0 || y2 + dy >= st->maze_size_y)
1106 if((st->maze[x2][y2] & WALL_ANY) == (sidewalls | endwall))
1108 endwall = (endwall >> 2 | endwall << 2) & WALL_ANY;
1109 while(x1 != x2 || y1 != y2)
1113 draw_solid_square(st, x1, y1, endwall, st->sgc);
1114 st->maze[x1][y1] |= SOLVER_VISIT;
1122 /* Find all dead regions -- areas from which the goal cannot be reached --
1123 and mark them visited. */
1125 find_dead_regions(struct state *st)
1127 int xx, yy, flipped;
1129 /* Find all not SOLVER_VISIT squares bordering NOT_DEAD squares
1130 and mark them NOT_DEAD also. Repeat until no more such squares. */
1131 st->maze[st->start_x][st->start_y] |= NOT_DEAD;
1136 for(xx = 0; xx < st->maze_size_x; xx++)
1137 for(yy = 0; yy < st->maze_size_y; yy++)
1138 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1139 && ( (xx && (st->maze[xx-1][yy] & NOT_DEAD))
1140 || (yy && (st->maze[xx][yy-1] & NOT_DEAD))))
1143 st->maze[xx][yy] |= NOT_DEAD;
1145 for(xx = st->maze_size_x-1; xx >= 0; xx--)
1146 for(yy = st->maze_size_y-1; yy >= 0; yy--)
1147 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1148 && ( (xx != st->maze_size_x-1 && (st->maze[xx+1][yy] & NOT_DEAD))
1149 || (yy != st->maze_size_y-1 && (st->maze[xx][yy+1] & NOT_DEAD))))
1152 st->maze[xx][yy] |= NOT_DEAD;
1157 for (yy = 0; yy < st->maze_size_y; yy++)
1158 for (xx = 0; xx < st->maze_size_x; xx++)
1160 if (st->maze[xx][yy] & NOT_DEAD)
1161 st->maze[xx][yy] &= ~NOT_DEAD;
1162 else if (!(st->maze[xx][yy] & SOLVER_VISIT))
1164 st->maze[xx][yy] |= SOLVER_VISIT;
1165 if((xx < st->logo_x || xx > st->logo_x + st->logo_width / st->grid_width) ||
1166 (yy < st->logo_y || yy > st->logo_y + st->logo_height / st->grid_height))
1168 /* if we are completely surrounded by walls, just draw the
1170 if ((st->maze[xx][yy] & WALL_ANY) == WALL_ANY)
1171 XFillRectangle(st->dpy, st->window, st->ugc,
1172 border_x + st->bw + st->grid_width * xx,
1173 border_y + st->bw + st->grid_height * yy,
1174 st->grid_width - (st->bw+st->bw), st->grid_height - (st->bw+st->bw));
1177 if (! (st->maze[xx][yy] & WALL_LEFT))
1178 draw_solid_square(st, xx, yy, WALL_LEFT, st->ugc);
1179 if (! (st->maze[xx][yy] & WALL_RIGHT))
1180 draw_solid_square(st, xx, yy, WALL_RIGHT, st->ugc);
1181 if (! (st->maze[xx][yy] & WALL_TOP))
1182 draw_solid_square(st, xx, yy, WALL_TOP, st->ugc);
1183 if (! (st->maze[xx][yy] & WALL_BOTTOM))
1184 draw_solid_square(st, xx, yy, WALL_BOTTOM, st->ugc);
1191 /* solve the maze by one more tick */
1193 solve_maze (struct state *st)
1195 struct solve_state *ss = st->solve_state;
1197 ss = st->solve_state = (struct solve_state *) calloc (1, sizeof(*ss));
1200 /* plug up the surrounding wall */
1201 st->maze[st->end_x][st->end_y] |= (WALL_TOP >> st->end_dir);
1203 /* initialize search path */
1205 st->path[ss->i].x = st->end_x;
1206 st->path[ss->i].y = st->end_y;
1207 st->path[ss->i].dir = 0;
1208 st->maze[st->end_x][st->end_y] |= SOLVER_VISIT;
1216 int dir, from, ways;
1218 if ( st->maze[st->path[ss->i].x][st->path[ss->i].y] & START_SQUARE )
1224 if(!st->path[ss->i].dir)
1227 /* First visit this square. Which adjacent squares are open? */
1228 for(dir = WALL_TOP; dir & WALL_ANY; dir >>= 1)
1230 if(st->maze[st->path[ss->i].x][st->path[ss->i].y] & dir)
1233 ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1234 ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1236 if(st->maze[ss->x][ss->y] & SOLVER_VISIT)
1239 from = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1240 /* don't enter obvious dead ends */
1241 if(((st->maze[ss->x][ss->y] & WALL_ANY) | from) != WALL_ANY)
1243 if(!longdeadend_p(st, st->path[ss->i].x, st->path[ss->i].y, ss->x, ss->y, dir))
1248 draw_solid_square(st, ss->x, ss->y, from, st->sgc);
1249 st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1254 ways = st->path[ss->i].ways;
1255 /* ways now has a bitmask of open paths. */
1260 if (!st->ignorant_p)
1262 ss->x = st->path[ss->i].x - st->start_x;
1263 ss->y = st->path[ss->i].y - st->start_y;
1265 if(abs(ss->y) <= abs(ss->x))
1266 dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1268 dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM;
1278 dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM; break;
1281 dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1289 dir = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1304 else if(ways&WALL_LEFT)
1306 else if(ways&WALL_BOTTOM)
1308 else if(ways&WALL_RIGHT)
1314 ways &= ~dir; /* tried this one */
1316 ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1317 ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1319 /* advance in direction dir */
1320 st->path[ss->i].dir = dir;
1321 st->path[ss->i].ways = ways;
1322 draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, dir, st->tgc);
1325 st->path[ss->i].dir = 0;
1326 st->path[ss->i].ways = 0;
1327 st->path[ss->i].x = ss->x;
1328 st->path[ss->i].y = ss->y;
1329 st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1336 printf("Unsolvable maze.\n");
1341 if(!ss->bt && !st->ignorant_p)
1342 find_dead_regions(st);
1344 from = st->path[ss->i-1].dir;
1345 from = (from << 2 & WALL_ANY) | (from >> 2 & WALL_ANY);
1347 draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, from, st->cgc);
1355 /****************************************************************************
1356 XScreenSaver boilerplate: resources, command line options, and main loop.
1357 ****************************************************************************/
1359 static const char *maze_defaults[] = {
1360 ".background: black",
1361 ".foreground: white",
1368 "*solveDelay: 10000",
1369 "*preDelay: 2000000",
1370 "*postDelay: 4000000",
1372 "*liveColor: #00FF00",
1373 "*deadColor: #880000",
1374 "*skipColor: #8B5A00",
1375 "*surroundColor: #220055",
1380 static XrmOptionDescRec maze_options[] = {
1381 { "-ignorant", ".ignorant", XrmoptionNoArg, "True" },
1382 { "-no-ignorant", ".ignorant", XrmoptionNoArg, "False" },
1383 { "-grid-size", ".gridSize", XrmoptionSepArg, 0 },
1384 { "-solve-delay", ".solveDelay", XrmoptionSepArg, 0 },
1385 { "-pre-delay", ".preDelay", XrmoptionSepArg, 0 },
1386 { "-post-delay", ".postDelay", XrmoptionSepArg, 0 },
1387 { "-bg-color", ".background", XrmoptionSepArg, 0 },
1388 { "-fg-color", ".foreground", XrmoptionSepArg, 0 },
1389 { "-live-color", ".liveColor", XrmoptionSepArg, 0 },
1390 { "-dead-color", ".deadColor", XrmoptionSepArg, 0 },
1391 { "-skip-color", ".skipColor", XrmoptionSepArg, 0 },
1392 { "-surround-color", ".surroundColor",XrmoptionSepArg, 0 },
1393 { "-generator", ".generator", XrmoptionSepArg, 0 },
1394 { "-max-length", ".maxLength", XrmoptionSepArg, 0 },
1398 static int generator = 0;
1401 maze_init (Display *dpy_arg, Window window_arg)
1403 struct state *st = (struct state *) calloc (1, sizeof(*st));
1405 XWindowAttributes xgwa;
1406 unsigned long bg, fg, pfg, pbg, sfg, ufg;
1409 st->window = window_arg;
1418 size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1419 st->solve_delay = get_integer_resource (st->dpy, "solveDelay", "Integer");
1420 st->pre_solve_delay = get_integer_resource (st->dpy, "preDelay", "Integer");
1421 st->post_solve_delay = get_integer_resource (st->dpy, "postDelay", "Integer");
1422 generator = get_integer_resource(st->dpy, "generator", "Integer");
1423 st->max_length = get_integer_resource(st->dpy, "maxLength", "Integer");
1424 st->ignorant_p = get_boolean_resource(st->dpy, "ignorant", "Boolean");
1426 if (get_boolean_resource (st->dpy, "doFPS", "DoFPS"))
1428 /* Just guess, rather than loading and measuring the "fpsFont"... */
1429 st->fps_width = 210;
1430 st->fps_height = 62;
1433 if (!size) st->ifrandom = 1;
1435 if (size < 2) size = 7 + (random () % 30);
1436 st->grid_width = st->grid_height = size;
1437 st->bw = (size > 6 ? 3 : (size-1)/2);
1439 XGetWindowAttributes (st->dpy, st->window, &xgwa);
1444 set_maze_sizes (st, xgwa.width, xgwa.height);
1446 st->gc = XCreateGC(st->dpy, st->window, 0, 0);
1447 st->cgc = XCreateGC(st->dpy, st->window, 0, 0);
1448 st->tgc = XCreateGC(st->dpy, st->window, 0, 0);
1449 st->sgc = XCreateGC(st->dpy, st->window, 0, 0);
1450 st->ugc = XCreateGC(st->dpy, st->window, 0, 0);
1451 st->logo_gc = XCreateGC(st->dpy, st->window, 0, 0);
1452 st->erase_gc = XCreateGC(st->dpy, st->window, 0, 0);
1454 bg = get_pixel_resource (st->dpy, xgwa.colormap, "background","Background");
1455 fg = get_pixel_resource (st->dpy, xgwa.colormap, "foreground","Foreground");
1456 pfg = get_pixel_resource (st->dpy, xgwa.colormap, "liveColor", "Foreground");
1457 pbg = get_pixel_resource (st->dpy, xgwa.colormap, "deadColor", "Foreground");
1458 sfg = get_pixel_resource (st->dpy, xgwa.colormap, "skipColor", "Foreground");
1459 ufg = get_pixel_resource (st->dpy, xgwa.colormap, "surroundColor", "Foreground");
1461 XSetForeground (st->dpy, st->gc, fg);
1462 XSetBackground (st->dpy, st->gc, bg);
1463 XSetForeground (st->dpy, st->cgc, pbg);
1464 XSetBackground (st->dpy, st->cgc, bg);
1465 XSetForeground (st->dpy, st->tgc, pfg);
1466 XSetBackground (st->dpy, st->tgc, bg);
1467 XSetForeground (st->dpy, st->sgc, sfg);
1468 XSetBackground (st->dpy, st->sgc, bg);
1469 XSetForeground (st->dpy, st->ugc, ufg);
1470 XSetBackground (st->dpy, st->ugc, bg);
1471 XSetForeground (st->dpy, st->logo_gc, fg);
1472 XSetBackground (st->dpy, st->logo_gc, bg);
1473 XSetForeground (st->dpy, st->erase_gc, bg);
1474 XSetBackground (st->dpy, st->erase_gc, bg);
1477 jwxyz_XSetAntiAliasing (st->dpy, st->gc, False);
1481 Pixmap logo_mask = 0;
1482 if (xgwa.width > 900 || xgwa.height > 900)
1483 st->logo_map = image_data_to_pixmap (st->dpy, st->window,
1484 logo_180_png, sizeof(logo_180_png),
1485 &st->logo_width, &st->logo_height,
1488 st->logo_map = image_data_to_pixmap (st->dpy, st->window,
1489 logo_50_png, sizeof(logo_50_png),
1490 &st->logo_width, &st->logo_height,
1493 XSetClipMask (st->dpy, st->logo_gc, logo_mask);
1494 XFreePixmap (st->dpy, logo_mask);
1506 maze_reshape (Display *dpy, Window window, void *closure,
1507 unsigned int w, unsigned int h)
1509 struct state *st = (struct state *) closure;
1514 static unsigned long
1515 maze_draw (Display *dpy, Window window, void *closure)
1517 struct state *st = (struct state *) closure;
1518 int this_delay = st->solve_delay;
1520 if (st->eraser || st->erase_window)
1522 st->erase_window = 0;
1523 st->eraser = erase_window (st->dpy, st->window, st->eraser);
1527 this_delay = 1000000;
1528 if (this_delay > st->pre_solve_delay)
1529 this_delay = st->pre_solve_delay;
1534 if (st->restart || st->stop) goto pop;
1535 switch (st->state) {
1537 initialize_maze(st);
1538 if (st->ifrandom && st->ifinit)
1541 size = 7 + (random () % 30);
1542 st->grid_width = st->grid_height = size;
1543 st->bw = (size > 6 ? 3 : (size-1)/2);
1549 XClearWindow(st->dpy, st->window);
1550 draw_maze_border(st);
1553 st->this_gen = generator;
1554 if(st->this_gen<0 || st->this_gen>2)
1555 st->this_gen = random()%3;
1557 switch(st->this_gen)
1563 alt_create_maze(st);
1566 set_create_maze(st);
1571 this_delay = st->pre_solve_delay;
1574 if (! solve_maze(st))
1575 --st->state; /* stay in state 5 */
1578 st->erase_window = 1;
1579 this_delay = st->post_solve_delay;
1590 XWindowAttributes xgwa;
1597 if (st->solve_state && st->solve_state->running)
1598 st->solve_state->running = 0;
1600 st->sync_p = ((random() % 4) != 0);
1602 size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1603 if (size < 2) size = 7 + (random () % 30);
1604 st->grid_width = st->grid_height = size;
1605 st->bw = (size > 6 ? 3 : (size-1)/2);
1607 XGetWindowAttributes (st->dpy, st->window, &xgwa);
1608 set_maze_sizes (st, xgwa.width, xgwa.height);
1617 maze_event (Display *dpy, Window window, void *closure, XEvent *event)
1619 struct state *st = (struct state *) closure;
1620 if (event->type == ButtonPress)
1622 switch (event->xbutton.button)
1625 st->stop = !st->stop ;
1626 if (st->state == 5) st->state = 4 ;
1639 else if (event->type == Expose)
1644 else if (screenhack_event_helper (dpy, window, event))
1655 maze_free (Display *dpy, Window window, void *closure)
1657 struct state *st = (struct state *) closure;
1661 XSCREENSAVER_MODULE ("Maze", maze)