1 /******************************************************************************
2 * [ maze ] ...
3 *
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.
9 *
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.
13 *
14 * modified: [ 6-28-98 ] Zack Weinberg <zack@rabi.phys.columbia.edu>
15 *
16 * Made the maze-solver somewhat more intelligent. There are
17 * three optimizations:
18 *
19 * - Straight-line lookahead: the solver does not enter dead-end
20 * corridors. This is a win with all maze generators.
21 *
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.
26 *
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.
34 *
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.
42 *
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
60 * [ Hacked for X11...
61 * [ Note the word "hacked" -- this is extremely ugly, but at
62 * [ least it does the job. NOT a good programming example
63 * [ for X.
64 * original: [ 6/21/85 ] Martin Weiss Sun Microsystems [ SunView ]
65 *
66 ******************************************************************************
67 Copyright 1988 by Sun Microsystems, Inc. Mountain View, CA.
68
69 All Rights Reserved
70
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.
80
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 *****************************************************************************/
89
90 #include "screenhack.h"
91 #include "erase.h"
92 #include "ximage-loader.h"
93 #include "images/gen/logo-50_png.h"
94 #include "images/gen/logo-180_png.h"
95
96 #include <stdio.h>
97
98 /* #include <X11/bitmaps/gray1> */
99 /*
100 #define gray1_width 2
101 #define gray1_height 2
102 static const char gray1_bits[] = { 0x01, 0x02 };
103 */
104
105 #define MAX_MAZE_SIZE_X 1000
106 #define MAX_MAZE_SIZE_Y 1000
107
108 #define MOVE_LIST_SIZE (MAX_MAZE_SIZE_X * MAX_MAZE_SIZE_Y)
109
110 #define NOT_DEAD 0x8000
111 #define SOLVER_VISIT 0x4000
112 #define START_SQUARE 0x2000
113 #define END_SQUARE 0x1000
114
115 #define WALL_TOP 0x8
116 #define WALL_RIGHT 0x4
117 #define WALL_BOTTOM 0x2
118 #define WALL_LEFT 0x1
119 #define WALL_ANY 0xF
120
121 #define DOOR_IN_TOP 0x800
122 #define DOOR_IN_RIGHT 0x400
123 #define DOOR_IN_BOTTOM 0x200
124 #define DOOR_IN_LEFT 0x100
125 #define DOOR_IN_ANY 0xF00
126
127 #define DOOR_OUT_TOP 0x80
128 #define DOOR_OUT_RIGHT 0x40
129 #define DOOR_OUT_BOTTOM 0x20
130 #define DOOR_OUT_LEFT 0x10
131
132
133 #define border_x (0)
134 #define border_y (0)
135
136 #define get_random(x) (random() % (x))
137
138
139 struct move_list_struct {
140 unsigned short x;
141 unsigned short y;
142 unsigned char dir, ways;
143 };
144
145 struct solve_state {
146 int running;
147 int i, x, y, bt;
148 };
149
150
151 struct state {
152 Display *dpy;
153 Window window;
154
155 GC gc, cgc, tgc, sgc, ugc, logo_gc, erase_gc;
156 Pixmap logo_map;
157
158 int logo_x, logo_y; /* in grid cells (or -1) */
159 int logo_width, logo_height; /* in pixels */
160 int fps_width, fps_height; /* in pixels */
161
162 int solve_delay, pre_solve_delay, post_solve_delay;
163
164 unsigned short maze[MAX_MAZE_SIZE_X][MAX_MAZE_SIZE_Y];
165
166 struct move_list_struct move_list[MOVE_LIST_SIZE];
167 struct move_list_struct save_path[MOVE_LIST_SIZE];
168 struct move_list_struct path[MOVE_LIST_SIZE];
169
170 int maze_size_x, maze_size_y;
171 int sqnum, cur_sq_x, cur_sq_y, path_length;
172 int start_x, start_y, start_dir, end_x, end_y, end_dir;
173 int grid_width, grid_height;
174 int bw;
175
176 int x, y, restart, stop, state, max_length;
177 int sync_p, sync_tick;
178 int ignorant_p;
179
180 struct solve_state *solve_state;
181
182 int *sets; /* The sets that our squares are in. */
183 int *hedges; /* The `list' of hedges. */
184
185 int this_gen;
186 int erase_window;
187 eraser_state *eraser;
188
189 int ifrandom;
190 int ifinit;
191
192 };
193
194
195 static void draw_wall (struct state *, int, int, int, GC);
196 static void draw_solid_square (struct state *, int, int, int, GC);
197 static void build_wall (struct state *, int, int, int);
198
199
200 static void
set_maze_sizes(struct state * st,int width,int height)201 set_maze_sizes (struct state *st, int width, int height)
202 {
203 st->maze_size_x = width / st->grid_width;
204 st->maze_size_y = height / st->grid_height;
205
206 if (st->maze_size_x < 4) st->maze_size_x = 4;
207 if (st->maze_size_y < 4) st->maze_size_y = 4;
208 }
209
210
211 /* Resets the maze grid, picks the starting and ending points,
212 and the position of the logo, if any.
213 */
214 static void
initialize_maze(struct state * st)215 initialize_maze (struct state *st)
216 {
217 int retry_count = 0;
218 int i, j, wall;
219 int logow = 1 + st->logo_width / st->grid_width;
220 int logoh = 1 + st->logo_height / st->grid_height;
221
222 AGAIN:
223
224 /* This can happen if the window is really small. Let's not sweat it. */
225 if (++retry_count > 100) return;
226
227
228 /* initialize all squares */
229 for ( i=0; i<st->maze_size_x; i++) {
230 for ( j=0; j<st->maze_size_y; j++) {
231 st->maze[i][j] = 0;
232 }
233 }
234
235 /* top wall */
236 for ( i=0; i<st->maze_size_x; i++ ) {
237 st->maze[i][0] |= WALL_TOP;
238 }
239
240 /* right wall */
241 for ( j=0; j<st->maze_size_y; j++ ) {
242 st->maze[st->maze_size_x-1][j] |= WALL_RIGHT;
243 }
244
245 /* bottom wall */
246 for ( i=0; i<st->maze_size_x; i++ ) {
247 st->maze[i][st->maze_size_y-1] |= WALL_BOTTOM;
248 }
249
250 /* left wall */
251 for ( j=0; j<st->maze_size_y; j++ ) {
252 st->maze[0][j] |= WALL_LEFT;
253 }
254
255 /* set start square */
256 wall = get_random(4);
257 switch (wall) {
258 case 0:
259 i = get_random(st->maze_size_x);
260 j = 0;
261 break;
262 case 1:
263 i = st->maze_size_x - 1;
264 j = get_random(st->maze_size_y);
265 break;
266 case 2:
267 i = get_random(st->maze_size_x);
268 j = st->maze_size_y - 1;
269 break;
270 case 3:
271 i = 0;
272 j = get_random(st->maze_size_y);
273 break;
274 }
275 st->maze[i][j] |= START_SQUARE;
276 st->maze[i][j] |= ( DOOR_IN_TOP >> wall );
277 st->maze[i][j] &= ~( WALL_TOP >> wall );
278 st->cur_sq_x = i;
279 st->cur_sq_y = j;
280 st->start_x = i;
281 st->start_y = j;
282 st->start_dir = wall;
283 st->sqnum = 0;
284
285 /* set end square */
286 wall = (wall + 2)%4;
287 switch (wall) {
288 case 0:
289 i = get_random(st->maze_size_x);
290 j = 0;
291 break;
292 case 1:
293 i = st->maze_size_x - 1;
294 j = get_random(st->maze_size_y);
295 break;
296 case 2:
297 i = get_random(st->maze_size_x);
298 j = st->maze_size_y - 1;
299 break;
300 case 3:
301 i = 0;
302 j = get_random(st->maze_size_y);
303 break;
304 }
305 st->maze[i][j] |= END_SQUARE;
306 st->maze[i][j] |= ( DOOR_OUT_TOP >> wall );
307 st->maze[i][j] &= ~( WALL_TOP >> wall );
308 st->end_x = i;
309 st->end_y = j;
310 st->end_dir = wall;
311
312 /* set logo */
313 if ((st->maze_size_x-logow >= 6) && (st->maze_size_y-logoh >= 6))
314 {
315 /* not closer than 3 grid units from a wall, to ensure that it
316 won't overlap the entrance or exit. */
317 st->logo_x = get_random (st->maze_size_x - logow - 5) + 3;
318 st->logo_y = get_random (st->maze_size_y - logoh - 5) + 3;
319 for (i=0; i<logow; i++)
320 for (j=0; j<logoh; j++)
321 /* mark as having doors to prevent these cells being used in maze. */
322 st->maze[st->logo_x + i][st->logo_y + j] |= DOOR_IN_ANY;
323 }
324 else
325 st->logo_y = st->logo_x = -1;
326
327 /* mask out the fps area */
328 if (st->fps_width > 0)
329 {
330 int fpsw = 1 + st->fps_width / st->grid_width;
331 int fpsh = 1 + st->fps_height / st->grid_width;
332
333 /* if the chosen logo position overlapped the fps area, try again! */
334 if (st->logo_x < fpsw+3 && st->logo_y+logoh > st->maze_size_y-fpsh-4)
335 goto AGAIN;
336
337 /* if the start or end point is inside the fps area, try again! */
338 if ((st->start_x <= fpsw && st->start_y >= st->maze_size_y-fpsh-1) ||
339 (st->end_x <= fpsw && st->end_y >= st->maze_size_y-fpsh-1))
340 goto AGAIN;
341
342 for (i=0; i<fpsw; i++)
343 for (j=0; j<fpsh; j++) {
344 /* mark as having doors to prevent these cells being used in maze.
345 mark as visit to prevent it being colored "unreachable". */
346 st->maze[i][st->maze_size_y - j - 1] |= DOOR_IN_ANY|SOLVER_VISIT;
347 /* take off left/bottom wall or the FPS text overlaps it */
348 st->maze[i][st->maze_size_y - j - 1] &= ~(WALL_BOTTOM|WALL_LEFT);
349 }
350 }
351 }
352
353
354 /****************************************************************************
355 Generator 2: Set-based maze generator.
356
357 Put each square in the maze in a separate set. Also, make a list of all the
358 hedges. Randomize that list. Walk through the list. If, for a certain
359 hedge, the two squares on both sides of it are in different sets, union the
360 sets and remove the hedge. Continue until all hedges have been processed or
361 only one set remains.
362
363 This is essentially the "Kruskal" algorithm.
364
365 ****************************************************************************/
366
367 static void mask_out_set_rect(struct state *st, int x, int y, int w, int h);
368
369 /* Initialise the sets. */
370 static void
init_sets(struct state * st)371 init_sets(struct state *st)
372 {
373 int i, t, r;
374
375 if(st->sets)
376 free(st->sets);
377 st->sets = (int *)malloc(st->maze_size_x*st->maze_size_y*sizeof(int));
378 if(!st->sets)
379 abort();
380 for(i = 0; i < st->maze_size_x*st->maze_size_y; i++)
381 {
382 st->sets[i] = i;
383 }
384
385 if(st->hedges)
386 free(st->hedges);
387 st->hedges = (int *)malloc(st->maze_size_x*st->maze_size_y*2*sizeof(int));
388 if(!st->hedges)
389 abort();
390 for(i = 0; i < st->maze_size_x*st->maze_size_y*2; i++)
391 {
392 st->hedges[i] = i;
393 }
394 /* Mask out outside walls. */
395 for(i = 0; i < st->maze_size_y; i++)
396 {
397 st->hedges[2*((st->maze_size_x)*i+st->maze_size_x-1)+1] = -1;
398 }
399 for(i = 0; i < st->maze_size_x; i++)
400 {
401 st->hedges[2*((st->maze_size_y-1)*st->maze_size_x+i)] = -1;
402 }
403
404 /* Mask out the logo area. */
405 if(st->logo_x!=-1)
406 {
407 int logow = 1 + st->logo_width / st->grid_width;
408 int logoh = 1 + st->logo_height / st->grid_height;
409 mask_out_set_rect(st, st->logo_x, st->logo_y, logow, logoh);
410 }
411
412 /* Mask out the FPS area. */
413 if(st->fps_width > 0)
414 {
415 int fpsw = 1 + st->fps_width / st->grid_width;
416 int fpsh = 1 + st->fps_height / st->grid_height;
417 mask_out_set_rect(st, 0, st->maze_size_y-fpsh, fpsw, fpsh);
418 }
419
420 for(i = 0; i < st->maze_size_x*st->maze_size_y*2; i++)
421 {
422 t = st->hedges[i];
423 r = random()%(st->maze_size_x*st->maze_size_y*2);
424 st->hedges[i] = st->hedges[r];
425 st->hedges[r] = t;
426 }
427 }
428
429 /* Get the representative of a set. */
430 static int
get_set(struct state * st,int num)431 get_set(struct state *st, int num)
432 {
433 int s;
434
435 if(st->sets[num]==num)
436 return num;
437 else
438 {
439 s = get_set(st, st->sets[num]);
440 st->sets[num] = s;
441 return s;
442 }
443 }
444
445 /* Join two sets together. */
446 static void
join_sets(struct state * st,int num1,int num2)447 join_sets(struct state *st, int num1, int num2)
448 {
449 int s1, s2;
450
451 s1 = get_set(st, num1);
452 s2 = get_set(st, num2);
453
454 if(s1<s2)
455 st->sets[s2] = s1;
456 else
457 st->sets[s1] = s2;
458 }
459
460 /* Exitialise the sets. */
461 static void
exit_sets(struct state * st)462 exit_sets(struct state *st)
463 {
464 if(st->hedges)
465 free(st->hedges);
466 st->hedges = 0;
467 if(st->sets)
468 free(st->sets);
469 st->sets = 0;
470 }
471
472
473 static void
set_create_maze(struct state * st)474 set_create_maze(struct state *st)
475 {
476 int i, h, xx, yy, dir, v, w;
477
478 /* Do almost all the setup. */
479 init_sets(st);
480
481 /* Start running through the hedges. */
482 for(i = 0; i < 2*st->maze_size_x*st->maze_size_y; i++)
483 {
484 h = st->hedges[i];
485
486 /* This one is in the logo or outside border. */
487 if(h==-1)
488 continue;
489
490 dir = h%2?1:2;
491 xx = (h>>1)%st->maze_size_x;
492 yy = (h>>1)/st->maze_size_x;
493
494 v = xx;
495 w = yy;
496 switch(dir)
497 {
498 case 1:
499 v++;
500 break;
501 case 2:
502 w++;
503 break;
504 }
505
506 if(get_set(st, xx+yy*st->maze_size_x)!=get_set(st, v+w*st->maze_size_x))
507 {
508 join_sets(st, xx+yy*st->maze_size_x, v+w*st->maze_size_x);
509 /* Don't draw the wall. */
510 }
511 else
512 {
513 /* Don't join the sets. */
514 build_wall(st, xx, yy, dir);
515 }
516 }
517
518 /* Free some memory. */
519 exit_sets(st);
520 }
521
522 /* mark a rectangle as being unavailable for usage in the maze */
523 static void
mask_out_set_rect(struct state * st,int x,int y,int w,int h)524 mask_out_set_rect(struct state *st, int x, int y, int w, int h)
525 {
526 int xx, yy;
527 for(xx = x; xx < x+w; xx++)
528 for(yy = y; yy < y+h; yy++)
529 {
530 st->hedges[2*(xx+st->maze_size_x*yy)+1] = -1;
531 st->hedges[2*(xx+st->maze_size_x*yy)] = -1;
532 }
533 for(xx = x; xx < x+w; xx++)
534 {
535 build_wall(st, xx, y, 0);
536 build_wall(st, xx, y+h, 0);
537 st->hedges[2*(xx+st->maze_size_x*(y-1))] = -1;
538 }
539 for(yy = y; yy < y+h; yy++)
540 {
541 build_wall(st, x, yy, 3);
542 build_wall(st, x+w, yy, 3);
543 st->hedges[2*(x-1+st->maze_size_x*yy)+1] = -1;
544 }
545 }
546
547
548 /****************************************************************************
549 Generator 1: Wall-building maze generator.
550
551 Pick a random, empty corner in the maze. Pick a random direction. Draw a
552 wall in that direction, from that corner until we hit a wall. Option: Only
553 draw the wall if it's going to be shorter than a certain length. Otherwise
554 we get lots of long walls.
555
556 This is essentially the "Prim" algorithm.
557 ****************************************************************************/
558
559 static void alt_mask_out_rect(struct state *st, char *corners,
560 int x, int y, int w, int h);
561
562 static void
alt_create_maze(struct state * st)563 alt_create_maze(struct state *st)
564 {
565 char *corners;
566 int *c_idx;
567 int i, j, height, width, open_corners, k, dir, xx, yy;
568
569 height = st->maze_size_y+1;
570 width = st->maze_size_x+1;
571
572 /* Allocate and clear some mem. */
573 corners = (char *)calloc(height*width, 1);
574 if(!corners)
575 return;
576
577 /* Set up the indexing array. */
578 c_idx = (int *)malloc(sizeof(int)*height*width);
579 if(!c_idx)
580 {
581 free(corners);
582 return;
583 }
584 for(i = 0; i < height*width; i++)
585 c_idx[i] = i;
586 for(i = 0; i < height*width; i++)
587 {
588 j = c_idx[i];
589 k = random()%(height*width);
590 c_idx[i] = c_idx[k];
591 c_idx[k] = j;
592 }
593
594 /* Set up some initial walls. */
595 /* Outside walls. */
596 for(i = 0; i < width; i++)
597 {
598 corners[i] = 1;
599 corners[i+width*(height-1)] = 1;
600 }
601 for(i = 0; i < height; i++)
602 {
603 corners[i*width] = 1;
604 corners[i*width+width-1] = 1;
605 }
606
607 /* mask out the logo area */
608 if(st->logo_x!=-1)
609 {
610 int logow = 1 + st->logo_width / st->grid_width;
611 int logoh = 1 + st->logo_height / st->grid_height;
612 alt_mask_out_rect (st, corners, st->logo_x, st->logo_y, logow, logoh);
613 }
614
615 /* mask out the FPS area */
616 if(st->fps_width>0)
617 {
618 int fpsw = 1 + st->fps_width / st->grid_width;
619 int fpsh = 1 + st->fps_height / st->grid_height;
620 alt_mask_out_rect (st, corners, 0, st->maze_size_y-fpsh, fpsw, fpsh);
621 }
622
623 /* Count open gridpoints. */
624 open_corners = 0;
625 for(i = 0; i < width; i++)
626 for(j = 0; j < height; j++)
627 if(!corners[i+width*j])
628 open_corners++;
629
630 /* Now do actual maze generation. */
631 while(open_corners>0)
632 {
633 for(i = 0; i < width*height; i++)
634 {
635 if(!corners[c_idx[i]])
636 {
637 xx = c_idx[i]%width;
638 yy = c_idx[i]/width;
639 /* Choose a random direction. */
640 dir = random()%4;
641
642 k = 0;
643 /* Measure the length of the wall we'd draw. */
644 while(!corners[xx+width*yy])
645 {
646 k++;
647 switch(dir)
648 {
649 case 0:
650 yy--;
651 break;
652 case 1:
653 xx++;
654 break;
655 case 2:
656 yy++;
657 break;
658 case 3:
659 xx--;
660 break;
661 }
662 }
663
664 if(k<=st->max_length)
665 {
666 xx = c_idx[i]%width;
667 yy = c_idx[i]/width;
668
669 /* Draw a wall until we hit something. */
670 while(!corners[xx+width*yy])
671 {
672 open_corners--;
673 corners[xx+width*yy] = 1;
674 switch(dir)
675 {
676 case 0:
677 build_wall(st, xx-1, yy-1, 1);
678 yy--;
679 break;
680 case 1:
681 build_wall(st, xx, yy, 0);
682 xx++;
683 break;
684 case 2:
685 build_wall(st, xx, yy, 3);
686 yy++;
687 break;
688 case 3:
689 build_wall(st, xx-1, yy-1, 2);
690 xx--;
691 break;
692 }
693 }
694 }
695 }
696 }
697 }
698
699 /* Free some memory we used. */
700 free(corners);
701 free(c_idx);
702 }
703
704
705 /* mark a rectangle as being unavailable for usage in the maze */
706 static void
alt_mask_out_rect(struct state * st,char * corners,int x,int y,int w,int h)707 alt_mask_out_rect(struct state *st, char *corners, int x, int y, int w, int h)
708 {
709 int i, j, xx, yy;
710 int mazew = st->maze_size_x+1;
711
712 for(i = x; i <= x+w; i++)
713 for(j = y; j <= y+h; j++)
714 corners[i+mazew*j] = 1;
715
716 for(xx = x; xx < x+w; xx++)
717 {
718 build_wall(st, xx, y, 0);
719 if (y+h < st->maze_size_y)
720 build_wall(st, xx, y+h, 0);
721 }
722 for(yy = y; yy < y+h; yy++)
723 {
724 if (x > 0)
725 build_wall(st, x, yy, 3);
726 build_wall(st, x+w, yy, 3);
727 }
728 }
729
730
731 /****************************************************************************
732 Generator 0: The original maze generator.
733
734 Start somewhere. Take a step in a random direction. Keep doing this until
735 we hit a wall. Then, backtrack until we find a point where we can go in
736 another direction.
737
738 This is essentially the "depth-first recursive backtracker" algorithm.
739 ****************************************************************************/
740
741 static int choose_door (struct state *st);
742 static int backup (struct state *st);
743
744 static void
create_maze(struct state * st)745 create_maze (struct state *st) /* create a maze layout given the initialized maze */
746 {
747 int i, newdoor = 0;
748
749 do {
750 st->move_list[st->sqnum].x = st->cur_sq_x;
751 st->move_list[st->sqnum].y = st->cur_sq_y;
752 st->move_list[st->sqnum].dir = newdoor;
753 while ( ( newdoor = choose_door(st) ) == -1 ) { /* pick a door */
754 if ( backup(st) == -1 ) { /* no more doors ... backup */
755 return; /* done ... return */
756 }
757 }
758
759 /* mark the out door */
760 st->maze[st->cur_sq_x][st->cur_sq_y] |= ( DOOR_OUT_TOP >> newdoor );
761
762 switch (newdoor) {
763 case 0: st->cur_sq_y--;
764 break;
765 case 1: st->cur_sq_x++;
766 break;
767 case 2: st->cur_sq_y++;
768 break;
769 case 3: st->cur_sq_x--;
770 break;
771 }
772 st->sqnum++;
773
774 /* mark the in door */
775 st->maze[st->cur_sq_x][st->cur_sq_y] |= ( DOOR_IN_TOP >> ((newdoor+2)%4) );
776
777 /* if end square set path length and save path */
778 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & END_SQUARE ) {
779 st->path_length = st->sqnum;
780 for ( i=0; i<st->path_length; i++) {
781 st->save_path[i].x = st->move_list[i].x;
782 st->save_path[i].y = st->move_list[i].y;
783 st->save_path[i].dir = st->move_list[i].dir;
784 }
785 }
786
787 } while (1);
788
789 }
790
791
792 static int
choose_door(struct state * st)793 choose_door (struct state *st) /* pick a new path */
794 {
795 int candidates[3];
796 int num_candidates;
797
798 num_candidates = 0;
799
800 /* top wall */
801 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_TOP )
802 goto rightwall;
803 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_TOP )
804 goto rightwall;
805 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_TOP )
806 goto rightwall;
807 if ( st->maze[st->cur_sq_x][st->cur_sq_y - 1] & DOOR_IN_ANY ) {
808 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_TOP;
809 st->maze[st->cur_sq_x][st->cur_sq_y - 1] |= WALL_BOTTOM;
810 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 0, st->gc);
811 goto rightwall;
812 }
813 candidates[num_candidates++] = 0;
814
815 rightwall:
816 /* right wall */
817 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_RIGHT )
818 goto bottomwall;
819 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_RIGHT )
820 goto bottomwall;
821 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_RIGHT )
822 goto bottomwall;
823 if ( st->maze[st->cur_sq_x + 1][st->cur_sq_y] & DOOR_IN_ANY ) {
824 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_RIGHT;
825 st->maze[st->cur_sq_x + 1][st->cur_sq_y] |= WALL_LEFT;
826 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 1, st->gc);
827 goto bottomwall;
828 }
829 candidates[num_candidates++] = 1;
830
831 bottomwall:
832 /* bottom wall */
833 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_BOTTOM )
834 goto leftwall;
835 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_BOTTOM )
836 goto leftwall;
837 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_BOTTOM )
838 goto leftwall;
839 if ( st->maze[st->cur_sq_x][st->cur_sq_y + 1] & DOOR_IN_ANY ) {
840 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_BOTTOM;
841 st->maze[st->cur_sq_x][st->cur_sq_y + 1] |= WALL_TOP;
842 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 2, st->gc);
843 goto leftwall;
844 }
845 candidates[num_candidates++] = 2;
846
847 leftwall:
848 /* left wall */
849 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_IN_LEFT )
850 goto donewall;
851 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & DOOR_OUT_LEFT )
852 goto donewall;
853 if ( st->maze[st->cur_sq_x][st->cur_sq_y] & WALL_LEFT )
854 goto donewall;
855 if ( st->maze[st->cur_sq_x - 1][st->cur_sq_y] & DOOR_IN_ANY ) {
856 st->maze[st->cur_sq_x][st->cur_sq_y] |= WALL_LEFT;
857 st->maze[st->cur_sq_x - 1][st->cur_sq_y] |= WALL_RIGHT;
858 draw_wall(st, st->cur_sq_x, st->cur_sq_y, 3, st->gc);
859 goto donewall;
860 }
861 candidates[num_candidates++] = 3;
862
863 donewall:
864 if (num_candidates == 0)
865 return ( -1 );
866 if (num_candidates == 1)
867 return ( candidates[0] );
868 return ( candidates[ get_random(num_candidates) ] );
869
870 }
871
872
873 static int
backup(struct state * st)874 backup (struct state *st) /* back up a move */
875 {
876 st->sqnum--;
877 if (st->sqnum >= 0) {
878 st->cur_sq_x = st->move_list[st->sqnum].x;
879 st->cur_sq_y = st->move_list[st->sqnum].y;
880 }
881 return ( st->sqnum );
882 }
883
884
885 /****************************************************************************
886 Drawing the maze
887 ****************************************************************************/
888
889 /* draws the maze outline, and the logo */
890 static void
draw_maze_border(struct state * st)891 draw_maze_border (struct state *st)
892 {
893 int i, j;
894
895 for ( i=0; i<st->maze_size_x; i++) {
896 if ( st->maze[i][0] & WALL_TOP ) {
897 XDrawLine(st->dpy, st->window, st->gc,
898 border_x + st->grid_width * i,
899 border_y,
900 border_x + st->grid_width * (i+1) - 1,
901 border_y);
902 }
903 if ((st->maze[i][st->maze_size_y - 1] & WALL_BOTTOM)) {
904 XDrawLine(st->dpy, st->window, st->gc,
905 border_x + st->grid_width * i,
906 border_y + st->grid_height * (st->maze_size_y) - 1,
907 border_x + st->grid_width * (i+1) - 1,
908 border_y + st->grid_height * (st->maze_size_y) - 1);
909 }
910 }
911 for ( j=0; j<st->maze_size_y; j++) {
912 if ( st->maze[st->maze_size_x - 1][j] & WALL_RIGHT ) {
913 XDrawLine(st->dpy, st->window, st->gc,
914 border_x + st->grid_width * st->maze_size_x - 1,
915 border_y + st->grid_height * j,
916 border_x + st->grid_width * st->maze_size_x - 1,
917 border_y + st->grid_height * (j+1) - 1);
918 }
919 if ( st->maze[0][j] & WALL_LEFT ) {
920 XDrawLine(st->dpy, st->window, st->gc,
921 border_x,
922 border_y + st->grid_height * j,
923 border_x,
924 border_y + st->grid_height * (j+1) - 1);
925 }
926 }
927
928 if (st->logo_x != -1)
929 {
930 Window r;
931 int xx, yy;
932 unsigned int w, h, bbw, d;
933
934 /* round up to grid size */
935 int ww = ((st->logo_width / st->grid_width) + 1) * st->grid_width;
936 int hh = ((st->logo_height / st->grid_height) + 1) * st->grid_height;
937 int lx, ly;
938
939 XGetGeometry (st->dpy, st->logo_map, &r, &xx, &yy, &w, &h, &bbw, &d);
940
941 /* kludge: if the logo "hole" is around the same size as the logo,
942 don't center it (since the xscreensaver logo image is a little
943 off center... But do center it if the hole/gridsize is large. */
944 if (ww < st->logo_width + 5) ww = w;
945 if (hh < st->logo_height + 5) hh = h;
946
947
948 lx = border_x + 3 + st->grid_width * st->logo_x + ((ww - w) / 2);
949 ly = border_y + 3 + st->grid_height * st->logo_y + ((hh - h) / 2);
950
951 /* Fill the background of the logo box with the "unreachable" color */
952 XFillRectangle (st->dpy, st->window, st->ugc,
953 border_x + 3 + st->grid_width * st->logo_x,
954 border_y + 3 + st->grid_height * st->logo_y,
955 ww, hh);
956
957 XSetClipOrigin (st->dpy, st->logo_gc, lx, ly);
958 if (d == 1)
959 XCopyPlane (st->dpy, st->logo_map, st->window, st->logo_gc,
960 0, 0, w, h, lx, ly, 1);
961 else
962 XCopyArea (st->dpy, st->logo_map, st->window, st->logo_gc,
963 0, 0, w, h, lx, ly);
964 }
965 draw_solid_square (st, st->start_x, st->start_y, WALL_TOP >> st->start_dir, st->tgc);
966 draw_solid_square (st, st->end_x, st->end_y, WALL_TOP >> st->end_dir, st->tgc);
967 }
968
969
970 /* Mark the maze grid as having a wall at the given coordinate,
971 and draw that wall on the screen. */
972 static void
build_wall(struct state * st,int i,int j,int dir)973 build_wall(struct state *st, int i, int j, int dir)
974 {
975 /* Draw it on the screen. */
976 draw_wall(st, i, j, dir, st->gc);
977 /* Put it in the maze. */
978 switch(dir)
979 {
980 case 0:
981 st->maze[i][j] |= WALL_TOP;
982 if(j>0)
983 st->maze[i][j-1] |= WALL_BOTTOM;
984 break;
985 case 1:
986 st->maze[i][j] |= WALL_RIGHT;
987 if(i<st->maze_size_x-1)
988 st->maze[i+1][j] |= WALL_LEFT;
989 break;
990 case 2:
991 st->maze[i][j] |= WALL_BOTTOM;
992 if(j<st->maze_size_y-1)
993 st->maze[i][j+1] |= WALL_TOP;
994 break;
995 case 3:
996 st->maze[i][j] |= WALL_LEFT;
997 if(i>0)
998 st->maze[i-1][j] |= WALL_RIGHT;
999 break;
1000 }
1001 }
1002
1003
1004 static void
draw_wall(struct state * st,int i,int j,int dir,GC with_gc)1005 draw_wall(struct state *st, int i, int j, int dir, GC with_gc) /* draw a single wall */
1006 {
1007 switch (dir) {
1008 case 0:
1009 XDrawLine(st->dpy, st->window, with_gc,
1010 border_x + st->grid_width * i,
1011 border_y + st->grid_height * j,
1012 border_x + st->grid_width * (i+1),
1013 border_y + st->grid_height * j);
1014 break;
1015 case 1:
1016 XDrawLine(st->dpy, st->window, with_gc,
1017 border_x + st->grid_width * (i+1),
1018 border_y + st->grid_height * j,
1019 border_x + st->grid_width * (i+1),
1020 border_y + st->grid_height * (j+1));
1021 break;
1022 case 2:
1023 XDrawLine(st->dpy, st->window, with_gc,
1024 border_x + st->grid_width * i,
1025 border_y + st->grid_height * (j+1),
1026 border_x + st->grid_width * (i+1),
1027 border_y + st->grid_height * (j+1));
1028 break;
1029 case 3:
1030 XDrawLine(st->dpy, st->window, with_gc,
1031 border_x + st->grid_width * i,
1032 border_y + st->grid_height * j,
1033 border_x + st->grid_width * i,
1034 border_y + st->grid_height * (j+1));
1035 break;
1036 }
1037
1038 if(st->sync_p) {
1039 /* too slow if we sync on every wall, so only sync about ten times
1040 during the maze-creation process.
1041 */
1042 st->sync_tick--;
1043 if (st->sync_tick <= 0) {
1044 XSync(st->dpy, False);
1045 st->sync_tick = st->maze_size_x * st->maze_size_x / 10;
1046 }
1047 }
1048 }
1049
1050
1051 static void
draw_solid_square(struct state * st,int i,int j,int dir,GC with_gc)1052 draw_solid_square(struct state *st,
1053 int i, int j,
1054 int dir, GC with_gc)
1055 {
1056 switch (dir) {
1057 case WALL_TOP:
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->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
1062 break;
1063 case WALL_RIGHT:
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->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
1068 break;
1069 case WALL_BOTTOM:
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->bw+st->bw+(st->bw==0?1:0)), st->grid_height);
1074 break;
1075 case WALL_LEFT:
1076 XFillRectangle(st->dpy, st->window, with_gc,
1077 border_x - st->bw-(st->bw==0?1:0) + st->grid_width * i,
1078 border_y + st->bw+(st->bw==0?1:0) + st->grid_height * j,
1079 st->grid_width, st->grid_height - (st->bw+st->bw+(st->bw==0?1:0)));
1080 break;
1081 }
1082 }
1083
1084 /****************************************************************************
1085 Solving the maze
1086 ****************************************************************************/
1087
1088 static int
longdeadend_p(struct state * st,int x1,int y1,int x2,int y2,int endwall)1089 longdeadend_p(struct state *st, int x1, int y1, int x2, int y2, int endwall)
1090 {
1091 int dx = x2 - x1, dy = y2 - y1;
1092 int sidewalls;
1093
1094 sidewalls = endwall | (endwall >> 2 | endwall << 2);
1095 sidewalls = ~sidewalls & WALL_ANY;
1096
1097 while((st->maze[x2][y2] & WALL_ANY) == sidewalls)
1098 {
1099 if (x2 + dx < 0 || x2 + dx >= st->maze_size_x ||
1100 y2 + dy < 0 || y2 + dy >= st->maze_size_y)
1101 break;
1102 x2 += dx;
1103 y2 += dy;
1104 }
1105
1106 if((st->maze[x2][y2] & WALL_ANY) == (sidewalls | endwall))
1107 {
1108 endwall = (endwall >> 2 | endwall << 2) & WALL_ANY;
1109 while(x1 != x2 || y1 != y2)
1110 {
1111 x1 += dx;
1112 y1 += dy;
1113 draw_solid_square(st, x1, y1, endwall, st->sgc);
1114 st->maze[x1][y1] |= SOLVER_VISIT;
1115 }
1116 return 1;
1117 }
1118 else
1119 return 0;
1120 }
1121
1122 /* Find all dead regions -- areas from which the goal cannot be reached --
1123 and mark them visited. */
1124 static void
find_dead_regions(struct state * st)1125 find_dead_regions(struct state *st)
1126 {
1127 int xx, yy, flipped;
1128
1129 /* Find all not SOLVER_VISIT squares bordering NOT_DEAD squares
1130 and mark them NOT_DEAD also. Repeat until no more such squares. */
1131 st->maze[st->start_x][st->start_y] |= NOT_DEAD;
1132
1133 do
1134 {
1135 flipped = 0;
1136 for(xx = 0; xx < st->maze_size_x; xx++)
1137 for(yy = 0; yy < st->maze_size_y; yy++)
1138 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1139 && ( (xx && (st->maze[xx-1][yy] & NOT_DEAD))
1140 || (yy && (st->maze[xx][yy-1] & NOT_DEAD))))
1141 {
1142 flipped = 1;
1143 st->maze[xx][yy] |= NOT_DEAD;
1144 }
1145 for(xx = st->maze_size_x-1; xx >= 0; xx--)
1146 for(yy = st->maze_size_y-1; yy >= 0; yy--)
1147 if(!(st->maze[xx][yy] & (SOLVER_VISIT | NOT_DEAD))
1148 && ( (xx != st->maze_size_x-1 && (st->maze[xx+1][yy] & NOT_DEAD))
1149 || (yy != st->maze_size_y-1 && (st->maze[xx][yy+1] & NOT_DEAD))))
1150 {
1151 flipped = 1;
1152 st->maze[xx][yy] |= NOT_DEAD;
1153 }
1154 }
1155 while(flipped);
1156
1157 for (yy = 0; yy < st->maze_size_y; yy++)
1158 for (xx = 0; xx < st->maze_size_x; xx++)
1159 {
1160 if (st->maze[xx][yy] & NOT_DEAD)
1161 st->maze[xx][yy] &= ~NOT_DEAD;
1162 else if (!(st->maze[xx][yy] & SOLVER_VISIT))
1163 {
1164 st->maze[xx][yy] |= SOLVER_VISIT;
1165 if((xx < st->logo_x || xx > st->logo_x + st->logo_width / st->grid_width) ||
1166 (yy < st->logo_y || yy > st->logo_y + st->logo_height / st->grid_height))
1167 {
1168 /* if we are completely surrounded by walls, just draw the
1169 inside part */
1170 if ((st->maze[xx][yy] & WALL_ANY) == WALL_ANY)
1171 XFillRectangle(st->dpy, st->window, st->ugc,
1172 border_x + st->bw + st->grid_width * xx,
1173 border_y + st->bw + st->grid_height * yy,
1174 st->grid_width - (st->bw+st->bw), st->grid_height - (st->bw+st->bw));
1175 else
1176 {
1177 if (! (st->maze[xx][yy] & WALL_LEFT))
1178 draw_solid_square(st, xx, yy, WALL_LEFT, st->ugc);
1179 if (! (st->maze[xx][yy] & WALL_RIGHT))
1180 draw_solid_square(st, xx, yy, WALL_RIGHT, st->ugc);
1181 if (! (st->maze[xx][yy] & WALL_TOP))
1182 draw_solid_square(st, xx, yy, WALL_TOP, st->ugc);
1183 if (! (st->maze[xx][yy] & WALL_BOTTOM))
1184 draw_solid_square(st, xx, yy, WALL_BOTTOM, st->ugc);
1185 }
1186 }
1187 }
1188 }
1189 }
1190
1191 /* solve the maze by one more tick */
1192 static int
solve_maze(struct state * st)1193 solve_maze (struct state *st)
1194 {
1195 struct solve_state *ss = st->solve_state;
1196 if (!ss)
1197 ss = st->solve_state = (struct solve_state *) calloc (1, sizeof(*ss));
1198
1199 if (!ss->running) {
1200 /* plug up the surrounding wall */
1201 st->maze[st->end_x][st->end_y] |= (WALL_TOP >> st->end_dir);
1202
1203 /* initialize search path */
1204 ss->i = 0;
1205 st->path[ss->i].x = st->end_x;
1206 st->path[ss->i].y = st->end_y;
1207 st->path[ss->i].dir = 0;
1208 st->maze[st->end_x][st->end_y] |= SOLVER_VISIT;
1209
1210 ss->running = 1;
1211 }
1212
1213 /* do it */
1214 /* while (1) */
1215 {
1216 int dir, from, ways;
1217
1218 if ( st->maze[st->path[ss->i].x][st->path[ss->i].y] & START_SQUARE )
1219 {
1220 ss->running = 0;
1221 return 1;
1222 }
1223
1224 if(!st->path[ss->i].dir)
1225 {
1226 ways = 0;
1227 /* First visit this square. Which adjacent squares are open? */
1228 for(dir = WALL_TOP; dir & WALL_ANY; dir >>= 1)
1229 {
1230 if(st->maze[st->path[ss->i].x][st->path[ss->i].y] & dir)
1231 continue;
1232
1233 ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1234 ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1235
1236 if(st->maze[ss->x][ss->y] & SOLVER_VISIT)
1237 continue;
1238
1239 from = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1240 /* don't enter obvious dead ends */
1241 if(((st->maze[ss->x][ss->y] & WALL_ANY) | from) != WALL_ANY)
1242 {
1243 if(!longdeadend_p(st, st->path[ss->i].x, st->path[ss->i].y, ss->x, ss->y, dir))
1244 ways |= dir;
1245 }
1246 else
1247 {
1248 draw_solid_square(st, ss->x, ss->y, from, st->sgc);
1249 st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1250 }
1251 }
1252 }
1253 else
1254 ways = st->path[ss->i].ways;
1255 /* ways now has a bitmask of open paths. */
1256
1257 if(!ways)
1258 goto backtrack;
1259
1260 if (!st->ignorant_p)
1261 {
1262 ss->x = st->path[ss->i].x - st->start_x;
1263 ss->y = st->path[ss->i].y - st->start_y;
1264 /* choice one */
1265 if(abs(ss->y) <= abs(ss->x))
1266 dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1267 else
1268 dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM;
1269
1270 if(dir & ways)
1271 goto found;
1272
1273 /* choice two */
1274 switch(dir)
1275 {
1276 case WALL_LEFT:
1277 case WALL_RIGHT:
1278 dir = (ss->y > 0) ? WALL_TOP : WALL_BOTTOM; break;
1279 case WALL_TOP:
1280 case WALL_BOTTOM:
1281 dir = (ss->x > 0) ? WALL_LEFT : WALL_RIGHT;
1282 }
1283
1284 if(dir & ways)
1285 goto found;
1286
1287 /* choice three */
1288
1289 dir = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1290 if(dir & ways)
1291 goto found;
1292
1293 /* choice four */
1294 dir = ways;
1295 if(!dir)
1296 goto backtrack;
1297
1298 found: ;
1299 }
1300 else
1301 {
1302 if(ways&WALL_TOP)
1303 dir = WALL_TOP;
1304 else if(ways&WALL_LEFT)
1305 dir = WALL_LEFT;
1306 else if(ways&WALL_BOTTOM)
1307 dir = WALL_BOTTOM;
1308 else if(ways&WALL_RIGHT)
1309 dir = WALL_RIGHT;
1310 else
1311 goto backtrack;
1312 }
1313 ss->bt = 0;
1314 ways &= ~dir; /* tried this one */
1315
1316 ss->y = st->path[ss->i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1317 ss->x = st->path[ss->i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1318
1319 /* advance in direction dir */
1320 st->path[ss->i].dir = dir;
1321 st->path[ss->i].ways = ways;
1322 draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, dir, st->tgc);
1323
1324 ss->i++;
1325 st->path[ss->i].dir = 0;
1326 st->path[ss->i].ways = 0;
1327 st->path[ss->i].x = ss->x;
1328 st->path[ss->i].y = ss->y;
1329 st->maze[ss->x][ss->y] |= SOLVER_VISIT;
1330 return 0;
1331 /* continue; */
1332
1333 backtrack:
1334 if(ss->i == 0)
1335 {
1336 printf("Unsolvable maze.\n");
1337 ss->running = 0;
1338 return 1;
1339 }
1340
1341 if(!ss->bt && !st->ignorant_p)
1342 find_dead_regions(st);
1343 ss->bt = 1;
1344 from = st->path[ss->i-1].dir;
1345 from = (from << 2 & WALL_ANY) | (from >> 2 & WALL_ANY);
1346
1347 draw_solid_square(st, st->path[ss->i].x, st->path[ss->i].y, from, st->cgc);
1348 ss->i--;
1349 }
1350
1351 return 0;
1352 }
1353
1354
1355 /****************************************************************************
1356 XScreenSaver boilerplate: resources, command line options, and main loop.
1357 ****************************************************************************/
1358
1359 static const char *maze_defaults[] = {
1360 ".background: black",
1361 ".foreground: white",
1362 "*fpsSolid: true",
1363 "*gridSize: 0",
1364 "*generator: -1",
1365 "*maxLength: 5",
1366 "*ignorant: False",
1367
1368 "*solveDelay: 10000",
1369 "*preDelay: 2000000",
1370 "*postDelay: 4000000",
1371
1372 "*liveColor: #00FF00",
1373 "*deadColor: #880000",
1374 "*skipColor: #8B5A00",
1375 "*surroundColor: #220055",
1376
1377 0
1378 };
1379
1380 static XrmOptionDescRec maze_options[] = {
1381 { "-ignorant", ".ignorant", XrmoptionNoArg, "True" },
1382 { "-no-ignorant", ".ignorant", XrmoptionNoArg, "False" },
1383 { "-grid-size", ".gridSize", XrmoptionSepArg, 0 },
1384 { "-solve-delay", ".solveDelay", XrmoptionSepArg, 0 },
1385 { "-pre-delay", ".preDelay", XrmoptionSepArg, 0 },
1386 { "-post-delay", ".postDelay", XrmoptionSepArg, 0 },
1387 { "-bg-color", ".background", XrmoptionSepArg, 0 },
1388 { "-fg-color", ".foreground", XrmoptionSepArg, 0 },
1389 { "-live-color", ".liveColor", XrmoptionSepArg, 0 },
1390 { "-dead-color", ".deadColor", XrmoptionSepArg, 0 },
1391 { "-skip-color", ".skipColor", XrmoptionSepArg, 0 },
1392 { "-surround-color", ".surroundColor",XrmoptionSepArg, 0 },
1393 { "-generator", ".generator", XrmoptionSepArg, 0 },
1394 { "-max-length", ".maxLength", XrmoptionSepArg, 0 },
1395 { 0, 0, 0, 0 }
1396 };
1397
1398 static int generator = 0;
1399
1400 static void *
maze_init(Display * dpy_arg,Window window_arg)1401 maze_init (Display *dpy_arg, Window window_arg)
1402 {
1403 struct state *st = (struct state *) calloc (1, sizeof(*st));
1404 int size;
1405 XWindowAttributes xgwa;
1406 unsigned long bg, fg, pfg, pbg, sfg, ufg;
1407
1408 st->dpy = dpy_arg;
1409 st->window = window_arg;
1410
1411 st->stop = 0;
1412 st->state = 1;
1413 st->restart = 1;
1414
1415 st->ifrandom = 0;
1416 st->ifinit = 1;
1417
1418 size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1419 st->solve_delay = get_integer_resource (st->dpy, "solveDelay", "Integer");
1420 st->pre_solve_delay = get_integer_resource (st->dpy, "preDelay", "Integer");
1421 st->post_solve_delay = get_integer_resource (st->dpy, "postDelay", "Integer");
1422 generator = get_integer_resource(st->dpy, "generator", "Integer");
1423 st->max_length = get_integer_resource(st->dpy, "maxLength", "Integer");
1424 st->ignorant_p = get_boolean_resource(st->dpy, "ignorant", "Boolean");
1425
1426 if (get_boolean_resource (st->dpy, "doFPS", "DoFPS"))
1427 {
1428 /* Just guess, rather than loading and measuring the "fpsFont"... */
1429 st->fps_width = 210;
1430 st->fps_height = 62;
1431 }
1432
1433 if (!size) st->ifrandom = 1;
1434
1435 if (size < 2) size = 7 + (random () % 30);
1436 st->grid_width = st->grid_height = size;
1437 st->bw = (size > 6 ? 3 : (size-1)/2);
1438
1439 XGetWindowAttributes (st->dpy, st->window, &xgwa);
1440
1441 st->x = 0;
1442 st->y = 0;
1443
1444 set_maze_sizes (st, xgwa.width, xgwa.height);
1445
1446 st->gc = XCreateGC(st->dpy, st->window, 0, 0);
1447 st->cgc = XCreateGC(st->dpy, st->window, 0, 0);
1448 st->tgc = XCreateGC(st->dpy, st->window, 0, 0);
1449 st->sgc = XCreateGC(st->dpy, st->window, 0, 0);
1450 st->ugc = XCreateGC(st->dpy, st->window, 0, 0);
1451 st->logo_gc = XCreateGC(st->dpy, st->window, 0, 0);
1452 st->erase_gc = XCreateGC(st->dpy, st->window, 0, 0);
1453
1454 bg = get_pixel_resource (st->dpy, xgwa.colormap, "background","Background");
1455 fg = get_pixel_resource (st->dpy, xgwa.colormap, "foreground","Foreground");
1456 pfg = get_pixel_resource (st->dpy, xgwa.colormap, "liveColor", "Foreground");
1457 pbg = get_pixel_resource (st->dpy, xgwa.colormap, "deadColor", "Foreground");
1458 sfg = get_pixel_resource (st->dpy, xgwa.colormap, "skipColor", "Foreground");
1459 ufg = get_pixel_resource (st->dpy, xgwa.colormap, "surroundColor", "Foreground");
1460
1461 XSetForeground (st->dpy, st->gc, fg);
1462 XSetBackground (st->dpy, st->gc, bg);
1463 XSetForeground (st->dpy, st->cgc, pbg);
1464 XSetBackground (st->dpy, st->cgc, bg);
1465 XSetForeground (st->dpy, st->tgc, pfg);
1466 XSetBackground (st->dpy, st->tgc, bg);
1467 XSetForeground (st->dpy, st->sgc, sfg);
1468 XSetBackground (st->dpy, st->sgc, bg);
1469 XSetForeground (st->dpy, st->ugc, ufg);
1470 XSetBackground (st->dpy, st->ugc, bg);
1471 XSetForeground (st->dpy, st->logo_gc, fg);
1472 XSetBackground (st->dpy, st->logo_gc, bg);
1473 XSetForeground (st->dpy, st->erase_gc, bg);
1474 XSetBackground (st->dpy, st->erase_gc, bg);
1475
1476 # ifdef HAVE_JWXYZ
1477 jwxyz_XSetAntiAliasing (st->dpy, st->gc, False);
1478 # endif
1479
1480 {
1481 Pixmap logo_mask = 0;
1482 if (xgwa.width > 900 || xgwa.height > 900)
1483 st->logo_map = image_data_to_pixmap (st->dpy, st->window,
1484 logo_180_png, sizeof(logo_180_png),
1485 &st->logo_width, &st->logo_height,
1486 &logo_mask);
1487 else
1488 st->logo_map = image_data_to_pixmap (st->dpy, st->window,
1489 logo_50_png, sizeof(logo_50_png),
1490 &st->logo_width, &st->logo_height,
1491 &logo_mask);
1492 if (logo_mask) {
1493 XSetClipMask (st->dpy, st->logo_gc, logo_mask);
1494 XFreePixmap (st->dpy, logo_mask);
1495 }
1496 }
1497
1498 st->restart = 0;
1499 st->sync_p = 1;
1500
1501 return st;
1502 }
1503
1504
1505 static void
maze_reshape(Display * dpy,Window window,void * closure,unsigned int w,unsigned int h)1506 maze_reshape (Display *dpy, Window window, void *closure,
1507 unsigned int w, unsigned int h)
1508 {
1509 struct state *st = (struct state *) closure;
1510 st->restart = 1;
1511 }
1512
1513
1514 static unsigned long
maze_draw(Display * dpy,Window window,void * closure)1515 maze_draw (Display *dpy, Window window, void *closure)
1516 {
1517 struct state *st = (struct state *) closure;
1518 int this_delay = st->solve_delay;
1519
1520 if (st->eraser || st->erase_window)
1521 {
1522 st->erase_window = 0;
1523 st->eraser = erase_window (st->dpy, st->window, st->eraser);
1524 if (st->eraser)
1525 this_delay = 10000;
1526 else {
1527 this_delay = 1000000;
1528 if (this_delay > st->pre_solve_delay)
1529 this_delay = st->pre_solve_delay;
1530 }
1531 goto END;
1532 }
1533
1534 if (st->restart || st->stop) goto pop;
1535 switch (st->state) {
1536 case 1:
1537 initialize_maze(st);
1538 if (st->ifrandom && st->ifinit)
1539 {
1540 int size;
1541 size = 7 + (random () % 30);
1542 st->grid_width = st->grid_height = size;
1543 st->bw = (size > 6 ? 3 : (size-1)/2);
1544 st->ifinit = 0;
1545 st->restart = 1;
1546 }
1547 break;
1548 case 2:
1549 XClearWindow(st->dpy, st->window);
1550 draw_maze_border(st);
1551 break;
1552 case 3:
1553 st->this_gen = generator;
1554 if(st->this_gen<0 || st->this_gen>2)
1555 st->this_gen = random()%3;
1556
1557 switch(st->this_gen)
1558 {
1559 case 0:
1560 create_maze(st);
1561 break;
1562 case 1:
1563 alt_create_maze(st);
1564 break;
1565 case 2:
1566 set_create_maze(st);
1567 break;
1568 }
1569 break;
1570 case 4:
1571 this_delay = st->pre_solve_delay;
1572 break;
1573 case 5:
1574 if (! solve_maze(st))
1575 --st->state; /* stay in state 5 */
1576 break;
1577 case 6:
1578 st->erase_window = 1;
1579 this_delay = st->post_solve_delay;
1580 st->state = 0 ;
1581 st->ifinit = 1;
1582 break;
1583 default:
1584 abort ();
1585 }
1586 ++st->state;
1587 pop:
1588 if (st->restart)
1589 {
1590 XWindowAttributes xgwa;
1591 int size;
1592
1593 st->restart = 0;
1594 st->stop = 0;
1595 st->state = 1;
1596
1597 if (st->solve_state && st->solve_state->running)
1598 st->solve_state->running = 0;
1599
1600 st->sync_p = ((random() % 4) != 0);
1601
1602 size = get_integer_resource (st->dpy, "gridSize", "Dimension");
1603 if (size < 2) size = 7 + (random () % 30);
1604 st->grid_width = st->grid_height = size;
1605 st->bw = (size > 6 ? 3 : (size-1)/2);
1606
1607 XGetWindowAttributes (st->dpy, st->window, &xgwa);
1608 set_maze_sizes (st, xgwa.width, xgwa.height);
1609 }
1610
1611 END:
1612 return this_delay;
1613 }
1614
1615
1616 static Bool
maze_event(Display * dpy,Window window,void * closure,XEvent * event)1617 maze_event (Display *dpy, Window window, void *closure, XEvent *event)
1618 {
1619 struct state *st = (struct state *) closure;
1620 if (event->type == ButtonPress)
1621 {
1622 switch (event->xbutton.button)
1623 {
1624 case 2:
1625 st->stop = !st->stop ;
1626 if (st->state == 5) st->state = 4 ;
1627 else {
1628 st->restart = 1;
1629 st->stop = 0;
1630 }
1631 return True;
1632
1633 default:
1634 st->restart = 1 ;
1635 st->stop = 0 ;
1636 return True;
1637 }
1638 }
1639 else if (event->type == Expose)
1640 {
1641 st->restart = 1;
1642 return False;
1643 }
1644 else if (screenhack_event_helper (dpy, window, event))
1645 {
1646 st->restart = 1 ;
1647 st->stop = 0 ;
1648 return True;
1649 }
1650 return False;
1651 }
1652
1653
1654 static void
maze_free(Display * dpy,Window window,void * closure)1655 maze_free (Display *dpy, Window window, void *closure)
1656 {
1657 struct state *st = (struct state *) closure;
1658 XFreeGC (dpy, st->gc);
1659 XFreeGC (dpy, st->cgc);
1660 XFreeGC (dpy, st->tgc);
1661 XFreeGC (dpy, st->sgc);
1662 XFreeGC (dpy, st->ugc);
1663 XFreeGC (dpy, st->logo_gc);
1664 XFreeGC (dpy, st->erase_gc);
1665 if (st->solve_state) free (st->solve_state);
1666 if (st->logo_map) XFreePixmap (dpy, st->logo_map);
1667 exit_sets (st);
1668 free (st);
1669 }
1670
1671 XSCREENSAVER_MODULE ("Maze", maze)
1672