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 if (st->sqnum >= 0) {
875 st->cur_sq_x = st->move_list[st->sqnum].x;
876 st->cur_sq_y = st->move_list[st->sqnum].y;
878 return ( st->sqnum );
882 /****************************************************************************
884 ****************************************************************************/
886 /* draws the maze outline, and the logo */
888 draw_maze_border (struct state *st)
892 for ( i=0; i<st->maze_size_x; i++) {
893 if ( st->maze[i][0] & WALL_TOP ) {
894 XDrawLine(st->dpy, st->window, st->gc,
895 border_x + st->grid_width * i,
897 border_x + st->grid_width * (i+1) - 1,
900 if ((st->maze[i][st->maze_size_y - 1] & WALL_BOTTOM)) {
901 XDrawLine(st->dpy, st->window, st->gc,
902 border_x + st->grid_width * i,
903 border_y + st->grid_height * (st->maze_size_y) - 1,
904 border_x + st->grid_width * (i+1) - 1,
905 border_y + st->grid_height * (st->maze_size_y) - 1);
908 for ( j=0; j<st->maze_size_y; j++) {
909 if ( st->maze[st->maze_size_x - 1][j] & WALL_RIGHT ) {
910 XDrawLine(st->dpy, st->window, st->gc,
911 border_x + st->grid_width * st->maze_size_x - 1,
912 border_y + st->grid_height * j,
913 border_x + st->grid_width * st->maze_size_x - 1,
914 border_y + st->grid_height * (j+1) - 1);
916 if ( st->maze[0][j] & WALL_LEFT ) {
917 XDrawLine(st->dpy, st->window, st->gc,
919 border_y + st->grid_height * j,
921 border_y + st->grid_height * (j+1) - 1);
925 if (st->logo_x != -1)
929 unsigned int w, h, bbw, d;
931 /* round up to grid size */
932 int ww = ((st->logo_width / st->grid_width) + 1) * st->grid_width;
933 int hh = ((st->logo_height / st->grid_height) + 1) * st->grid_height;
936 XGetGeometry (st->dpy, st->logo_map, &r, &xx, &yy, &w, &h, &bbw, &d);
938 /* kludge: if the logo "hole" is around the same size as the logo,
939 don't center it (since the xscreensaver logo image is a little
940 off center... But do center it if the hole/gridsize is large. */
941 if (ww < st->logo_width + 5) ww = w;
942 if (hh < st->logo_height + 5) hh = h;
945 lx = border_x + 3 + st->grid_width * st->logo_x + ((ww - w) / 2);
946 ly = border_y + 3 + st->grid_height * st->logo_y + ((hh - h) / 2);
948 /* Fill the background of the logo box with the "unreachable" color */
949 XFillRectangle (st->dpy, st->window, st->ugc,
950 border_x + 3 + st->grid_width * st->logo_x,
951 border_y + 3 + st->grid_height * st->logo_y,
954 XSetClipOrigin (st->dpy, st->logo_gc, lx, ly);
956 XCopyPlane (st->dpy, st->logo_map, st->window, st->logo_gc,
957 0, 0, w, h, lx, ly, 1);
959 XCopyArea (st->dpy, st->logo_map, st->window, st->logo_gc,
962 draw_solid_square (st, st->start_x, st->start_y, WALL_TOP >> st->start_dir, st->tgc);
963 draw_solid_square (st, st->end_x, st->end_y, WALL_TOP >> st->end_dir, st->tgc);
967 /* Mark the maze grid as having a wall at the given coordinate,
968 and draw that wall on the screen. */
970 build_wall(struct state *st, int i, int j, int dir)
972 /* Draw it on the screen. */
973 draw_wall(st, i, j, dir, st->gc);
974 /* Put it in the maze. */
978 st->maze[i][j] |= WALL_TOP;
980 st->maze[i][j-1] |= WALL_BOTTOM;
983 st->maze[i][j] |= WALL_RIGHT;
984 if(i<st->maze_size_x-1)
985 st->maze[i+1][j] |= WALL_LEFT;
988 st->maze[i][j] |= WALL_BOTTOM;
989 if(j<st->maze_size_y-1)
990 st->maze[i][j+1] |= WALL_TOP;
993 st->maze[i][j] |= WALL_LEFT;
995 st->maze[i-1][j] |= WALL_RIGHT;
1002 draw_wall(struct state *st, int i, int j, int dir, GC with_gc) /* draw a single wall */
1006 XDrawLine(st->dpy, st->window, with_gc,
1007 border_x + st->grid_width * i,
1008 border_y + st->grid_height * j,
1009 border_x + st->grid_width * (i+1),
1010 border_y + st->grid_height * j);
1013 XDrawLine(st->dpy, st->window, with_gc,
1014 border_x + st->grid_width * (i+1),
1015 border_y + st->grid_height * j,
1016 border_x + st->grid_width * (i+1),
1017 border_y + st->grid_height * (j+1));
1020 XDrawLine(st->dpy, st->window, with_gc,
1021 border_x + st->grid_width * i,
1022 border_y + st->grid_height * (j+1),
1023 border_x + st->grid_width * (i+1),
1024 border_y + st->grid_height * (j+1));
1027 XDrawLine(st->dpy, st->window, with_gc,
1028 border_x + st->grid_width * i,
1029 border_y + st->grid_height * j,
1030 border_x + st->grid_width * i,
1031 border_y + st->grid_height * (j+1));
1036 /* too slow if we sync on every wall, so only sync about ten times
1037 during the maze-creation process.
1040 if (st->sync_tick <= 0) {
1041 XSync(st->dpy, False);
1042 st->sync_tick = st->maze_size_x * st->maze_size_x / 10;
1049 draw_solid_square(struct state *st,
1051 int dir, GC with_gc)
1055 XFillRectangle(st->dpy, st->window, with_gc,
1056 border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1057 border_y - st->bw-(st->bw==0?1:0) + st->grid_height * j,
1058 st->grid_width - (st->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
1061 XFillRectangle(st->dpy, st->window, with_gc,
1062 border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1063 border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1064 st->grid_width, st->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
1067 XFillRectangle(st->dpy, st->window, with_gc,
1068 border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1069 border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1070 st->grid_width - (st->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
1073 XFillRectangle(st->dpy, st->window, with_gc,
1074 border_x - st->bw-(st->bw==0?1:0) + st->grid_width * i,
1075 border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1076 st->grid_width, st->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
1081 /****************************************************************************
1083 ****************************************************************************/
1086 longdeadend_p(struct state *st, int x1, int y1, int x2, int y2, int endwall)
1088 int dx = x2 - x1, dy = y2 - y1;
1091 sidewalls = endwall | (endwall >> 2 | endwall << 2);
1092 sidewalls = ~sidewalls & WALL_ANY;
1094 while((st->maze[x2][y2] & WALL_ANY) == sidewalls)
1096 if (x2 + dx < 0 || x2 + dx >= st->maze_size_x ||
1097 y2 + dy < 0 || y2 + dy >= st->maze_size_y)
1103 if((st->maze[x2][y2] & WALL_ANY) == (sidewalls | endwall))
1105 endwall = (endwall >> 2 | endwall << 2) & WALL_ANY;
1106 while(x1 != x2 || y1 != y2)
1110 draw_solid_square(st, x1, y1, endwall, st->sgc);
1111 st->maze[x1][y1] |= SOLVER_VISIT;
1119 /* Find all dead regions -- areas from which the goal cannot be reached --
1120 and mark them visited. */
1122 find_dead_regions(struct state *st)
1124 int xx, yy, flipped;
1126 /* Find all not SOLVER_VISIT squares bordering NOT_DEAD squares
1127 and mark them NOT_DEAD also. Repeat until no more such squares. */
1128 st->maze[st->start_x][st->start_y] |= NOT_DEAD;
1133 for(xx = 0; xx < st->maze_size_x; xx++)
1134 for(yy = 0; yy < st->maze_size_y; yy++)
1135 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1136 && ( (xx && (st->maze[xx-1][yy] & NOT_DEAD))
1137 || (yy && (st->maze[xx][yy-1] & NOT_DEAD))))
1140 st->maze[xx][yy] |= NOT_DEAD;
1142 for(xx = st->maze_size_x-1; xx >= 0; xx--)
1143 for(yy = st->maze_size_y-1; yy >= 0; yy--)
1144 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1145 && ( (xx != st->maze_size_x-1 && (st->maze[xx+1][yy] & NOT_DEAD))
1146 || (yy != st->maze_size_y-1 && (st->maze[xx][yy+1] & NOT_DEAD))))
1149 st->maze[xx][yy] |= NOT_DEAD;
1154 for (yy = 0; yy < st->maze_size_y; yy++)
1155 for (xx = 0; xx < st->maze_size_x; xx++)
1157 if (st->maze[xx][yy] & NOT_DEAD)
1158 st->maze[xx][yy] &= ~NOT_DEAD;
1159 else if (!(st->maze[xx][yy] & SOLVER_VISIT))
1161 st->maze[xx][yy] |= SOLVER_VISIT;
1162 if((xx < st->logo_x || xx > st->logo_x + st->logo_width / st->grid_width) ||
1163 (yy < st->logo_y || yy > st->logo_y + st->logo_height / st->grid_height))
1165 /* if we are completely surrounded by walls, just draw the
1167 if ((st->maze[xx][yy] & WALL_ANY) == WALL_ANY)
1168 XFillRectangle(st->dpy, st->window, st->ugc,
1169 border_x + st->bw + st->grid_width * xx,
1170 border_y + st->bw + st->grid_height * yy,
1171 st->grid_width - (st->bw+st->bw), st->grid_height - (st->bw+st->bw));
1174 if (! (st->maze[xx][yy] & WALL_LEFT))
1175 draw_solid_square(st, xx, yy, WALL_LEFT, st->ugc);
1176 if (! (st->maze[xx][yy] & WALL_RIGHT))
1177 draw_solid_square(st, xx, yy, WALL_RIGHT, st->ugc);
1178 if (! (st->maze[xx][yy] & WALL_TOP))
1179 draw_solid_square(st, xx, yy, WALL_TOP, st->ugc);
1180 if (! (st->maze[xx][yy] & WALL_BOTTOM))
1181 draw_solid_square(st, xx, yy, WALL_BOTTOM, st->ugc);
1188 /* solve the maze by one more tick */
1190 solve_maze (struct state *st)
1192 struct solve_state *ss = st->solve_state;
1194 ss = st->solve_state = (struct solve_state *) calloc (1, sizeof(*ss));
1197 /* plug up the surrounding wall */
1198 st->maze[st->end_x][st->end_y] |= (WALL_TOP >> st->end_dir);
1200 /* initialize search path */
1202 st->path[ss->i].x = st->end_x;
1203 st->path[ss->i].y = st->end_y;
1204 st->path[ss->i].dir = 0;
1205 st->maze[st->end_x][st->end_y] |= SOLVER_VISIT;
1213 int dir, from, ways;
1215 if ( st->maze[st->path[ss->i].x][st->path[ss->i].y] & START_SQUARE )
1221 if(!st->path[ss->i].dir)
1224 /* First visit this square. Which adjacent squares are open? */
1225 for(dir = WALL_TOP; dir & WALL_ANY; dir >>= 1)
1227 if(st->maze[st->path[ss->i].x][st->path[ss->i].y] & dir)
1230 ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1231 ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1233 if(st->maze[ss->x][ss->y] & SOLVER_VISIT)
1236 from = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1237 /* don't enter obvious dead ends */
1238 if(((st->maze[ss->x][ss->y] & WALL_ANY) | from) != WALL_ANY)
1240 if(!longdeadend_p(st, st->path[ss->i].x, st->path[ss->i].y, ss->x, ss->y, dir))
1245 draw_solid_square(st, ss->x, ss->y, from, st->sgc);
1246 st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1251 ways = st->path[ss->i].ways;
1252 /* ways now has a bitmask of open paths. */
1257 if (!st->ignorant_p)
1259 ss->x = st->path[ss->i].x - st->start_x;
1260 ss->y = st->path[ss->i].y - st->start_y;
1262 if(abs(ss->y) <= abs(ss->x))
1263 dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1265 dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM;
1275 dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM; break;
1278 dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1286 dir = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1301 else if(ways&WALL_LEFT)
1303 else if(ways&WALL_BOTTOM)
1305 else if(ways&WALL_RIGHT)
1311 ways &= ~dir; /* tried this one */
1313 ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1314 ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1316 /* advance in direction dir */
1317 st->path[ss->i].dir = dir;
1318 st->path[ss->i].ways = ways;
1319 draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, dir, st->tgc);
1322 st->path[ss->i].dir = 0;
1323 st->path[ss->i].ways = 0;
1324 st->path[ss->i].x = ss->x;
1325 st->path[ss->i].y = ss->y;
1326 st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1333 printf("Unsolvable maze.\n");
1338 if(!ss->bt && !st->ignorant_p)
1339 find_dead_regions(st);
1341 from = st->path[ss->i-1].dir;
1342 from = (from << 2 & WALL_ANY) | (from >> 2 & WALL_ANY);
1344 draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, from, st->cgc);
1352 /****************************************************************************
1353 XScreenSaver boilerplate: resources, command line options, and main loop.
1354 ****************************************************************************/
1356 static const char *maze_defaults[] = {
1357 ".background: black",
1358 ".foreground: white",
1365 "*solveDelay: 10000",
1366 "*preDelay: 2000000",
1367 "*postDelay: 4000000",
1369 "*liveColor: #00FF00",
1370 "*deadColor: #880000",
1371 "*skipColor: #8B5A00",
1372 "*surroundColor: #220055",
1377 static XrmOptionDescRec maze_options[] = {
1378 { "-ignorant", ".ignorant", XrmoptionNoArg, "True" },
1379 { "-no-ignorant", ".ignorant", XrmoptionNoArg, "False" },
1380 { "-grid-size", ".gridSize", XrmoptionSepArg, 0 },
1381 { "-solve-delay", ".solveDelay", XrmoptionSepArg, 0 },
1382 { "-pre-delay", ".preDelay", XrmoptionSepArg, 0 },
1383 { "-post-delay", ".postDelay", XrmoptionSepArg, 0 },
1384 { "-bg-color", ".background", XrmoptionSepArg, 0 },
1385 { "-fg-color", ".foreground", XrmoptionSepArg, 0 },
1386 { "-live-color", ".liveColor", XrmoptionSepArg, 0 },
1387 { "-dead-color", ".deadColor", XrmoptionSepArg, 0 },
1388 { "-skip-color", ".skipColor", XrmoptionSepArg, 0 },
1389 { "-surround-color", ".surroundColor",XrmoptionSepArg, 0 },
1390 { "-generator", ".generator", XrmoptionSepArg, 0 },
1391 { "-max-length", ".maxLength", XrmoptionSepArg, 0 },
1395 static int generator = 0;
1398 maze_init (Display *dpy_arg, Window window_arg)
1400 struct state *st = (struct state *) calloc (1, sizeof(*st));
1402 XWindowAttributes xgwa;
1403 unsigned long bg, fg, pfg, pbg, sfg, ufg;
1406 st->window = window_arg;
1415 size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1416 st->solve_delay = get_integer_resource (st->dpy, "solveDelay", "Integer");
1417 st->pre_solve_delay = get_integer_resource (st->dpy, "preDelay", "Integer");
1418 st->post_solve_delay = get_integer_resource (st->dpy, "postDelay", "Integer");
1419 generator = get_integer_resource(st->dpy, "generator", "Integer");
1420 st->max_length = get_integer_resource(st->dpy, "maxLength", "Integer");
1421 st->ignorant_p = get_boolean_resource(st->dpy, "ignorant", "Boolean");
1423 if (get_boolean_resource (st->dpy, "doFPS", "DoFPS"))
1425 /* Just guess, rather than loading and measuring the "fpsFont"... */
1426 st->fps_width = 210;
1427 st->fps_height = 62;
1430 if (!size) st->ifrandom = 1;
1432 if (size < 2) size = 7 + (random () % 30);
1433 st->grid_width = st->grid_height = size;
1434 st->bw = (size > 6 ? 3 : (size-1)/2);
1436 XGetWindowAttributes (st->dpy, st->window, &xgwa);
1441 set_maze_sizes (st, xgwa.width, xgwa.height);
1443 st->gc = XCreateGC(st->dpy, st->window, 0, 0);
1444 st->cgc = XCreateGC(st->dpy, st->window, 0, 0);
1445 st->tgc = XCreateGC(st->dpy, st->window, 0, 0);
1446 st->sgc = XCreateGC(st->dpy, st->window, 0, 0);
1447 st->ugc = XCreateGC(st->dpy, st->window, 0, 0);
1448 st->logo_gc = XCreateGC(st->dpy, st->window, 0, 0);
1449 st->erase_gc = XCreateGC(st->dpy, st->window, 0, 0);
1451 bg = get_pixel_resource (st->dpy, xgwa.colormap, "background","Background");
1452 fg = get_pixel_resource (st->dpy, xgwa.colormap, "foreground","Foreground");
1453 pfg = get_pixel_resource (st->dpy, xgwa.colormap, "liveColor", "Foreground");
1454 pbg = get_pixel_resource (st->dpy, xgwa.colormap, "deadColor", "Foreground");
1455 sfg = get_pixel_resource (st->dpy, xgwa.colormap, "skipColor", "Foreground");
1456 ufg = get_pixel_resource (st->dpy, xgwa.colormap, "surroundColor", "Foreground");
1458 XSetForeground (st->dpy, st->gc, fg);
1459 XSetBackground (st->dpy, st->gc, bg);
1460 XSetForeground (st->dpy, st->cgc, pbg);
1461 XSetBackground (st->dpy, st->cgc, bg);
1462 XSetForeground (st->dpy, st->tgc, pfg);
1463 XSetBackground (st->dpy, st->tgc, bg);
1464 XSetForeground (st->dpy, st->sgc, sfg);
1465 XSetBackground (st->dpy, st->sgc, bg);
1466 XSetForeground (st->dpy, st->ugc, ufg);
1467 XSetBackground (st->dpy, st->ugc, bg);
1468 XSetForeground (st->dpy, st->logo_gc, fg);
1469 XSetBackground (st->dpy, st->logo_gc, bg);
1470 XSetForeground (st->dpy, st->erase_gc, bg);
1471 XSetBackground (st->dpy, st->erase_gc, bg);
1476 unsigned int w, h, bbw, d;
1477 unsigned long *pixels;
1479 Pixmap logo_mask = 0;
1480 st->logo_map = xscreensaver_logo (xgwa.screen, xgwa.visual, st->window,
1482 &pixels, &npixels, &logo_mask,
1483 xgwa.width > 800 || xgwa.height > 800);
1485 XSetClipMask (st->dpy, st->logo_gc, logo_mask);
1486 XFreePixmap (st->dpy, logo_mask);
1488 if (pixels) free (pixels);
1489 XGetGeometry (st->dpy, st->logo_map, &r, &x, &y, &w, &h, &bbw, &d);
1491 st->logo_height = h;
1503 maze_reshape (Display *dpy, Window window, void *closure,
1504 unsigned int w, unsigned int h)
1506 struct state *st = (struct state *) closure;
1511 static unsigned long
1512 maze_draw (Display *dpy, Window window, void *closure)
1514 struct state *st = (struct state *) closure;
1515 int this_delay = st->solve_delay;
1517 if (st->eraser || st->erase_window)
1519 st->erase_window = 0;
1520 st->eraser = erase_window (st->dpy, st->window, st->eraser);
1524 this_delay = 1000000;
1525 if (this_delay > st->pre_solve_delay)
1526 this_delay = st->pre_solve_delay;
1531 if (st->restart || st->stop) goto pop;
1532 switch (st->state) {
1534 initialize_maze(st);
1535 if (st->ifrandom && st->ifinit)
1538 size = 7 + (random () % 30);
1539 st->grid_width = st->grid_height = size;
1540 st->bw = (size > 6 ? 3 : (size-1)/2);
1546 XClearWindow(st->dpy, st->window);
1547 draw_maze_border(st);
1550 st->this_gen = generator;
1551 if(st->this_gen<0 || st->this_gen>2)
1552 st->this_gen = random()%3;
1554 switch(st->this_gen)
1560 alt_create_maze(st);
1563 set_create_maze(st);
1568 this_delay = st->pre_solve_delay;
1571 if (! solve_maze(st))
1572 --st->state; /* stay in state 5 */
1575 st->erase_window = 1;
1576 this_delay = st->post_solve_delay;
1587 XWindowAttributes xgwa;
1594 if (st->solve_state && st->solve_state->running)
1595 st->solve_state->running = 0;
1597 st->sync_p = ((random() % 4) != 0);
1599 size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1600 if (size < 2) size = 7 + (random () % 30);
1601 st->grid_width = st->grid_height = size;
1602 st->bw = (size > 6 ? 3 : (size-1)/2);
1604 XGetWindowAttributes (st->dpy, st->window, &xgwa);
1605 set_maze_sizes (st, xgwa.width, xgwa.height);
1614 maze_event (Display *dpy, Window window, void *closure, XEvent *event)
1616 struct state *st = (struct state *) closure;
1617 if (event->type == ButtonPress)
1619 switch (event->xbutton.button)
1622 st->stop = !st->stop ;
1623 if (st->state == 5) st->state = 4 ;
1636 else if (event->type == Expose)
1641 else if (screenhack_event_helper (dpy, window, event))
1652 maze_free (Display *dpy, Window window, void *closure)
1654 struct state *st = (struct state *) closure;
1658 XSCREENSAVER_MODULE ("Maze", maze)