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)
215 int logow = 1 + st->logo_width / st->grid_width;
216 int logoh = 1 + st->logo_height / st->grid_height;
220 /* This can happen if the window is really small. Let's not sweat it. */
221 if (++retry_count > 100) return;
224 /* initialize all squares */
225 for ( i=0; i<st->maze_size_x; i++) {
226 for ( j=0; j<st->maze_size_y; j++) {
232 for ( i=0; i<st->maze_size_x; i++ ) {
233 st->maze[i][0] |= WALL_TOP;
237 for ( j=0; j<st->maze_size_y; j++ ) {
238 st->maze[st->maze_size_x-1][j] |= WALL_RIGHT;
242 for ( i=0; i<st->maze_size_x; i++ ) {
243 st->maze[i][st->maze_size_y-1] |= WALL_BOTTOM;
247 for ( j=0; j<st->maze_size_y; j++ ) {
248 st->maze[0][j] |= WALL_LEFT;
251 /* set start square */
252 wall = get_random(4);
255 i = get_random(st->maze_size_x);
259 i = st->maze_size_x - 1;
260 j = get_random(st->maze_size_y);
263 i = get_random(st->maze_size_x);
264 j = st->maze_size_y - 1;
268 j = get_random(st->maze_size_y);
271 st->maze[i][j] |= START_SQUARE;
272 st->maze[i][j] |= ( DOOR_IN_TOP >> wall );
273 st->maze[i][j] &= ~( WALL_TOP >> wall );
278 st->start_dir = wall;
285 i = get_random(st->maze_size_x);
289 i = st->maze_size_x - 1;
290 j = get_random(st->maze_size_y);
293 i = get_random(st->maze_size_x);
294 j = st->maze_size_y - 1;
298 j = get_random(st->maze_size_y);
301 st->maze[i][j] |= END_SQUARE;
302 st->maze[i][j] |= ( DOOR_OUT_TOP >> wall );
303 st->maze[i][j] &= ~( WALL_TOP >> wall );
309 if ((st->maze_size_x-logow >= 6) && (st->maze_size_y-logoh >= 6))
311 /* not closer than 3 grid units from a wall, to ensure that it
312 won't overlap the entrance or exit. */
313 st->logo_x = get_random (st->maze_size_x - logow - 5) + 3;
314 st->logo_y = get_random (st->maze_size_y - logoh - 5) + 3;
315 for (i=0; i<logow; i++)
316 for (j=0; j<logoh; j++)
317 /* mark as having doors to prevent these cells being used in maze. */
318 st->maze[st->logo_x + i][st->logo_y + j] |= DOOR_IN_ANY;
321 st->logo_y = st->logo_x = -1;
323 /* mask out the fps area */
324 if (st->fps_width > 0)
326 int fpsw = 1 + st->fps_width / st->grid_width;
327 int fpsh = 1 + st->fps_height / st->grid_width;
329 /* if the chosen logo position overlapped the fps area, try again! */
330 if (st->logo_x < fpsw+3 && st->logo_y+logoh > st->maze_size_y-fpsh-4)
333 /* if the start or end point is inside the fps area, try again! */
334 if ((st->start_x <= fpsw && st->start_y >= st->maze_size_y-fpsh-1) ||
335 (st->end_x <= fpsw && st->end_y >= st->maze_size_y-fpsh-1))
338 for (i=0; i<fpsw; i++)
339 for (j=0; j<fpsh; j++) {
340 /* mark as having doors to prevent these cells being used in maze.
341 mark as visit to prevent it being colored "unreachable". */
342 st->maze[i][st->maze_size_y - j - 1] |= DOOR_IN_ANY|SOLVER_VISIT;
343 /* take off left/bottom wall or the FPS text overlaps it */
344 st->maze[i][st->maze_size_y - j - 1] &= ~(WALL_BOTTOM|WALL_LEFT);
350 /****************************************************************************
351 Generator 2: Set-based maze generator.
353 Put each square in the maze in a separate set. Also, make a list of all the
354 hedges. Randomize that list. Walk through the list. If, for a certain
355 hedge, the two squares on both sides of it are in different sets, union the
356 sets and remove the hedge. Continue until all hedges have been processed or
357 only one set remains.
359 This is essentially the "Kruskal" algorithm.
361 ****************************************************************************/
363 static void mask_out_set_rect(struct state *st, int x, int y, int w, int h);
365 /* Initialise the sets. */
367 init_sets(struct state *st)
373 st->sets = (int *)malloc(st->maze_size_x*st->maze_size_y*sizeof(int));
376 for(i = 0; i < st->maze_size_x*st->maze_size_y; i++)
383 st->hedges = (int *)malloc(st->maze_size_x*st->maze_size_y*2*sizeof(int));
386 for(i = 0; i < st->maze_size_x*st->maze_size_y*2; i++)
390 /* Mask out outside walls. */
391 for(i = 0; i < st->maze_size_y; i++)
393 st->hedges[2*((st->maze_size_x)*i+st->maze_size_x-1)+1] = -1;
395 for(i = 0; i < st->maze_size_x; i++)
397 st->hedges[2*((st->maze_size_y-1)*st->maze_size_x+i)] = -1;
400 /* Mask out the logo area. */
403 int logow = 1 + st->logo_width / st->grid_width;
404 int logoh = 1 + st->logo_height / st->grid_height;
405 mask_out_set_rect(st, st->logo_x, st->logo_y, logow, logoh);
408 /* Mask out the FPS area. */
409 if(st->fps_width > 0)
411 int fpsw = 1 + st->fps_width / st->grid_width;
412 int fpsh = 1 + st->fps_height / st->grid_height;
413 mask_out_set_rect(st, 0, st->maze_size_y-fpsh, fpsw, fpsh);
416 for(i = 0; i < st->maze_size_x*st->maze_size_y*2; i++)
419 r = random()%(st->maze_size_x*st->maze_size_y*2);
420 st->hedges[i] = st->hedges[r];
425 /* Get the representative of a set. */
427 get_set(struct state *st, int num)
431 if(st->sets[num]==num)
435 s = get_set(st, st->sets[num]);
441 /* Join two sets together. */
443 join_sets(struct state *st, int num1, int num2)
447 s1 = get_set(st, num1);
448 s2 = get_set(st, num2);
456 /* Exitialise the sets. */
458 exit_sets(struct state *st)
470 set_create_maze(struct state *st)
472 int i, h, xx, yy, dir, v, w;
474 /* Do almost all the setup. */
477 /* Start running through the hedges. */
478 for(i = 0; i < 2*st->maze_size_x*st->maze_size_y; i++)
482 /* This one is in the logo or outside border. */
487 xx = (h>>1)%st->maze_size_x;
488 yy = (h>>1)/st->maze_size_x;
502 if(get_set(st, xx+yy*st->maze_size_x)!=get_set(st, v+w*st->maze_size_x))
504 join_sets(st, xx+yy*st->maze_size_x, v+w*st->maze_size_x);
505 /* Don't draw the wall. */
509 /* Don't join the sets. */
510 build_wall(st, xx, yy, dir);
514 /* Free some memory. */
518 /* mark a rectangle as being unavailable for usage in the maze */
520 mask_out_set_rect(struct state *st, int x, int y, int w, int h)
523 for(xx = x; xx < x+w; xx++)
524 for(yy = y; yy < y+h; yy++)
526 st->hedges[2*(xx+st->maze_size_x*yy)+1] = -1;
527 st->hedges[2*(xx+st->maze_size_x*yy)] = -1;
529 for(xx = x; xx < x+w; xx++)
531 build_wall(st, xx, y, 0);
532 build_wall(st, xx, y+h, 0);
533 st->hedges[2*(xx+st->maze_size_x*(y-1))] = -1;
535 for(yy = y; yy < y+h; yy++)
537 build_wall(st, x, yy, 3);
538 build_wall(st, x+w, yy, 3);
539 st->hedges[2*(x-1+st->maze_size_x*yy)+1] = -1;
544 /****************************************************************************
545 Generator 1: Wall-building maze generator.
547 Pick a random, empty corner in the maze. Pick a random direction. Draw a
548 wall in that direction, from that corner until we hit a wall. Option: Only
549 draw the wall if it's going to be shorter than a certain length. Otherwise
550 we get lots of long walls.
552 This is essentially the "Prim" algorithm.
553 ****************************************************************************/
555 static void alt_mask_out_rect(struct state *st, char *corners,
556 int x, int y, int w, int h);
559 alt_create_maze(struct state *st)
563 int i, j, height, width, open_corners, k, dir, xx, yy;
565 height = st->maze_size_y+1;
566 width = st->maze_size_x+1;
568 /* Allocate and clear some mem. */
569 corners = (char *)calloc(height*width, 1);
573 /* Set up the indexing array. */
574 c_idx = (int *)malloc(sizeof(int)*height*width);
580 for(i = 0; i < height*width; i++)
582 for(i = 0; i < height*width; i++)
585 k = random()%(height*width);
590 /* Set up some initial walls. */
592 for(i = 0; i < width; i++)
595 corners[i+width*(height-1)] = 1;
597 for(i = 0; i < height; i++)
599 corners[i*width] = 1;
600 corners[i*width+width-1] = 1;
603 /* mask out the logo area */
606 int logow = 1 + st->logo_width / st->grid_width;
607 int logoh = 1 + st->logo_height / st->grid_height;
608 alt_mask_out_rect (st, corners, st->logo_x, st->logo_y, logow, logoh);
611 /* mask out the FPS area */
614 int fpsw = 1 + st->fps_width / st->grid_width;
615 int fpsh = 1 + st->fps_height / st->grid_height;
616 alt_mask_out_rect (st, corners, 0, st->maze_size_y-fpsh, fpsw, fpsh);
619 /* Count open gridpoints. */
621 for(i = 0; i < width; i++)
622 for(j = 0; j < height; j++)
623 if(!corners[i+width*j])
626 /* Now do actual maze generation. */
627 while(open_corners>0)
629 for(i = 0; i < width*height; i++)
631 if(!corners[c_idx[i]])
635 /* Choose a random direction. */
639 /* Measure the length of the wall we'd draw. */
640 while(!corners[xx+width*yy])
660 if(k<=st->max_length)
665 /* Draw a wall until we hit something. */
666 while(!corners[xx+width*yy])
669 corners[xx+width*yy] = 1;
673 build_wall(st, xx-1, yy-1, 1);
677 build_wall(st, xx, yy, 0);
681 build_wall(st, xx, yy, 3);
685 build_wall(st, xx-1, yy-1, 2);
695 /* Free some memory we used. */
701 /* mark a rectangle as being unavailable for usage in the maze */
703 alt_mask_out_rect(struct state *st, char *corners, int x, int y, int w, int h)
706 int mazew = st->maze_size_x+1;
708 for(i = x; i <= x+w; i++)
709 for(j = y; j <= y+h; j++)
710 corners[i+mazew*j] = 1;
712 for(xx = x; xx < x+w; xx++)
714 build_wall(st, xx, y, 0);
715 if (y+h < st->maze_size_y)
716 build_wall(st, xx, y+h, 0);
718 for(yy = y; yy < y+h; yy++)
721 build_wall(st, x, yy, 3);
722 build_wall(st, x+w, yy, 3);
727 /****************************************************************************
728 Generator 0: The original maze generator.
730 Start somewhere. Take a step in a random direction. Keep doing this until
731 we hit a wall. Then, backtrack until we find a point where we can go in
734 This is essentially the "depth-first recursive backtracker" algorithm.
735 ****************************************************************************/
737 static int choose_door (struct state *st);
738 static int backup (struct state *st);
741 create_maze (struct state *st) /* create a maze layout given the initialized maze */
746 st->move_list[st->sqnum].x = st->cur_sq_x;
747 st->move_list[st->sqnum].y = st->cur_sq_y;
748 st->move_list[st->sqnum].dir = newdoor;
749 while ( ( newdoor = choose_door(st) ) == -1 ) { /* pick a door */
750 if ( backup(st) == -1 ) { /* no more doors ... backup */
751 return; /* done ... return */
755 /* mark the out door */
756 st->maze[st->cur_sq_x][st->cur_sq_y] |= ( DOOR_OUT_TOP >> newdoor );
759 case 0: st->cur_sq_y--;
761 case 1: st->cur_sq_x++;
763 case 2: st->cur_sq_y++;
765 case 3: st->cur_sq_x--;
770 /* mark the in door */
771 st->maze[st->cur_sq_x][st->cur_sq_y] |= ( DOOR_IN_TOP >> ((newdoor+2)%4) );
773 /* if end square set path length and save path */
774 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & END_SQUARE ) {
775 st->path_length = st->sqnum;
776 for ( i=0; i<st->path_length; i++) {
777 st->save_path[i].x = st->move_list[i].x;
778 st->save_path[i].y = st->move_list[i].y;
779 st->save_path[i].dir = st->move_list[i].dir;
789 choose_door (struct state *st) /* pick a new path */
797 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_TOP )
799 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_TOP )
801 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_TOP )
803 if ( st->maze[st->cur_sq_x][st->cur_sq_y - 1] & DOOR_IN_ANY ) {
804 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_TOP;
805 st->maze[st->cur_sq_x][st->cur_sq_y - 1] |= WALL_BOTTOM;
806 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 0, st->gc);
809 candidates[num_candidates++] = 0;
813 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_RIGHT )
815 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_RIGHT )
817 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_RIGHT )
819 if ( st->maze[st->cur_sq_x + 1][st->cur_sq_y] & DOOR_IN_ANY ) {
820 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_RIGHT;
821 st->maze[st->cur_sq_x + 1][st->cur_sq_y] |= WALL_LEFT;
822 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 1, st->gc);
825 candidates[num_candidates++] = 1;
829 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_BOTTOM )
831 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_BOTTOM )
833 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_BOTTOM )
835 if ( st->maze[st->cur_sq_x][st->cur_sq_y + 1] & DOOR_IN_ANY ) {
836 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_BOTTOM;
837 st->maze[st->cur_sq_x][st->cur_sq_y + 1] |= WALL_TOP;
838 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 2, st->gc);
841 candidates[num_candidates++] = 2;
845 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_LEFT )
847 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_LEFT )
849 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_LEFT )
851 if ( st->maze[st->cur_sq_x - 1][st->cur_sq_y] & DOOR_IN_ANY ) {
852 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_LEFT;
853 st->maze[st->cur_sq_x - 1][st->cur_sq_y] |= WALL_RIGHT;
854 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 3, st->gc);
857 candidates[num_candidates++] = 3;
860 if (num_candidates == 0)
862 if (num_candidates == 1)
863 return ( candidates[0] );
864 return ( candidates[ get_random(num_candidates) ] );
870 backup (struct state *st) /* back up a move */
873 st->cur_sq_x = st->move_list[st->sqnum].x;
874 st->cur_sq_y = st->move_list[st->sqnum].y;
875 return ( st->sqnum );
879 /****************************************************************************
881 ****************************************************************************/
883 /* draws the maze outline, and the logo */
885 draw_maze_border (struct state *st)
889 for ( i=0; i<st->maze_size_x; i++) {
890 if ( st->maze[i][0] & WALL_TOP ) {
891 XDrawLine(st->dpy, st->window, st->gc,
892 border_x + st->grid_width * i,
894 border_x + st->grid_width * (i+1) - 1,
897 if ((st->maze[i][st->maze_size_y - 1] & WALL_BOTTOM)) {
898 XDrawLine(st->dpy, st->window, st->gc,
899 border_x + st->grid_width * i,
900 border_y + st->grid_height * (st->maze_size_y) - 1,
901 border_x + st->grid_width * (i+1) - 1,
902 border_y + st->grid_height * (st->maze_size_y) - 1);
905 for ( j=0; j<st->maze_size_y; j++) {
906 if ( st->maze[st->maze_size_x - 1][j] & WALL_RIGHT ) {
907 XDrawLine(st->dpy, st->window, st->gc,
908 border_x + st->grid_width * st->maze_size_x - 1,
909 border_y + st->grid_height * j,
910 border_x + st->grid_width * st->maze_size_x - 1,
911 border_y + st->grid_height * (j+1) - 1);
913 if ( st->maze[0][j] & WALL_LEFT ) {
914 XDrawLine(st->dpy, st->window, st->gc,
916 border_y + st->grid_height * j,
918 border_y + st->grid_height * (j+1) - 1);
922 if (st->logo_x != -1)
926 unsigned int w, h, bbw, d;
928 /* round up to grid size */
929 int ww = ((st->logo_width / st->grid_width) + 1) * st->grid_width;
930 int hh = ((st->logo_height / st->grid_height) + 1) * st->grid_height;
933 XGetGeometry (st->dpy, st->logo_map, &r, &xx, &yy, &w, &h, &bbw, &d);
935 /* kludge: if the logo "hole" is around the same size as the logo,
936 don't center it (since the xscreensaver logo image is a little
937 off center... But do center it if the hole/gridsize is large. */
938 if (ww < st->logo_width + 5) ww = w;
939 if (hh < st->logo_height + 5) hh = h;
942 lx = border_x + 3 + st->grid_width * st->logo_x + ((ww - w) / 2);
943 ly = border_y + 3 + st->grid_height * st->logo_y + ((hh - h) / 2);
945 /* Fill the background of the logo box with the "unreachable" color */
946 XFillRectangle (st->dpy, st->window, st->ugc,
947 border_x + 3 + st->grid_width * st->logo_x,
948 border_y + 3 + st->grid_height * st->logo_y,
951 XSetClipOrigin (st->dpy, st->logo_gc, lx, ly);
953 XCopyPlane (st->dpy, st->logo_map, st->window, st->logo_gc,
954 0, 0, w, h, lx, ly, 1);
956 XCopyArea (st->dpy, st->logo_map, st->window, st->logo_gc,
959 draw_solid_square (st, st->start_x, st->start_y, WALL_TOP >> st->start_dir, st->tgc);
960 draw_solid_square (st, st->end_x, st->end_y, WALL_TOP >> st->end_dir, st->tgc);
964 /* Mark the maze grid as having a wall at the given coordinate,
965 and draw that wall on the screen. */
967 build_wall(struct state *st, int i, int j, int dir)
969 /* Draw it on the screen. */
970 draw_wall(st, i, j, dir, st->gc);
971 /* Put it in the maze. */
975 st->maze[i][j] |= WALL_TOP;
977 st->maze[i][j-1] |= WALL_BOTTOM;
980 st->maze[i][j] |= WALL_RIGHT;
981 if(i<st->maze_size_x-1)
982 st->maze[i+1][j] |= WALL_LEFT;
985 st->maze[i][j] |= WALL_BOTTOM;
986 if(j<st->maze_size_y-1)
987 st->maze[i][j+1] |= WALL_TOP;
990 st->maze[i][j] |= WALL_LEFT;
992 st->maze[i-1][j] |= WALL_RIGHT;
999 draw_wall(struct state *st, int i, int j, int dir, GC with_gc) /* draw a single wall */
1003 XDrawLine(st->dpy, st->window, with_gc,
1004 border_x + st->grid_width * i,
1005 border_y + st->grid_height * j,
1006 border_x + st->grid_width * (i+1),
1007 border_y + st->grid_height * j);
1010 XDrawLine(st->dpy, st->window, with_gc,
1011 border_x + st->grid_width * (i+1),
1012 border_y + st->grid_height * j,
1013 border_x + st->grid_width * (i+1),
1014 border_y + st->grid_height * (j+1));
1017 XDrawLine(st->dpy, st->window, with_gc,
1018 border_x + st->grid_width * i,
1019 border_y + st->grid_height * (j+1),
1020 border_x + st->grid_width * (i+1),
1021 border_y + st->grid_height * (j+1));
1024 XDrawLine(st->dpy, st->window, with_gc,
1025 border_x + st->grid_width * i,
1026 border_y + st->grid_height * j,
1027 border_x + st->grid_width * i,
1028 border_y + st->grid_height * (j+1));
1033 /* too slow if we sync on every wall, so only sync about ten times
1034 during the maze-creation process.
1037 if (st->sync_tick <= 0) {
1038 XSync(st->dpy, False);
1039 st->sync_tick = st->maze_size_x * st->maze_size_x / 10;
1046 draw_solid_square(struct state *st,
1048 int dir, GC with_gc)
1052 XFillRectangle(st->dpy, st->window, with_gc,
1053 border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1054 border_y - st->bw-(st->bw==0?1:0) + st->grid_height * j,
1055 st->grid_width - (st->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
1058 XFillRectangle(st->dpy, st->window, with_gc,
1059 border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1060 border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1061 st->grid_width, st->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
1064 XFillRectangle(st->dpy, st->window, with_gc,
1065 border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1066 border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1067 st->grid_width - (st->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
1070 XFillRectangle(st->dpy, st->window, with_gc,
1071 border_x - st->bw-(st->bw==0?1:0) + st->grid_width * i,
1072 border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1073 st->grid_width, st->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
1078 /****************************************************************************
1080 ****************************************************************************/
1083 longdeadend_p(struct state *st, int x1, int y1, int x2, int y2, int endwall)
1085 int dx = x2 - x1, dy = y2 - y1;
1088 sidewalls = endwall | (endwall >> 2 | endwall << 2);
1089 sidewalls = ~sidewalls & WALL_ANY;
1091 while((st->maze[x2][y2] & WALL_ANY) == sidewalls)
1093 if (x2 + dx < 0 || x2 + dx >= st->maze_size_x ||
1094 y2 + dy < 0 || y2 + dy >= st->maze_size_y)
1100 if((st->maze[x2][y2] & WALL_ANY) == (sidewalls | endwall))
1102 endwall = (endwall >> 2 | endwall << 2) & WALL_ANY;
1103 while(x1 != x2 || y1 != y2)
1107 draw_solid_square(st, x1, y1, endwall, st->sgc);
1108 st->maze[x1][y1] |= SOLVER_VISIT;
1116 /* Find all dead regions -- areas from which the goal cannot be reached --
1117 and mark them visited. */
1119 find_dead_regions(struct state *st)
1121 int xx, yy, flipped;
1123 /* Find all not SOLVER_VISIT squares bordering NOT_DEAD squares
1124 and mark them NOT_DEAD also. Repeat until no more such squares. */
1125 st->maze[st->start_x][st->start_y] |= NOT_DEAD;
1130 for(xx = 0; xx < st->maze_size_x; xx++)
1131 for(yy = 0; yy < st->maze_size_y; yy++)
1132 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1133 && ( (xx && (st->maze[xx-1][yy] & NOT_DEAD))
1134 || (yy && (st->maze[xx][yy-1] & NOT_DEAD))))
1137 st->maze[xx][yy] |= NOT_DEAD;
1139 for(xx = st->maze_size_x-1; xx >= 0; xx--)
1140 for(yy = st->maze_size_y-1; yy >= 0; yy--)
1141 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1142 && ( (xx != st->maze_size_x-1 && (st->maze[xx+1][yy] & NOT_DEAD))
1143 || (yy != st->maze_size_y-1 && (st->maze[xx][yy+1] & NOT_DEAD))))
1146 st->maze[xx][yy] |= NOT_DEAD;
1151 for (yy = 0; yy < st->maze_size_y; yy++)
1152 for (xx = 0; xx < st->maze_size_x; xx++)
1154 if (st->maze[xx][yy] & NOT_DEAD)
1155 st->maze[xx][yy] &= ~NOT_DEAD;
1156 else if (!(st->maze[xx][yy] & SOLVER_VISIT))
1158 st->maze[xx][yy] |= SOLVER_VISIT;
1159 if((xx < st->logo_x || xx > st->logo_x + st->logo_width / st->grid_width) ||
1160 (yy < st->logo_y || yy > st->logo_y + st->logo_height / st->grid_height))
1162 /* if we are completely surrounded by walls, just draw the
1164 if ((st->maze[xx][yy] & WALL_ANY) == WALL_ANY)
1165 XFillRectangle(st->dpy, st->window, st->ugc,
1166 border_x + st->bw + st->grid_width * xx,
1167 border_y + st->bw + st->grid_height * yy,
1168 st->grid_width - (st->bw+st->bw), st->grid_height - (st->bw+st->bw));
1171 if (! (st->maze[xx][yy] & WALL_LEFT))
1172 draw_solid_square(st, xx, yy, WALL_LEFT, st->ugc);
1173 if (! (st->maze[xx][yy] & WALL_RIGHT))
1174 draw_solid_square(st, xx, yy, WALL_RIGHT, st->ugc);
1175 if (! (st->maze[xx][yy] & WALL_TOP))
1176 draw_solid_square(st, xx, yy, WALL_TOP, st->ugc);
1177 if (! (st->maze[xx][yy] & WALL_BOTTOM))
1178 draw_solid_square(st, xx, yy, WALL_BOTTOM, st->ugc);
1185 /* solve the maze by one more tick */
1187 solve_maze (struct state *st)
1189 struct solve_state *ss = st->solve_state;
1191 ss = st->solve_state = (struct solve_state *) calloc (1, sizeof(*ss));
1194 /* plug up the surrounding wall */
1195 st->maze[st->end_x][st->end_y] |= (WALL_TOP >> st->end_dir);
1197 /* initialize search path */
1199 st->path[ss->i].x = st->end_x;
1200 st->path[ss->i].y = st->end_y;
1201 st->path[ss->i].dir = 0;
1202 st->maze[st->end_x][st->end_y] |= SOLVER_VISIT;
1210 int dir, from, ways;
1212 if ( st->maze[st->path[ss->i].x][st->path[ss->i].y] & START_SQUARE )
1218 if(!st->path[ss->i].dir)
1221 /* First visit this square. Which adjacent squares are open? */
1222 for(dir = WALL_TOP; dir & WALL_ANY; dir >>= 1)
1224 if(st->maze[st->path[ss->i].x][st->path[ss->i].y] & dir)
1227 ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1228 ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1230 if(st->maze[ss->x][ss->y] & SOLVER_VISIT)
1233 from = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1234 /* don't enter obvious dead ends */
1235 if(((st->maze[ss->x][ss->y] & WALL_ANY) | from) != WALL_ANY)
1237 if(!longdeadend_p(st, st->path[ss->i].x, st->path[ss->i].y, ss->x, ss->y, dir))
1242 draw_solid_square(st, ss->x, ss->y, from, st->sgc);
1243 st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1248 ways = st->path[ss->i].ways;
1249 /* ways now has a bitmask of open paths. */
1254 if (!st->ignorant_p)
1256 ss->x = st->path[ss->i].x - st->start_x;
1257 ss->y = st->path[ss->i].y - st->start_y;
1259 if(abs(ss->y) <= abs(ss->x))
1260 dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1262 dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM;
1272 dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM; break;
1275 dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1283 dir = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1298 else if(ways&WALL_LEFT)
1300 else if(ways&WALL_BOTTOM)
1302 else if(ways&WALL_RIGHT)
1308 ways &= ~dir; /* tried this one */
1310 ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1311 ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1313 /* advance in direction dir */
1314 st->path[ss->i].dir = dir;
1315 st->path[ss->i].ways = ways;
1316 draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, dir, st->tgc);
1319 st->path[ss->i].dir = 0;
1320 st->path[ss->i].ways = 0;
1321 st->path[ss->i].x = ss->x;
1322 st->path[ss->i].y = ss->y;
1323 st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1330 printf("Unsolvable maze.\n");
1335 if(!ss->bt && !st->ignorant_p)
1336 find_dead_regions(st);
1338 from = st->path[ss->i-1].dir;
1339 from = (from << 2 & WALL_ANY) | (from >> 2 & WALL_ANY);
1341 draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, from, st->cgc);
1349 /****************************************************************************
1350 XScreenSaver boilerplate: resources, command line options, and main loop.
1351 ****************************************************************************/
1353 static const char *maze_defaults[] = {
1354 ".background: black",
1355 ".foreground: white",
1362 "*solveDelay: 10000",
1363 "*preDelay: 2000000",
1364 "*postDelay: 4000000",
1366 "*liveColor: #00FF00",
1367 "*deadColor: #880000",
1368 "*skipColor: #8B5A00",
1369 "*surroundColor: #220055",
1374 static XrmOptionDescRec maze_options[] = {
1375 { "-ignorant", ".ignorant", XrmoptionNoArg, "True" },
1376 { "-no-ignorant", ".ignorant", XrmoptionNoArg, "False" },
1377 { "-grid-size", ".gridSize", XrmoptionSepArg, 0 },
1378 { "-solve-delay", ".solveDelay", XrmoptionSepArg, 0 },
1379 { "-pre-delay", ".preDelay", XrmoptionSepArg, 0 },
1380 { "-post-delay", ".postDelay", XrmoptionSepArg, 0 },
1381 { "-bg-color", ".background", XrmoptionSepArg, 0 },
1382 { "-fg-color", ".foreground", XrmoptionSepArg, 0 },
1383 { "-live-color", ".liveColor", XrmoptionSepArg, 0 },
1384 { "-dead-color", ".deadColor", XrmoptionSepArg, 0 },
1385 { "-skip-color", ".skipColor", XrmoptionSepArg, 0 },
1386 { "-surround-color", ".surroundColor",XrmoptionSepArg, 0 },
1387 { "-generator", ".generator", XrmoptionSepArg, 0 },
1388 { "-max-length", ".maxLength", XrmoptionSepArg, 0 },
1392 static int generator = 0;
1395 maze_init (Display *dpy_arg, Window window_arg)
1397 struct state *st = (struct state *) calloc (1, sizeof(*st));
1399 XWindowAttributes xgwa;
1400 unsigned long bg, fg, pfg, pbg, sfg, ufg;
1403 st->window = window_arg;
1412 size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1413 st->solve_delay = get_integer_resource (st->dpy, "solveDelay", "Integer");
1414 st->pre_solve_delay = get_integer_resource (st->dpy, "preDelay", "Integer");
1415 st->post_solve_delay = get_integer_resource (st->dpy, "postDelay", "Integer");
1416 generator = get_integer_resource(st->dpy, "generator", "Integer");
1417 st->max_length = get_integer_resource(st->dpy, "maxLength", "Integer");
1418 st->ignorant_p = get_boolean_resource(st->dpy, "ignorant", "Boolean");
1420 if (get_boolean_resource (st->dpy, "doFPS", "DoFPS"))
1422 /* Just guess, rather than loading and measuring the "fpsFont"... */
1423 st->fps_width = 210;
1424 st->fps_height = 62;
1427 if (!size) st->ifrandom = 1;
1429 if (size < 2) size = 7 + (random () % 30);
1430 st->grid_width = st->grid_height = size;
1431 st->bw = (size > 6 ? 3 : (size-1)/2);
1433 XGetWindowAttributes (st->dpy, st->window, &xgwa);
1438 set_maze_sizes (st, xgwa.width, xgwa.height);
1440 st->gc = XCreateGC(st->dpy, st->window, 0, 0);
1441 st->cgc = XCreateGC(st->dpy, st->window, 0, 0);
1442 st->tgc = XCreateGC(st->dpy, st->window, 0, 0);
1443 st->sgc = XCreateGC(st->dpy, st->window, 0, 0);
1444 st->ugc = XCreateGC(st->dpy, st->window, 0, 0);
1445 st->logo_gc = XCreateGC(st->dpy, st->window, 0, 0);
1446 st->erase_gc = XCreateGC(st->dpy, st->window, 0, 0);
1448 bg = get_pixel_resource (st->dpy, xgwa.colormap, "background","Background");
1449 fg = get_pixel_resource (st->dpy, xgwa.colormap, "foreground","Foreground");
1450 pfg = get_pixel_resource (st->dpy, xgwa.colormap, "liveColor", "Foreground");
1451 pbg = get_pixel_resource (st->dpy, xgwa.colormap, "deadColor", "Foreground");
1452 sfg = get_pixel_resource (st->dpy, xgwa.colormap, "skipColor", "Foreground");
1453 ufg = get_pixel_resource (st->dpy, xgwa.colormap, "surroundColor", "Foreground");
1455 XSetForeground (st->dpy, st->gc, fg);
1456 XSetBackground (st->dpy, st->gc, bg);
1457 XSetForeground (st->dpy, st->cgc, pbg);
1458 XSetBackground (st->dpy, st->cgc, bg);
1459 XSetForeground (st->dpy, st->tgc, pfg);
1460 XSetBackground (st->dpy, st->tgc, bg);
1461 XSetForeground (st->dpy, st->sgc, sfg);
1462 XSetBackground (st->dpy, st->sgc, bg);
1463 XSetForeground (st->dpy, st->ugc, ufg);
1464 XSetBackground (st->dpy, st->ugc, bg);
1465 XSetForeground (st->dpy, st->logo_gc, fg);
1466 XSetBackground (st->dpy, st->logo_gc, bg);
1467 XSetForeground (st->dpy, st->erase_gc, bg);
1468 XSetBackground (st->dpy, st->erase_gc, bg);
1473 unsigned int w, h, bbw, d;
1474 unsigned long *pixels;
1476 Pixmap logo_mask = 0;
1477 st->logo_map = xscreensaver_logo (xgwa.screen, xgwa.visual, st->window,
1479 &pixels, &npixels, &logo_mask,
1482 XSetClipMask (st->dpy, st->logo_gc, logo_mask);
1483 XFreePixmap (st->dpy, logo_mask);
1485 if (pixels) free (pixels);
1486 XGetGeometry (st->dpy, st->logo_map, &r, &x, &y, &w, &h, &bbw, &d);
1488 st->logo_height = h;
1500 maze_reshape (Display *dpy, Window window, void *closure,
1501 unsigned int w, unsigned int h)
1503 struct state *st = (struct state *) closure;
1508 static unsigned long
1509 maze_draw (Display *dpy, Window window, void *closure)
1511 struct state *st = (struct state *) closure;
1512 int this_delay = st->solve_delay;
1514 if (st->eraser || st->erase_window)
1516 st->erase_window = 0;
1517 st->eraser = erase_window (st->dpy, st->window, st->eraser);
1521 this_delay = 1000000;
1522 if (this_delay > st->pre_solve_delay)
1523 this_delay = st->pre_solve_delay;
1528 if (st->restart || st->stop) goto pop;
1529 switch (st->state) {
1531 initialize_maze(st);
1532 if (st->ifrandom && st->ifinit)
1535 size = 7 + (random () % 30);
1536 st->grid_width = st->grid_height = size;
1537 st->bw = (size > 6 ? 3 : (size-1)/2);
1543 XClearWindow(st->dpy, st->window);
1544 draw_maze_border(st);
1547 st->this_gen = generator;
1548 if(st->this_gen<0 || st->this_gen>2)
1549 st->this_gen = random()%3;
1551 switch(st->this_gen)
1557 alt_create_maze(st);
1560 set_create_maze(st);
1565 this_delay = st->pre_solve_delay;
1568 if (! solve_maze(st))
1569 --st->state; /* stay in state 5 */
1572 st->erase_window = 1;
1573 this_delay = st->post_solve_delay;
1584 XWindowAttributes xgwa;
1591 st->sync_p = ((random() % 4) != 0);
1593 size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1594 if (size < 2) size = 7 + (random () % 30);
1595 st->grid_width = st->grid_height = size;
1596 st->bw = (size > 6 ? 3 : (size-1)/2);
1598 XGetWindowAttributes (st->dpy, st->window, &xgwa);
1599 set_maze_sizes (st, xgwa.width, xgwa.height);
1608 maze_event (Display *dpy, Window window, void *closure, XEvent *event)
1610 struct state *st = (struct state *) closure;
1611 switch (event->type)
1614 switch (event->xbutton.button)
1617 st->stop = !st->stop ;
1618 if (st->state == 5) st->state = 4 ;
1644 maze_free (Display *dpy, Window window, void *closure)
1646 struct state *st = (struct state *) closure;
1650 XSCREENSAVER_MODULE ("Maze", maze)