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> */
97 #define gray1_height 2
98 static const char gray1_bits[] = { 0x01, 0x02 };
101 #define MAX_MAZE_SIZE_X 1000
102 #define MAX_MAZE_SIZE_Y 1000
104 #define MOVE_LIST_SIZE (MAX_MAZE_SIZE_X * MAX_MAZE_SIZE_Y)
106 #define NOT_DEAD 0x8000
107 #define SOLVER_VISIT 0x4000
108 #define START_SQUARE 0x2000
109 #define END_SQUARE 0x1000
112 #define WALL_RIGHT 0x4
113 #define WALL_BOTTOM 0x2
114 #define WALL_LEFT 0x1
117 #define DOOR_IN_TOP 0x800
118 #define DOOR_IN_RIGHT 0x400
119 #define DOOR_IN_BOTTOM 0x200
120 #define DOOR_IN_LEFT 0x100
121 #define DOOR_IN_ANY 0xF00
123 #define DOOR_OUT_TOP 0x80
124 #define DOOR_OUT_RIGHT 0x40
125 #define DOOR_OUT_BOTTOM 0x20
126 #define DOOR_OUT_LEFT 0x10
132 #define get_random(x) (random() % (x))
135 struct move_list_struct {
138 unsigned char dir, ways;
151 GC gc, cgc, tgc, sgc, ugc, logo_gc, erase_gc;
154 int logo_x, logo_y; /* in grid cells (or -1) */
155 int logo_width, logo_height; /* in pixels */
156 int fps_width, fps_height; /* in pixels */
158 int solve_delay, pre_solve_delay, post_solve_delay;
160 unsigned short maze[MAX_MAZE_SIZE_X][MAX_MAZE_SIZE_Y];
162 struct move_list_struct move_list[MOVE_LIST_SIZE];
163 struct move_list_struct save_path[MOVE_LIST_SIZE];
164 struct move_list_struct path[MOVE_LIST_SIZE];
166 int maze_size_x, maze_size_y;
167 int sqnum, cur_sq_x, cur_sq_y, path_length;
168 int start_x, start_y, start_dir, end_x, end_y, end_dir;
169 int grid_width, grid_height;
172 int x, y, restart, stop, state, max_length;
173 int sync_p, sync_tick;
176 struct solve_state *solve_state;
178 int *sets; /* The sets that our squares are in. */
179 int *hedges; /* The `list' of hedges. */
183 eraser_state *eraser;
191 static void draw_wall (struct state *, int, int, int, GC);
192 static void draw_solid_square (struct state *, int, int, int, GC);
193 static void build_wall (struct state *, int, int, int);
197 set_maze_sizes (struct state *st, int width, int height)
199 st->maze_size_x = width / st->grid_width;
200 st->maze_size_y = height / st->grid_height;
202 if (st->maze_size_x < 4) st->maze_size_x = 4;
203 if (st->maze_size_y < 4) st->maze_size_y = 4;
207 /* Resets the maze grid, picks the starting and ending points,
208 and the position of the logo, if any.
211 initialize_maze (struct state *st)
214 int logow = 1 + st->logo_width / st->grid_width;
215 int logoh = 1 + st->logo_height / st->grid_height;
219 /* initialize all squares */
220 for ( i=0; i<st->maze_size_x; i++) {
221 for ( j=0; j<st->maze_size_y; j++) {
227 for ( i=0; i<st->maze_size_x; i++ ) {
228 st->maze[i][0] |= WALL_TOP;
232 for ( j=0; j<st->maze_size_y; j++ ) {
233 st->maze[st->maze_size_x-1][j] |= WALL_RIGHT;
237 for ( i=0; i<st->maze_size_x; i++ ) {
238 st->maze[i][st->maze_size_y-1] |= WALL_BOTTOM;
242 for ( j=0; j<st->maze_size_y; j++ ) {
243 st->maze[0][j] |= WALL_LEFT;
246 /* set start square */
247 wall = get_random(4);
250 i = get_random(st->maze_size_x);
254 i = st->maze_size_x - 1;
255 j = get_random(st->maze_size_y);
258 i = get_random(st->maze_size_x);
259 j = st->maze_size_y - 1;
263 j = get_random(st->maze_size_y);
266 st->maze[i][j] |= START_SQUARE;
267 st->maze[i][j] |= ( DOOR_IN_TOP >> wall );
268 st->maze[i][j] &= ~( WALL_TOP >> wall );
273 st->start_dir = wall;
280 i = get_random(st->maze_size_x);
284 i = st->maze_size_x - 1;
285 j = get_random(st->maze_size_y);
288 i = get_random(st->maze_size_x);
289 j = st->maze_size_y - 1;
293 j = get_random(st->maze_size_y);
296 st->maze[i][j] |= END_SQUARE;
297 st->maze[i][j] |= ( DOOR_OUT_TOP >> wall );
298 st->maze[i][j] &= ~( WALL_TOP >> wall );
304 if ((st->maze_size_x-logow >= 6) && (st->maze_size_y-logoh >= 6))
306 /* not closer than 3 grid units from a wall, to ensure that it
307 won't overlap the entrance or exit. */
308 st->logo_x = get_random (st->maze_size_x - logow - 5) + 3;
309 st->logo_y = get_random (st->maze_size_y - logoh - 5) + 3;
310 for (i=0; i<logow; i++)
311 for (j=0; j<logoh; j++)
312 /* mark as having doors to prevent these cells being used in maze. */
313 st->maze[st->logo_x + i][st->logo_y + j] |= DOOR_IN_ANY;
316 st->logo_y = st->logo_x = -1;
318 /* mask out the fps area */
319 if (st->fps_width > 0)
321 int fpsw = 1 + st->fps_width / st->grid_width;
322 int fpsh = 1 + st->fps_height / st->grid_width;
324 /* if the chosen logo position overlapped the fps area, try again! */
325 if (st->logo_x < fpsw+3 && st->logo_y+logoh > st->maze_size_y-fpsh-4)
328 /* if the start or end point is inside the fps area, try again! */
329 if ((st->start_x <= fpsw && st->start_y >= st->maze_size_y-fpsh-1) ||
330 (st->end_x <= fpsw && st->end_y >= st->maze_size_y-fpsh-1))
333 for (i=0; i<fpsw; i++)
334 for (j=0; j<fpsh; j++) {
335 /* mark as having doors to prevent these cells being used in maze.
336 mark as visit to prevent it being colored "unreachable". */
337 st->maze[i][st->maze_size_y - j - 1] |= DOOR_IN_ANY|SOLVER_VISIT;
338 /* take off left/bottom wall or the FPS text overlaps it */
339 st->maze[i][st->maze_size_y - j - 1] &= ~(WALL_BOTTOM|WALL_LEFT);
345 /****************************************************************************
346 Generator 2: Set-based maze generator.
348 Put each square in the maze in a separate set. Also, make a list of all the
349 hedges. Randomize that list. Walk through the list. If, for a certain
350 hedge, the two squares on both sides of it are in different sets, union the
351 sets and remove the hedge. Continue until all hedges have been processed or
352 only one set remains.
354 This is essentially the "Kruskal" algorithm.
356 ****************************************************************************/
358 static void mask_out_set_rect(struct state *st, int x, int y, int w, int h);
360 /* Initialise the sets. */
362 init_sets(struct state *st)
368 st->sets = (int *)malloc(st->maze_size_x*st->maze_size_y*sizeof(int));
371 for(i = 0; i < st->maze_size_x*st->maze_size_y; i++)
378 st->hedges = (int *)malloc(st->maze_size_x*st->maze_size_y*2*sizeof(int));
381 for(i = 0; i < st->maze_size_x*st->maze_size_y*2; i++)
385 /* Mask out outside walls. */
386 for(i = 0; i < st->maze_size_y; i++)
388 st->hedges[2*((st->maze_size_x)*i+st->maze_size_x-1)+1] = -1;
390 for(i = 0; i < st->maze_size_x; i++)
392 st->hedges[2*((st->maze_size_y-1)*st->maze_size_x+i)] = -1;
395 /* Mask out the logo area. */
398 int logow = 1 + st->logo_width / st->grid_width;
399 int logoh = 1 + st->logo_height / st->grid_height;
400 mask_out_set_rect(st, st->logo_x, st->logo_y, logow, logoh);
403 /* Mask out the FPS area. */
404 if(st->fps_width > 0)
406 int fpsw = 1 + st->fps_width / st->grid_width;
407 int fpsh = 1 + st->fps_height / st->grid_height;
408 mask_out_set_rect(st, 0, st->maze_size_y-fpsh, fpsw, fpsh);
411 for(i = 0; i < st->maze_size_x*st->maze_size_y*2; i++)
414 r = random()%(st->maze_size_x*st->maze_size_y*2);
415 st->hedges[i] = st->hedges[r];
420 /* Get the representative of a set. */
422 get_set(struct state *st, int num)
426 if(st->sets[num]==num)
430 s = get_set(st, st->sets[num]);
436 /* Join two sets together. */
438 join_sets(struct state *st, int num1, int num2)
442 s1 = get_set(st, num1);
443 s2 = get_set(st, num2);
451 /* Exitialise the sets. */
453 exit_sets(struct state *st)
465 set_create_maze(struct state *st)
467 int i, h, xx, yy, dir, v, w;
469 /* Do almost all the setup. */
472 /* Start running through the hedges. */
473 for(i = 0; i < 2*st->maze_size_x*st->maze_size_y; i++)
477 /* This one is in the logo or outside border. */
482 xx = (h>>1)%st->maze_size_x;
483 yy = (h>>1)/st->maze_size_x;
497 if(get_set(st, xx+yy*st->maze_size_x)!=get_set(st, v+w*st->maze_size_x))
499 join_sets(st, xx+yy*st->maze_size_x, v+w*st->maze_size_x);
500 /* Don't draw the wall. */
504 /* Don't join the sets. */
505 build_wall(st, xx, yy, dir);
509 /* Free some memory. */
513 /* mark a rectangle as being unavailable for usage in the maze */
515 mask_out_set_rect(struct state *st, int x, int y, int w, int h)
518 for(xx = x; xx < x+w; xx++)
519 for(yy = y; yy < y+h; yy++)
521 st->hedges[2*(xx+st->maze_size_x*yy)+1] = -1;
522 st->hedges[2*(xx+st->maze_size_x*yy)] = -1;
524 for(xx = x; xx < x+w; xx++)
526 build_wall(st, xx, y, 0);
527 build_wall(st, xx, y+h, 0);
528 st->hedges[2*(xx+st->maze_size_x*(y-1))] = -1;
530 for(yy = y; yy < y+h; yy++)
532 build_wall(st, x, yy, 3);
533 build_wall(st, x+w, yy, 3);
534 st->hedges[2*(x-1+st->maze_size_x*yy)+1] = -1;
539 /****************************************************************************
540 Generator 1: Wall-building maze generator.
542 Pick a random, empty corner in the maze. Pick a random direction. Draw a
543 wall in that direction, from that corner until we hit a wall. Option: Only
544 draw the wall if it's going to be shorter than a certain length. Otherwise
545 we get lots of long walls.
547 This is essentially the "Prim" algorithm.
548 ****************************************************************************/
550 static void alt_mask_out_rect(struct state *st, char *corners,
551 int x, int y, int w, int h);
554 alt_create_maze(struct state *st)
558 int i, j, height, width, open_corners, k, dir, xx, yy;
560 height = st->maze_size_y+1;
561 width = st->maze_size_x+1;
563 /* Allocate and clear some mem. */
564 corners = (char *)calloc(height*width, 1);
568 /* Set up the indexing array. */
569 c_idx = (int *)malloc(sizeof(int)*height*width);
575 for(i = 0; i < height*width; i++)
577 for(i = 0; i < height*width; i++)
580 k = random()%(height*width);
585 /* Set up some initial walls. */
587 for(i = 0; i < width; i++)
590 corners[i+width*(height-1)] = 1;
592 for(i = 0; i < height; i++)
594 corners[i*width] = 1;
595 corners[i*width+width-1] = 1;
598 /* mask out the logo area */
601 int logow = 1 + st->logo_width / st->grid_width;
602 int logoh = 1 + st->logo_height / st->grid_height;
603 alt_mask_out_rect (st, corners, st->logo_x, st->logo_y, logow, logoh);
606 /* mask out the FPS area */
609 int fpsw = 1 + st->fps_width / st->grid_width;
610 int fpsh = 1 + st->fps_height / st->grid_height;
611 alt_mask_out_rect (st, corners, 0, st->maze_size_y-fpsh, fpsw, fpsh);
614 /* Count open gridpoints. */
616 for(i = 0; i < width; i++)
617 for(j = 0; j < height; j++)
618 if(!corners[i+width*j])
621 /* Now do actual maze generation. */
622 while(open_corners>0)
624 for(i = 0; i < width*height; i++)
626 if(!corners[c_idx[i]])
630 /* Choose a random direction. */
634 /* Measure the length of the wall we'd draw. */
635 while(!corners[xx+width*yy])
655 if(k<=st->max_length)
660 /* Draw a wall until we hit something. */
661 while(!corners[xx+width*yy])
664 corners[xx+width*yy] = 1;
668 build_wall(st, xx-1, yy-1, 1);
672 build_wall(st, xx, yy, 0);
676 build_wall(st, xx, yy, 3);
680 build_wall(st, xx-1, yy-1, 2);
690 /* Free some memory we used. */
696 /* mark a rectangle as being unavailable for usage in the maze */
698 alt_mask_out_rect(struct state *st, char *corners, int x, int y, int w, int h)
701 int mazew = st->maze_size_x+1;
703 for(i = x; i <= x+w; i++)
704 for(j = y; j <= y+h; j++)
705 corners[i+mazew*j] = 1;
707 for(xx = x; xx < x+w; xx++)
709 build_wall(st, xx, y, 0);
710 if (y+h < st->maze_size_y)
711 build_wall(st, xx, y+h, 0);
713 for(yy = y; yy < y+h; yy++)
716 build_wall(st, x, yy, 3);
717 build_wall(st, x+w, yy, 3);
722 /****************************************************************************
723 Generator 0: The original maze generator.
725 Start somewhere. Take a step in a random direction. Keep doing this until
726 we hit a wall. Then, backtrack until we find a point where we can go in
729 This is essentially the "depth-first recursive backtracker" algorithm.
730 ****************************************************************************/
732 static int choose_door (struct state *st);
733 static int backup (struct state *st);
736 create_maze (struct state *st) /* create a maze layout given the initialized maze */
741 st->move_list[st->sqnum].x = st->cur_sq_x;
742 st->move_list[st->sqnum].y = st->cur_sq_y;
743 st->move_list[st->sqnum].dir = newdoor;
744 while ( ( newdoor = choose_door(st) ) == -1 ) { /* pick a door */
745 if ( backup(st) == -1 ) { /* no more doors ... backup */
746 return; /* done ... return */
750 /* mark the out door */
751 st->maze[st->cur_sq_x][st->cur_sq_y] |= ( DOOR_OUT_TOP >> newdoor );
754 case 0: st->cur_sq_y--;
756 case 1: st->cur_sq_x++;
758 case 2: st->cur_sq_y++;
760 case 3: st->cur_sq_x--;
765 /* mark the in door */
766 st->maze[st->cur_sq_x][st->cur_sq_y] |= ( DOOR_IN_TOP >> ((newdoor+2)%4) );
768 /* if end square set path length and save path */
769 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & END_SQUARE ) {
770 st->path_length = st->sqnum;
771 for ( i=0; i<st->path_length; i++) {
772 st->save_path[i].x = st->move_list[i].x;
773 st->save_path[i].y = st->move_list[i].y;
774 st->save_path[i].dir = st->move_list[i].dir;
784 choose_door (struct state *st) /* pick a new path */
792 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_TOP )
794 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_TOP )
796 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_TOP )
798 if ( st->maze[st->cur_sq_x][st->cur_sq_y - 1] & DOOR_IN_ANY ) {
799 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_TOP;
800 st->maze[st->cur_sq_x][st->cur_sq_y - 1] |= WALL_BOTTOM;
801 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 0, st->gc);
804 candidates[num_candidates++] = 0;
808 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_RIGHT )
810 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_RIGHT )
812 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_RIGHT )
814 if ( st->maze[st->cur_sq_x + 1][st->cur_sq_y] & DOOR_IN_ANY ) {
815 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_RIGHT;
816 st->maze[st->cur_sq_x + 1][st->cur_sq_y] |= WALL_LEFT;
817 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 1, st->gc);
820 candidates[num_candidates++] = 1;
824 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_BOTTOM )
826 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_BOTTOM )
828 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_BOTTOM )
830 if ( st->maze[st->cur_sq_x][st->cur_sq_y + 1] & DOOR_IN_ANY ) {
831 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_BOTTOM;
832 st->maze[st->cur_sq_x][st->cur_sq_y + 1] |= WALL_TOP;
833 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 2, st->gc);
836 candidates[num_candidates++] = 2;
840 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_LEFT )
842 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_LEFT )
844 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_LEFT )
846 if ( st->maze[st->cur_sq_x - 1][st->cur_sq_y] & DOOR_IN_ANY ) {
847 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_LEFT;
848 st->maze[st->cur_sq_x - 1][st->cur_sq_y] |= WALL_RIGHT;
849 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 3, st->gc);
852 candidates[num_candidates++] = 3;
855 if (num_candidates == 0)
857 if (num_candidates == 1)
858 return ( candidates[0] );
859 return ( candidates[ get_random(num_candidates) ] );
865 backup (struct state *st) /* back up a move */
868 st->cur_sq_x = st->move_list[st->sqnum].x;
869 st->cur_sq_y = st->move_list[st->sqnum].y;
870 return ( st->sqnum );
874 /****************************************************************************
876 ****************************************************************************/
878 /* draws the maze outline, and the logo */
880 draw_maze_border (struct state *st)
884 for ( i=0; i<st->maze_size_x; i++) {
885 if ( st->maze[i][0] & WALL_TOP ) {
886 XDrawLine(st->dpy, st->window, st->gc,
887 border_x + st->grid_width * i,
889 border_x + st->grid_width * (i+1) - 1,
892 if ((st->maze[i][st->maze_size_y - 1] & WALL_BOTTOM)) {
893 XDrawLine(st->dpy, st->window, st->gc,
894 border_x + st->grid_width * i,
895 border_y + st->grid_height * (st->maze_size_y) - 1,
896 border_x + st->grid_width * (i+1) - 1,
897 border_y + st->grid_height * (st->maze_size_y) - 1);
900 for ( j=0; j<st->maze_size_y; j++) {
901 if ( st->maze[st->maze_size_x - 1][j] & WALL_RIGHT ) {
902 XDrawLine(st->dpy, st->window, st->gc,
903 border_x + st->grid_width * st->maze_size_x - 1,
904 border_y + st->grid_height * j,
905 border_x + st->grid_width * st->maze_size_x - 1,
906 border_y + st->grid_height * (j+1) - 1);
908 if ( st->maze[0][j] & WALL_LEFT ) {
909 XDrawLine(st->dpy, st->window, st->gc,
911 border_y + st->grid_height * j,
913 border_y + st->grid_height * (j+1) - 1);
917 if (st->logo_x != -1)
921 unsigned int w, h, bbw, d;
923 /* round up to grid size */
924 int ww = ((st->logo_width / st->grid_width) + 1) * st->grid_width;
925 int hh = ((st->logo_height / st->grid_height) + 1) * st->grid_height;
928 XGetGeometry (st->dpy, st->logo_map, &r, &xx, &yy, &w, &h, &bbw, &d);
930 /* kludge: if the logo "hole" is around the same size as the logo,
931 don't center it (since the xscreensaver logo image is a little
932 off center... But do center it if the hole/gridsize is large. */
933 if (ww < st->logo_width + 5) ww = w;
934 if (hh < st->logo_height + 5) hh = h;
937 lx = border_x + 3 + st->grid_width * st->logo_x + ((ww - w) / 2);
938 ly = border_y + 3 + st->grid_height * st->logo_y + ((hh - h) / 2);
940 /* Fill the background of the logo box with the "unreachable" color */
941 XFillRectangle (st->dpy, st->window, st->ugc,
942 border_x + 3 + st->grid_width * st->logo_x,
943 border_y + 3 + st->grid_height * st->logo_y,
946 XSetClipOrigin (st->dpy, st->logo_gc, lx, ly);
948 XCopyPlane (st->dpy, st->logo_map, st->window, st->logo_gc,
949 0, 0, w, h, lx, ly, 1);
951 XCopyArea (st->dpy, st->logo_map, st->window, st->logo_gc,
954 draw_solid_square (st, st->start_x, st->start_y, WALL_TOP >> st->start_dir, st->tgc);
955 draw_solid_square (st, st->end_x, st->end_y, WALL_TOP >> st->end_dir, st->tgc);
959 /* Mark the maze grid as having a wall at the given coordinate,
960 and draw that wall on the screen. */
962 build_wall(struct state *st, int i, int j, int dir)
964 /* Draw it on the screen. */
965 draw_wall(st, i, j, dir, st->gc);
966 /* Put it in the maze. */
970 st->maze[i][j] |= WALL_TOP;
972 st->maze[i][j-1] |= WALL_BOTTOM;
975 st->maze[i][j] |= WALL_RIGHT;
976 if(i<st->maze_size_x-1)
977 st->maze[i+1][j] |= WALL_LEFT;
980 st->maze[i][j] |= WALL_BOTTOM;
981 if(j<st->maze_size_y-1)
982 st->maze[i][j+1] |= WALL_TOP;
985 st->maze[i][j] |= WALL_LEFT;
987 st->maze[i-1][j] |= WALL_RIGHT;
994 draw_wall(struct state *st, int i, int j, int dir, GC with_gc) /* draw a single wall */
998 XDrawLine(st->dpy, st->window, with_gc,
999 border_x + st->grid_width * i,
1000 border_y + st->grid_height * j,
1001 border_x + st->grid_width * (i+1),
1002 border_y + st->grid_height * j);
1005 XDrawLine(st->dpy, st->window, with_gc,
1006 border_x + st->grid_width * (i+1),
1007 border_y + st->grid_height * j,
1008 border_x + st->grid_width * (i+1),
1009 border_y + st->grid_height * (j+1));
1012 XDrawLine(st->dpy, st->window, with_gc,
1013 border_x + st->grid_width * i,
1014 border_y + st->grid_height * (j+1),
1015 border_x + st->grid_width * (i+1),
1016 border_y + st->grid_height * (j+1));
1019 XDrawLine(st->dpy, st->window, with_gc,
1020 border_x + st->grid_width * i,
1021 border_y + st->grid_height * j,
1022 border_x + st->grid_width * i,
1023 border_y + st->grid_height * (j+1));
1028 /* too slow if we sync on every wall, so only sync about ten times
1029 during the maze-creation process.
1032 if (st->sync_tick <= 0) {
1033 XSync(st->dpy, False);
1034 st->sync_tick = st->maze_size_x * st->maze_size_x / 10;
1041 draw_solid_square(struct state *st,
1043 int dir, GC with_gc)
1047 XFillRectangle(st->dpy, st->window, with_gc,
1048 border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1049 border_y - st->bw-(st->bw==0?1:0) + st->grid_height * j,
1050 st->grid_width - (st->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
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->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
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->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
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->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
1073 /****************************************************************************
1075 ****************************************************************************/
1078 longdeadend_p(struct state *st, int x1, int y1, int x2, int y2, int endwall)
1080 int dx = x2 - x1, dy = y2 - y1;
1083 sidewalls = endwall | (endwall >> 2 | endwall << 2);
1084 sidewalls = ~sidewalls & WALL_ANY;
1086 while((st->maze[x2][y2] & WALL_ANY) == sidewalls)
1088 if (x2 + dx < 0 || x2 + dx >= st->maze_size_x ||
1089 y2 + dy < 0 || y2 + dy >= st->maze_size_y)
1095 if((st->maze[x2][y2] & WALL_ANY) == (sidewalls | endwall))
1097 endwall = (endwall >> 2 | endwall << 2) & WALL_ANY;
1098 while(x1 != x2 || y1 != y2)
1102 draw_solid_square(st, x1, y1, endwall, st->sgc);
1103 st->maze[x1][y1] |= SOLVER_VISIT;
1111 /* Find all dead regions -- areas from which the goal cannot be reached --
1112 and mark them visited. */
1114 find_dead_regions(struct state *st)
1116 int xx, yy, flipped;
1118 /* Find all not SOLVER_VISIT squares bordering NOT_DEAD squares
1119 and mark them NOT_DEAD also. Repeat until no more such squares. */
1120 st->maze[st->start_x][st->start_y] |= NOT_DEAD;
1125 for(xx = 0; xx < st->maze_size_x; xx++)
1126 for(yy = 0; yy < st->maze_size_y; yy++)
1127 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1128 && ( (xx && (st->maze[xx-1][yy] & NOT_DEAD))
1129 || (yy && (st->maze[xx][yy-1] & NOT_DEAD))))
1132 st->maze[xx][yy] |= NOT_DEAD;
1134 for(xx = st->maze_size_x-1; xx >= 0; xx--)
1135 for(yy = st->maze_size_y-1; yy >= 0; yy--)
1136 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1137 && ( (xx != st->maze_size_x-1 && (st->maze[xx+1][yy] & NOT_DEAD))
1138 || (yy != st->maze_size_y-1 && (st->maze[xx][yy+1] & NOT_DEAD))))
1141 st->maze[xx][yy] |= NOT_DEAD;
1146 for (yy = 0; yy < st->maze_size_y; yy++)
1147 for (xx = 0; xx < st->maze_size_x; xx++)
1149 if (st->maze[xx][yy] & NOT_DEAD)
1150 st->maze[xx][yy] &= ~NOT_DEAD;
1151 else if (!(st->maze[xx][yy] & SOLVER_VISIT))
1153 st->maze[xx][yy] |= SOLVER_VISIT;
1154 if((xx < st->logo_x || xx > st->logo_x + st->logo_width / st->grid_width) ||
1155 (yy < st->logo_y || yy > st->logo_y + st->logo_height / st->grid_height))
1157 /* if we are completely surrounded by walls, just draw the
1159 if ((st->maze[xx][yy] & WALL_ANY) == WALL_ANY)
1160 XFillRectangle(st->dpy, st->window, st->ugc,
1161 border_x + st->bw + st->grid_width * xx,
1162 border_y + st->bw + st->grid_height * yy,
1163 st->grid_width - (st->bw+st->bw), st->grid_height - (st->bw+st->bw));
1166 if (! (st->maze[xx][yy] & WALL_LEFT))
1167 draw_solid_square(st, xx, yy, WALL_LEFT, st->ugc);
1168 if (! (st->maze[xx][yy] & WALL_RIGHT))
1169 draw_solid_square(st, xx, yy, WALL_RIGHT, st->ugc);
1170 if (! (st->maze[xx][yy] & WALL_TOP))
1171 draw_solid_square(st, xx, yy, WALL_TOP, st->ugc);
1172 if (! (st->maze[xx][yy] & WALL_BOTTOM))
1173 draw_solid_square(st, xx, yy, WALL_BOTTOM, st->ugc);
1180 /* solve the maze by one more tick */
1182 solve_maze (struct state *st)
1184 struct solve_state *ss = st->solve_state;
1186 ss = st->solve_state = (struct solve_state *) calloc (1, sizeof(*ss));
1189 /* plug up the surrounding wall */
1190 st->maze[st->end_x][st->end_y] |= (WALL_TOP >> st->end_dir);
1192 /* initialize search path */
1194 st->path[ss->i].x = st->end_x;
1195 st->path[ss->i].y = st->end_y;
1196 st->path[ss->i].dir = 0;
1197 st->maze[st->end_x][st->end_y] |= SOLVER_VISIT;
1205 int dir, from, ways;
1207 if ( st->maze[st->path[ss->i].x][st->path[ss->i].y] & START_SQUARE )
1213 if(!st->path[ss->i].dir)
1216 /* First visit this square. Which adjacent squares are open? */
1217 for(dir = WALL_TOP; dir & WALL_ANY; dir >>= 1)
1219 if(st->maze[st->path[ss->i].x][st->path[ss->i].y] & dir)
1222 ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1223 ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1225 if(st->maze[ss->x][ss->y] & SOLVER_VISIT)
1228 from = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1229 /* don't enter obvious dead ends */
1230 if(((st->maze[ss->x][ss->y] & WALL_ANY) | from) != WALL_ANY)
1232 if(!longdeadend_p(st, st->path[ss->i].x, st->path[ss->i].y, ss->x, ss->y, dir))
1237 draw_solid_square(st, ss->x, ss->y, from, st->sgc);
1238 st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1243 ways = st->path[ss->i].ways;
1244 /* ways now has a bitmask of open paths. */
1249 if (!st->ignorant_p)
1251 ss->x = st->path[ss->i].x - st->start_x;
1252 ss->y = st->path[ss->i].y - st->start_y;
1254 if(abs(ss->y) <= abs(ss->x))
1255 dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1257 dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM;
1267 dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM; break;
1270 dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1278 dir = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1293 else if(ways&WALL_LEFT)
1295 else if(ways&WALL_BOTTOM)
1297 else if(ways&WALL_RIGHT)
1303 ways &= ~dir; /* tried this one */
1305 ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1306 ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1308 /* advance in direction dir */
1309 st->path[ss->i].dir = dir;
1310 st->path[ss->i].ways = ways;
1311 draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, dir, st->tgc);
1314 st->path[ss->i].dir = 0;
1315 st->path[ss->i].ways = 0;
1316 st->path[ss->i].x = ss->x;
1317 st->path[ss->i].y = ss->y;
1318 st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1325 printf("Unsolvable maze.\n");
1330 if(!ss->bt && !st->ignorant_p)
1331 find_dead_regions(st);
1333 from = st->path[ss->i-1].dir;
1334 from = (from << 2 & WALL_ANY) | (from >> 2 & WALL_ANY);
1336 draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, from, st->cgc);
1344 /****************************************************************************
1345 XScreenSaver boilerplate: resources, command line options, and main loop.
1346 ****************************************************************************/
1348 static const char *maze_defaults[] = {
1349 ".background: black",
1350 ".foreground: white",
1357 "*solveDelay: 10000",
1358 "*preDelay: 2000000",
1359 "*postDelay: 4000000",
1361 "*liveColor: #00FF00",
1362 "*deadColor: #880000",
1363 "*skipColor: #8B5A00",
1364 "*surroundColor: #220055",
1369 static XrmOptionDescRec maze_options[] = {
1370 { "-ignorant", ".ignorant", XrmoptionNoArg, "True" },
1371 { "-no-ignorant", ".ignorant", XrmoptionNoArg, "False" },
1372 { "-grid-size", ".gridSize", XrmoptionSepArg, 0 },
1373 { "-solve-delay", ".solveDelay", XrmoptionSepArg, 0 },
1374 { "-pre-delay", ".preDelay", XrmoptionSepArg, 0 },
1375 { "-post-delay", ".postDelay", XrmoptionSepArg, 0 },
1376 { "-bg-color", ".background", XrmoptionSepArg, 0 },
1377 { "-fg-color", ".foreground", XrmoptionSepArg, 0 },
1378 { "-live-color", ".liveColor", XrmoptionSepArg, 0 },
1379 { "-dead-color", ".deadColor", XrmoptionSepArg, 0 },
1380 { "-skip-color", ".skipColor", XrmoptionSepArg, 0 },
1381 { "-surround-color", ".surroundColor",XrmoptionSepArg, 0 },
1382 { "-generator", ".generator", XrmoptionSepArg, 0 },
1383 { "-max-length", ".maxLength", XrmoptionSepArg, 0 },
1387 static int generator = 0;
1390 maze_init (Display *dpy_arg, Window window_arg)
1392 struct state *st = (struct state *) calloc (1, sizeof(*st));
1394 XWindowAttributes xgwa;
1395 unsigned long bg, fg, pfg, pbg, sfg, ufg;
1398 st->window = window_arg;
1407 size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1408 st->solve_delay = get_integer_resource (st->dpy, "solveDelay", "Integer");
1409 st->pre_solve_delay = get_integer_resource (st->dpy, "preDelay", "Integer");
1410 st->post_solve_delay = get_integer_resource (st->dpy, "postDelay", "Integer");
1411 generator = get_integer_resource(st->dpy, "generator", "Integer");
1412 st->max_length = get_integer_resource(st->dpy, "maxLength", "Integer");
1413 st->ignorant_p = get_boolean_resource(st->dpy, "ignorant", "Boolean");
1415 if (get_boolean_resource (st->dpy, "doFPS", "DoFPS"))
1417 /* Just guess, rather than loading and measuring the "fpsFont"... */
1418 st->fps_width = 210;
1419 st->fps_height = 62;
1422 if (!size) st->ifrandom = 1;
1424 if (size < 2) size = 7 + (random () % 30);
1425 st->grid_width = st->grid_height = size;
1426 st->bw = (size > 6 ? 3 : (size-1)/2);
1428 XGetWindowAttributes (st->dpy, st->window, &xgwa);
1433 set_maze_sizes (st, xgwa.width, xgwa.height);
1435 st->gc = XCreateGC(st->dpy, st->window, 0, 0);
1436 st->cgc = XCreateGC(st->dpy, st->window, 0, 0);
1437 st->tgc = XCreateGC(st->dpy, st->window, 0, 0);
1438 st->sgc = XCreateGC(st->dpy, st->window, 0, 0);
1439 st->ugc = XCreateGC(st->dpy, st->window, 0, 0);
1440 st->logo_gc = XCreateGC(st->dpy, st->window, 0, 0);
1441 st->erase_gc = XCreateGC(st->dpy, st->window, 0, 0);
1443 bg = get_pixel_resource (st->dpy, xgwa.colormap, "background","Background");
1444 fg = get_pixel_resource (st->dpy, xgwa.colormap, "foreground","Foreground");
1445 pfg = get_pixel_resource (st->dpy, xgwa.colormap, "liveColor", "Foreground");
1446 pbg = get_pixel_resource (st->dpy, xgwa.colormap, "deadColor", "Foreground");
1447 sfg = get_pixel_resource (st->dpy, xgwa.colormap, "skipColor", "Foreground");
1448 ufg = get_pixel_resource (st->dpy, xgwa.colormap, "surroundColor", "Foreground");
1450 XSetForeground (st->dpy, st->gc, fg);
1451 XSetBackground (st->dpy, st->gc, bg);
1452 XSetForeground (st->dpy, st->cgc, pbg);
1453 XSetBackground (st->dpy, st->cgc, bg);
1454 XSetForeground (st->dpy, st->tgc, pfg);
1455 XSetBackground (st->dpy, st->tgc, bg);
1456 XSetForeground (st->dpy, st->sgc, sfg);
1457 XSetBackground (st->dpy, st->sgc, bg);
1458 XSetForeground (st->dpy, st->ugc, ufg);
1459 XSetBackground (st->dpy, st->ugc, bg);
1460 XSetForeground (st->dpy, st->logo_gc, fg);
1461 XSetBackground (st->dpy, st->logo_gc, bg);
1462 XSetForeground (st->dpy, st->erase_gc, bg);
1463 XSetBackground (st->dpy, st->erase_gc, bg);
1468 unsigned int w, h, bbw, d;
1469 unsigned long *pixels;
1471 Pixmap logo_mask = 0;
1472 st->logo_map = xscreensaver_logo (xgwa.screen, xgwa.visual, st->window,
1474 &pixels, &npixels, &logo_mask,
1477 XSetClipMask (st->dpy, st->logo_gc, logo_mask);
1478 XFreePixmap (st->dpy, logo_mask);
1480 if (pixels) free (pixels);
1481 XGetGeometry (st->dpy, st->logo_map, &r, &x, &y, &w, &h, &bbw, &d);
1483 st->logo_height = h;
1495 maze_reshape (Display *dpy, Window window, void *closure,
1496 unsigned int w, unsigned int h)
1498 struct state *st = (struct state *) closure;
1503 static unsigned long
1504 maze_draw (Display *dpy, Window window, void *closure)
1506 struct state *st = (struct state *) closure;
1507 int this_delay = st->solve_delay;
1509 if (st->eraser || st->erase_window)
1511 st->erase_window = 0;
1512 st->eraser = erase_window (st->dpy, st->window, st->eraser);
1516 this_delay = 1000000;
1517 if (this_delay > st->pre_solve_delay)
1518 this_delay = st->pre_solve_delay;
1523 if (st->restart || st->stop) goto pop;
1524 switch (st->state) {
1526 initialize_maze(st);
1527 if (st->ifrandom && st->ifinit)
1530 size = 7 + (random () % 30);
1531 st->grid_width = st->grid_height = size;
1532 st->bw = (size > 6 ? 3 : (size-1)/2);
1538 XClearWindow(st->dpy, st->window);
1539 draw_maze_border(st);
1542 st->this_gen = generator;
1543 if(st->this_gen<0 || st->this_gen>2)
1544 st->this_gen = random()%3;
1546 switch(st->this_gen)
1552 alt_create_maze(st);
1555 set_create_maze(st);
1560 this_delay = st->pre_solve_delay;
1563 if (! solve_maze(st))
1564 --st->state; /* stay in state 5 */
1567 st->erase_window = 1;
1568 this_delay = st->post_solve_delay;
1579 XWindowAttributes xgwa;
1586 st->sync_p = ((random() % 4) != 0);
1588 size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1589 if (size < 2) size = 7 + (random () % 30);
1590 st->grid_width = st->grid_height = size;
1591 st->bw = (size > 6 ? 3 : (size-1)/2);
1593 XGetWindowAttributes (st->dpy, st->window, &xgwa);
1594 set_maze_sizes (st, xgwa.width, xgwa.height);
1603 maze_event (Display *dpy, Window window, void *closure, XEvent *event)
1605 struct state *st = (struct state *) closure;
1606 switch (event->type)
1609 switch (event->xbutton.button)
1612 st->stop = !st->stop ;
1613 if (st->state == 5) st->state = 4 ;
1639 maze_free (Display *dpy, Window window, void *closure)
1641 struct state *st = (struct state *) closure;
1645 XSCREENSAVER_MODULE ("Maze", maze)