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"
95 /* #include <X11/bitmaps/gray1> */
98 #define gray1_height 2
99 static const char gray1_bits[] = { 0x01, 0x02 };
102 #define MAX_MAZE_SIZE_X 1000
103 #define MAX_MAZE_SIZE_Y 1000
105 #define MOVE_LIST_SIZE (MAX_MAZE_SIZE_X * MAX_MAZE_SIZE_Y)
107 #define NOT_DEAD 0x8000
108 #define SOLVER_VISIT 0x4000
109 #define START_SQUARE 0x2000
110 #define END_SQUARE 0x1000
113 #define WALL_RIGHT 0x4
114 #define WALL_BOTTOM 0x2
115 #define WALL_LEFT 0x1
118 #define DOOR_IN_TOP 0x800
119 #define DOOR_IN_RIGHT 0x400
120 #define DOOR_IN_BOTTOM 0x200
121 #define DOOR_IN_LEFT 0x100
122 #define DOOR_IN_ANY 0xF00
124 #define DOOR_OUT_TOP 0x80
125 #define DOOR_OUT_RIGHT 0x40
126 #define DOOR_OUT_BOTTOM 0x20
127 #define DOOR_OUT_LEFT 0x10
133 #define get_random(x) (random() % (x))
136 struct move_list_struct {
139 unsigned char dir, ways;
152 GC gc, cgc, tgc, sgc, ugc, logo_gc, erase_gc;
155 int logo_x, logo_y; /* in grid cells (or -1) */
156 int logo_width, logo_height; /* in pixels */
157 int fps_width, fps_height; /* in pixels */
159 int solve_delay, pre_solve_delay, post_solve_delay;
161 unsigned short maze[MAX_MAZE_SIZE_X][MAX_MAZE_SIZE_Y];
163 struct move_list_struct move_list[MOVE_LIST_SIZE];
164 struct move_list_struct save_path[MOVE_LIST_SIZE];
165 struct move_list_struct path[MOVE_LIST_SIZE];
167 int maze_size_x, maze_size_y;
168 int sqnum, cur_sq_x, cur_sq_y, path_length;
169 int start_x, start_y, start_dir, end_x, end_y, end_dir;
170 int grid_width, grid_height;
173 int x, y, restart, stop, state, max_length;
174 int sync_p, sync_tick;
177 struct solve_state *solve_state;
179 int *sets; /* The sets that our squares are in. */
180 int *hedges; /* The `list' of hedges. */
184 eraser_state *eraser;
192 static void draw_wall (struct state *, int, int, int, GC);
193 static void draw_solid_square (struct state *, int, int, int, GC);
194 static void build_wall (struct state *, int, int, int);
198 set_maze_sizes (struct state *st, int width, int height)
200 st->maze_size_x = width / st->grid_width;
201 st->maze_size_y = height / st->grid_height;
203 if (st->maze_size_x < 4) st->maze_size_x = 4;
204 if (st->maze_size_y < 4) st->maze_size_y = 4;
208 /* Resets the maze grid, picks the starting and ending points,
209 and the position of the logo, if any.
212 initialize_maze (struct state *st)
216 int logow = 1 + st->logo_width / st->grid_width;
217 int logoh = 1 + st->logo_height / st->grid_height;
221 /* This can happen if the window is really small. Let's not sweat it. */
222 if (++retry_count > 100) return;
225 /* initialize all squares */
226 for ( i=0; i<st->maze_size_x; i++) {
227 for ( j=0; j<st->maze_size_y; j++) {
233 for ( i=0; i<st->maze_size_x; i++ ) {
234 st->maze[i][0] |= WALL_TOP;
238 for ( j=0; j<st->maze_size_y; j++ ) {
239 st->maze[st->maze_size_x-1][j] |= WALL_RIGHT;
243 for ( i=0; i<st->maze_size_x; i++ ) {
244 st->maze[i][st->maze_size_y-1] |= WALL_BOTTOM;
248 for ( j=0; j<st->maze_size_y; j++ ) {
249 st->maze[0][j] |= WALL_LEFT;
252 /* set start square */
253 wall = get_random(4);
256 i = get_random(st->maze_size_x);
260 i = st->maze_size_x - 1;
261 j = get_random(st->maze_size_y);
264 i = get_random(st->maze_size_x);
265 j = st->maze_size_y - 1;
269 j = get_random(st->maze_size_y);
272 st->maze[i][j] |= START_SQUARE;
273 st->maze[i][j] |= ( DOOR_IN_TOP >> wall );
274 st->maze[i][j] &= ~( WALL_TOP >> wall );
279 st->start_dir = wall;
286 i = get_random(st->maze_size_x);
290 i = st->maze_size_x - 1;
291 j = get_random(st->maze_size_y);
294 i = get_random(st->maze_size_x);
295 j = st->maze_size_y - 1;
299 j = get_random(st->maze_size_y);
302 st->maze[i][j] |= END_SQUARE;
303 st->maze[i][j] |= ( DOOR_OUT_TOP >> wall );
304 st->maze[i][j] &= ~( WALL_TOP >> wall );
310 if ((st->maze_size_x-logow >= 6) && (st->maze_size_y-logoh >= 6))
312 /* not closer than 3 grid units from a wall, to ensure that it
313 won't overlap the entrance or exit. */
314 st->logo_x = get_random (st->maze_size_x - logow - 5) + 3;
315 st->logo_y = get_random (st->maze_size_y - logoh - 5) + 3;
316 for (i=0; i<logow; i++)
317 for (j=0; j<logoh; j++)
318 /* mark as having doors to prevent these cells being used in maze. */
319 st->maze[st->logo_x + i][st->logo_y + j] |= DOOR_IN_ANY;
322 st->logo_y = st->logo_x = -1;
324 /* mask out the fps area */
325 if (st->fps_width > 0)
327 int fpsw = 1 + st->fps_width / st->grid_width;
328 int fpsh = 1 + st->fps_height / st->grid_width;
330 /* if the chosen logo position overlapped the fps area, try again! */
331 if (st->logo_x < fpsw+3 && st->logo_y+logoh > st->maze_size_y-fpsh-4)
334 /* if the start or end point is inside the fps area, try again! */
335 if ((st->start_x <= fpsw && st->start_y >= st->maze_size_y-fpsh-1) ||
336 (st->end_x <= fpsw && st->end_y >= st->maze_size_y-fpsh-1))
339 for (i=0; i<fpsw; i++)
340 for (j=0; j<fpsh; j++) {
341 /* mark as having doors to prevent these cells being used in maze.
342 mark as visit to prevent it being colored "unreachable". */
343 st->maze[i][st->maze_size_y - j - 1] |= DOOR_IN_ANY|SOLVER_VISIT;
344 /* take off left/bottom wall or the FPS text overlaps it */
345 st->maze[i][st->maze_size_y - j - 1] &= ~(WALL_BOTTOM|WALL_LEFT);
351 /****************************************************************************
352 Generator 2: Set-based maze generator.
354 Put each square in the maze in a separate set. Also, make a list of all the
355 hedges. Randomize that list. Walk through the list. If, for a certain
356 hedge, the two squares on both sides of it are in different sets, union the
357 sets and remove the hedge. Continue until all hedges have been processed or
358 only one set remains.
360 This is essentially the "Kruskal" algorithm.
362 ****************************************************************************/
364 static void mask_out_set_rect(struct state *st, int x, int y, int w, int h);
366 /* Initialise the sets. */
368 init_sets(struct state *st)
374 st->sets = (int *)malloc(st->maze_size_x*st->maze_size_y*sizeof(int));
377 for(i = 0; i < st->maze_size_x*st->maze_size_y; i++)
384 st->hedges = (int *)malloc(st->maze_size_x*st->maze_size_y*2*sizeof(int));
387 for(i = 0; i < st->maze_size_x*st->maze_size_y*2; i++)
391 /* Mask out outside walls. */
392 for(i = 0; i < st->maze_size_y; i++)
394 st->hedges[2*((st->maze_size_x)*i+st->maze_size_x-1)+1] = -1;
396 for(i = 0; i < st->maze_size_x; i++)
398 st->hedges[2*((st->maze_size_y-1)*st->maze_size_x+i)] = -1;
401 /* Mask out the logo area. */
404 int logow = 1 + st->logo_width / st->grid_width;
405 int logoh = 1 + st->logo_height / st->grid_height;
406 mask_out_set_rect(st, st->logo_x, st->logo_y, logow, logoh);
409 /* Mask out the FPS area. */
410 if(st->fps_width > 0)
412 int fpsw = 1 + st->fps_width / st->grid_width;
413 int fpsh = 1 + st->fps_height / st->grid_height;
414 mask_out_set_rect(st, 0, st->maze_size_y-fpsh, fpsw, fpsh);
417 for(i = 0; i < st->maze_size_x*st->maze_size_y*2; i++)
420 r = random()%(st->maze_size_x*st->maze_size_y*2);
421 st->hedges[i] = st->hedges[r];
426 /* Get the representative of a set. */
428 get_set(struct state *st, int num)
432 if(st->sets[num]==num)
436 s = get_set(st, st->sets[num]);
442 /* Join two sets together. */
444 join_sets(struct state *st, int num1, int num2)
448 s1 = get_set(st, num1);
449 s2 = get_set(st, num2);
457 /* Exitialise the sets. */
459 exit_sets(struct state *st)
471 set_create_maze(struct state *st)
473 int i, h, xx, yy, dir, v, w;
475 /* Do almost all the setup. */
478 /* Start running through the hedges. */
479 for(i = 0; i < 2*st->maze_size_x*st->maze_size_y; i++)
483 /* This one is in the logo or outside border. */
488 xx = (h>>1)%st->maze_size_x;
489 yy = (h>>1)/st->maze_size_x;
503 if(get_set(st, xx+yy*st->maze_size_x)!=get_set(st, v+w*st->maze_size_x))
505 join_sets(st, xx+yy*st->maze_size_x, v+w*st->maze_size_x);
506 /* Don't draw the wall. */
510 /* Don't join the sets. */
511 build_wall(st, xx, yy, dir);
515 /* Free some memory. */
519 /* mark a rectangle as being unavailable for usage in the maze */
521 mask_out_set_rect(struct state *st, int x, int y, int w, int h)
524 for(xx = x; xx < x+w; xx++)
525 for(yy = y; yy < y+h; yy++)
527 st->hedges[2*(xx+st->maze_size_x*yy)+1] = -1;
528 st->hedges[2*(xx+st->maze_size_x*yy)] = -1;
530 for(xx = x; xx < x+w; xx++)
532 build_wall(st, xx, y, 0);
533 build_wall(st, xx, y+h, 0);
534 st->hedges[2*(xx+st->maze_size_x*(y-1))] = -1;
536 for(yy = y; yy < y+h; yy++)
538 build_wall(st, x, yy, 3);
539 build_wall(st, x+w, yy, 3);
540 st->hedges[2*(x-1+st->maze_size_x*yy)+1] = -1;
545 /****************************************************************************
546 Generator 1: Wall-building maze generator.
548 Pick a random, empty corner in the maze. Pick a random direction. Draw a
549 wall in that direction, from that corner until we hit a wall. Option: Only
550 draw the wall if it's going to be shorter than a certain length. Otherwise
551 we get lots of long walls.
553 This is essentially the "Prim" algorithm.
554 ****************************************************************************/
556 static void alt_mask_out_rect(struct state *st, char *corners,
557 int x, int y, int w, int h);
560 alt_create_maze(struct state *st)
564 int i, j, height, width, open_corners, k, dir, xx, yy;
566 height = st->maze_size_y+1;
567 width = st->maze_size_x+1;
569 /* Allocate and clear some mem. */
570 corners = (char *)calloc(height*width, 1);
574 /* Set up the indexing array. */
575 c_idx = (int *)malloc(sizeof(int)*height*width);
581 for(i = 0; i < height*width; i++)
583 for(i = 0; i < height*width; i++)
586 k = random()%(height*width);
591 /* Set up some initial walls. */
593 for(i = 0; i < width; i++)
596 corners[i+width*(height-1)] = 1;
598 for(i = 0; i < height; i++)
600 corners[i*width] = 1;
601 corners[i*width+width-1] = 1;
604 /* mask out the logo area */
607 int logow = 1 + st->logo_width / st->grid_width;
608 int logoh = 1 + st->logo_height / st->grid_height;
609 alt_mask_out_rect (st, corners, st->logo_x, st->logo_y, logow, logoh);
612 /* mask out the FPS area */
615 int fpsw = 1 + st->fps_width / st->grid_width;
616 int fpsh = 1 + st->fps_height / st->grid_height;
617 alt_mask_out_rect (st, corners, 0, st->maze_size_y-fpsh, fpsw, fpsh);
620 /* Count open gridpoints. */
622 for(i = 0; i < width; i++)
623 for(j = 0; j < height; j++)
624 if(!corners[i+width*j])
627 /* Now do actual maze generation. */
628 while(open_corners>0)
630 for(i = 0; i < width*height; i++)
632 if(!corners[c_idx[i]])
636 /* Choose a random direction. */
640 /* Measure the length of the wall we'd draw. */
641 while(!corners[xx+width*yy])
661 if(k<=st->max_length)
666 /* Draw a wall until we hit something. */
667 while(!corners[xx+width*yy])
670 corners[xx+width*yy] = 1;
674 build_wall(st, xx-1, yy-1, 1);
678 build_wall(st, xx, yy, 0);
682 build_wall(st, xx, yy, 3);
686 build_wall(st, xx-1, yy-1, 2);
696 /* Free some memory we used. */
702 /* mark a rectangle as being unavailable for usage in the maze */
704 alt_mask_out_rect(struct state *st, char *corners, int x, int y, int w, int h)
707 int mazew = st->maze_size_x+1;
709 for(i = x; i <= x+w; i++)
710 for(j = y; j <= y+h; j++)
711 corners[i+mazew*j] = 1;
713 for(xx = x; xx < x+w; xx++)
715 build_wall(st, xx, y, 0);
716 if (y+h < st->maze_size_y)
717 build_wall(st, xx, y+h, 0);
719 for(yy = y; yy < y+h; yy++)
722 build_wall(st, x, yy, 3);
723 build_wall(st, x+w, yy, 3);
728 /****************************************************************************
729 Generator 0: The original maze generator.
731 Start somewhere. Take a step in a random direction. Keep doing this until
732 we hit a wall. Then, backtrack until we find a point where we can go in
735 This is essentially the "depth-first recursive backtracker" algorithm.
736 ****************************************************************************/
738 static int choose_door (struct state *st);
739 static int backup (struct state *st);
742 create_maze (struct state *st) /* create a maze layout given the initialized maze */
747 st->move_list[st->sqnum].x = st->cur_sq_x;
748 st->move_list[st->sqnum].y = st->cur_sq_y;
749 st->move_list[st->sqnum].dir = newdoor;
750 while ( ( newdoor = choose_door(st) ) == -1 ) { /* pick a door */
751 if ( backup(st) == -1 ) { /* no more doors ... backup */
752 return; /* done ... return */
756 /* mark the out door */
757 st->maze[st->cur_sq_x][st->cur_sq_y] |= ( DOOR_OUT_TOP >> newdoor );
760 case 0: st->cur_sq_y--;
762 case 1: st->cur_sq_x++;
764 case 2: st->cur_sq_y++;
766 case 3: st->cur_sq_x--;
771 /* mark the in door */
772 st->maze[st->cur_sq_x][st->cur_sq_y] |= ( DOOR_IN_TOP >> ((newdoor+2)%4) );
774 /* if end square set path length and save path */
775 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & END_SQUARE ) {
776 st->path_length = st->sqnum;
777 for ( i=0; i<st->path_length; i++) {
778 st->save_path[i].x = st->move_list[i].x;
779 st->save_path[i].y = st->move_list[i].y;
780 st->save_path[i].dir = st->move_list[i].dir;
790 choose_door (struct state *st) /* pick a new path */
798 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_TOP )
800 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_TOP )
802 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_TOP )
804 if ( st->maze[st->cur_sq_x][st->cur_sq_y - 1] & DOOR_IN_ANY ) {
805 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_TOP;
806 st->maze[st->cur_sq_x][st->cur_sq_y - 1] |= WALL_BOTTOM;
807 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 0, st->gc);
810 candidates[num_candidates++] = 0;
814 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_RIGHT )
816 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_RIGHT )
818 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_RIGHT )
820 if ( st->maze[st->cur_sq_x + 1][st->cur_sq_y] & DOOR_IN_ANY ) {
821 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_RIGHT;
822 st->maze[st->cur_sq_x + 1][st->cur_sq_y] |= WALL_LEFT;
823 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 1, st->gc);
826 candidates[num_candidates++] = 1;
830 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_BOTTOM )
832 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_BOTTOM )
834 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_BOTTOM )
836 if ( st->maze[st->cur_sq_x][st->cur_sq_y + 1] & DOOR_IN_ANY ) {
837 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_BOTTOM;
838 st->maze[st->cur_sq_x][st->cur_sq_y + 1] |= WALL_TOP;
839 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 2, st->gc);
842 candidates[num_candidates++] = 2;
846 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_LEFT )
848 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_LEFT )
850 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_LEFT )
852 if ( st->maze[st->cur_sq_x - 1][st->cur_sq_y] & DOOR_IN_ANY ) {
853 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_LEFT;
854 st->maze[st->cur_sq_x - 1][st->cur_sq_y] |= WALL_RIGHT;
855 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 3, st->gc);
858 candidates[num_candidates++] = 3;
861 if (num_candidates == 0)
863 if (num_candidates == 1)
864 return ( candidates[0] );
865 return ( candidates[ get_random(num_candidates) ] );
871 backup (struct state *st) /* back up a move */
874 st->cur_sq_x = st->move_list[st->sqnum].x;
875 st->cur_sq_y = st->move_list[st->sqnum].y;
876 return ( st->sqnum );
880 /****************************************************************************
882 ****************************************************************************/
884 /* draws the maze outline, and the logo */
886 draw_maze_border (struct state *st)
890 for ( i=0; i<st->maze_size_x; i++) {
891 if ( st->maze[i][0] & WALL_TOP ) {
892 XDrawLine(st->dpy, st->window, st->gc,
893 border_x + st->grid_width * i,
895 border_x + st->grid_width * (i+1) - 1,
898 if ((st->maze[i][st->maze_size_y - 1] & WALL_BOTTOM)) {
899 XDrawLine(st->dpy, st->window, st->gc,
900 border_x + st->grid_width * i,
901 border_y + st->grid_height * (st->maze_size_y) - 1,
902 border_x + st->grid_width * (i+1) - 1,
903 border_y + st->grid_height * (st->maze_size_y) - 1);
906 for ( j=0; j<st->maze_size_y; j++) {
907 if ( st->maze[st->maze_size_x - 1][j] & WALL_RIGHT ) {
908 XDrawLine(st->dpy, st->window, st->gc,
909 border_x + st->grid_width * st->maze_size_x - 1,
910 border_y + st->grid_height * j,
911 border_x + st->grid_width * st->maze_size_x - 1,
912 border_y + st->grid_height * (j+1) - 1);
914 if ( st->maze[0][j] & WALL_LEFT ) {
915 XDrawLine(st->dpy, st->window, st->gc,
917 border_y + st->grid_height * j,
919 border_y + st->grid_height * (j+1) - 1);
923 if (st->logo_x != -1)
927 unsigned int w, h, bbw, d;
929 /* round up to grid size */
930 int ww = ((st->logo_width / st->grid_width) + 1) * st->grid_width;
931 int hh = ((st->logo_height / st->grid_height) + 1) * st->grid_height;
934 XGetGeometry (st->dpy, st->logo_map, &r, &xx, &yy, &w, &h, &bbw, &d);
936 /* kludge: if the logo "hole" is around the same size as the logo,
937 don't center it (since the xscreensaver logo image is a little
938 off center... But do center it if the hole/gridsize is large. */
939 if (ww < st->logo_width + 5) ww = w;
940 if (hh < st->logo_height + 5) hh = h;
943 lx = border_x + 3 + st->grid_width * st->logo_x + ((ww - w) / 2);
944 ly = border_y + 3 + st->grid_height * st->logo_y + ((hh - h) / 2);
946 /* Fill the background of the logo box with the "unreachable" color */
947 XFillRectangle (st->dpy, st->window, st->ugc,
948 border_x + 3 + st->grid_width * st->logo_x,
949 border_y + 3 + st->grid_height * st->logo_y,
952 XSetClipOrigin (st->dpy, st->logo_gc, lx, ly);
954 XCopyPlane (st->dpy, st->logo_map, st->window, st->logo_gc,
955 0, 0, w, h, lx, ly, 1);
957 XCopyArea (st->dpy, st->logo_map, st->window, st->logo_gc,
960 draw_solid_square (st, st->start_x, st->start_y, WALL_TOP >> st->start_dir, st->tgc);
961 draw_solid_square (st, st->end_x, st->end_y, WALL_TOP >> st->end_dir, st->tgc);
965 /* Mark the maze grid as having a wall at the given coordinate,
966 and draw that wall on the screen. */
968 build_wall(struct state *st, int i, int j, int dir)
970 /* Draw it on the screen. */
971 draw_wall(st, i, j, dir, st->gc);
972 /* Put it in the maze. */
976 st->maze[i][j] |= WALL_TOP;
978 st->maze[i][j-1] |= WALL_BOTTOM;
981 st->maze[i][j] |= WALL_RIGHT;
982 if(i<st->maze_size_x-1)
983 st->maze[i+1][j] |= WALL_LEFT;
986 st->maze[i][j] |= WALL_BOTTOM;
987 if(j<st->maze_size_y-1)
988 st->maze[i][j+1] |= WALL_TOP;
991 st->maze[i][j] |= WALL_LEFT;
993 st->maze[i-1][j] |= WALL_RIGHT;
1000 draw_wall(struct state *st, int i, int j, int dir, GC with_gc) /* draw a single wall */
1004 XDrawLine(st->dpy, st->window, with_gc,
1005 border_x + st->grid_width * i,
1006 border_y + st->grid_height * j,
1007 border_x + st->grid_width * (i+1),
1008 border_y + st->grid_height * j);
1011 XDrawLine(st->dpy, st->window, with_gc,
1012 border_x + st->grid_width * (i+1),
1013 border_y + st->grid_height * j,
1014 border_x + st->grid_width * (i+1),
1015 border_y + st->grid_height * (j+1));
1018 XDrawLine(st->dpy, st->window, with_gc,
1019 border_x + st->grid_width * i,
1020 border_y + st->grid_height * (j+1),
1021 border_x + st->grid_width * (i+1),
1022 border_y + st->grid_height * (j+1));
1025 XDrawLine(st->dpy, st->window, with_gc,
1026 border_x + st->grid_width * i,
1027 border_y + st->grid_height * j,
1028 border_x + st->grid_width * i,
1029 border_y + st->grid_height * (j+1));
1034 /* too slow if we sync on every wall, so only sync about ten times
1035 during the maze-creation process.
1038 if (st->sync_tick <= 0) {
1039 XSync(st->dpy, False);
1040 st->sync_tick = st->maze_size_x * st->maze_size_x / 10;
1047 draw_solid_square(struct state *st,
1049 int dir, GC with_gc)
1053 XFillRectangle(st->dpy, st->window, with_gc,
1054 border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1055 border_y - st->bw-(st->bw==0?1:0) + st->grid_height * j,
1056 st->grid_width - (st->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
1059 XFillRectangle(st->dpy, st->window, with_gc,
1060 border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1061 border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1062 st->grid_width, st->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
1065 XFillRectangle(st->dpy, st->window, with_gc,
1066 border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1067 border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1068 st->grid_width - (st->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
1071 XFillRectangle(st->dpy, st->window, with_gc,
1072 border_x - st->bw-(st->bw==0?1:0) + st->grid_width * i,
1073 border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1074 st->grid_width, st->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
1079 /****************************************************************************
1081 ****************************************************************************/
1084 longdeadend_p(struct state *st, int x1, int y1, int x2, int y2, int endwall)
1086 int dx = x2 - x1, dy = y2 - y1;
1089 sidewalls = endwall | (endwall >> 2 | endwall << 2);
1090 sidewalls = ~sidewalls & WALL_ANY;
1092 while((st->maze[x2][y2] & WALL_ANY) == sidewalls)
1094 if (x2 + dx < 0 || x2 + dx >= st->maze_size_x ||
1095 y2 + dy < 0 || y2 + dy >= st->maze_size_y)
1101 if((st->maze[x2][y2] & WALL_ANY) == (sidewalls | endwall))
1103 endwall = (endwall >> 2 | endwall << 2) & WALL_ANY;
1104 while(x1 != x2 || y1 != y2)
1108 draw_solid_square(st, x1, y1, endwall, st->sgc);
1109 st->maze[x1][y1] |= SOLVER_VISIT;
1117 /* Find all dead regions -- areas from which the goal cannot be reached --
1118 and mark them visited. */
1120 find_dead_regions(struct state *st)
1122 int xx, yy, flipped;
1124 /* Find all not SOLVER_VISIT squares bordering NOT_DEAD squares
1125 and mark them NOT_DEAD also. Repeat until no more such squares. */
1126 st->maze[st->start_x][st->start_y] |= NOT_DEAD;
1131 for(xx = 0; xx < st->maze_size_x; xx++)
1132 for(yy = 0; yy < st->maze_size_y; yy++)
1133 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1134 && ( (xx && (st->maze[xx-1][yy] & NOT_DEAD))
1135 || (yy && (st->maze[xx][yy-1] & NOT_DEAD))))
1138 st->maze[xx][yy] |= NOT_DEAD;
1140 for(xx = st->maze_size_x-1; xx >= 0; xx--)
1141 for(yy = st->maze_size_y-1; yy >= 0; yy--)
1142 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1143 && ( (xx != st->maze_size_x-1 && (st->maze[xx+1][yy] & NOT_DEAD))
1144 || (yy != st->maze_size_y-1 && (st->maze[xx][yy+1] & NOT_DEAD))))
1147 st->maze[xx][yy] |= NOT_DEAD;
1152 for (yy = 0; yy < st->maze_size_y; yy++)
1153 for (xx = 0; xx < st->maze_size_x; xx++)
1155 if (st->maze[xx][yy] & NOT_DEAD)
1156 st->maze[xx][yy] &= ~NOT_DEAD;
1157 else if (!(st->maze[xx][yy] & SOLVER_VISIT))
1159 st->maze[xx][yy] |= SOLVER_VISIT;
1160 if((xx < st->logo_x || xx > st->logo_x + st->logo_width / st->grid_width) ||
1161 (yy < st->logo_y || yy > st->logo_y + st->logo_height / st->grid_height))
1163 /* if we are completely surrounded by walls, just draw the
1165 if ((st->maze[xx][yy] & WALL_ANY) == WALL_ANY)
1166 XFillRectangle(st->dpy, st->window, st->ugc,
1167 border_x + st->bw + st->grid_width * xx,
1168 border_y + st->bw + st->grid_height * yy,
1169 st->grid_width - (st->bw+st->bw), st->grid_height - (st->bw+st->bw));
1172 if (! (st->maze[xx][yy] & WALL_LEFT))
1173 draw_solid_square(st, xx, yy, WALL_LEFT, st->ugc);
1174 if (! (st->maze[xx][yy] & WALL_RIGHT))
1175 draw_solid_square(st, xx, yy, WALL_RIGHT, st->ugc);
1176 if (! (st->maze[xx][yy] & WALL_TOP))
1177 draw_solid_square(st, xx, yy, WALL_TOP, st->ugc);
1178 if (! (st->maze[xx][yy] & WALL_BOTTOM))
1179 draw_solid_square(st, xx, yy, WALL_BOTTOM, st->ugc);
1186 /* solve the maze by one more tick */
1188 solve_maze (struct state *st)
1190 struct solve_state *ss = st->solve_state;
1192 ss = st->solve_state = (struct solve_state *) calloc (1, sizeof(*ss));
1195 /* plug up the surrounding wall */
1196 st->maze[st->end_x][st->end_y] |= (WALL_TOP >> st->end_dir);
1198 /* initialize search path */
1200 st->path[ss->i].x = st->end_x;
1201 st->path[ss->i].y = st->end_y;
1202 st->path[ss->i].dir = 0;
1203 st->maze[st->end_x][st->end_y] |= SOLVER_VISIT;
1211 int dir, from, ways;
1213 if ( st->maze[st->path[ss->i].x][st->path[ss->i].y] & START_SQUARE )
1219 if(!st->path[ss->i].dir)
1222 /* First visit this square. Which adjacent squares are open? */
1223 for(dir = WALL_TOP; dir & WALL_ANY; dir >>= 1)
1225 if(st->maze[st->path[ss->i].x][st->path[ss->i].y] & dir)
1228 ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1229 ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1231 if(st->maze[ss->x][ss->y] & SOLVER_VISIT)
1234 from = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1235 /* don't enter obvious dead ends */
1236 if(((st->maze[ss->x][ss->y] & WALL_ANY) | from) != WALL_ANY)
1238 if(!longdeadend_p(st, st->path[ss->i].x, st->path[ss->i].y, ss->x, ss->y, dir))
1243 draw_solid_square(st, ss->x, ss->y, from, st->sgc);
1244 st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1249 ways = st->path[ss->i].ways;
1250 /* ways now has a bitmask of open paths. */
1255 if (!st->ignorant_p)
1257 ss->x = st->path[ss->i].x - st->start_x;
1258 ss->y = st->path[ss->i].y - st->start_y;
1260 if(abs(ss->y) <= abs(ss->x))
1261 dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1263 dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM;
1273 dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM; break;
1276 dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1284 dir = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1299 else if(ways&WALL_LEFT)
1301 else if(ways&WALL_BOTTOM)
1303 else if(ways&WALL_RIGHT)
1309 ways &= ~dir; /* tried this one */
1311 ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1312 ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1314 /* advance in direction dir */
1315 st->path[ss->i].dir = dir;
1316 st->path[ss->i].ways = ways;
1317 draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, dir, st->tgc);
1320 st->path[ss->i].dir = 0;
1321 st->path[ss->i].ways = 0;
1322 st->path[ss->i].x = ss->x;
1323 st->path[ss->i].y = ss->y;
1324 st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1331 printf("Unsolvable maze.\n");
1336 if(!ss->bt && !st->ignorant_p)
1337 find_dead_regions(st);
1339 from = st->path[ss->i-1].dir;
1340 from = (from << 2 & WALL_ANY) | (from >> 2 & WALL_ANY);
1342 draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, from, st->cgc);
1350 /****************************************************************************
1351 XScreenSaver boilerplate: resources, command line options, and main loop.
1352 ****************************************************************************/
1354 static const char *maze_defaults[] = {
1355 ".background: black",
1356 ".foreground: white",
1363 "*solveDelay: 10000",
1364 "*preDelay: 2000000",
1365 "*postDelay: 4000000",
1367 "*liveColor: #00FF00",
1368 "*deadColor: #880000",
1369 "*skipColor: #8B5A00",
1370 "*surroundColor: #220055",
1375 static XrmOptionDescRec maze_options[] = {
1376 { "-ignorant", ".ignorant", XrmoptionNoArg, "True" },
1377 { "-no-ignorant", ".ignorant", XrmoptionNoArg, "False" },
1378 { "-grid-size", ".gridSize", XrmoptionSepArg, 0 },
1379 { "-solve-delay", ".solveDelay", XrmoptionSepArg, 0 },
1380 { "-pre-delay", ".preDelay", XrmoptionSepArg, 0 },
1381 { "-post-delay", ".postDelay", XrmoptionSepArg, 0 },
1382 { "-bg-color", ".background", XrmoptionSepArg, 0 },
1383 { "-fg-color", ".foreground", XrmoptionSepArg, 0 },
1384 { "-live-color", ".liveColor", XrmoptionSepArg, 0 },
1385 { "-dead-color", ".deadColor", XrmoptionSepArg, 0 },
1386 { "-skip-color", ".skipColor", XrmoptionSepArg, 0 },
1387 { "-surround-color", ".surroundColor",XrmoptionSepArg, 0 },
1388 { "-generator", ".generator", XrmoptionSepArg, 0 },
1389 { "-max-length", ".maxLength", XrmoptionSepArg, 0 },
1393 static int generator = 0;
1396 maze_init (Display *dpy_arg, Window window_arg)
1398 struct state *st = (struct state *) calloc (1, sizeof(*st));
1400 XWindowAttributes xgwa;
1401 unsigned long bg, fg, pfg, pbg, sfg, ufg;
1404 st->window = window_arg;
1413 size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1414 st->solve_delay = get_integer_resource (st->dpy, "solveDelay", "Integer");
1415 st->pre_solve_delay = get_integer_resource (st->dpy, "preDelay", "Integer");
1416 st->post_solve_delay = get_integer_resource (st->dpy, "postDelay", "Integer");
1417 generator = get_integer_resource(st->dpy, "generator", "Integer");
1418 st->max_length = get_integer_resource(st->dpy, "maxLength", "Integer");
1419 st->ignorant_p = get_boolean_resource(st->dpy, "ignorant", "Boolean");
1421 if (get_boolean_resource (st->dpy, "doFPS", "DoFPS"))
1423 /* Just guess, rather than loading and measuring the "fpsFont"... */
1424 st->fps_width = 210;
1425 st->fps_height = 62;
1428 if (!size) st->ifrandom = 1;
1430 if (size < 2) size = 7 + (random () % 30);
1431 st->grid_width = st->grid_height = size;
1432 st->bw = (size > 6 ? 3 : (size-1)/2);
1434 XGetWindowAttributes (st->dpy, st->window, &xgwa);
1439 set_maze_sizes (st, xgwa.width, xgwa.height);
1441 st->gc = XCreateGC(st->dpy, st->window, 0, 0);
1442 st->cgc = XCreateGC(st->dpy, st->window, 0, 0);
1443 st->tgc = XCreateGC(st->dpy, st->window, 0, 0);
1444 st->sgc = XCreateGC(st->dpy, st->window, 0, 0);
1445 st->ugc = XCreateGC(st->dpy, st->window, 0, 0);
1446 st->logo_gc = XCreateGC(st->dpy, st->window, 0, 0);
1447 st->erase_gc = XCreateGC(st->dpy, st->window, 0, 0);
1449 bg = get_pixel_resource (st->dpy, xgwa.colormap, "background","Background");
1450 fg = get_pixel_resource (st->dpy, xgwa.colormap, "foreground","Foreground");
1451 pfg = get_pixel_resource (st->dpy, xgwa.colormap, "liveColor", "Foreground");
1452 pbg = get_pixel_resource (st->dpy, xgwa.colormap, "deadColor", "Foreground");
1453 sfg = get_pixel_resource (st->dpy, xgwa.colormap, "skipColor", "Foreground");
1454 ufg = get_pixel_resource (st->dpy, xgwa.colormap, "surroundColor", "Foreground");
1456 XSetForeground (st->dpy, st->gc, fg);
1457 XSetBackground (st->dpy, st->gc, bg);
1458 XSetForeground (st->dpy, st->cgc, pbg);
1459 XSetBackground (st->dpy, st->cgc, bg);
1460 XSetForeground (st->dpy, st->tgc, pfg);
1461 XSetBackground (st->dpy, st->tgc, bg);
1462 XSetForeground (st->dpy, st->sgc, sfg);
1463 XSetBackground (st->dpy, st->sgc, bg);
1464 XSetForeground (st->dpy, st->ugc, ufg);
1465 XSetBackground (st->dpy, st->ugc, bg);
1466 XSetForeground (st->dpy, st->logo_gc, fg);
1467 XSetBackground (st->dpy, st->logo_gc, bg);
1468 XSetForeground (st->dpy, st->erase_gc, bg);
1469 XSetBackground (st->dpy, st->erase_gc, bg);
1474 unsigned int w, h, bbw, d;
1475 unsigned long *pixels;
1477 Pixmap logo_mask = 0;
1478 st->logo_map = xscreensaver_logo (xgwa.screen, xgwa.visual, st->window,
1480 &pixels, &npixels, &logo_mask,
1481 xgwa.width > 800 || xgwa.height > 800);
1483 XSetClipMask (st->dpy, st->logo_gc, logo_mask);
1484 XFreePixmap (st->dpy, logo_mask);
1486 if (pixels) free (pixels);
1487 XGetGeometry (st->dpy, st->logo_map, &r, &x, &y, &w, &h, &bbw, &d);
1489 st->logo_height = h;
1501 maze_reshape (Display *dpy, Window window, void *closure,
1502 unsigned int w, unsigned int h)
1504 struct state *st = (struct state *) closure;
1509 static unsigned long
1510 maze_draw (Display *dpy, Window window, void *closure)
1512 struct state *st = (struct state *) closure;
1513 int this_delay = st->solve_delay;
1515 if (st->eraser || st->erase_window)
1517 st->erase_window = 0;
1518 st->eraser = erase_window (st->dpy, st->window, st->eraser);
1522 this_delay = 1000000;
1523 if (this_delay > st->pre_solve_delay)
1524 this_delay = st->pre_solve_delay;
1529 if (st->restart || st->stop) goto pop;
1530 switch (st->state) {
1532 initialize_maze(st);
1533 if (st->ifrandom && st->ifinit)
1536 size = 7 + (random () % 30);
1537 st->grid_width = st->grid_height = size;
1538 st->bw = (size > 6 ? 3 : (size-1)/2);
1544 XClearWindow(st->dpy, st->window);
1545 draw_maze_border(st);
1548 st->this_gen = generator;
1549 if(st->this_gen<0 || st->this_gen>2)
1550 st->this_gen = random()%3;
1552 switch(st->this_gen)
1558 alt_create_maze(st);
1561 set_create_maze(st);
1566 this_delay = st->pre_solve_delay;
1569 if (! solve_maze(st))
1570 --st->state; /* stay in state 5 */
1573 st->erase_window = 1;
1574 this_delay = st->post_solve_delay;
1585 XWindowAttributes xgwa;
1592 if (st->solve_state && st->solve_state->running)
1593 st->solve_state->running = 0;
1595 st->sync_p = ((random() % 4) != 0);
1597 size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1598 if (size < 2) size = 7 + (random () % 30);
1599 st->grid_width = st->grid_height = size;
1600 st->bw = (size > 6 ? 3 : (size-1)/2);
1602 XGetWindowAttributes (st->dpy, st->window, &xgwa);
1603 set_maze_sizes (st, xgwa.width, xgwa.height);
1612 maze_event (Display *dpy, Window window, void *closure, XEvent *event)
1614 struct state *st = (struct state *) closure;
1615 switch (event->type)
1618 switch (event->xbutton.button)
1621 st->stop = !st->stop ;
1622 if (st->state == 5) st->state = 4 ;
1648 maze_free (Display *dpy, Window window, void *closure)
1650 struct state *st = (struct state *) closure;
1654 XSCREENSAVER_MODULE ("Maze", maze)