1 /* -*- Mode: C; tab-width: 4 -*- */
2 /* dragon --- Oskar van Deventer's Hexagonal Dragons Maze */
3
4 #if 0
5 static const char sccsid[] = "@(#)dragon.c 5.24 2007/01/18 xlockmore";
6
7 #endif
8
9 /*-
10 * Copyright (c) 2001 by David Bagley.
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 * From "Fractal Garden Maze" by Oskar van Deventer, Cubism For Fun
25 * Issue 54 February 2001 p16, 17. The maze itself is called a "Hexagonal
26 * Dragons Maze", named after its similarity to the Dragon Curve (see
27 * turtle.c).
28 *
29 * Revision History:
30 * 18-Jan-2007: Added vertical option.
31 * 07-Mar-2001: Started writing, based on demon mode
32 */
33
34 /*-
35 Grid Number of Neighbors
36 ---- ------------------
37 Hexagon 6
38 */
39
40 #ifdef STANDALONE
41 # define MODE_dragon
42 # define DEFAULTS "*delay: 2000000 \n" \
43 "*cycles: 16 \n" \
44 "*size: -24 \n" \
45 "*ncolors: 64 \n" \
46 "*neighbors: 6 \n" \
47
48 # define free_dragon 0
49 # define reshape_dragon 0
50 # define dragon_handle_event 0
51 # define UNIFORM_COLORS
52 # include "xlockmore.h" /* in xscreensaver distribution */
53 #else /* STANDALONE */
54 # include "xlock.h" /* in xlockmore distribution */
55 #endif /* STANDALONE */
56 #include "automata.h"
57
58 #ifdef MODE_dragon
59
60 #define DEF_VERTICAL "False"
61
62 static Bool vertical;
63
64 static XrmOptionDescRec opts[] =
65 {
66 {(char *) "-vertical", (char *) ".dragon.vertical", XrmoptionNoArg, (caddr_t) "on"},
67 {(char *) "+vertical", (char *) ".dragon.vertical", XrmoptionNoArg, (caddr_t) "off"}
68
69 };
70 static argtype vars[] =
71 {
72 {(void *) & vertical, (char *) "vertical", (char *) "Vertical", (char *) DEF_VERTICAL, t_Bool}
73 };
74 static OptionStruct desc[] =
75 {
76 {(char *) "-/+vertical", (char *) "change orientation for hexagons"}
77 };
78
79 ENTRYPOINT ModeSpecOpt dragon_opts =
80 {sizeof opts / sizeof opts[0], opts, sizeof vars / sizeof vars[0], vars, desc};
81
82 #ifdef USE_MODULES
83 ModStruct dragon_description =
84 {"dragon", "init_dragon", "draw_dragon", "release_dragon",
85 "refresh_dragon", "init_dragon", (char *) NULL, &dragon_opts,
86 2000000, 1, 16, -24, 64, 1.0, "",
87 "Shows Deventer's Hexagonal Dragons Maze", 0, NULL};
88
89 #endif
90
91 #include "bitmaps/gray1.xbm"
92
93 #define STATES 3
94 #define LISTS 2
95 #define REDRAWSTEP 2000 /* How many cells to draw per cycle */
96 #define MINGRIDSIZE 16
97 #define MINSIZE 4
98
99 /* Singly linked list */
100 typedef struct _CellList {
101 XPoint pt;
102 struct _CellList *next;
103 } CellList;
104
105 typedef struct {
106 Bool vertical;
107 int generation;
108 int xs, ys;
109 int xb, yb;
110 int nrows, ncols;
111 int width, height;
112 int addlist;
113 int redrawing, redrawpos;
114 int *ncells;
115 unsigned long color;
116 CellList **cellList;
117 unsigned char *oldcell;
118 GC stippledGC;
119 Pixmap graypix;
120 XPoint hexagon[6];
121 } dragonstruct;
122
123 static dragonstruct *dragons = (dragonstruct *) NULL;
124
125 static void
drawcell(ModeInfo * mi,int col,int row,unsigned char state)126 drawcell(ModeInfo * mi, int col, int row, unsigned char state)
127 {
128 dragonstruct *dp = &dragons[MI_SCREEN(mi)];
129 Display *display = MI_DISPLAY(mi);
130 GC gc;
131
132 if (!state) {
133 XSetForeground(display, MI_GC(mi), MI_WHITE_PIXEL(mi));
134 gc = MI_GC(mi);
135 } else if (state == 1) {
136 XSetForeground(display, MI_GC(mi), MI_BLACK_PIXEL(mi));
137 gc = MI_GC(mi);
138 } else if (MI_NPIXELS(mi) > 2) {
139 XSetForeground(display, MI_GC(mi), dp->color);
140 gc = MI_GC(mi);
141 } else {
142 XGCValues gcv;
143
144 gcv.stipple = dp->graypix;
145 gcv.foreground = MI_WHITE_PIXEL(mi);
146 gcv.background = MI_BLACK_PIXEL(mi);
147 XChangeGC(display, dp->stippledGC,
148 GCStipple | GCForeground | GCBackground, &gcv);
149 gc = dp->stippledGC;
150 }
151 {
152 int ccol = 2 * col + !(row & 1), crow = 2 * row;
153
154 if (dp->vertical) {
155 dp->hexagon[0].x = dp->xb + ccol * dp->xs;
156 dp->hexagon[0].y = dp->yb + crow * dp->ys;
157 } else {
158 dp->hexagon[0].y = dp->xb + ccol * dp->xs;
159 dp->hexagon[0].x = dp->yb + crow * dp->ys;
160 }
161 if (dp->xs == 1 && dp->ys == 1)
162 XDrawPoint(display, MI_WINDOW(mi), gc,
163 dp->hexagon[0].x, dp->hexagon[0].y);
164 else
165 XFillPolygon(display, MI_WINDOW(mi), gc,
166 dp->hexagon, 6, Convex, CoordModePrevious);
167 }
168 }
169
170 static Bool
addtolist(ModeInfo * mi,int col,int row)171 addtolist(ModeInfo * mi, int col, int row)
172 {
173 dragonstruct *dp = &dragons[MI_SCREEN(mi)];
174 CellList *current;
175
176 current = dp->cellList[dp->addlist];
177 if ((dp->cellList[dp->addlist] = (CellList *)
178 malloc(sizeof (CellList))) == NULL) {
179 return False;
180 }
181 dp->cellList[dp->addlist]->pt.x = col;
182 dp->cellList[dp->addlist]->pt.y = row;
183 dp->cellList[dp->addlist]->next = current;
184 dp->ncells[dp->addlist]++;
185 return True;
186 }
187
188 #ifdef DEBUG
189 static void
print_state(ModeInfo * mi,int state)190 print_state(ModeInfo * mi, int state)
191 {
192 dragonstruct *dp = &dragons[MI_SCREEN(mi)];
193 CellList *locallist;
194 int i = 0;
195
196 locallist = dp->cellList[state];
197 (void) printf("state %d\n", state);
198 while (locallist) {
199 (void) printf("%d x %d, y %d\n", i,
200 locallist->pt.x, locallist->pt.y);
201 locallist = locallist->next;
202 i++;
203 }
204 }
205
206 #endif
207
208 static void
free_alist(dragonstruct * dp,int list)209 free_alist(dragonstruct * dp, int list)
210 {
211 CellList *current;
212
213 while (dp->cellList[list]) {
214 current = dp->cellList[list];
215 dp->cellList[list] = dp->cellList[list]->next;
216 free(current);
217 }
218 dp->cellList[list] = (CellList *) NULL;
219 if (dp->ncells != NULL)
220 dp->ncells[list] = 0;
221 }
222
223
224 static void
free_list(dragonstruct * dp)225 free_list(dragonstruct * dp)
226 {
227 int list;
228
229 for (list = 0; list < LISTS; list++)
230 free_alist(dp, list);
231 free(dp->cellList);
232 dp->cellList = (CellList **) NULL;
233 if (dp->ncells != NULL) {
234 free(dp->ncells);
235 dp->ncells = (int *) NULL;
236 }
237 }
238
239 static void
free_struct(dragonstruct * dp)240 free_struct(dragonstruct * dp)
241 {
242 if (dp->cellList != NULL) {
243 free_list(dp);
244 }
245 if (dp->oldcell != NULL) {
246 free(dp->oldcell);
247 dp->oldcell = (unsigned char *) NULL;
248 }
249 }
250
251 static void
free_dragon_screen(Display * display,dragonstruct * dp)252 free_dragon_screen(Display *display, dragonstruct *dp)
253 {
254 if (dp == NULL) {
255 return;
256 }
257 if (dp->stippledGC != None) {
258 XFreeGC(display, dp->stippledGC);
259 dp->stippledGC = None;
260 }
261 if (dp->graypix != None) {
262 XFreePixmap(display, dp->graypix);
263 dp->graypix = None;
264 }
265 free_struct(dp);
266 dp = NULL;
267 }
268
269 #if 0
270 static Bool
271 draw_state(ModeInfo * mi, int state)
272 {
273 dragonstruct *dp = &dragons[MI_SCREEN(mi)];
274 Display *display = MI_DISPLAY(mi);
275 GC gc;
276 CellList *current;
277
278 if (!state) {
279 XSetForeground(display, MI_GC(mi), MI_WHITE_PIXEL(mi));
280 gc = MI_GC(mi);
281 } else if (state == 1) {
282 XSetForeground(display, MI_GC(mi), MI_BLACK_PIXEL(mi));
283 gc = MI_GC(mi);
284 } else if (MI_NPIXELS(mi) > 2) {
285 XSetForeground(display, MI_GC(mi), dp->color);
286 gc = MI_GC(mi);
287 } else {
288 XGCValues gcv;
289
290 gcv.stipple = dp->graypix;
291 gcv.foreground = MI_WHITE_PIXEL(mi);
292 gcv.background = MI_BLACK_PIXEL(mi);
293 XChangeGC(display, dp->stippledGC,
294 GCStipple | GCForeground | GCBackground, &gcv);
295 gc = dp->stippledGC;
296 }
297 { /* Draw right away, slow */
298 current = dp->cellList[state];
299 while (current) {
300 int col, row, ccol, crow;
301
302 col = current->pt.x;
303 row = current->pt.y;
304 ccol = 2 * col + !(row & 1), crow = 2 * row;
305 if (dp->vertical) {
306 dp->hexagon[0].x = dp->xb + ccol * dp->xs;
307 dp->hexagon[0].y = dp->yb + crow * dp->ys;
308 } else {
309 dp->hexagon[0].y = dp->xb + ccol * dp->xs;
310 dp->hexagon[0].x = dp->yb + crow * dp->ys;
311 }
312 if (dp->xs == 1 && dp->ys == 1)
313 XDrawPoint(display, MI_WINDOW(mi), gc,
314 dp->hexagon[0].x, dp->hexagon[0].y);
315 else
316 XFillPolygon(display, MI_WINDOW(mi), gc,
317 dp->hexagon, 6, Convex, CoordModePrevious);
318 current = current->next;
319 }
320 }
321 XFlush(MI_DISPLAY(mi));
322 return True;
323 }
324 #endif
325
326 static Bool
SetSoup(ModeInfo * mi)327 SetSoup(ModeInfo * mi)
328 {
329 dragonstruct *dp = &dragons[MI_SCREEN(mi)];
330 int row, col, mrow = 0;
331
332 for (row = dp->nrows - 1; row >= 0; --row) {
333 for (col = dp->ncols - 1; col >= 0; --col) {
334 if (!addtolist(mi, col, row))
335 return False;
336 }
337 mrow += dp->ncols;
338 }
339 dp->addlist = !dp->addlist;
340 return True;
341 }
342
343 ENTRYPOINT void
init_dragon(ModeInfo * mi)344 init_dragon(ModeInfo * mi)
345 {
346 Display *display = MI_DISPLAY(mi);
347 Window window = MI_WINDOW(mi);
348 int size = MI_SIZE(mi);
349 dragonstruct *dp;
350
351 MI_INIT(mi, dragons);
352 dp = &dragons[MI_SCREEN(mi)];
353
354 dp->generation = 0;
355 dp->redrawing = 0;
356 if (MI_NPIXELS(mi) <= 2) {
357 if (dp->stippledGC == None) {
358 XGCValues gcv;
359
360 gcv.fill_style = FillOpaqueStippled;
361 if ((dp->stippledGC = XCreateGC(display, window,
362 GCFillStyle, &gcv)) == None) {
363 free_dragon_screen(display, dp);
364 return;
365 }
366 }
367 if (dp->graypix == None) {
368 if ((dp->graypix = XCreateBitmapFromData(display, window,
369 (char *) gray1_bits, gray1_width, gray1_height)) == None) {
370 free_dragon_screen(display, dp);
371 return;
372 }
373 }
374 }
375 free_struct(dp);
376 if (MI_NPIXELS(mi) > 2)
377 dp->color = MI_PIXEL(mi, NRAND(MI_NPIXELS(mi)));
378
379 if ((dp->cellList = (CellList **) calloc(STATES,
380 sizeof (CellList *))) == NULL) {
381 free_dragon_screen(display, dp);
382 return;
383 }
384 if ((dp->ncells = (int *) calloc(STATES, sizeof (int))) == NULL) {
385 free_dragon_screen(display, dp);
386 return;
387 }
388
389 dp->addlist = 0;
390 if (MI_IS_FULLRANDOM(mi)) {
391 dp->vertical = (Bool) (LRAND() & 1);
392 } else {
393 dp->vertical = vertical;
394 }
395 dp->width = MI_WIDTH(mi);
396 dp->height = MI_HEIGHT(mi);
397 {
398 int nccols, ncrows, i;
399
400 if (!dp->vertical) {
401 dp->height = MI_WIDTH(mi);
402 dp->width = MI_HEIGHT(mi);
403 }
404 if (dp->width < 8)
405 dp->width = 8;
406 if (dp->height < 8)
407 dp->height = 8;
408 if (size < -MINSIZE)
409 dp->ys = NRAND(MIN(-size, MAX(MINSIZE, MIN(dp->width, dp->height) /
410 MINGRIDSIZE)) - MINSIZE + 1) + MINSIZE;
411 else if (size < MINSIZE) {
412 if (!size)
413 dp->ys = MAX(MINSIZE, MIN(dp->width, dp->height) / MINGRIDSIZE);
414 else
415 dp->ys = MINSIZE;
416 } else
417 dp->ys = MIN(size, MAX(MINSIZE, MIN(dp->width, dp->height) /
418 MINGRIDSIZE));
419 dp->xs = dp->ys;
420 nccols = MAX(dp->width / dp->xs - 2, 2);
421 ncrows = MAX(dp->height / dp->ys - 1, 4);
422 dp->ncols = nccols / 2;
423 dp->nrows = 2 * (ncrows / 4);
424 dp->xb = (dp->width - dp->xs * nccols) / 2 + dp->xs / 2;
425 dp->yb = (dp->height - dp->ys * (ncrows / 2) * 2) / 2 -
426 dp->ys / 4;
427 for (i = 0; i < 6; i++) {
428 if (dp->vertical) {
429 dp->hexagon[i].x =
430 dp->xs * hexagonUnit[i].x;
431 dp->hexagon[i].y =
432 ((dp->ys + 1) * hexagonUnit[i].y /
433 2) * 4 / 3;
434 } else {
435 dp->hexagon[i].y =
436 dp->xs * hexagonUnit[i].x;
437 dp->hexagon[i].x =
438 ((dp->ys + 1) * hexagonUnit[i].y /
439 2) * 4 / 3;
440 }
441 }
442 }
443
444 MI_CLEARWINDOW(mi);
445
446 if ((dp->oldcell = (unsigned char *)
447 calloc(dp->ncols * dp->nrows,
448 sizeof (unsigned char))) == NULL) {
449 free_dragon_screen(display, dp);
450 return;
451 }
452 if (!SetSoup(mi)) {
453 free_dragon_screen(display, dp);
454 return;
455 }
456 }
457
458 ENTRYPOINT void
draw_dragon(ModeInfo * mi)459 draw_dragon(ModeInfo * mi)
460 {
461 int white, black;
462 int choose_layer, factor, orient, l;
463 dragonstruct *dp;
464 CellList *locallist;
465 Bool detour = False;
466
467 if (dragons == NULL)
468 return;
469 dp = &dragons[MI_SCREEN(mi)];
470 if (dp->cellList == NULL)
471 return;
472
473 MI_IS_DRAWN(mi) = True;
474 choose_layer= NRAND(6);
475 if (dp->ncells[!dp->addlist] == 1) {
476 /* Since the maze is infinite, it may not get to this last
477 * spot for a while. Force it to do it right away so it
478 * does not appear to be stuck. */
479 detour = True;
480 white = black = 0; /* not used but make -Wall happy */
481 } else {
482 white = (choose_layer / 2);
483 black = (choose_layer % 2) ?
484 ((white + 2) % 3) : ((white + 1) % 3);
485 /* gray = (choose_layer % 2) ?
486 ((white + 1) % 3) : ((white + 2) % 3); */
487 }
488 locallist = dp->cellList[!dp->addlist];
489 orient = dp->generation % 2;
490 factor = 1;
491 for (l = 0; l < dp->generation / 2; l++) {
492 factor *= 3;
493 }
494 if (!locallist && dp->generation >= MI_CYCLES(mi)) {
495 init_dragon(mi);
496 return;
497 }
498
499 while (locallist) {
500 int i, j, k;
501
502 i = locallist->pt.x;
503 j = locallist->pt.y;
504 if (orient) {
505 k = (j / factor) % 3;
506 } else {
507 if (j % 2) {
508 /* Had trouble with this line... */
509 k = ((i + factor / 2) / factor + 1) % 3;
510 } else {
511 k = (i / factor) % 3;
512 }
513 }
514 if (detour) {
515 k = (LRAND() & 1) + 1;
516 dp->oldcell[j * dp->ncols + i] = k;
517 drawcell(mi, i, j, k);
518 } if (white == k) {
519 dp->oldcell[j * dp->ncols + i] = 0;
520 drawcell(mi, i, j, 0);
521 if (!addtolist(mi, i, j)) {
522 free_dragon_screen(MI_DISPLAY(mi), dp);
523 return;
524 }
525 } else if (black == k) {
526 dp->oldcell[j * dp->ncols + i] = 1;
527 drawcell(mi, i, j, 1);
528 } else /* if (gray == k) */ {
529 dp->oldcell[j * dp->ncols + i] = 2;
530 drawcell(mi, i, j, 2);
531 }
532 dp->cellList[!dp->addlist] = dp->cellList[!dp->addlist]->next;
533 free(locallist);
534 dp->ncells[!dp->addlist]--;
535 locallist = dp->cellList[!dp->addlist];
536 if ((dp->cellList[!dp->addlist] == NULL) &&
537 (dp->cellList[dp->addlist] == NULL))
538 dp->generation = 0;
539 }
540 dp->addlist = !dp->addlist;
541 if (dp->redrawing) {
542 int i;
543
544 for (i = 0; i < REDRAWSTEP; i++) {
545 if (dp->oldcell[dp->redrawpos] != 1) {
546 drawcell(mi, dp->redrawpos % dp->ncols, dp->redrawpos / dp->ncols,
547 dp->oldcell[dp->redrawpos]);
548 }
549 if (++(dp->redrawpos) >= dp->ncols * dp->nrows) {
550 dp->redrawing = 0;
551 break;
552 }
553 }
554 }
555 dp->generation++;
556 }
557 ENTRYPOINT void
release_dragon(ModeInfo * mi)558 release_dragon(ModeInfo * mi)
559 {
560 if (dragons != NULL) {
561 int screen;
562
563 for (screen = 0; screen < MI_NUM_SCREENS(mi); screen++)
564 free_dragon_screen(MI_DISPLAY(mi), &dragons[screen]);
565 free(dragons);
566 dragons = (dragonstruct *) NULL;
567 }
568 }
569
570 #ifndef STANDALONE
571 ENTRYPOINT void
refresh_dragon(ModeInfo * mi)572 refresh_dragon(ModeInfo * mi)
573 {
574 dragonstruct *dp;
575
576 if (dragons == NULL)
577 return;
578 dp = &dragons[MI_SCREEN(mi)];
579
580 dp->redrawing = 1;
581 dp->redrawpos = 0;
582 }
583 #endif
584
585 XSCREENSAVER_MODULE ("Dragon", dragon)
586
587 #endif /* MODE_dragon */
588