1 /* -*- Mode: C; tab-width: 4 -*- */
2 /* maze --- a varying maze */
3
4 #if 0
5 static const char sccsid[] = "@(#)maze.c 5.00 2000/11/01 xlockmore";
6
7 #endif
8
9 /*-
10 * Copyright (c) 1988 by Sun Microsystems
11 *
12 * Permission to use, copy, modify, and distribute this software and its
13 * documentation for any purpose and without fee is hereby granted,
14 * provided that the above copyright notice appear in all copies and that
15 * both that copyright notice and this permission notice appear in
16 * supporting documentation.
17 *
18 * This file is provided AS IS with no warranties of any kind. The author
19 * shall have no liability with respect to the infringement of copyrights,
20 * trade secrets or any patents by this file or any part thereof. In no
21 * event will the author be liable for any lost revenue or profits or
22 * other special, indirect and consequential damages.
23 *
24 * Revision History:
25 * 27-Nov-2001: interactive maze mode Ephraim Yawitz fyawitz@actcom.co.il
26 * 01-Nov-2000: Allocation checks
27 * 27-Oct-1997: xpm and ras capability added
28 * 10-May-1997: Compatible with xscreensaver
29 * 27-Feb-1996: Add ModeInfo args to init and callback hooks, use new
30 * ModeInfo handle to specify long pauses (eliminate onepause).
31 * Ron Hitchens <ron AT idiom.com>
32 * 20-Jul-1995: minimum size fix Peter Schmitzberger <schmitz@coma.sbg.ac.at>
33 * 17-Jun-1995: removed sleep statements
34 * 22-Mar-1995: multidisplay fix Caleb Epstein <epstein_caleb@jpmorgan.com>
35 * 09-Mar-1995: changed how batchcount is used
36 * 27-Feb-1995: patch for VMS
37 * 04-Feb-1995: patch to slow down maze Heath Kehoe <hakehoe AT icaen.uiowa.edu>
38 * 17-Jun-1994: HP ANSI C compiler needs a type cast for gray_bits
39 * Richard Lloyd <R.K.Lloyd@csc.liv.ac.uk>
40 * 02-Sep-1993: xlock version David Bagley <bagleyd AT verizon.net>
41 * 07-Mar-1993: Good ideas from xscreensaver Jamie Zawinski <jwz AT jwz.org>
42 * 06-Jun-1985: Martin Weiss Sun Microsystems
43 */
44
45 /*-
46 * original copyright
47 * **************************************************************************
48 * Copyright 1988 by Sun Microsystems, Inc. Mountain View, CA.
49 *
50 * All Rights Reserved
51 *
52 * Permission to use, copy, modify, and distribute this software and its
53 * documentation for any purpose and without fee is hereby granted, provided
54 * that the above copyright notice appear in all copies and that both that
55 * copyright notice and this permission notice appear in supporting
56 * documentation, and that the names of Sun or MIT not be used in advertising
57 * or publicity pertaining to distribution of the software without specific
58 * prior written permission. Sun and M.I.T. make no representations about the
59 * suitability of this software for any purpose. It is provided "as is"
60 * without any express or implied warranty.
61 *
62 * SUN DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL
63 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
64 * IN NO EVENT SHALL SUN BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
65 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
66 * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
67 * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
68 * SOFTWARE.
69 * ***************************************************************************
70 */
71
72 #ifdef STANDALONE
73 #define MODE_maze
74 #define DEFAULTS "*delay: 1000 \n" \
75 "*cycles: 3000 \n" \
76 "*size: -10 \n" \
77 "*ncolors: 64 \n" \
78 "*bitmap: \n" \
79 "*trackmouse: False \n" \
80
81 # define free_maze 0
82 # define reshape_maze 0
83 # define maze_handle_event 0
84 #include "xlockmore.h" /* in xscreensaver distribution */
85 #else /* STANDALONE */
86 #include "xlock.h" /* in xlockmore distribution */
87 #include "color.h"
88 #include "iostuff.h"
89 #endif /* STANDALONE */
90
91 #ifdef MODE_maze
92
93 #define DEF_TRACKMOUSE "False"
94 #define DEF_THICK "False"
95 #define DEF_THREED "False"
96 static Bool trackmouse;
97 static Bool thick;
98 static Bool threed;
99
100 static XrmOptionDescRec opts[] =
101 {
102 #ifdef DISABLE_INTERACTIVE
103 {(char *) "-trackmouse", (char *) ".maze.trackmouse", XrmoptionNoArg, (caddr_t) "on"},
104 {(char *) "+trackmouse", (char *) ".maze.trackmouse", XrmoptionNoArg, (caddr_t) "off"},
105 #endif
106 {(char *) "-thick", (char *) ".maze.thick", XrmoptionNoArg, (caddr_t) "on"},
107 {(char *) "+thick", (char *) ".maze.thick", XrmoptionNoArg, (caddr_t) "off"},
108 {(char *) "-threed", (char *) ".maze.threed", XrmoptionNoArg, (caddr_t) "on"},
109 {(char *) "+threed", (char *) ".maze.threed", XrmoptionNoArg, (caddr_t) "off"},
110 };
111
112 static argtype vars[] =
113 {
114 #ifdef DISABLE_INTERACTIVE
115 {(void *) & trackmouse, (char *) "trackmouse", (char *) "TrackMouse", (char *) DEF_TRACKMOUSE, t_Bool},
116 #endif
117 {(void *) & thick, (char *) "thick", (char *) "Thick", (char *) DEF_THICK, t_Bool},
118 {(void *) & threed, (char *) "threed", (char *) "ThreeD", (char *) DEF_THREED, t_Bool},
119 };
120
121 static OptionStruct desc[] =
122 {
123 #ifdef DISABLE_INTERACTIVE
124 {(char *) "-/+trackmouse", (char *) "turn on/off the tracking of the mouse"},
125 #endif
126 {(char *) "-/+thick", (char *) "turn on/off the thick tracing"},
127 {(char *) "-/+threed", (char *) "turn on/off the Three D look"},
128 };
129
130 ENTRYPOINT ModeSpecOpt maze_opts =
131 {sizeof opts / sizeof opts[0], opts, sizeof vars / sizeof vars[0], vars, desc};
132
133 #ifdef USE_MODULES
134 ModStruct maze_description =
135 {"maze", "init_maze", "draw_maze", "release_maze",
136 "refresh_maze", "init_maze", (char *) NULL, &maze_opts,
137 1000, 1, 3000, -40, 64, 1.0, "",
138 "Shows a random maze and a depth first search solution", 0, NULL};
139
140 #endif
141
142 #include "bitmaps/gray1.xbm"
143
144 #ifndef STANDALONE
145 /* aliases for vars defined in the bitmap file */
146 #define ICON_WIDTH image_width
147 #define ICON_HEIGHT image_height
148 #define ICON_BITS image_bits
149
150 #include "maze.xbm"
151
152 #ifdef HAVE_XPM
153 #define ICON_NAME image_name
154 #include "maze.xpm"
155 #define DEFAULT_XPM 1
156 #endif
157 #endif
158
159 #define MINGRIDSIZE 2
160
161 #define LOGOWIDTH ((mp->logo == NULL)?64:mp->logo->width)
162 #define LOGOHEIGHT ((mp->logo == NULL)?64:mp->logo->height)
163
164 #define WALL_TOP 0x8000
165 #define WALL_RIGHT 0x4000
166 #define WALL_BOTTOM 0x2000
167 #define WALL_LEFT 0x1000
168
169 #define DOOR_IN_TOP 0x800
170 #define DOOR_IN_RIGHT 0x400
171 #define DOOR_IN_BOTTOM 0x200
172 #define DOOR_IN_LEFT 0x100
173 #define DOOR_IN_ANY 0xF00
174
175 #define DOOR_OUT_TOP 0x80
176 #define DOOR_OUT_RIGHT 0x40
177 #define DOOR_OUT_BOTTOM 0x20
178 #define DOOR_OUT_LEFT 0x10
179
180 #define DIR_UP 0
181 #define DIR_RIGHT 1
182 #define DIR_DOWN 2
183 #define DIR_LEFT 3
184
185 #define START_SQUARE 0x2
186 #define END_SQUARE 0x1
187
188 typedef struct {
189 unsigned int x;
190 unsigned int y;
191 char dir;
192 } paths;
193
194 typedef struct {
195 int ncols, nrows, maze_size, xb, yb;
196 int sqnum, cur_sq_x, cur_sq_y, path_length;
197 int start_x, start_y, start_dir, end_x, end_y, end_dir;
198 int logo_x, logo_y;
199 int width, height;
200 int xs, ys, logo_size_x, logo_size_y;
201 int solving, current_path, stage;
202 int cycles;
203 unsigned int *maze;
204 paths *move_list;
205 paths *save_path, *path;
206 GC grayGC;
207 Pixmap graypix;
208 XImage *logo;
209 Colormap cmap;
210 unsigned long black, color;
211 int graphics_format;
212 GC backGC;
213 int time, space, threed;
214 } mazestruct;
215
216 static mazestruct *mazes = (mazestruct *) NULL;
217
218 static void
draw_wall(ModeInfo * mi,int i,int j,int dir)219 draw_wall(ModeInfo * mi, int i, int j, int dir)
220 { /* draw a single wall */
221 Display *display = MI_DISPLAY(mi);
222 Window window = MI_WINDOW(mi);
223 mazestruct *mp = &mazes[MI_SCREEN(mi)];
224 GC gc = mp->backGC;
225
226 switch (dir) {
227 case 0:
228 XDrawLine(display, window, gc,
229 mp->xb + mp->xs * i,
230 mp->yb + mp->ys * j,
231 mp->xb + mp->xs * (i + 1),
232 mp->yb + mp->ys * j);
233 break;
234 case 1:
235 XDrawLine(display, window, gc,
236 mp->xb + mp->xs * (i + 1),
237 mp->yb + mp->ys * j,
238 mp->xb + mp->xs * (i + 1),
239 mp->yb + mp->ys * (j + 1));
240 break;
241 case 2:
242 XDrawLine(display, window, gc,
243 mp->xb + mp->xs * i,
244 mp->yb + mp->ys * (j + 1),
245 mp->xb + mp->xs * (i + 1),
246 mp->yb + mp->ys * (j + 1));
247 break;
248 case 3:
249 XDrawLine(display, window, gc,
250 mp->xb + mp->xs * i,
251 mp->yb + mp->ys * j,
252 mp->xb + mp->xs * i,
253 mp->yb + mp->ys * (j + 1));
254 break;
255 }
256 } /* end of draw_wall */
257
258 static void
draw_solid_square(ModeInfo * mi,GC gc,register int i,register int j,register int dir)259 draw_solid_square(ModeInfo * mi, GC gc,
260 register int i, register int j, register int dir)
261 { /* draw a solid square in a square */
262 Display *display = MI_DISPLAY(mi);
263 Window window = MI_WINDOW(mi);
264 mazestruct *mp = &mazes[MI_SCREEN(mi)];
265
266 switch (dir) {
267 case 0:
268 XFillRectangle(display, window, gc,
269 mp->xb + 3 * mp->space + mp->xs * i,
270 mp->yb - 3 * mp->space + mp->ys * j,
271 mp->xs + 1 - 6 * mp->space - mp->threed,
272 mp->ys + 1 - mp->threed);
273 break;
274 case 1:
275 XFillRectangle(display, window, gc,
276 mp->xb + 3 * mp->space + mp->xs * i,
277 mp->yb + 3 * mp->space + mp->ys * j,
278 mp->xs + 1 - mp->threed,
279 mp->ys + 1 - 6 * mp->space - mp->threed);
280 break;
281 case 2:
282 XFillRectangle(display, window, gc,
283 mp->xb + 3 * mp->space + mp->xs * i,
284 mp->yb + 3 * mp->space + mp->ys * j,
285 mp->xs + 1 - 6 * mp->space - mp->threed,
286 mp->ys + 1 - mp->threed);
287 break;
288 case 3:
289 XFillRectangle(display, window, gc,
290 mp->xb - 3 * mp->space + mp->xs * i,
291 mp->yb + 3 * mp->space + mp->ys * j,
292 mp->xs + 1 - mp->threed,
293 mp->ys + 1 - 6 * mp->space - mp->threed);
294 break;
295 }
296
297 } /* end of draw_solid_square() */
298
299 static void
enter_square(ModeInfo * mi,int n)300 enter_square(ModeInfo * mi, int n)
301 { /* move into a neighboring square */
302 mazestruct *mp = &mazes[MI_SCREEN(mi)];
303
304 draw_solid_square(mi, mp->backGC, (int) mp->path[n].x, (int) mp->path[n].y,
305 (int) mp->path[n].dir);
306
307 mp->path[n + 1].dir = -1;
308 switch (mp->path[n].dir) {
309 case 0:
310 mp->path[n + 1].x = mp->path[n].x;
311 mp->path[n + 1].y = mp->path[n].y - 1;
312 break;
313 case 1:
314 mp->path[n + 1].x = mp->path[n].x + 1;
315 mp->path[n + 1].y = mp->path[n].y;
316 break;
317 case 2:
318 mp->path[n + 1].x = mp->path[n].x;
319 mp->path[n + 1].y = mp->path[n].y + 1;
320 break;
321 case 3:
322 mp->path[n + 1].x = mp->path[n].x - 1;
323 mp->path[n + 1].y = mp->path[n].y;
324 break;
325 }
326
327 } /* end of enter_square() */
328
329 static void
free_path(mazestruct * mp)330 free_path(mazestruct * mp)
331 {
332 if (mp->maze) {
333 free(mp->maze);
334 mp->maze = (unsigned int *) NULL;
335 }
336 if (mp->move_list) {
337 free(mp->move_list);
338 mp->move_list = (paths *) NULL;
339 }
340 if (mp->save_path) {
341 free(mp->save_path);
342 mp->save_path = (paths *) NULL;
343 }
344 if (mp->path) {
345 free(mp->path);
346 mp->path = (paths *) NULL;
347 }
348 }
349
350 static void
free_stuff(Display * display,mazestruct * mp)351 free_stuff(Display * display, mazestruct * mp)
352 {
353 if (mp->cmap != None) {
354 XFreeColormap(display, mp->cmap);
355 if (mp->backGC != None) {
356 XFreeGC(display, mp->backGC);
357 mp->backGC = None;
358 }
359 mp->cmap = None;
360 } else
361 mp->backGC = None;
362 }
363
364 static void
free_maze_screen(Display * display,mazestruct * mp)365 free_maze_screen(Display * display, mazestruct * mp)
366 {
367 if (mp == NULL) {
368 return;
369 }
370 free_path(mp);
371 if (mp->grayGC != None) {
372 XFreeGC(display, mp->grayGC);
373 mp->grayGC = None;
374 }
375 if (mp->graypix != None) {
376 XFreePixmap(display, mp->graypix);
377 mp->graypix = None;
378 }
379 free_stuff(display, mp);
380 #ifndef STANDALONE
381 /* this used to work there I think */
382
383 if (mp->logo != None) {
384 destroyImage(&mp->logo, &mp->graphics_format);
385 mp->logo = None;
386 }
387 #endif
388 mp = NULL;
389 }
390
391 static Bool
set_maze_sizes(ModeInfo * mi)392 set_maze_sizes(ModeInfo * mi)
393 {
394 mazestruct *mp = &mazes[MI_SCREEN(mi)];
395 Display *display = MI_DISPLAY(mi);
396 int size = MI_SIZE(mi);
397 int minsize;
398
399 if (MI_IS_FULLRANDOM(mi)) {
400 int randNum = NRAND(4);
401
402 mp->threed = (randNum == 1) ? 1 : 0;
403 mp->space = (randNum == 0) ? 0 : 1;
404 } else {
405 mp->threed = (threed) ? 1 : 0;
406 mp->space = (!threed && thick) ? 0 : 1;
407 }
408 minsize = mp->space * 4 + 3 + mp->threed;
409 if (size < -minsize) {
410 free_path(mp);
411 mp->ys = NRAND(MIN(-size, MAX(minsize, (MIN(mp->width, mp->height) - 1) /
412 MINGRIDSIZE)) - minsize + 1) + minsize;
413 } else if (size < minsize) {
414 if (!size)
415 mp->ys = MAX(minsize, (MIN(mp->width, mp->height) - 1) / MINGRIDSIZE);
416 else
417 mp->ys = minsize;
418 } else
419 mp->ys = MIN(size, MAX(minsize, (MIN(mp->width, mp->height) - 1) /
420 MINGRIDSIZE));
421 mp->xs = mp->ys;
422 if (mp->logo == NULL) {
423 mp->logo_size_x = 64 / mp->xs + 1;
424 mp->logo_size_y = 64 / mp->ys + 1;
425 } else {
426 mp->logo_size_x = LOGOWIDTH / mp->xs + 1;
427 mp->logo_size_y = LOGOHEIGHT / mp->ys + 1;
428 }
429 mp->ncols = MAX((mp->width - 1) / mp->xs, MINGRIDSIZE);
430 mp->nrows = MAX((mp->height - 1) / mp->ys, MINGRIDSIZE);
431
432 mp->xb = (mp->width - mp->ncols * mp->xs) / 2;
433 mp->yb = (mp->height - mp->nrows * mp->ys) / 2;
434 mp->maze_size = mp->ncols * mp->nrows;
435 if (!mp->maze)
436 if ((mp->maze = (unsigned int *) calloc(mp->maze_size,
437 sizeof (unsigned int))) == NULL) {
438 free_maze_screen(display, mp);
439 return False;
440 }
441 if (!mp->move_list)
442 if ((mp->move_list = (paths *) calloc(mp->maze_size,
443 sizeof (paths))) == NULL) {
444 free_maze_screen(display, mp);
445 return False;
446 }
447 if (!mp->save_path)
448 if ((mp->save_path = (paths *) calloc(mp->maze_size,
449 sizeof (paths))) == NULL) {
450 free_maze_screen(display, mp);
451 return False;
452 }
453 if (!mp->path)
454 if (( mp->path = (paths *) calloc(mp->maze_size,
455 sizeof (paths))) == NULL) {
456 free_maze_screen(display, mp);
457 return False;
458 }
459 return True;
460 } /* end of set_maze_sizes */
461
462
463 static void
initialize_maze(ModeInfo * mi)464 initialize_maze(ModeInfo * mi)
465 { /* draw the surrounding wall and start/end squares */
466 Display *display = MI_DISPLAY(mi);
467 mazestruct *mp = &mazes[MI_SCREEN(mi)];
468 register int i, j, wall;
469
470 if (MI_NPIXELS(mi) <= 2) {
471 mp->color = MI_WHITE_PIXEL(mi);
472 } else {
473 mp->color = MI_PIXEL(mi, NRAND(MI_NPIXELS(mi)));
474 }
475 XSetForeground(display, mp->backGC, mp->color);
476 XSetForeground(display, mp->grayGC, mp->color);
477 /* initialize all squares */
478 for (i = 0; i < mp->ncols; i++) {
479 for (j = 0; j < mp->nrows; j++) {
480 mp->maze[i * mp->nrows + j] = 0;
481 }
482 }
483
484 /* top wall */
485 for (i = 0; i < mp->ncols; i++) {
486 mp->maze[i * mp->nrows] |= WALL_TOP;
487 }
488
489 /* right wall */
490 for (j = 0; j < mp->nrows; j++) {
491 mp->maze[(mp->ncols - 1) * mp->nrows + j] |= WALL_RIGHT;
492 }
493
494 /* bottom wall */
495 for (i = 0; i < mp->ncols; i++) {
496 mp->maze[i * mp->nrows + mp->nrows - 1] |= WALL_BOTTOM;
497 }
498
499 /* left wall */
500 for (j = 0; j < mp->nrows; j++) {
501 mp->maze[j] |= WALL_LEFT;
502 }
503
504 /* set start square */
505 wall = NRAND(4);
506 switch (wall) {
507 case 0:
508 i = NRAND(mp->ncols);
509 j = 0;
510 break;
511 case 1:
512 i = mp->ncols - 1;
513 j = NRAND(mp->nrows);
514 break;
515 case 2:
516 i = NRAND(mp->ncols);
517 j = mp->nrows - 1;
518 break;
519 case 3:
520 i = 0;
521 j = NRAND(mp->nrows);
522 break;
523 }
524 mp->maze[i * mp->nrows + j] |= START_SQUARE;
525 mp->maze[i * mp->nrows + j] |= (DOOR_IN_TOP >> wall);
526 mp->maze[i * mp->nrows + j] &= ~(WALL_TOP >> wall);
527 mp->cur_sq_x = i;
528 mp->cur_sq_y = j;
529 mp->start_x = i;
530 mp->start_y = j;
531 mp->start_dir = wall;
532 mp->sqnum = 0;
533
534 /* set end square */
535 wall = (wall + 2) % 4;
536 switch (wall) {
537 case 0:
538 i = NRAND(mp->ncols);
539 j = 0;
540 break;
541 case 1:
542 i = mp->ncols - 1;
543 j = NRAND(mp->nrows);
544 break;
545 case 2:
546 i = NRAND(mp->ncols);
547 j = mp->nrows - 1;
548 break;
549 case 3:
550 i = 0;
551 j = NRAND(mp->nrows);
552 break;
553 }
554 mp->maze[i * mp->nrows + j] |= END_SQUARE;
555 mp->maze[i * mp->nrows + j] |= (DOOR_OUT_TOP >> wall);
556 mp->maze[i * mp->nrows + j] &= ~(WALL_TOP >> wall);
557 mp->end_x = i;
558 mp->end_y = j;
559 mp->end_dir = wall;
560
561 /* set logo */
562 if ((mp->ncols > mp->logo_size_x + 2 + 4 * mp->space) &&
563 (mp->nrows > mp->logo_size_y + 2 + 4 * mp->space)) {
564 mp->logo_x = NRAND(mp->ncols - mp->logo_size_x - 2 -
565 4 * mp->space) + 1 + 2 * mp->space;
566 mp->logo_y = NRAND(mp->nrows - mp->logo_size_y - 2 -
567 4 * mp->space) + 1 + 2 * mp->space;
568
569 for (i = 0; i < mp->logo_size_x; i++)
570 for (j = 0; j < mp->logo_size_y; j++)
571 mp->maze[(mp->logo_x + i) * mp->nrows + mp->logo_y + j] |=
572 DOOR_IN_TOP;
573 } else
574 mp->logo_y = mp->logo_x = -1;
575 }
576
577 static int
choose_door(ModeInfo * mi)578 choose_door(ModeInfo * mi)
579 { /* pick a new path */
580 mazestruct *mp = &mazes[MI_SCREEN(mi)];
581 int candidates[3];
582 register int num_candidates;
583
584 num_candidates = 0;
585
586 /* top wall */
587 if ((!(mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y] &
588 DOOR_IN_TOP)) &&
589 (!(mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y] &
590 DOOR_OUT_TOP)) &&
591 (!(mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y] &
592 WALL_TOP))) {
593 if (mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y - 1] &
594 DOOR_IN_ANY) {
595 mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y] |= WALL_TOP;
596 mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y - 1] |=
597 WALL_BOTTOM;
598 } else
599 candidates[num_candidates++] = 0;
600 }
601 /* right wall */
602 if ((!(mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y] &
603 DOOR_IN_RIGHT)) &&
604 (!(mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y] &
605 DOOR_OUT_RIGHT)) &&
606 (!(mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y] &
607 WALL_RIGHT))) {
608 if (mp->maze[(mp->cur_sq_x + 1) * mp->nrows + mp->cur_sq_y] &
609 DOOR_IN_ANY) {
610 mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y] |= WALL_RIGHT;
611 mp->maze[(mp->cur_sq_x + 1) * mp->nrows + mp->cur_sq_y] |=
612 WALL_LEFT;
613 } else
614 candidates[num_candidates++] = 1;
615 }
616 /* bottom wall */
617 if ((!(mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y] &
618 DOOR_IN_BOTTOM)) &&
619 (!(mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y] &
620 DOOR_OUT_BOTTOM)) &&
621 (!(mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y] &
622 WALL_BOTTOM))) {
623 if (mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y + 1] &
624 DOOR_IN_ANY) {
625 mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y] |= WALL_BOTTOM;
626 mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y + 1] |= WALL_TOP;
627 } else
628 candidates[num_candidates++] = 2;
629 }
630 /* left wall */
631 if ((!(mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y] &
632 DOOR_IN_LEFT)) &&
633 (!(mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y] &
634 DOOR_OUT_LEFT)) &&
635 (!(mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y] &
636 WALL_LEFT))) {
637 if (mp->maze[(mp->cur_sq_x - 1) * mp->nrows + mp->cur_sq_y] &
638 DOOR_IN_ANY) {
639 mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y] |= WALL_LEFT;
640 mp->maze[(mp->cur_sq_x - 1) * mp->nrows + mp->cur_sq_y] |=
641 WALL_RIGHT;
642 } else
643 candidates[num_candidates++] = 3;
644 }
645 /* done wall */
646 if (num_candidates == 0)
647 return (-1);
648 if (num_candidates == 1)
649 return (candidates[0]);
650 return (candidates[NRAND(num_candidates)]);
651
652 } /* end of choose_door() */
653
654 static void
draw_maze_walls(ModeInfo * mi)655 draw_maze_walls(ModeInfo * mi)
656 { /* pick a new path */
657 mazestruct *mp = &mazes[MI_SCREEN(mi)];
658 int i, j, isize;
659
660 MI_IS_DRAWN(mi) = True;
661
662 for (i = 0; i < mp->ncols; i++) {
663 isize = i * mp->nrows;
664 for (j = 0; j < mp->nrows; j++) {
665 /* Only need to draw half the walls... since they are shared */
666 /* top wall */
667 if ( /*(!(mp->maze[isize + j] & DOOR_IN_TOP)) &&
668 (!(mp->maze[isize + j] & DOOR_OUT_TOP)) && */
669 (mp->maze[isize + j] & WALL_TOP))
670 draw_wall(mi, i, j, 0);
671 /* left wall */
672 if ( /*(!(mp->maze[isize + j] & DOOR_IN_RIGHT)) &&
673 (!(mp->maze[isize + j] & DOOR_OUT_RIGHT)) && */
674 (mp->maze[isize + j] & WALL_RIGHT))
675 draw_wall(mi, i, j, 1);
676 }
677 }
678 } /* end of draw_maze_walls() */
679
680 static int
backup(mazestruct * mp)681 backup(mazestruct * mp)
682 { /* back up a move */
683 mp->sqnum--;
684 if (mp->sqnum >= 0) {
685 mp->cur_sq_x = mp->move_list[mp->sqnum].x;
686 mp->cur_sq_y = mp->move_list[mp->sqnum].y;
687 }
688 return (mp->sqnum);
689 } /* end of backup() */
690
691 static void
create_maze_walls(ModeInfo * mi)692 create_maze_walls(ModeInfo * mi)
693 { /* create a maze layout given the intiialized maze */
694 mazestruct *mp = &mazes[MI_SCREEN(mi)];
695 register int i, newdoor;
696
697 for (;;) {
698 mp->move_list[mp->sqnum].x = mp->cur_sq_x;
699 mp->move_list[mp->sqnum].y = mp->cur_sq_y;
700 mp->move_list[mp->sqnum].dir = -1;
701 while ((newdoor = choose_door(mi)) == -1) /* pick a door */
702 if (backup(mp) == -1) /* no more doors ... backup */
703 return; /* done ... return */
704
705 /* mark the out door */
706 mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y] |=
707 (DOOR_OUT_TOP >> newdoor);
708
709 switch (newdoor) {
710 case 0:
711 mp->cur_sq_y--;
712 break;
713 case 1:
714 mp->cur_sq_x++;
715 break;
716 case 2:
717 mp->cur_sq_y++;
718 break;
719 case 3:
720 mp->cur_sq_x--;
721 break;
722 }
723 mp->sqnum++;
724
725 /* mark the in door */
726 mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y] |=
727 (DOOR_IN_TOP >> ((newdoor + 2) % 4));
728
729 /* if end square set path length and save path */
730 if (mp->maze[mp->cur_sq_x * mp->nrows + mp->cur_sq_y] &
731 END_SQUARE) {
732 mp->path_length = mp->sqnum;
733 for (i = 0; i < mp->path_length; i++) {
734 mp->save_path[i].x = mp->move_list[i].x;
735 mp->save_path[i].y = mp->move_list[i].y;
736 mp->save_path[i].dir = mp->move_list[i].dir;
737 }
738 }
739 }
740
741 } /* end of create_maze_walls() */
742
743 static void
draw_maze_border(ModeInfo * mi)744 draw_maze_border(ModeInfo * mi)
745 { /* draw the maze outline */
746 Display *display = MI_DISPLAY(mi);
747 Window window = MI_WINDOW(mi);
748 mazestruct *mp = &mazes[MI_SCREEN(mi)];
749 GC gc = mp->backGC;
750 register int i, j;
751
752 #ifndef STANDALONE
753 if (mp->logo_x != -1) {
754 (void) XPutImage(display, window, gc, mp->logo,
755 0, 0,
756 mp->xb + mp->xs * mp->logo_x +
757 (mp->xs * mp->logo_size_x - LOGOWIDTH + 1) / 2,
758 mp->yb + mp->ys * mp->logo_y +
759 (mp->ys * mp->logo_size_y - LOGOHEIGHT + 1) / 2,
760 LOGOWIDTH, LOGOHEIGHT);
761 }
762 #endif
763 for (i = 0; i < mp->ncols; i++) {
764 if (mp->maze[i * mp->nrows] & WALL_TOP) {
765 XDrawLine(display, window, gc,
766 mp->xb + mp->xs * i, mp->yb,
767 mp->xb + mp->xs * (i + 1), mp->yb);
768 }
769 if ((mp->maze[i * mp->nrows + mp->nrows - 1] & WALL_BOTTOM)) {
770 XDrawLine(display, window, gc,
771 mp->xb + mp->xs * i,
772 mp->yb + mp->ys * (mp->nrows),
773 mp->xb + mp->xs * (i + 1),
774 mp->yb + mp->ys * (mp->nrows));
775 }
776 }
777 for (j = 0; j < mp->nrows; j++) {
778 if (mp->maze[(mp->ncols - 1) * mp->nrows + j] & WALL_RIGHT) {
779 XDrawLine(display, window, gc,
780 mp->xb + mp->xs * mp->ncols,
781 mp->yb + mp->ys * j,
782 mp->xb + mp->xs * mp->ncols,
783 mp->yb + mp->ys * (j + 1));
784 }
785 if (mp->maze[j] & WALL_LEFT) {
786 XDrawLine(display, window, gc,
787 mp->xb, mp->yb + mp->ys * j,
788 mp->xb, mp->yb + mp->ys * (j + 1));
789 }
790 }
791
792 draw_solid_square(mi, gc, mp->start_x, mp->start_y, mp->start_dir);
793 draw_solid_square(mi, gc, mp->end_x, mp->end_y, mp->end_dir);
794 } /* end of draw_maze() */
795
796 static void
try_to_move(ModeInfo * mi,int dir)797 try_to_move(ModeInfo *mi, int dir)
798 { /* based on solve_maze */
799 mazestruct *mp = &mazes[MI_SCREEN(mi)];
800 int colliding = mp->maze[mp->path[mp->current_path].x * mp->nrows +
801 mp->path[mp->current_path].y] &
802 (WALL_TOP >> dir); /* Are we trying to go through a wall? */
803
804 if (!colliding && ((mp->current_path == 0) ||
805 /* We're either on the first path or we're not going backwards */
806 ((dir != (unsigned char) (mp->path[mp->current_path - 1].dir +
807 2) % 4))) ) {
808 mp->path[mp->current_path].dir = dir;
809 enter_square(mi, mp->current_path);
810 mp->current_path++;
811 #if 0
812 (void) fprintf(stderr,
813 "Calling draw_solid_square with params: x=%d, y= %d, dir=%d\n",
814 (int) (mp->path[mp->current_path].x),
815 (int) (mp->path[mp->current_path].y),
816 (int) (dir));
817 #endif
818 /* The following call is supposed to make things look more
819 intuitive, i.e., that the square we think we are on is
820 filled in.
821 The direction has to be reversed to prevent it from
822 drawing squares on top of lines.
823 */
824 draw_solid_square(mi, mp->backGC,
825 (int) (mp->path[mp->current_path].x),
826 (int) (mp->path[mp->current_path].y),
827 (int) ((dir + 2) % 4));
828 if (mp->maze[mp->path[mp->current_path].x * mp->nrows +
829 mp->path[mp->current_path].y] & START_SQUARE) {
830 mp->solving = 0;
831 return;
832 }
833 } else {
834 if (!colliding) {
835 draw_solid_square(mi, mp->grayGC,
836 (int) (mp->path[mp->current_path].x),
837 (int) (mp->path[mp->current_path].y),
838 (int) (mp->path[mp->current_path - 1].dir +
839 2) % 4);
840 mp->path[mp->current_path].dir = 4;
841 mp->current_path--;
842 draw_solid_square(mi, mp->grayGC,
843 (int) (mp->path[mp->current_path].x),
844 (int) (mp->path[mp->current_path].y),
845 (int) (mp->path[mp->current_path].dir));
846 }
847 #if 0
848 else {
849 /* Beep if we can't go in that direction */
850 (void) fprintf(stdout, "\a");
851 (void) fflush(stdout);
852 }
853 #endif
854 }
855 } /* end of try_to_move() */
856
857 static void
solve_maze(ModeInfo * mi)858 solve_maze(ModeInfo * mi)
859 { /* solve it with graphical feedback */
860 mazestruct *mp = &mazes[MI_SCREEN(mi)];
861
862 if (!mp->solving) {
863 /* plug up the surrounding wall */
864 mp->maze[mp->start_x * mp->nrows + mp->start_y] |=
865 (WALL_TOP >> mp->start_dir);
866 mp->maze[mp->end_x * mp->nrows + mp->end_y] |=
867 (WALL_TOP >> mp->end_dir);
868
869 /* initialize search path */
870 mp->current_path = 0;
871 mp->path[mp->current_path].x = mp->end_x;
872 mp->path[mp->current_path].y = mp->end_y;
873 mp->path[mp->current_path].dir = -1;
874
875 mp->solving = 1;
876 }
877 if (++mp->path[mp->current_path].dir >= 4) {
878 if (mp->current_path == 0) {
879 /* this can happen if a person backs up from going
880 the right way and then autosolves */
881 mp->path[mp->current_path].dir = -1;
882 return;
883 }
884 /* This draw is to fill in the dead ends,
885 it ends up drawing more gray boxes then it needs to. */
886 draw_solid_square(mi, mp->grayGC,
887 (int) (mp->path[mp->current_path].x),
888 (int) (mp->path[mp->current_path].y),
889 (int) (mp->path[mp->current_path - 1].dir + 2) % 4);
890
891 mp->current_path--;
892 draw_solid_square(mi, mp->grayGC,
893 (int) (mp->path[mp->current_path].x),
894 (int) (mp->path[mp->current_path].y),
895 (int) (mp->path[mp->current_path].dir));
896 } else if (!(mp->maze[mp->path[mp->current_path].x * mp->nrows +
897 mp->path[mp->current_path].y] &
898 (WALL_TOP >> mp->path[mp->current_path].dir)) &&
899 ((mp->current_path == 0) ||
900 ((mp->path[mp->current_path].dir !=
901 (unsigned char) (mp->path[mp->current_path - 1].dir +
902 2) % 4)))) {
903 enter_square(mi, mp->current_path);
904 mp->current_path++;
905 /* This next call is to make the appearance more 'intuitive' */
906 draw_solid_square(mi, mp->backGC,
907 (int) (mp->path[mp->current_path].x),
908 (int) (mp->path[mp->current_path].y),
909 (int) (mp->path[mp->current_path - 1].dir + 2) % 4);
910 if (mp->maze[mp->path[mp->current_path].x * mp->nrows +
911 mp->path[mp->current_path].y] & START_SQUARE) {
912 mp->solving = 0;
913 return;
914 }
915 }
916 } /* end of solve_maze() */
917
918 static void
mouse_maze(ModeInfo * mi)919 mouse_maze(ModeInfo * mi)
920 { /* solve it with graphical feedback */
921 mazestruct *mp = &mazes[MI_SCREEN(mi)];
922 Window r, c;
923 int dx, dy, cx, cy;
924 unsigned int m;
925
926 (void) XQueryPointer(MI_DISPLAY(mi), MI_WINDOW(mi),
927 &r, &c, &dx, &dy, &cx, &cy, &m);
928 dx = cx - (mp->path[mp->current_path].x * mp->xs + mp->xb) - mp->xs / 2;
929 dy = cy - (mp->path[mp->current_path].y * mp->ys + mp->yb) - mp->ys / 2;
930 if (cx <= mp->xb || cy <= mp->yb || cx > mp->ncols * mp->xs + mp->xb ||
931 cy > mp->nrows * mp->ys + mp->yb) {
932 solve_maze(mi);
933 return;
934 }
935 if (2 * abs(dx) / (mp->xs + 1) > 2 * abs(dy) / mp->ys) {
936 if (dx > 0) {
937 try_to_move(mi, DIR_RIGHT);
938 } else {
939 try_to_move(mi, DIR_LEFT);
940 }
941 } else if (2 * abs(dx) / mp->xs < 2 * abs(dy) / (mp->ys + 1)) {
942 if (dy > 0) {
943 try_to_move(mi, DIR_DOWN);
944 } else {
945 try_to_move(mi, DIR_UP);
946 }
947 }
948 }
949
950 static Bool
init_stuff(ModeInfo * mi)951 init_stuff(ModeInfo * mi)
952 {
953 mazestruct *mp = &mazes[MI_SCREEN(mi)];
954 #ifndef STANDALONE
955 Display *display = MI_DISPLAY(mi);
956
957 if (mp->logo == None) {
958 getImage(mi, &mp->logo, ICON_WIDTH, ICON_HEIGHT, ICON_BITS,
959 #ifdef HAVE_XPM
960 DEFAULT_XPM, ICON_NAME,
961 #endif
962 &mp->graphics_format, &mp->cmap, &mp->black);
963 if (mp->logo == None) {
964 free_maze_screen(display, mp);
965 return False;
966 }
967 }
968 if (mp->cmap != None) {
969 Window window = MI_WINDOW(mi);
970 setColormap(display, window, mp->cmap, MI_IS_INWINDOW(mi));
971 if (mp->backGC == None) {
972 XGCValues xgcv;
973
974 xgcv.background = mp->black;
975 if ((mp->backGC = XCreateGC(display, window, GCBackground,
976 &xgcv)) == None) {
977 free_maze_screen(display, mp);
978 return False;
979 }
980 }
981 } else
982 #endif /* STANDALONE */
983 {
984 mp->black = MI_BLACK_PIXEL(mi);
985 mp->backGC = MI_GC(mi);
986 }
987 return True;
988 }
989
990 ENTRYPOINT void
init_maze(ModeInfo * mi)991 init_maze(ModeInfo * mi)
992 {
993 Display *display = MI_DISPLAY(mi);
994 mazestruct *mp;
995
996 MI_INIT(mi, mazes);
997 mp = &mazes[MI_SCREEN(mi)];
998
999 if (!init_stuff(mi))
1000 return;
1001
1002 mp->width = MI_WIDTH(mi);
1003 mp->height = MI_HEIGHT(mi);
1004 mp->width = (mp->width >= 32) ? mp->width : 32;
1005 mp->height = (mp->height >= 32) ? mp->height : 32;
1006
1007 if (mp->graypix == None)
1008 if ((mp->graypix = XCreateBitmapFromData(display, MI_WINDOW(mi),
1009 (char *) gray1_bits, gray1_width, gray1_height)) == None) {
1010 free_maze_screen(display, mp);
1011 return;
1012 }
1013 if (!mp->grayGC) {
1014 if ((mp->grayGC = XCreateGC(display, MI_WINDOW(mi),
1015 0L, (XGCValues *) 0)) == None) {
1016 free_maze_screen(display, mp);
1017 return;
1018 }
1019 XSetBackground(display, mp->grayGC, mp->black);
1020 XSetFillStyle(display, mp->grayGC, FillOpaqueStippled);
1021 XSetStipple(display, mp->grayGC, mp->graypix);
1022 }
1023 mp->solving = 0;
1024 mp->stage = 0;
1025 mp->time = 0;
1026 mp->cycles = MI_CYCLES(mi);
1027 if (mp->cycles < 4)
1028 mp->cycles = 4;
1029 }
1030
1031 ENTRYPOINT void
draw_maze(ModeInfo * mi)1032 draw_maze(ModeInfo * mi)
1033 {
1034 mazestruct *mp;
1035
1036 if (mazes == NULL)
1037 return;
1038 mp = &mazes[MI_SCREEN(mi)];
1039 if (mp->graypix == None)
1040 return;
1041 if (mp->solving) {
1042 if (trackmouse)
1043 mouse_maze(mi);
1044 else
1045 solve_maze(mi);
1046 return;
1047 }
1048 switch (mp->stage) {
1049 case 0:
1050 MI_CLEARWINDOWCOLORMAP(mi, mp->backGC, mp->black);
1051
1052 if (!set_maze_sizes(mi))
1053 return;
1054 initialize_maze(mi);
1055 create_maze_walls(mi);
1056 mp->stage++;
1057 break;
1058 case 1:
1059 draw_maze_border(mi);
1060 mp->stage++;
1061 break;
1062 case 2:
1063 draw_maze_walls(mi);
1064 mp->stage++;
1065 break;
1066 case 3:
1067 if (++mp->time > mp->cycles / (4 * (1 + trackmouse)))
1068 mp->stage++;
1069 break;
1070 case 4:
1071 if (trackmouse) {
1072 /* Initialize paths and draw a square or two */
1073 int i;
1074 for (i = 0; i < 4; i++)
1075 solve_maze(mi);
1076 } else {
1077 solve_maze(mi);
1078 }
1079 mp->stage++;
1080 break;
1081 case 5:
1082 if (++mp->time > 3 * mp->cycles / 4)
1083 init_maze(mi);
1084 break;
1085 }
1086 } /* end of draw_maze() */
1087
1088 ENTRYPOINT void
release_maze(ModeInfo * mi)1089 release_maze(ModeInfo * mi)
1090 {
1091 if (mazes != NULL) {
1092 int screen;
1093
1094 for (screen = 0; screen < MI_NUM_SCREENS(mi); screen++)
1095 free_maze_screen(MI_DISPLAY(mi), &mazes[screen]);
1096 free(mazes);
1097 mazes = (mazestruct *) NULL;
1098 }
1099 }
1100
1101 #ifndef STANDALONE
1102 ENTRYPOINT void
refresh_maze(ModeInfo * mi)1103 refresh_maze(ModeInfo * mi)
1104 {
1105 mazestruct *mp;
1106
1107 if (mazes == NULL)
1108 return;
1109 mp = &mazes[MI_SCREEN(mi)];
1110 if (mp->graypix == None)
1111 return;
1112
1113 #ifdef HAVE_XPM
1114 if (mp->graphics_format >= IS_XPM) {
1115 /* This is needed when another program changes the colormap. */
1116 free_maze_screen(MI_DISPLAY(mi), mp);
1117 init_maze(mi);
1118 return;
1119 }
1120 #endif
1121 MI_CLEARWINDOWCOLORMAP(mi, mp->backGC, mp->black);
1122 XSetForeground(MI_DISPLAY(mi), mp->backGC, mp->color);
1123 if (mp->stage >= 1) {
1124 mp->stage = 3;
1125 mp->sqnum = 0;
1126 mp->cur_sq_x = mp->start_x;
1127 mp->cur_sq_y = mp->start_y;
1128 mp->maze[mp->start_x * mp->nrows + mp->start_y] |= START_SQUARE;
1129 mp->maze[mp->start_x * mp->nrows + mp->start_y] |=
1130 (DOOR_IN_TOP >> mp->start_dir);
1131 mp->maze[mp->start_x * mp->nrows + mp->start_y] &=
1132 ~(WALL_TOP >> mp->start_dir);
1133 mp->maze[mp->end_x * mp->nrows + mp->end_y] |= END_SQUARE;
1134 mp->maze[mp->end_x * mp->nrows + mp->end_y] |=
1135 (DOOR_OUT_TOP >> mp->end_dir);
1136 mp->maze[mp->end_x * mp->nrows + mp->end_y] &=
1137 ~(WALL_TOP >> mp->end_dir);
1138 draw_maze_border(mi);
1139 draw_maze_walls(mi);
1140 }
1141 mp->solving = 0;
1142 }
1143 #endif
1144
1145 XSCREENSAVER_MODULE ("Maze", maze)
1146
1147 #endif /* MODE_maze */
1148