1 /******************************************************************************
4 * modified: [ 1-04-00 ] Johannes Keukelaar <johannes@nada.kth.se>
5 * Added -ignorant option (not the default) to remove knowlege
6 * of the direction in which the exit lies.
8 * modified: [ 6-28-98 ] Zack Weinberg <zack@rabi.phys.columbia.edu>
10 * Made the maze-solver somewhat more intelligent. There are
11 * three optimizations:
13 * - Straight-line lookahead: the solver does not enter dead-end
14 * corridors. This is a win with all maze generators.
16 * - First order direction choice: the solver knows where the
17 * exit is in relation to itself, and will try paths leading in
18 * that direction first. This is a major win on maze generator 1
19 * which tends to offer direct routes to the exit.
21 * - Dead region elimination: the solver already has a map of
22 * all squares visited. Whenever it starts to backtrack, it
23 * consults this map and marks off all squares that cannot be
24 * reached from the exit without crossing a square already
25 * visited. Those squares can never contribute to the path to
26 * the exit, so it doesn't bother checking them. This helps a
27 * lot with maze generator 2 and somewhat less with generator 1.
29 * Further improvements would require knowledge of the wall map
30 * as well as the position of the exit and the squares visited.
31 * I would consider that to be cheating. Generator 0 makes
32 * mazes which are remarkably difficult to solve mechanically --
33 * even with these optimizations the solver generally must visit
34 * at least two-thirds of the squares. This is partially
35 * because generator 0's mazes have longer paths to the exit.
37 * modified: [ 4-10-97 ] Johannes Keukelaar <johannes@nada.kth.se>
38 * Added multiple maze creators. Robustified solver.
39 * Added bridge option.
40 * modified: [ 8-11-95 ] Ed James <james@mml.mmc.com>
41 * added fill of dead-end box to solve_maze while loop.
42 * modified: [ 3-7-93 ] Jamie Zawinski <jwz@jwz.org>
43 * added the XRoger logo, cleaned up resources, made
44 * grid size a parameter.
45 * modified: [ 3-3-93 ] Jim Randell <jmr@mddjmr.fc.hp.com>
46 * Added the colour stuff and integrated it with jwz's
47 * screenhack stuff. There's still some work that could
48 * be done on this, particularly allowing a resource to
49 * specify how big the squares are.
50 * modified: [ 10-4-88 ] Richard Hess ...!uunet!cimshop!rhess
51 * [ Revised primary execution loop within main()...
52 * [ Extended X event handler, check_events()...
53 * modified: [ 1-29-88 ] Dave Lemke lemke@sun.com
55 * [ Note the word "hacked" -- this is extremely ugly, but at
56 * [ least it does the job. NOT a good programming example
58 * original: [ 6/21/85 ] Martin Weiss Sun Microsystems [ SunView ]
60 ******************************************************************************
61 Copyright 1988 by Sun Microsystems, Inc. Mountain View, CA.
65 Permission to use, copy, modify, and distribute this software and its
66 documentation for any purpose and without fee is hereby granted,
67 provided that the above copyright notice appear in all copies and that
68 both that copyright notice and this permission notice appear in
69 supporting documentation, and that the names of Sun or MIT not be
70 used in advertising or publicity pertaining to distribution of the
71 software without specific prior written permission. Sun and M.I.T.
72 make no representations about the suitability of this software for
73 any purpose. It is provided "as is" without any express or implied warranty.
75 SUN DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
76 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
77 PURPOSE. IN NO EVENT SHALL SUN BE LIABLE FOR ANY SPECIAL, INDIRECT
78 OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
79 OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
80 OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE
81 OR PERFORMANCE OF THIS SOFTWARE.
82 *****************************************************************************/
84 #include "screenhack.h"
89 /* #include <X11/bitmaps/gray1> */
91 #define gray1_height 2
92 static const char gray1_bits[] = { 0x01, 0x02 };
95 #define MAX_MAZE_SIZE_X 1000
96 #define MAX_MAZE_SIZE_Y 1000
98 #define MOVE_LIST_SIZE (MAX_MAZE_SIZE_X * MAX_MAZE_SIZE_Y)
100 #define NOT_DEAD 0x8000
101 #define SOLVER_VISIT 0x4000
102 #define START_SQUARE 0x2000
103 #define END_SQUARE 0x1000
106 #define WALL_RIGHT 0x4
107 #define WALL_BOTTOM 0x2
108 #define WALL_LEFT 0x1
111 #define DOOR_IN_TOP 0x800
112 #define DOOR_IN_RIGHT 0x400
113 #define DOOR_IN_BOTTOM 0x200
114 #define DOOR_IN_LEFT 0x100
115 #define DOOR_IN_ANY 0xF00
117 #define DOOR_OUT_TOP 0x80
118 #define DOOR_OUT_RIGHT 0x40
119 #define DOOR_OUT_BOTTOM 0x20
120 #define DOOR_OUT_LEFT 0x10
126 #define get_random(x) (random() % (x))
129 struct move_list_struct {
132 unsigned char dir, ways;
145 GC gc, cgc, tgc, sgc, ugc, logo_gc, erase_gc;
147 int logo_width, logo_height; /* in pixels */
149 int solve_delay, pre_solve_delay, post_solve_delay;
152 unsigned short maze[MAX_MAZE_SIZE_X][MAX_MAZE_SIZE_Y];
154 struct move_list_struct move_list[MOVE_LIST_SIZE];
155 struct move_list_struct save_path[MOVE_LIST_SIZE];
156 struct move_list_struct path[MOVE_LIST_SIZE];
158 int maze_size_x, maze_size_y;
159 int sqnum, cur_sq_x, cur_sq_y, path_length;
160 int start_x, start_y, start_dir, end_x, end_y, end_dir;
161 int grid_width, grid_height;
164 int x, y, restart, stop, state, max_length;
165 int sync_p, sync_tick;
166 int bridge_p, ignorant_p;
168 struct solve_state *solve_state;
170 int *sets; /* The sets that our squares are in. */
171 int *hedges; /* The `list' of hedges. */
175 eraser_state *eraser;
184 set_maze_sizes (struct state *st, int width, int height)
186 st->maze_size_x = width / st->grid_width;
187 st->maze_size_y = height / st->grid_height;
189 if (st->maze_size_x < 4) st->maze_size_x = 4;
190 if (st->maze_size_y < 4) st->maze_size_y = 4;
195 initialize_maze (struct state *st) /* draw the surrounding wall and start/end squares */
197 register int i, j, wall;
198 int logow = 1 + st->logo_width / st->grid_width;
199 int logoh = 1 + st->logo_height / st->grid_height;
201 /* initialize all squares */
202 for ( i=0; i<st->maze_size_x; i++) {
203 for ( j=0; j<st->maze_size_y; j++) {
209 for ( i=0; i<st->maze_size_x; i++ ) {
210 st->maze[i][0] |= WALL_TOP;
214 for ( j=0; j<st->maze_size_y; j++ ) {
215 st->maze[st->maze_size_x-1][j] |= WALL_RIGHT;
219 for ( i=0; i<st->maze_size_x; i++ ) {
220 st->maze[i][st->maze_size_y-1] |= WALL_BOTTOM;
224 for ( j=0; j<st->maze_size_y; j++ ) {
225 st->maze[0][j] |= WALL_LEFT;
228 /* set start square */
229 wall = get_random(4);
232 i = get_random(st->maze_size_x);
236 i = st->maze_size_x - 1;
237 j = get_random(st->maze_size_y);
240 i = get_random(st->maze_size_x);
241 j = st->maze_size_y - 1;
245 j = get_random(st->maze_size_y);
248 st->maze[i][j] |= START_SQUARE;
249 st->maze[i][j] |= ( DOOR_IN_TOP >> wall );
250 st->maze[i][j] &= ~( WALL_TOP >> wall );
255 st->start_dir = wall;
262 i = get_random(st->maze_size_x);
266 i = st->maze_size_x - 1;
267 j = get_random(st->maze_size_y);
270 i = get_random(st->maze_size_x);
271 j = st->maze_size_y - 1;
275 j = get_random(st->maze_size_y);
278 st->maze[i][j] |= END_SQUARE;
279 st->maze[i][j] |= ( DOOR_OUT_TOP >> wall );
280 st->maze[i][j] &= ~( WALL_TOP >> wall );
286 if ((st->maze_size_x-logow >= 6) && (st->maze_size_y-logoh >= 6))
288 /* not closer than 3 grid units from a wall */
289 st->logo_x = get_random (st->maze_size_x - logow - 5) + 3;
290 st->logo_y = get_random (st->maze_size_y - logoh - 5) + 3;
291 for (i=0; i<logow; i++)
292 for (j=0; j<logoh; j++)
293 st->maze[st->logo_x + i][st->logo_y + j] |= DOOR_IN_TOP;
296 st->logo_y = st->logo_x = -1;
299 static int choose_door (struct state *st);
300 static int backup (struct state *st);
301 static void draw_wall (struct state *, int, int, int, GC);
302 static void draw_solid_square (struct state *, int, int, int, GC);
303 /*static void enter_square (struct state *, int);*/
304 static void build_wall (struct state *, int, int, int);
305 /*static void break_wall (struct state *, int, int, int);*/
307 static void join_sets(struct state *, int, int);
311 /* Initialise the sets. */
313 init_sets(struct state *st)
319 st->sets = (int *)malloc(st->maze_size_x*st->maze_size_y*sizeof(int));
322 for(i = 0; i < st->maze_size_x*st->maze_size_y; i++)
329 st->hedges = (int *)malloc(st->maze_size_x*st->maze_size_y*2*sizeof(int));
332 for(i = 0; i < st->maze_size_x*st->maze_size_y*2; i++)
336 /* Mask out outside walls. */
337 for(i = 0; i < st->maze_size_y; i++)
339 st->hedges[2*((st->maze_size_x)*i+st->maze_size_x-1)+1] = -1;
341 for(i = 0; i < st->maze_size_x; i++)
343 st->hedges[2*((st->maze_size_y-1)*st->maze_size_x+i)] = -1;
345 /* Mask out a possible logo. */
348 int logow = 1 + st->logo_width / st->grid_width;
349 int logoh = 1 + st->logo_height / st->grid_height;
350 int bridge_dir, bridge_c;
352 if(st->bridge_p && logoh>=3 && logow>=3)
354 bridge_dir = 1+random()%2;
357 bridge_c = st->logo_y+random()%(logoh-2)+1;
361 bridge_c = st->logo_x+random()%(logow-2)+1;
370 for(xx = st->logo_x; xx < st->logo_x+logow; xx++)
371 for(yy = st->logo_y; yy < st->logo_y+logoh; yy++)
373 /* I should check for the bridge here, except that I join the
374 * bridge together below.
376 st->hedges[2*(xx+st->maze_size_x*yy)+1] = -1;
377 st->hedges[2*(xx+st->maze_size_x*yy)] = -1;
379 for(xx = st->logo_x; xx < st->logo_x+logow; xx++)
381 if(!(bridge_dir==2 && xx==bridge_c))
383 build_wall(st, xx, st->logo_y, 0);
384 build_wall(st, xx, st->logo_y+logoh, 0);
386 st->hedges[2*(xx+st->maze_size_x*(st->logo_y-1))] = -1;
389 build_wall(st, xx, bridge_c, 0);
390 build_wall(st, xx, bridge_c, 2);
393 for(yy = st->logo_y; yy < st->logo_y+logoh; yy++)
395 if(!(bridge_dir==1 && yy==bridge_c))
397 build_wall(st, st->logo_x, yy, 3);
398 build_wall(st, st->logo_x+logow, yy, 3);
400 st->hedges[2*(st->logo_x-1+st->maze_size_x*yy)+1] = -1;
403 build_wall(st, bridge_c, yy, 1);
404 build_wall(st, bridge_c, yy, 3);
407 /* Join the whole bridge together. */
414 for(i = st->logo_x; i < st->logo_x+logow+1; i++)
415 join_sets(st, xx+yy*st->maze_size_x, i+yy*st->maze_size_x);
421 for(i = st->logo_y; i < st->logo_y+logoh+1; i++)
422 join_sets(st, xx+yy*st->maze_size_x, xx+i*st->maze_size_x);
427 for(i = 0; i < st->maze_size_x*st->maze_size_y*2; i++)
430 r = random()%(st->maze_size_x*st->maze_size_y*2);
431 st->hedges[i] = st->hedges[r];
436 /* Get the representative of a set. */
438 get_set(struct state *st, int num)
442 if(st->sets[num]==num)
446 s = get_set(st, st->sets[num]);
452 /* Join two sets together. */
454 join_sets(struct state *st, int num1, int num2)
458 s1 = get_set(st, num1);
459 s2 = get_set(st, num2);
467 /* Exitialise the sets. */
469 exit_sets(struct state *st)
480 /* Temporary hack. */
482 show_set(int num, GC gc)
484 int st->x, st->y, set;
488 for(st->x = 0; st->x < st->maze_size_x; st->x++)
489 for(st->y = 0; st->y < st->maze_size_y; st->y++)
491 if(get_set(st->x+st->y*st->maze_size_x)==set)
493 XFillRectangle(st->dpy, st->window, st->gc, border_x + st->bw + st->grid_width * st->x,
494 border_y + st->bw + st->grid_height * st->y,
495 st->grid_width-2*st->bw , st->grid_height-2*st->bw);
501 /* Second alternative maze creator: Put each square in the maze in a
502 * separate set. Also, make a list of all the hedges. Randomize that list.
503 * Walk through the list. If, for a certain hedge, the two squares on both
504 * sides of it are in different sets, union the sets and remove the hedge.
505 * Continue until all hedges have been processed or only one set remains.
508 set_create_maze(struct state *st)
510 int i, h, xx, yy, dir, v, w;
516 /* Do almost all the setup. */
519 /* Start running through the hedges. */
520 for(i = 0; i < 2*st->maze_size_x*st->maze_size_y; i++)
524 /* This one is in the logo or outside border. */
529 xx = (h>>1)%st->maze_size_x;
530 yy = (h>>1)/st->maze_size_x;
545 show_set(st, xx+yy*st->maze_size_x, st->logo_gc);
546 show_set(st, v+w*st->maze_size_x, st->tgc);
548 if(get_set(st, xx+yy*st->maze_size_x)!=get_set(st, v+w*st->maze_size_x))
553 join_sets(st, xx+yy*st->maze_size_x, v+w*st->maze_size_x);
554 /* Don't draw the wall. */
561 /* Don't join the sets. */
562 build_wall(st, xx, yy, dir);
567 XSync(st->dpy, False);
572 show_set(xx+yy*st->maze_size_x, st->erase_gc);
573 show_set(v+w*st->maze_size_x, st->erase_gc);
577 /* Free some memory. */
581 /* First alternative maze creator: Pick a random, empty corner in the maze.
582 * Pick a random direction. Draw a wall in that direction, from that corner
583 * until we hit a wall. Option: Only draw the wall if it's going to be
584 * shorter than a certain length. Otherwise we get lots of long walls.
587 alt_create_maze(struct state *st)
591 int i, j, height, width, open_corners, k, dir, xx, yy;
593 height = st->maze_size_y+1;
594 width = st->maze_size_x+1;
596 /* Allocate and clear some mem. */
597 corners = (char *)calloc(height*width, 1);
601 /* Set up the indexing array. */
602 c_idx = (int *)malloc(sizeof(int)*height*width);
608 for(i = 0; i < height*width; i++)
610 for(i = 0; i < height*width; i++)
613 k = random()%(height*width);
618 /* Set up some initial walls. */
620 for(i = 0; i < width; i++)
623 corners[i+width*(height-1)] = 1;
625 for(i = 0; i < height; i++)
627 corners[i*width] = 1;
628 corners[i*width+width-1] = 1;
630 /* Walls around logo. In fact, inside the logo, too. */
631 /* Also draw the walls. */
634 int logow = 1 + st->logo_width / st->grid_width;
635 int logoh = 1 + st->logo_height / st->grid_height;
636 int bridge_dir, bridge_c;
638 if(st->bridge_p && logoh>=3 && logow>=3)
640 bridge_dir = 1+random()%2;
643 bridge_c = st->logo_y+random()%(logoh-2)+1;
647 bridge_c = st->logo_x+random()%(logow-2)+1;
655 for(i = st->logo_x; i <= st->logo_x + logow; i++)
657 for(j = st->logo_y; j <= st->logo_y + logoh; j++)
659 corners[i+width*j] = 1;
662 for(xx = st->logo_x; xx < st->logo_x+logow; xx++)
664 if(!(bridge_dir==2 && xx==bridge_c))
666 build_wall(st, xx, st->logo_y, 0);
667 build_wall(st, xx, st->logo_y+logoh, 0);
671 build_wall(st, xx, bridge_c, 0);
672 build_wall(st, xx, bridge_c, 2);
675 for(yy = st->logo_y; yy < st->logo_y+logoh; yy++)
677 if(!(bridge_dir==1 && yy==bridge_c))
679 build_wall(st, st->logo_x, yy, 3);
680 build_wall(st, st->logo_x+logow, yy, 3);
684 build_wall(st, bridge_c, yy, 1);
685 build_wall(st, bridge_c, yy, 3);
688 /* Connect one wall of the logo with an outside wall. */
690 dir = (bridge_dir+1)%4;
696 xx = st->logo_x+(random()%(logow+1));
700 xx = st->logo_x+logow;
701 yy = st->logo_y+(random()%(logoh+1));
704 xx = st->logo_x+(random()%(logow+1));
705 yy = st->logo_y+logoh;
709 yy = st->logo_y+(random()%(logoh+1));
714 corners[xx+width*yy] = 1;
718 build_wall(st, xx-1, yy-1, 1);
722 build_wall(st, xx, yy, 0);
726 build_wall(st, xx, yy, 3);
730 build_wall(st, xx-1, yy-1, 2);
735 while(!corners[xx+width*yy]);
742 xx = st->logo_x+(random()%(logow+1));
746 xx = st->logo_x+logow;
747 yy = st->logo_y+(random()%(logoh+1));
750 xx = st->logo_x+(random()%(logow+1));
751 yy = st->logo_y+logoh;
755 yy = st->logo_y+(random()%(logoh+1));
760 corners[xx+width*yy] = 1;
764 build_wall(st, xx-1, yy-1, 1);
768 build_wall(st, xx, yy, 0);
772 build_wall(st, xx, yy, 3);
776 build_wall(st, xx-1, yy-1, 2);
781 while(!corners[xx+width*yy]);
785 /* Count open gridpoints. */
787 for(i = 0; i < width; i++)
788 for(j = 0; j < height; j++)
789 if(!corners[i+width*j])
792 /* Now do actual maze generation. */
793 while(open_corners>0)
795 for(i = 0; i < width*height; i++)
797 if(!corners[c_idx[i]])
801 /* Choose a random direction. */
805 /* Measure the length of the wall we'd draw. */
806 while(!corners[xx+width*yy])
826 if(k<=st->max_length)
831 /* Draw a wall until we hit something. */
832 while(!corners[xx+width*yy])
835 corners[xx+width*yy] = 1;
839 build_wall(st, xx-1, yy-1, 1);
843 build_wall(st, xx, yy, 0);
847 build_wall(st, xx, yy, 3);
851 build_wall(st, xx-1, yy-1, 2);
861 /* Free some memory we used. */
866 /* The original maze creator. Start somewhere. Take a step in a random
867 * direction. Keep doing this until we hit a wall. Then, backtrack until
868 * we find a point where we can go in another direction.
871 create_maze (struct state *st) /* create a maze layout given the initialized maze */
873 register int i, newdoor = 0;
874 int logow = 1 + st->logo_width / st->grid_width;
875 int logoh = 1 + st->logo_height / st->grid_height;
877 /* Maybe we should make a bridge? */
878 if(st->bridge_p && st->logo_x >= 0 && logow>=3 && logoh>=3)
880 int bridge_dir, bridge_c;
882 bridge_dir = 1+random()%2;
886 bridge_c = st->logo_y+random()%(logoh-2)+1;
888 bridge_c = st->logo_y+random()%logoh;
893 bridge_c = st->logo_x+random()%(logow-2)+1;
895 bridge_c = st->logo_x+random()%logow;
900 for(i = st->logo_x; i < st->logo_x+logow; i++)
902 st->maze[i][bridge_c] &= ~DOOR_IN_TOP;
907 for(i = st->logo_y; i < st->logo_y+logoh; i++)
909 st->maze[bridge_c][i] &= ~DOOR_IN_TOP;
915 st->move_list[st->sqnum].x = st->cur_sq_x;
916 st->move_list[st->sqnum].y = st->cur_sq_y;
917 st->move_list[st->sqnum].dir = newdoor;
918 while ( ( newdoor = choose_door(st) ) == -1 ) { /* pick a door */
919 if ( backup(st) == -1 ) { /* no more doors ... backup */
920 return; /* done ... return */
924 /* mark the out door */
925 st->maze[st->cur_sq_x][st->cur_sq_y] |= ( DOOR_OUT_TOP >> newdoor );
928 case 0: st->cur_sq_y--;
930 case 1: st->cur_sq_x++;
932 case 2: st->cur_sq_y++;
934 case 3: st->cur_sq_x--;
939 /* mark the in door */
940 st->maze[st->cur_sq_x][st->cur_sq_y] |= ( DOOR_IN_TOP >> ((newdoor+2)%4) );
942 /* if end square set path length and save path */
943 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & END_SQUARE ) {
944 st->path_length = st->sqnum;
945 for ( i=0; i<st->path_length; i++) {
946 st->save_path[i].x = st->move_list[i].x;
947 st->save_path[i].y = st->move_list[i].y;
948 st->save_path[i].dir = st->move_list[i].dir;
958 choose_door (struct state *st) /* pick a new path */
961 register int num_candidates;
966 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_TOP )
968 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_TOP )
970 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_TOP )
972 if ( st->maze[st->cur_sq_x][st->cur_sq_y - 1] & DOOR_IN_ANY ) {
973 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_TOP;
974 st->maze[st->cur_sq_x][st->cur_sq_y - 1] |= WALL_BOTTOM;
975 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 0, st->gc);
978 candidates[num_candidates++] = 0;
982 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_RIGHT )
984 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_RIGHT )
986 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_RIGHT )
988 if ( st->maze[st->cur_sq_x + 1][st->cur_sq_y] & DOOR_IN_ANY ) {
989 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_RIGHT;
990 st->maze[st->cur_sq_x + 1][st->cur_sq_y] |= WALL_LEFT;
991 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 1, st->gc);
994 candidates[num_candidates++] = 1;
998 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_BOTTOM )
1000 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_BOTTOM )
1002 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_BOTTOM )
1004 if ( st->maze[st->cur_sq_x][st->cur_sq_y + 1] & DOOR_IN_ANY ) {
1005 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_BOTTOM;
1006 st->maze[st->cur_sq_x][st->cur_sq_y + 1] |= WALL_TOP;
1007 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 2, st->gc);
1010 candidates[num_candidates++] = 2;
1014 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_LEFT )
1016 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_LEFT )
1018 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_LEFT )
1020 if ( st->maze[st->cur_sq_x - 1][st->cur_sq_y] & DOOR_IN_ANY ) {
1021 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_LEFT;
1022 st->maze[st->cur_sq_x - 1][st->cur_sq_y] |= WALL_RIGHT;
1023 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 3, st->gc);
1026 candidates[num_candidates++] = 3;
1029 if (num_candidates == 0)
1031 if (num_candidates == 1)
1032 return ( candidates[0] );
1033 return ( candidates[ get_random(num_candidates) ] );
1039 backup (struct state *st) /* back up a move */
1042 st->cur_sq_x = st->move_list[st->sqnum].x;
1043 st->cur_sq_y = st->move_list[st->sqnum].y;
1044 return ( st->sqnum );
1049 draw_maze_border (struct state *st) /* draw the maze outline */
1054 for ( i=0; i<st->maze_size_x; i++) {
1055 if ( st->maze[i][0] & WALL_TOP ) {
1056 XDrawLine(st->dpy, st->window, st->gc,
1057 border_x + st->grid_width * i,
1059 border_x + st->grid_width * (i+1) - 1,
1062 if ((st->maze[i][st->maze_size_y - 1] & WALL_BOTTOM)) {
1063 XDrawLine(st->dpy, st->window, st->gc,
1064 border_x + st->grid_width * i,
1065 border_y + st->grid_height * (st->maze_size_y) - 1,
1066 border_x + st->grid_width * (i+1) - 1,
1067 border_y + st->grid_height * (st->maze_size_y) - 1);
1070 for ( j=0; j<st->maze_size_y; j++) {
1071 if ( st->maze[st->maze_size_x - 1][j] & WALL_RIGHT ) {
1072 XDrawLine(st->dpy, st->window, st->gc,
1073 border_x + st->grid_width * st->maze_size_x - 1,
1074 border_y + st->grid_height * j,
1075 border_x + st->grid_width * st->maze_size_x - 1,
1076 border_y + st->grid_height * (j+1) - 1);
1078 if ( st->maze[0][j] & WALL_LEFT ) {
1079 XDrawLine(st->dpy, st->window, st->gc,
1081 border_y + st->grid_height * j,
1083 border_y + st->grid_height * (j+1) - 1);
1087 if (st->logo_x != -1)
1091 unsigned int w, h, bbw, d;
1093 /* round up to grid size */
1094 int ww = ((st->logo_width / st->grid_width) + 1) * st->grid_width;
1095 int hh = ((st->logo_height / st->grid_height) + 1) * st->grid_height;
1098 XGetGeometry (st->dpy, st->logo_map, &r, &xx, &yy, &w, &h, &bbw, &d);
1100 /* kludge: if the logo "hole" is around the same size as the logo,
1101 don't center it (since the xscreensaver logo image is a little
1102 off center... But do center it if the hole/gridsize is large. */
1103 if (ww < st->logo_width + 5) ww = w;
1104 if (hh < st->logo_height + 5) hh = h;
1107 lx = border_x + 3 + st->grid_width * st->logo_x + ((ww - w) / 2);
1108 ly = border_y + 3 + st->grid_height * st->logo_y + ((hh - h) / 2);
1110 /* Fill the background of the logo box with the "unreachable" color */
1111 XFillRectangle (st->dpy, st->window, st->ugc,
1112 border_x + 3 + st->grid_width * st->logo_x,
1113 border_y + 3 + st->grid_height * st->logo_y,
1116 XSetClipOrigin (st->dpy, st->logo_gc, lx, ly);
1118 XCopyPlane (st->dpy, st->logo_map, st->window, st->logo_gc,
1119 0, 0, w, h, lx, ly, 1);
1121 XCopyArea (st->dpy, st->logo_map, st->window, st->logo_gc,
1122 0, 0, w, h, lx, ly);
1124 draw_solid_square (st, st->start_x, st->start_y, WALL_TOP >> st->start_dir, st->tgc);
1125 draw_solid_square (st, st->end_x, st->end_y, WALL_TOP >> st->end_dir, st->tgc);
1130 draw_wall(struct state *st, int i, int j, int dir, GC with_gc) /* draw a single wall */
1134 XDrawLine(st->dpy, st->window, with_gc,
1135 border_x + st->grid_width * i,
1136 border_y + st->grid_height * j,
1137 border_x + st->grid_width * (i+1),
1138 border_y + st->grid_height * j);
1141 XDrawLine(st->dpy, st->window, with_gc,
1142 border_x + st->grid_width * (i+1),
1143 border_y + st->grid_height * j,
1144 border_x + st->grid_width * (i+1),
1145 border_y + st->grid_height * (j+1));
1148 XDrawLine(st->dpy, st->window, with_gc,
1149 border_x + st->grid_width * i,
1150 border_y + st->grid_height * (j+1),
1151 border_x + st->grid_width * (i+1),
1152 border_y + st->grid_height * (j+1));
1155 XDrawLine(st->dpy, st->window, with_gc,
1156 border_x + st->grid_width * i,
1157 border_y + st->grid_height * j,
1158 border_x + st->grid_width * i,
1159 border_y + st->grid_height * (j+1));
1164 /* too slow if we sync on every wall, so only sync about ten times
1165 during the maze-creation process.
1168 if (st->sync_tick <= 0) {
1169 XSync(st->dpy, False);
1170 st->sync_tick = st->maze_size_x * st->maze_size_x / 10;
1175 /* Actually build a wall. */
1177 build_wall(struct state *st, int i, int j, int dir)
1179 /* Draw it on the screen. */
1180 draw_wall(st, i, j, dir, st->gc);
1181 /* Put it in the maze. */
1185 st->maze[i][j] |= WALL_TOP;
1187 st->maze[i][j-1] |= WALL_BOTTOM;
1190 st->maze[i][j] |= WALL_RIGHT;
1191 if(i<st->maze_size_x-1)
1192 st->maze[i+1][j] |= WALL_LEFT;
1195 st->maze[i][j] |= WALL_BOTTOM;
1196 if(j<st->maze_size_y-1)
1197 st->maze[i][j+1] |= WALL_TOP;
1200 st->maze[i][j] |= WALL_LEFT;
1202 st->maze[i-1][j] |= WALL_RIGHT;
1207 /* Break out a wall. */
1210 break_wall(i, j, dir)
1213 /* Draw it on the screen. */
1214 draw_wall(i, j, dir, st->erase_gc);
1215 /* Put it in the maze. */
1219 st->maze[i][j] &= ~WALL_TOP;
1221 maze[i][j-1] &= ~WALL_BOTTOM;
1224 st->maze[i][j] &= ~WALL_RIGHT;
1225 if(i<st->maze_size_x-1)
1226 maze[i+1][j] &= ~WALL_LEFT;
1229 st->maze[i][j] &= ~WALL_BOTTOM;
1230 if(j<st->maze_size_y-1)
1231 maze[i][j+1] &= ~WALL_BOTTOM;
1234 st->maze[i][j] &= ~WALL_LEFT;
1236 maze[i-1][j] &= ~WALL_RIGHT;
1244 draw_solid_square(struct state *st,
1245 int i, int j, /* draw a solid square in a square */
1246 int dir, GC with_gc)
1250 XFillRectangle(st->dpy, st->window, with_gc,
1251 border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1252 border_y - st->bw-(st->bw==0?1:0) + st->grid_height * j,
1253 st->grid_width - (st->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
1256 XFillRectangle(st->dpy, st->window, with_gc,
1257 border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1258 border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1259 st->grid_width, st->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
1262 XFillRectangle(st->dpy, st->window, with_gc,
1263 border_x + st->bw+(st->bw==0?1:0) + st->grid_width * i,
1264 border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1265 st->grid_width - (st->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
1268 XFillRectangle(st->dpy, st->window, with_gc,
1269 border_x - st->bw-(st->bw==0?1:0) + st->grid_width * i,
1270 border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1271 st->grid_width, st->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
1277 longdeadend_p(struct state *st, int x1, int y1, int x2, int y2, int endwall)
1279 int dx = x2 - x1, dy = y2 - y1;
1282 sidewalls = endwall | (endwall >> 2 | endwall << 2);
1283 sidewalls = ~sidewalls & WALL_ANY;
1285 while((st->maze[x2][y2] & WALL_ANY) == sidewalls)
1287 if (x2 + dx < 0 || x2 + dx >= st->maze_size_x ||
1288 y2 + dy < 0 || y2 + dy >= st->maze_size_y)
1294 if((st->maze[x2][y2] & WALL_ANY) == (sidewalls | endwall))
1296 endwall = (endwall >> 2 | endwall << 2) & WALL_ANY;
1297 while(x1 != x2 || y1 != y2)
1301 draw_solid_square(st, x1, y1, endwall, st->sgc);
1302 st->maze[x1][y1] |= SOLVER_VISIT;
1310 /* Find all dead regions -- areas from which the goal cannot be reached --
1311 and mark them visited. */
1313 find_dead_regions(struct state *st)
1315 int xx, yy, flipped;
1317 /* Find all not SOLVER_VISIT squares bordering NOT_DEAD squares
1318 and mark them NOT_DEAD also. Repeat until no more such squares. */
1319 st->maze[st->start_x][st->start_y] |= NOT_DEAD;
1324 for(xx = 0; xx < st->maze_size_x; xx++)
1325 for(yy = 0; yy < st->maze_size_y; yy++)
1326 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1327 && ( (xx && (st->maze[xx-1][yy] & NOT_DEAD))
1328 || (yy && (st->maze[xx][yy-1] & NOT_DEAD))))
1331 st->maze[xx][yy] |= NOT_DEAD;
1333 for(xx = st->maze_size_x-1; xx >= 0; xx--)
1334 for(yy = st->maze_size_y-1; yy >= 0; yy--)
1335 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1336 && ( (xx != st->maze_size_x-1 && (st->maze[xx+1][yy] & NOT_DEAD))
1337 || (yy != st->maze_size_y-1 && (st->maze[xx][yy+1] & NOT_DEAD))))
1340 st->maze[xx][yy] |= NOT_DEAD;
1345 for (yy = 0; yy < st->maze_size_y; yy++)
1346 for (xx = 0; xx < st->maze_size_x; xx++)
1348 if (st->maze[xx][yy] & NOT_DEAD)
1349 st->maze[xx][yy] &= ~NOT_DEAD;
1350 else if (!(st->maze[xx][yy] & SOLVER_VISIT))
1352 st->maze[xx][yy] |= SOLVER_VISIT;
1353 if((xx < st->logo_x || xx > st->logo_x + st->logo_width / st->grid_width) ||
1354 (yy < st->logo_y || yy > st->logo_y + st->logo_height / st->grid_height))
1356 /* if we are completely surrounded by walls, just draw the
1358 if ((st->maze[xx][yy] & WALL_ANY) == WALL_ANY)
1359 XFillRectangle(st->dpy, st->window, st->ugc,
1360 border_x + st->bw + st->grid_width * xx,
1361 border_y + st->bw + st->grid_height * yy,
1362 st->grid_width - (st->bw+st->bw), st->grid_height - (st->bw+st->bw));
1365 if (! (st->maze[xx][yy] & WALL_LEFT))
1366 draw_solid_square(st, xx, yy, WALL_LEFT, st->ugc);
1367 if (! (st->maze[xx][yy] & WALL_RIGHT))
1368 draw_solid_square(st, xx, yy, WALL_RIGHT, st->ugc);
1369 if (! (st->maze[xx][yy] & WALL_TOP))
1370 draw_solid_square(st, xx, yy, WALL_TOP, st->ugc);
1371 if (! (st->maze[xx][yy] & WALL_BOTTOM))
1372 draw_solid_square(st, xx, yy, WALL_BOTTOM, st->ugc);
1380 solve_maze (struct state *st) /* solve it with graphical feedback */
1382 struct solve_state *ss = st->solve_state;
1384 ss = st->solve_state = (struct solve_state *) calloc (1, sizeof(*ss));
1387 /* plug up the surrounding wall */
1388 st->maze[st->end_x][st->end_y] |= (WALL_TOP >> st->end_dir);
1390 /* initialize search path */
1392 st->path[ss->i].x = st->end_x;
1393 st->path[ss->i].y = st->end_y;
1394 st->path[ss->i].dir = 0;
1395 st->maze[st->end_x][st->end_y] |= SOLVER_VISIT;
1403 int dir, from, ways;
1405 if ( st->maze[st->path[ss->i].x][st->path[ss->i].y] & START_SQUARE )
1411 if(!st->path[ss->i].dir)
1414 /* First visit this square. Which adjacent squares are open? */
1415 for(dir = WALL_TOP; dir & WALL_ANY; dir >>= 1)
1417 if(st->maze[st->path[ss->i].x][st->path[ss->i].y] & dir)
1420 ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1421 ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1423 if(st->maze[ss->x][ss->y] & SOLVER_VISIT)
1426 from = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1427 /* don't enter obvious dead ends */
1428 if(((st->maze[ss->x][ss->y] & WALL_ANY) | from) != WALL_ANY)
1430 if(!longdeadend_p(st, st->path[ss->i].x, st->path[ss->i].y, ss->x, ss->y, dir))
1435 draw_solid_square(st, ss->x, ss->y, from, st->sgc);
1436 st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1441 ways = st->path[ss->i].ways;
1442 /* ways now has a bitmask of open paths. */
1447 if (!st->ignorant_p)
1449 ss->x = st->path[ss->i].x - st->start_x;
1450 ss->y = st->path[ss->i].y - st->start_y;
1452 if(abs(ss->y) <= abs(ss->x))
1453 dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1455 dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM;
1465 dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM; break;
1468 dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1476 dir = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1491 else if(ways&WALL_LEFT)
1493 else if(ways&WALL_BOTTOM)
1495 else if(ways&WALL_RIGHT)
1501 ways &= ~dir; /* tried this one */
1503 ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1504 ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1506 /* advance in direction dir */
1507 st->path[ss->i].dir = dir;
1508 st->path[ss->i].ways = ways;
1509 draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, dir, st->tgc);
1512 st->path[ss->i].dir = 0;
1513 st->path[ss->i].ways = 0;
1514 st->path[ss->i].x = ss->x;
1515 st->path[ss->i].y = ss->y;
1516 st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1523 printf("Unsolvable maze.\n");
1528 if(!ss->bt && !st->ignorant_p)
1529 find_dead_regions(st);
1531 from = st->path[ss->i-1].dir;
1532 from = (from << 2 & WALL_ANY) | (from >> 2 & WALL_ANY);
1534 draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, from, st->cgc);
1543 enter_square (int n) /* move into a neighboring square */
1545 draw_solid_square( (int)st->path[n].x, (int)st->path[n].y,
1546 (int)st->path[n].dir, st->tgc);
1548 st->path[n+1].dir = -1;
1549 switch (st->path[n].dir) {
1550 case 0: st->path[n+1].x = st->path[n].x;
1551 st->path[n+1].y = st->path[n].y - 1;
1553 case 1: st->path[n+1].x = st->path[n].x + 1;
1554 st->path[n+1].y = st->path[n].y;
1556 case 2: st->path[n+1].x = st->path[n].x;
1557 st->path[n+1].y = st->path[n].y + 1;
1559 case 3: st->path[n+1].x = st->path[n].x - 1;
1560 st->path[n+1].y = st->path[n].y;
1568 * jmr additions for Jamie Zawinski's <jwz@jwz.org> screensaver stuff,
1569 * note that the code above this has probably been hacked about in some
1573 static const char *maze_defaults[] = {
1574 ".background: black",
1575 ".foreground: white",
1582 "*solveDelay: 5000",
1583 "*preDelay: 2000000",
1584 "*postDelay: 4000000",
1586 "*liveColor: #00FF00",
1587 "*deadColor: #880000",
1588 "*skipColor: #8B5A00",
1589 "*surroundColor: #220055",
1594 static XrmOptionDescRec maze_options[] = {
1595 { "-ignorant", ".ignorant", XrmoptionNoArg, "True" },
1596 { "-no-ignorant", ".ignorant", XrmoptionNoArg, "False" },
1597 { "-grid-size", ".gridSize", XrmoptionSepArg, 0 },
1598 { "-solve-delay", ".solveDelay", XrmoptionSepArg, 0 },
1599 { "-pre-delay", ".preDelay", XrmoptionSepArg, 0 },
1600 { "-post-delay", ".postDelay", XrmoptionSepArg, 0 },
1601 { "-bg-color", ".background", XrmoptionSepArg, 0 },
1602 { "-fg-color", ".foreground", XrmoptionSepArg, 0 },
1603 { "-live-color", ".liveColor", XrmoptionSepArg, 0 },
1604 { "-dead-color", ".deadColor", XrmoptionSepArg, 0 },
1605 { "-skip-color", ".skipColor", XrmoptionSepArg, 0 },
1606 { "-surround-color", ".surroundColor",XrmoptionSepArg, 0 },
1607 { "-generator", ".generator", XrmoptionSepArg, 0 },
1608 { "-max-length", ".maxLength", XrmoptionSepArg, 0 },
1609 { "-bridge", ".bridge", XrmoptionNoArg, "True" },
1610 { "-no-bridge", ".bridge", XrmoptionNoArg, "False" },
1614 static int generator = 0;
1617 maze_init (Display *dpy_arg, Window window_arg)
1619 struct state *st = (struct state *) calloc (1, sizeof(*st));
1624 XWindowAttributes xgwa;
1625 unsigned long bg, fg, pfg, pbg, sfg, ufg;
1628 st->window = window_arg;
1637 size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1638 st->solve_delay = get_integer_resource (st->dpy, "solveDelay", "Integer");
1639 st->pre_solve_delay = get_integer_resource (st->dpy, "preDelay", "Integer");
1640 st->post_solve_delay = get_integer_resource (st->dpy, "postDelay", "Integer");
1641 generator = get_integer_resource(st->dpy, "generator", "Integer");
1642 st->max_length = get_integer_resource(st->dpy, "maxLength", "Integer");
1643 st->bridge_p = get_boolean_resource(st->dpy, "bridge", "Boolean");
1644 st->ignorant_p = get_boolean_resource(st->dpy, "ignorant", "Boolean");
1646 if (!size) st->ifrandom = 1;
1648 if (size < 2) size = 7 + (random () % 30);
1649 st->grid_width = st->grid_height = size;
1650 st->bw = (size > 6 ? 3 : (size-1)/2);
1652 XGetWindowAttributes (st->dpy, st->window, &xgwa);
1657 set_maze_sizes (st, xgwa.width, xgwa.height);
1659 st->gc = XCreateGC(st->dpy, st->window, 0, 0);
1660 st->cgc = XCreateGC(st->dpy, st->window, 0, 0);
1661 st->tgc = XCreateGC(st->dpy, st->window, 0, 0);
1662 st->sgc = XCreateGC(st->dpy, st->window, 0, 0);
1663 st->ugc = XCreateGC(st->dpy, st->window, 0, 0);
1664 st->logo_gc = XCreateGC(st->dpy, st->window, 0, 0);
1665 st->erase_gc = XCreateGC(st->dpy, st->window, 0, 0);
1668 gray = XCreateBitmapFromData (st->dpy,st->window,gray1_bits,gray1_width,gray1_height);
1671 bg = get_pixel_resource (st->dpy, xgwa.colormap, "background","Background");
1672 fg = get_pixel_resource (st->dpy, xgwa.colormap, "foreground","Foreground");
1673 pfg = get_pixel_resource (st->dpy, xgwa.colormap, "liveColor", "Foreground");
1674 pbg = get_pixel_resource (st->dpy, xgwa.colormap, "deadColor", "Foreground");
1675 sfg = get_pixel_resource (st->dpy, xgwa.colormap, "skipColor", "Foreground");
1676 ufg = get_pixel_resource (st->dpy, xgwa.colormap, "surroundColor", "Foreground");
1678 XSetForeground (st->dpy, st->gc, fg);
1679 XSetBackground (st->dpy, st->gc, bg);
1680 XSetForeground (st->dpy, st->cgc, pbg);
1681 XSetBackground (st->dpy, st->cgc, bg);
1682 XSetForeground (st->dpy, st->tgc, pfg);
1683 XSetBackground (st->dpy, st->tgc, bg);
1684 XSetForeground (st->dpy, st->sgc, sfg);
1685 XSetBackground (st->dpy, st->sgc, bg);
1686 XSetForeground (st->dpy, st->ugc, ufg);
1687 XSetBackground (st->dpy, st->ugc, bg);
1688 XSetForeground (st->dpy, st->logo_gc, fg);
1689 XSetBackground (st->dpy, st->logo_gc, bg);
1690 XSetForeground (st->dpy, st->erase_gc, bg);
1691 XSetBackground (st->dpy, st->erase_gc, bg);
1694 XSetStipple (st->dpy, st->cgc, gray);
1695 XSetFillStyle (st->dpy, st->cgc, FillOpaqueStippled);
1696 XSetStipple (st->dpy, st->sgc, gray);
1697 XSetFillStyle (st->dpy, st->sgc, FillOpaqueStippled);
1698 XSetStipple (st->dpy, st->ugc, gray);
1699 XSetFillStyle (st->dpy, st->ugc, FillOpaqueStippled);
1705 unsigned int w, h, bbw, d;
1706 unsigned long *pixels;
1708 Pixmap logo_mask = 0;
1709 st->logo_map = xscreensaver_logo (xgwa.screen, xgwa.visual, st->window,
1711 &pixels, &npixels, &logo_mask,
1714 XSetClipMask (st->dpy, st->logo_gc, logo_mask);
1715 XFreePixmap (st->dpy, logo_mask);
1717 if (pixels) free (pixels);
1718 XGetGeometry (st->dpy, st->logo_map, &r, &x, &y, &w, &h, &bbw, &d);
1720 st->logo_height = h;
1732 maze_reshape (Display *dpy, Window window, void *closure,
1733 unsigned int w, unsigned int h)
1735 struct state *st = (struct state *) closure;
1740 static unsigned long
1741 maze_draw (Display *dpy, Window window, void *closure)
1743 struct state *st = (struct state *) closure;
1744 int this_delay = st->solve_delay;
1746 if (st->eraser || st->erase_window)
1748 st->erase_window = 0;
1749 st->eraser = erase_window (st->dpy, st->window, st->eraser);
1753 this_delay = 1000000;
1754 if (this_delay > st->pre_solve_delay)
1755 this_delay = st->pre_solve_delay;
1760 if (st->restart || st->stop) goto pop;
1761 switch (st->state) {
1763 initialize_maze(st);
1764 if (st->ifrandom && st->ifinit)
1767 size = 7 + (random () % 30);
1768 st->grid_width = st->grid_height = size;
1769 st->bw = (size > 6 ? 3 : (size-1)/2);
1775 XClearWindow(st->dpy, st->window);
1776 draw_maze_border(st);
1779 st->this_gen = generator;
1780 if(st->this_gen<0 || st->this_gen>2)
1781 st->this_gen = random()%3;
1783 switch(st->this_gen)
1789 alt_create_maze(st);
1792 set_create_maze(st);
1797 this_delay = st->pre_solve_delay;
1800 if (! solve_maze(st))
1801 --st->state; /* stay in state 5 */
1804 st->erase_window = 1;
1805 this_delay = st->post_solve_delay;
1816 XWindowAttributes xgwa;
1823 st->sync_p = ((random() % 4) != 0);
1825 size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1826 if (size < 2) size = 7 + (random () % 30);
1827 st->grid_width = st->grid_height = size;
1828 st->bw = (size > 6 ? 3 : (size-1)/2);
1830 XGetWindowAttributes (st->dpy, st->window, &xgwa);
1831 set_maze_sizes (st, xgwa.width, xgwa.height);
1840 maze_event (Display *dpy, Window window, void *closure, XEvent *event)
1842 struct state *st = (struct state *) closure;
1843 switch (event->type)
1846 switch (event->xbutton.button)
1849 st->stop = !st->stop ;
1850 if (st->state == 5) st->state = 4 ;
1876 maze_free (Display *dpy, Window window, void *closure)
1878 struct state *st = (struct state *) closure;
1882 XSCREENSAVER_MODULE ("Maze", maze)