6b07d8ca65e722e6e462b91681167cf83b890ac8
[xscreensaver] / hacks / penrose.c
1 /* -*- Mode: C; tab-width: 4 -*- */
2 /* penrose --- quasiperiodic tilings */
3
4 /*  As reported in News of the Weird:
5
6           In April, Sir Roger Penrose, a British math professor who has worked
7           with Stephen Hawking on such topics as relativity, black holes, and
8           whether time has a beginning, filed a copyright-infringement lawsuit
9           against the Kimberly-Clark Corporation, which Penrose said copied a
10           pattern he created (a pattern demonstrating that "a nonrepeating
11           pattern could exist in nature") for its Kleenex quilted toilet paper.
12           Penrose said he doesn't like litigation but, "When it comes to the
13           population of Great Britain being invited by a multinational to wipe
14           their bottoms on what appears to be the work of a Knight of the
15           Realm, then a last stand must be taken."
16
17                                 NOTW #491, 4-jul-1997, by Chuck Shepherd.
18                                 http://www.nine.org/notw/notw.html
19  */
20
21 #if 0
22 static const char sccsid[] = "@(#)penrose.c     5.00 2000/11/01 xlockmore";
23 #endif
24
25 /*-
26  * Copyright (c) 1996 by Timo Korvola <tkorvola@dopey.hut.fi>
27  *
28  * Permission to use, copy, modify, and distribute this software and its
29  * documentation for any purpose and without fee is hereby granted,
30  * provided that the above copyright notice appear in all copies and that
31  * both that copyright notice and this permission notice appear in
32  * supporting documentation.
33  *
34  * This file is provided AS IS with no warranties of any kind.  The author
35  * shall have no liability with respect to the infringement of copyrights,
36  * trade secrets or any patents by this file or any part thereof.  In no
37  * event will the author be liable for any lost revenue or profits or
38  * other special, indirect and consequential damages.
39  *
40  * Revision History:
41  * 01-Nov-2000: Allocation checks
42  * 10-May-1997: Jamie Zawinski <jwz@jwz.org> compatible with xscreensaver
43  * 09-Sep-1996: Written.
44  */
45
46 /*-
47 Be careful, this probably still has a few bugs (many of which may only
48 appear with a very low probability).  These are seen with -verbose .
49 If one of these are hit penrose will reinitialize.
50 */
51
52 /*-
53  * See Onoda, Steinhardt, DiVincenzo and Socolar in
54  * Phys. Rev. Lett. 60, #25, 1988 or
55  * Strandburg in Computers in Physics, Sep/Oct 1991.
56  *
57  * This implementation uses the simpler version of the growth
58  * algorithm, i.e., if there are no forced vertices, a randomly chosen
59  * tile is added to a randomly chosen vertex (no preference for those
60  * 108 degree angles).
61  *
62  * There are two essential differences to the algorithm presented in
63  * the literature: First, we do not allow the tiling to enclose an
64  * untiled area.  Whenever this is in danger of happening, we just
65  * do not add the tile, hoping for a better random choice the next
66  * time.  Second, when choosing a vertex randomly, we will take
67  * one that lies within the viewport if available.  If this seems to
68  * cause enclosures in the forced rule case, we will allow invisible
69  * vertices to be chosen.
70  *
71  * Tiling is restarted whenever one of the following happens: there
72  * are no incomplete vertices within the viewport or the tiling has
73  * extended a window's length beyond the edge of the window
74  * horizontally or vertically or forced rule choice has failed 100
75  * times due to areas about to become enclosed.
76  *
77  * Introductory info:
78  * Science News March 23 1985 Vol 127, No. 12
79  * Science News July 16 1988 Vol 134, No. 3
80  * The Economist Sept 17 1988 pg. 100
81  *
82  */
83
84 #ifdef STANDALONE
85 #define MODE_penrose
86 #define DEFAULTS        "*delay: 10000 \n" \
87                                         "*size: 40 \n" \
88                                         "*ncolors: 64 \n" \
89                                         "*fpsSolid: true \n" \
90
91 # define refresh_penrose 0
92 # define penrose_handle_event 0
93 # include "xlockmore.h"         /* from the xscreensaver distribution */
94 #else /* !STANDALONE */
95 # include "xlock.h"             /* from the xlockmore distribution */
96 #endif /* !STANDALONE */
97
98 #ifdef MODE_penrose
99
100 #define DEF_AMMANN  "False"
101
102 static Bool ammann;
103
104 static XrmOptionDescRec opts[] =
105 {
106         {"-ammann", ".penrose.ammann", XrmoptionNoArg, "on"},
107         {"+ammann", ".penrose.ammann", XrmoptionNoArg, "off"}
108 };
109 static argtype vars[] =
110 {
111         {&ammann, "ammann", "Ammann", DEF_AMMANN, t_Bool}
112 };
113 static OptionStruct desc[] =
114 {
115         {"-/+ammann", "turn on/off Ammann lines"}
116 };
117
118 ENTRYPOINT ModeSpecOpt penrose_opts =
119 {sizeof opts / sizeof opts[0], opts, sizeof vars / sizeof vars[0], vars, desc};
120
121 #ifdef USE_MODULES
122 ModStruct   penrose_description =
123 {"penrose", "init_penrose", "draw_penrose", "release_penrose",
124  "init_penrose", "init_penrose", (char *) NULL, &penrose_opts,
125  10000, 1, 1, -40, 64, 1.0, "",
126  "Shows Penrose's quasiperiodic tilings", 0, NULL};
127
128 #endif
129
130 /*-
131  * Annoyingly the ANSI C library people have reserved all identifiers
132  * ending with _t for future use.  Hence we use _c as a suffix for
133  * typedefs (c for class, although this is not C++).
134  */
135
136 #define MINSIZE 5
137
138 /*-
139  * In theory one could fit 10 tiles to a single vertex.  However, the
140  * vertex rules only allow at most seven tiles to meet at a vertex.
141  */
142
143 #define CELEBRATE 31415         /* This causes a pause, an error occurred. */
144 #define COMPLETION 3141         /* This causes a pause, tiles filled up screen. */
145
146 #define MAX_TILES_PER_VERTEX 7
147 #define N_VERTEX_RULES 8
148 #define ALLOC_NODE(type) (type *)malloc(sizeof (type))
149
150 /*-
151  * These are used to specify directions.  They can also be used in bit
152  * masks to specify a combination of directions.
153  */
154 #define S_LEFT 1
155 #define S_RIGHT 2
156
157
158 /*-
159  * We do not actually maintain objects corresponding to the tiles since
160  * we do not really need them and they would only consume memory and
161  * cause additional bookkeeping.  Instead we only have vertices, and
162  * each vertex lists the type of each adjacent tile as well as the
163  * position of the vertex on the tile (hereafter refered to as
164  * "corner").  These positions are numbered in counterclockwise order
165  * so that 0 is where two double arrows meet (see one of the
166  * articles).  The tile type and vertex number are stored in a single
167  * integer (we use char, and even most of it remains unused).
168  *
169  * The primary use of tile objects would be draw traversal, but we do
170  * not currently do redraws at all (we just start over).
171  */
172 #define VT_CORNER_MASK 0x3
173 #define VT_TYPE_MASK 0x4
174 #define VT_THIN 0
175 #define VT_THICK 0x4
176 #define VT_BITS 3
177 #define VT_TOTAL_MASK 0x7
178
179 typedef unsigned char vertex_type_c;
180
181 /*-
182  * These allow one to compute the types of the other corners of the tile.  If
183  * you are standing at a vertex of type vt looking towards the middle of the
184  * tile, VT_LEFT( vt) is the vertex on your left etc.
185  */
186 #define VT_LEFT( vt) ((((vt) - 1) & VT_CORNER_MASK) | (((vt) & VT_TYPE_MASK)))
187 #define VT_RIGHT( vt) ((((vt) + 1) & VT_CORNER_MASK) | (((vt) & VT_TYPE_MASK)))
188 #define VT_FAR( vt) ((vt) ^ 2)
189
190
191 /*-
192  * Since we do not do redraws, we only store the vertices we need.  These are
193  * the ones with still some empty space around them for the growth algorithm
194  * to fill.
195  *
196  * Here we use a doubly chained ring-like structure as vertices often need
197  * to be removed or inserted (they are kept in geometrical order
198  * circling the tiled area counterclockwise).  The ring is refered to by
199  * a pointer to one more or less random node.  When deleting nodes one
200  * must make sure that this pointer continues to refer to a valid
201  * node.  A vertex count is maintained to make it easier to pick
202  * vertices randomly.
203  */
204 typedef struct forced_node forced_node_c;
205
206 typedef struct fringe_node {
207         struct fringe_node *prev;
208         struct fringe_node *next;
209         /* These are numbered counterclockwise.  The gap, if any, lies
210            between the last and first tiles.  */
211         vertex_type_c tiles[MAX_TILES_PER_VERTEX];
212         int         n_tiles;
213         /* A bit mask used to indicate vertex rules that are still applicable for
214            completing this vertex.  Initialize this to (1 << N_VERTEX_RULES) - 1,
215            i.e., all ones, and the rule matching functions will automatically mask
216            out rules that no longer match. */
217         unsigned char rule_mask;
218         /* If the vertex is on the forced vertex list, this points to the
219            pointer to the appropriate node in the list.  To remove the
220            vertex from the list just set *list_ptr to the next node,
221            deallocate and decrement node count. */
222         struct forced_node **list_ptr;
223         /* Screen coordinates. */
224         XPoint      loc;
225         /* We also keep track of 5D coordinates to avoid rounding errors.
226            These are in units of edge length. */
227         int         fived[5];
228         /* This is used to quickly check if a vertex is visible. */
229         unsigned char off_screen;
230 } fringe_node_c;
231
232 typedef struct {
233         fringe_node_c *nodes;
234         /* This does not count off-screen nodes. */
235         int         n_nodes;
236 } fringe_c;
237
238
239 /*-
240  * The forced vertex pool contains vertices where at least one
241  * side of the tiled region can only be extended in one way.  Note
242  * that this does not necessarily mean that there would only be one
243  * applicable rule.  forced_sides are specified using S_LEFT and
244  * S_RIGHT as if looking at the untiled region from the vertex.
245  */
246 struct forced_node {
247         fringe_node_c *vertex;
248         unsigned    forced_sides;
249         struct forced_node *next;
250 };
251
252 typedef struct {
253         forced_node_c *first;
254         int         n_nodes, n_visible;
255 } forced_pool_c;
256
257
258 /* The tiles are listed in counterclockwise order. */
259 typedef struct {
260         vertex_type_c tiles[MAX_TILES_PER_VERTEX];
261         int         n_tiles;
262 } vertex_rule_c;
263
264 static vertex_rule_c vertex_rules[N_VERTEX_RULES] =
265 {
266         {
267   {VT_THICK | 2, VT_THICK | 2, VT_THICK | 2, VT_THICK | 2, VT_THICK | 2}, 5},
268         {
269   {VT_THICK | 0, VT_THICK | 0, VT_THICK | 0, VT_THICK | 0, VT_THICK | 0}, 5},
270         {
271                 {VT_THICK | 0, VT_THICK | 0, VT_THICK | 0, VT_THIN | 0}, 4},
272         {
273          {VT_THICK | 2, VT_THICK | 2, VT_THIN | 1, VT_THIN | 3, VT_THICK | 2,
274           VT_THIN | 1, VT_THIN | 3}, 7},
275         {
276                 {VT_THICK | 2, VT_THICK | 2, VT_THICK | 2, VT_THICK | 2,
277                  VT_THIN | 1, VT_THIN | 3}, 6},
278         {
279                 {VT_THICK | 1, VT_THICK | 3, VT_THIN | 2}, 3},
280         {
281                 {VT_THICK | 0, VT_THIN | 0, VT_THIN | 0}, 3},
282         {
283      {VT_THICK | 2, VT_THIN | 1, VT_THICK | 3, VT_THICK | 1, VT_THIN | 3}, 5}
284 };
285
286
287 /* Match information returned by match_rules. */
288 typedef struct {
289         int         rule;
290         int         pos;
291 } rule_match_c;
292
293
294 /* Occasionally floating point coordinates are needed. */
295 typedef struct {
296         float       x, y;
297 } fcoord_c;
298
299
300 /* All angles are measured in multiples of 36 degrees. */
301 typedef int angle_c;
302
303 static angle_c vtype_angles[] =
304 {4, 1, 4, 1, 2, 3, 2, 3};
305
306 #define vtype_angle( v) (vtype_angles[ v])
307
308
309 /* This is the data related to the tiling of one screen. */
310 typedef struct {
311         int         width, height;
312         XPoint      origin;
313         int         edge_length;
314         fringe_c    fringe;
315         forced_pool_c forced;
316         int         done, failures;
317         unsigned long thick_color, thin_color;
318         int         busyLoop;
319         Bool        ammann;
320     float       ammann_r;
321     fcoord_c    fived_table[5];
322 } tiling_c;
323
324 static tiling_c *tilings = (tiling_c *) NULL;
325
326
327
328 /* Direction angle of an edge. */
329 static      angle_c
330 vertex_dir(ModeInfo * mi, fringe_node_c * vertex, unsigned side)
331 {
332         tiling_c   *tp = &tilings[MI_SCREEN(mi)];
333         fringe_node_c *v2 =
334         (side == S_LEFT ? vertex->next : vertex->prev);
335         register int i;
336
337         for (i = 0; i < 5; i++)
338                 switch (v2->fived[i] - vertex->fived[i]) {
339                         case 1:
340                                 return 2 * i;
341                         case -1:
342                                 return (2 * i + 5) % 10;
343                 }
344         tp->done = True;
345         if (MI_IS_VERBOSE(mi)) {
346                 (void) fprintf(stderr,
347                        "Weirdness in vertex_dir (this has been reported)\n");
348                 for (i = 0; i < 5; i++)
349                         (void) fprintf(stderr, "v2->fived[%d]=%d, vertex->fived[%d]=%d\n",
350                                        i, v2->fived[i], i, vertex->fived[i]);
351         }
352         tp->busyLoop = CELEBRATE;
353         return 0;
354 }
355
356
357 /* Move one step to a given direction. */
358 static void
359 add_unit_vec(angle_c dir, int *fived)
360 {
361         static const int dir2i[] = {0, 3, 1, 4, 2};
362
363         while (dir < 0)
364                 dir += 10;
365         fived[dir2i[dir % 5]] += (dir % 2 ? -1 : 1);
366 }
367
368
369 /* For comparing coordinates. */
370 #define fived_equal( f1, f2) (!memcmp( (f1), (f2), 5 * sizeof( int)))
371
372
373 /*-
374  * This computes screen coordinates from 5D representation.  Note that X
375  * uses left-handed coordinates (y increases downwards).
376  */
377 static void
378 fived_to_loc(int fived[], tiling_c * tp, XPoint *pt)
379 {
380         float       fifth = 8 * atan(1.) / 5;
381         register int i;
382         register float r;
383         register fcoord_c offset;
384
385         *pt = tp->origin;
386         offset.x = 0.0;
387         offset.y = 0.0;
388         if (tp->fived_table[0].x == .0)
389                 for (i = 0; i < 5; i++) {
390                         tp->fived_table[i].x = cos(fifth * i);
391                         tp->fived_table[i].y = sin(fifth * i);
392                 }
393         for (i = 0; i < 5; i++) {
394                 r = fived[i] * tp->edge_length;
395                 offset.x += r * tp->fived_table[i].x;
396                 offset.y -= r * tp->fived_table[i].y;
397         }
398         (*pt).x += (int) (offset.x + .5);
399         (*pt).y += (int) (offset.y + .5);
400 }
401
402
403 /* Mop up dynamic data for one screen. */
404 static void
405 free_penrose(tiling_c * tp)
406 {
407         register fringe_node_c *fp1, *fp2;
408         register forced_node_c *lp1, *lp2;
409
410         if (tp->fringe.nodes == NULL)
411                 return;
412         fp1 = tp->fringe.nodes;
413         do {
414                 fp2 = fp1;
415                 fp1 = fp1->next;
416                 (void) free((void *) fp2);
417         } while (fp1 != tp->fringe.nodes);
418         tp->fringe.nodes = (fringe_node_c *) NULL;
419         for (lp1 = tp->forced.first; lp1 != 0;) {
420                 lp2 = lp1;
421                 lp1 = lp1->next;
422                 (void) free((void *) lp2);
423         }
424         tp->forced.first = 0;
425 }
426
427
428 /* Called to init the mode. */
429 ENTRYPOINT void
430 init_penrose(ModeInfo * mi)
431 {
432         tiling_c   *tp;
433         fringe_node_c *fp;
434         int         i, size;
435
436         if (tilings == NULL) {
437                 if ((tilings = (tiling_c *) calloc(MI_NUM_SCREENS(mi),
438                                                  sizeof (tiling_c))) == NULL)
439                         return;
440         }
441         tp = &tilings[MI_SCREEN(mi)];
442
443 #if 0 /* if you do this, then the -ammann and -no-ammann options don't work.
444          -- jwz */
445         if (MI_IS_FULLRANDOM(mi))
446                 tp->ammann = (Bool) (LRAND() & 1);
447         else
448 #endif /* 0 */
449                 tp->ammann = ammann;
450
451         tp->done = False;
452         tp->busyLoop = 0;
453         tp->failures = 0;
454         tp->width = MI_WIDTH(mi);
455         tp->height = MI_HEIGHT(mi);
456         if (MI_NPIXELS(mi) > 2) {
457                 tp->thick_color = NRAND(MI_NPIXELS(mi));
458                 /* Insure good contrast */
459                 tp->thin_color = (NRAND(2 * MI_NPIXELS(mi) / 3) + tp->thick_color +
460                                   MI_NPIXELS(mi) / 6) % MI_NPIXELS(mi);
461         }
462         size = MI_SIZE(mi);
463         if (size < -MINSIZE)
464                 tp->edge_length = NRAND(MIN(-size, MAX(MINSIZE,
465                    MIN(tp->width, tp->height) / 2)) - MINSIZE + 1) + MINSIZE;
466         else if (size < MINSIZE) {
467                 if (!size)
468                         tp->edge_length = MAX(MINSIZE, MIN(tp->width, tp->height) / 2);
469                 else
470                         tp->edge_length = MINSIZE;
471         } else
472                 tp->edge_length = MIN(size, MAX(MINSIZE,
473                                             MIN(tp->width, tp->height) / 2));
474         tp->origin.x = (tp->width / 2 + NRAND(tp->width)) / 2;
475         tp->origin.y = (tp->height / 2 + NRAND(tp->height)) / 2;
476         tp->fringe.n_nodes = 2;
477         if (tp->fringe.nodes != NULL)
478                 free_penrose(tp);
479         if (tp->fringe.nodes != NULL || tp->forced.first != 0) {
480                 if (MI_IS_VERBOSE(mi)) {
481                         (void) fprintf(stderr, "Weirdness in init_penrose()\n");
482                         (void) fprintf(stderr, "tp->fringe.nodes = NULL && tp->forced.first = 0\n");
483                 }
484                 free_penrose(tp);       /* Try again */
485                 tp->done = True;
486         }
487         tp->forced.n_nodes = tp->forced.n_visible = 0;
488         if ((fp = tp->fringe.nodes = ALLOC_NODE(fringe_node_c)) == NULL) {
489                 free_penrose(tp);
490                 return;
491         }
492         if (fp == 0) {
493                 if (MI_IS_VERBOSE(mi)) {
494                         (void) fprintf(stderr, "Weirdness in init_penrose()\n");
495                         (void) fprintf(stderr, "fp = 0\n");
496                 }
497                 if ((fp = tp->fringe.nodes = ALLOC_NODE(fringe_node_c)) == NULL) {
498                         free_penrose(tp);
499                         return;
500                 }
501                 tp->done = True;
502         }
503         /* First vertex. */
504         fp->rule_mask = (1 << N_VERTEX_RULES) - 1;
505         fp->list_ptr = 0;
506         if  ((fp->prev = fp->next = ALLOC_NODE(fringe_node_c)) == NULL) {
507                 free_penrose(tp);
508                 return;
509         }
510         if (fp->next == 0) {
511                 if (MI_IS_VERBOSE(mi)) {
512                         (void) fprintf(stderr, "Weirdness in init_penrose()\n");
513                         (void) fprintf(stderr, "fp->next = 0\n");
514                 }
515                 if ((fp->prev = fp->next = ALLOC_NODE(fringe_node_c)) == NULL) {
516                         free_penrose(tp);
517                         return;
518                 }
519                 tp->done = True;
520         }
521         fp->n_tiles = 0;
522         fp->loc = tp->origin;
523         fp->off_screen = False;
524         for (i = 0; i < 5; i++)
525                 fp->fived[i] = 0;
526
527         /* Second vertex. */
528         *(fp->next) = *fp;
529         fp->next->prev = fp->next->next = fp;
530         fp = fp->next;
531         i = NRAND(5);
532         fp->fived[i] = 2 * NRAND(2) - 1;
533         fived_to_loc(fp->fived, tp, &(fp->loc));
534         /* That's it!  We have created our first edge. */
535 }
536
537 /*-
538  * This attempts to match the configuration of vertex with the vertex
539  * rules.   The return value is a total match count.  If matches is
540  * non-null, it will be used to store information about the matches
541  * and must be large enough to contain it.  To play it absolutely
542  * safe, allocate room for MAX_TILES_PER_VERTEX * N_VERTEX_RULES
543  * entries when searching all matches.   The rule mask of vertex will
544  * be applied and rules masked out will not be searched.  Only strict
545  * subsequences match.  If first_only is true, the search stops when
546  * the first match is found.  Otherwise all matches will be found and
547  * the rule_mask of vertex will be updated, which also happens in
548  * single-match mode if no match is found.
549  */
550 static int
551 match_rules(fringe_node_c * vertex, rule_match_c * matches, int first_only)
552 {
553         /* I will assume that I can fit all the relevant bits in vertex->tiles
554            into one unsigned long.  With 3 bits per element and at most 7
555            elements this means 21 bits, which should leave plenty of room.
556            After packing the bits the rest is just integer comparisons and
557            some bit shuffling.  This is essentially Rabin-Karp without
558            congruence arithmetic. */
559         register int i, j;
560         int         hits = 0, good_rules[N_VERTEX_RULES], n_good = 0;
561         unsigned long
562                     vertex_hash = 0, lower_bits_mask = ~(VT_TOTAL_MASK << VT_BITS * (vertex->n_tiles - 1));
563         unsigned    new_rule_mask = 0;
564
565         for (i = 0; i < N_VERTEX_RULES; i++)
566                 if (vertex->n_tiles >= vertex_rules[i].n_tiles)
567                         vertex->rule_mask &= ~(1 << i);
568                 else if (vertex->rule_mask & 1 << i)
569                         good_rules[n_good++] = i;
570         for (i = 0; i < vertex->n_tiles; i++)
571                 vertex_hash |= (unsigned long) vertex->tiles[i] << (VT_BITS * i);
572
573         for (j = 0; j < n_good; j++) {
574                 unsigned long rule_hash = 0;
575                 vertex_rule_c *vr = vertex_rules + good_rules[j];
576
577                 for (i = 0; i < vertex->n_tiles; i++)
578                         rule_hash |= (unsigned long) vr->tiles[i] << (VT_BITS * i);
579                 if (rule_hash == vertex_hash) {
580                         if (matches != 0) {
581                                 matches[hits].rule = good_rules[j];
582                                 matches[hits].pos = 0;
583                         }
584                         hits++;
585                         if (first_only)
586                                 return hits;
587                         else
588                                 new_rule_mask |= 1 << good_rules[j];
589                 }
590                 for (i = vr->n_tiles - 1; i > 0; i--) {
591                         rule_hash = vr->tiles[i] | (rule_hash & lower_bits_mask) << VT_BITS;
592                         if (vertex_hash == rule_hash) {
593                                 if (matches != 0) {
594                                         matches[hits].rule = good_rules[j];
595                                         matches[hits].pos = i;
596                                 }
597                                 hits++;
598                                 if (first_only)
599                                         return hits;
600                                 else
601                                         new_rule_mask |= 1 << good_rules[j];
602                         }
603                 }
604         }
605         vertex->rule_mask = new_rule_mask;
606         return hits;
607 }
608
609
610 /*-
611  * find_completions finds the possible ways to add a tile to a vertex.
612  * The return values is the number of such possibilities.  You must
613  * first call match_rules to produce matches and n_matches.  sides
614  * specifies which side of the vertex to extend and can be S_LEFT or
615  * S_RIGHT.  If results is non-null, it should point to an array large
616  * enough to contain the results, which will be stored there.
617  * MAX_COMPL elements will always suffice.  If first_only is true we
618  * stop as soon as we find one possibility (NOT USED).
619  */
620 #define MAX_COMPL 2
621
622 static int
623 find_completions(fringe_node_c * vertex, rule_match_c * matches, int n_matches,
624                unsigned side, vertex_type_c * results /*, int first_only */ )
625 {
626         int         n_res = 0, cont;
627         register int i, j;
628         vertex_type_c buf[MAX_COMPL];
629
630         if (results == 0)
631                 results = buf;
632         if (n_matches <= 0)
633                 return 0;
634         for (i = 0; i < n_matches; i++) {
635                 vertex_rule_c *rule = vertex_rules + matches[i].rule;
636                 int         pos = (matches[i].pos
637                    + (side == S_RIGHT ? vertex->n_tiles : rule->n_tiles - 1))
638                 % rule->n_tiles;
639                 vertex_type_c vtype = rule->tiles[pos];
640
641                 cont = 1;
642                 for (j = 0; j < n_res; j++)
643                         if (vtype == results[j]) {
644                                 cont = 0;
645                                 break;
646                         }
647                 if (cont)
648                         results[n_res++] = vtype;
649         }
650         return n_res;
651 }
652
653
654 /*-
655  * Draw a tile on the display.  Vertices must be given in a
656  * counterclockwise order.  vtype is the vertex type of v1 (and thus
657  * also gives the tile type).
658  */
659 static void
660 draw_tile(fringe_node_c * v1, fringe_node_c * v2,
661           fringe_node_c * v3, fringe_node_c * v4,
662           vertex_type_c vtype, ModeInfo * mi)
663 {
664         Display    *display = MI_DISPLAY(mi);
665         Window      window = MI_WINDOW(mi);
666         GC          gc = MI_GC(mi);
667         tiling_c   *tp = &tilings[MI_SCREEN(mi)];
668         XPoint      pts[5];
669         vertex_type_c corner = vtype & VT_CORNER_MASK;
670
671         if (v1->off_screen && v2->off_screen && v3->off_screen && v4->off_screen)
672                 return;
673         pts[corner] = v1->loc;
674         pts[VT_RIGHT(corner)] = v2->loc;
675         pts[VT_FAR(corner)] = v3->loc;
676         pts[VT_LEFT(corner)] = v4->loc;
677         pts[4] = pts[0];
678         if (MI_NPIXELS(mi) > 2) {
679                 if ((vtype & VT_TYPE_MASK) == VT_THICK)
680                         XSetForeground(display, gc, MI_PIXEL(mi, tp->thick_color));
681                 else
682                         XSetForeground(display, gc, MI_PIXEL(mi, tp->thin_color));
683         } else
684                 XSetForeground(display, gc, MI_WHITE_PIXEL(mi));
685         XFillPolygon(display, window, gc, pts, 4, Convex, CoordModeOrigin);
686         XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
687         XDrawLines(display, window, gc, pts, 5, CoordModeOrigin);
688
689         if (tp->ammann) {
690                 /* Draw some Ammann lines for debugging purposes.  This will probably
691                    fail miserably on a b&w display. */
692
693                 if ((vtype & VT_TYPE_MASK) == VT_THICK) {
694
695                         if (tp->ammann_r == .0) {
696                                 float       pi10 = 2 * atan(1.) / 5;
697
698                                 tp->ammann_r = 1 - sin(pi10) / (2 * sin(3 * pi10));
699                         }
700                         if (MI_NPIXELS(mi) > 2)
701                                 XSetForeground(display, gc, MI_PIXEL(mi, tp->thin_color));
702                         else {
703                                 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
704                                 XSetLineAttributes(display, gc, 1, LineOnOffDash, CapNotLast, JoinMiter);
705                         }
706                         XDrawLine(display, window, gc,
707                               (int) (tp->ammann_r * pts[3].x + (1 - tp->ammann_r) * pts[0].x + .5),
708                               (int) (tp->ammann_r * pts[3].y + (1 - tp->ammann_r) * pts[0].y + .5),
709                               (int) (tp->ammann_r * pts[1].x + (1 - tp->ammann_r) * pts[0].x + .5),
710                              (int) (tp->ammann_r * pts[1].y + (1 - tp->ammann_r) * pts[0].y + .5));
711                         if (MI_NPIXELS(mi) <= 2)
712                                 XSetLineAttributes(display, gc, 1, LineSolid, CapNotLast, JoinMiter);
713                 } else {
714                         if (MI_NPIXELS(mi) > 2)
715                                 XSetForeground(display, gc, MI_PIXEL(mi, tp->thick_color));
716                         else {
717                                 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
718                                 XSetLineAttributes(display, gc, 1, LineOnOffDash, CapNotLast, JoinMiter);
719                         }
720                         XDrawLine(display, window, gc,
721                                   (int) ((pts[3].x + pts[2].x) / 2 + .5),
722                                   (int) ((pts[3].y + pts[2].y) / 2 + .5),
723                                   (int) ((pts[1].x + pts[2].x) / 2 + .5),
724                                   (int) ((pts[1].y + pts[2].y) / 2 + .5));
725                         if (MI_NPIXELS(mi) <= 2)
726                                 XSetLineAttributes(display, gc, 1, LineSolid, CapNotLast, JoinMiter);
727                 }
728         }
729 }
730
731 /*-
732  * Update the status of this vertex on the forced vertex queue.  If
733  * the vertex has become untileable set tp->done.  This is supposed
734  * to detect dislocations -- never call this routine with a completely
735  * tiled vertex.
736  *
737  * Check for untileable vertices in check_vertex and stop tiling as
738  * soon as one finds one.  I don't know if it is possible to run out
739  * of forced vertices while untileable vertices exist (or will
740  * cavities inevitably appear).  If this can happen, add_random_tile
741  * might get called with an untileable vertex, causing ( n <= 1).
742  * (This is what the tp->done checks for).
743  *
744  * A delayLoop celebrates the dislocation.
745  */
746 static void
747 check_vertex(ModeInfo * mi, fringe_node_c * vertex, tiling_c * tp)
748 {
749         rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
750         int         n_hits = match_rules(vertex, hits, False);
751         unsigned    forced_sides = 0;
752
753         if (vertex->rule_mask == 0) {
754                 tp->done = True;
755                 if (MI_IS_VERBOSE(mi)) {
756                         (void) fprintf(stderr, "Dislocation occurred!\n");
757                 }
758                 tp->busyLoop = CELEBRATE;       /* Should be able to recover */
759         }
760         if (1 == find_completions(vertex, hits, n_hits, S_LEFT, 0 /*, False */ ))
761                 forced_sides |= S_LEFT;
762         if (1 == find_completions(vertex, hits, n_hits, S_RIGHT, 0 /*, False */ ))
763                 forced_sides |= S_RIGHT;
764         if (forced_sides == 0) {
765                 if (vertex->list_ptr != 0) {
766                         forced_node_c *node = *vertex->list_ptr;
767
768                         *vertex->list_ptr = node->next;
769                         if (node->next != 0)
770                                 node->next->vertex->list_ptr = vertex->list_ptr;
771                         (void) free((void *) node);
772                         tp->forced.n_nodes--;
773                         if (!vertex->off_screen)
774                                 tp->forced.n_visible--;
775                         vertex->list_ptr = 0;
776                 }
777         } else {
778                 forced_node_c *node;
779
780                 if (vertex->list_ptr == 0) {
781                         if ((node = ALLOC_NODE(forced_node_c)) == NULL)
782                                 return;
783                         node->vertex = vertex;
784                         node->next = tp->forced.first;
785                         if (tp->forced.first != 0)
786                                 tp->forced.first->vertex->list_ptr = &(node->next);
787                         tp->forced.first = node;
788                         vertex->list_ptr = &(tp->forced.first);
789                         tp->forced.n_nodes++;
790                         if (!vertex->off_screen)
791                                 tp->forced.n_visible++;
792                 } else
793                         node = *vertex->list_ptr;
794                 node->forced_sides = forced_sides;
795         }
796 }
797
798
799 /*-
800  * Delete this vertex.  If the vertex is a member of the forced vertex queue,
801  * also remove that entry.  We assume that the vertex is no longer
802  * connected to the fringe.  Note that tp->fringe.nodes must not point to
803  * the vertex being deleted.
804  */
805 static void
806 delete_vertex(ModeInfo * mi, fringe_node_c * vertex, tiling_c * tp)
807 {
808         if (tp->fringe.nodes == vertex) {
809                 tp->done = True;
810                 if (MI_IS_VERBOSE(mi)) {
811                         (void) fprintf(stderr, "Weirdness in delete_penrose()\n");
812                         (void) fprintf(stderr, "tp->fringe.nodes == vertex\n");
813                 }
814                 tp->busyLoop = CELEBRATE;
815         }
816         if (vertex->list_ptr != 0) {
817                 forced_node_c *node = *vertex->list_ptr;
818
819                 *vertex->list_ptr = node->next;
820                 if (node->next != 0)
821                         node->next->vertex->list_ptr = vertex->list_ptr;
822                 (void) free((void *) node);
823                 tp->forced.n_nodes--;
824                 if (!vertex->off_screen)
825                         tp->forced.n_visible--;
826         }
827         if (!vertex->off_screen)
828                 tp->fringe.n_nodes--;
829         (void) free((void *) vertex);
830 }
831
832
833 /*-
834  * Check whether the addition of a tile of type vtype would completely fill
835  * the space available at vertex.
836  */
837 static int
838 fills_vertex(ModeInfo * mi, vertex_type_c vtype, fringe_node_c * vertex)
839 {
840         return
841                 (vertex_dir(mi, vertex, S_LEFT) - vertex_dir(mi, vertex, S_RIGHT)
842                  - vtype_angle(vtype)) % 10 == 0;
843 }
844
845
846 /*-
847  * If you were to add a tile of type vtype to a specified side of
848  * vertex, fringe_changes tells you which other vertices it would
849  * attach to.  The addresses of these vertices will be stored in the
850  * last three arguments.  Null is stored if the corresponding vertex
851  * would need to be allocated.
852  *
853  * The function also analyzes which vertices would be swallowed by the tiling
854  * and thus cut off from the fringe.  The result is returned as a bit pattern.
855  */
856 #define FC_BAG 1                /* Total enclosure.  Should never occur. */
857 #define FC_NEW_RIGHT 2
858 #define FC_NEW_FAR 4
859 #define FC_NEW_LEFT 8
860 #define FC_NEW_MASK 0xe
861 #define FC_CUT_THIS 0x10
862 #define FC_CUT_RIGHT 0x20
863 #define FC_CUT_FAR 0x40
864 #define FC_CUT_LEFT 0x80
865 #define FC_CUT_MASK 0xf0
866 #define FC_TOTAL_MASK 0xff
867
868 static unsigned
869 fringe_changes(ModeInfo * mi, fringe_node_c * vertex,
870                unsigned side, vertex_type_c vtype,
871                fringe_node_c ** right, fringe_node_c ** far,
872                fringe_node_c ** left)
873 {
874         fringe_node_c *v, *f = (fringe_node_c *) NULL;
875         unsigned    result = FC_NEW_FAR;        /* We clear this later if necessary. */
876
877         if (far)
878                 *far = 0;
879         if (fills_vertex(mi, vtype, vertex)) {
880                 result |= FC_CUT_THIS;
881         } else if (side == S_LEFT) {
882                 result |= FC_NEW_RIGHT;
883                 if (right)
884                         *right = 0;
885         } else {
886                 result |= FC_NEW_LEFT;
887                 if (left)
888                         *left = 0;
889         }
890
891         if (!(result & FC_NEW_LEFT)) {
892                 v = vertex->next;
893                 if (left)
894                         *left = v;
895                 if (fills_vertex(mi, VT_LEFT(vtype), v)) {
896                         result = (result & ~FC_NEW_FAR) | FC_CUT_LEFT;
897                         f = v->next;
898                         if (far)
899                                 *far = f;
900                 }
901         }
902         if (!(result & FC_NEW_RIGHT)) {
903                 v = vertex->prev;
904                 if (right)
905                         *right = v;
906                 if (fills_vertex(mi, VT_RIGHT(vtype), v)) {
907                         result = (result & ~FC_NEW_FAR) | FC_CUT_RIGHT;
908                         f = v->prev;
909                         if (far)
910                                 *far = f;
911                 }
912         }
913         if (!(result & FC_NEW_FAR)
914             && fills_vertex(mi, VT_FAR(vtype), f)) {
915                 result |= FC_CUT_FAR;
916                 result &= (~FC_NEW_LEFT & ~FC_NEW_RIGHT);
917                 if (right && (result & FC_CUT_LEFT))
918                         *right = f->next;
919                 if (left && (result & FC_CUT_RIGHT))
920                         *left = f->prev;
921         }
922         if (((result & FC_CUT_LEFT) && (result & FC_CUT_RIGHT))
923             || ((result & FC_CUT_THIS) && (result & FC_CUT_FAR)))
924                 result |= FC_BAG;
925         return result;
926 }
927
928
929 /* A couple of lesser helper functions for add_tile. */
930 static void
931 add_vtype(fringe_node_c * vertex, unsigned side, vertex_type_c vtype)
932 {
933         if (side == S_RIGHT)
934                 vertex->tiles[vertex->n_tiles++] = vtype;
935         else {
936                 register int i;
937
938                 for (i = vertex->n_tiles; i > 0; i--)
939                         vertex->tiles[i] = vertex->tiles[i - 1];
940                 vertex->tiles[0] = vtype;
941                 vertex->n_tiles++;
942         }
943 }
944
945 static fringe_node_c *
946 alloc_vertex(ModeInfo * mi, angle_c dir, fringe_node_c * from, tiling_c * tp)
947 {
948         fringe_node_c *v;
949
950         if ((v = ALLOC_NODE(fringe_node_c)) == NULL) {
951                 tp->done = True;
952                 if (MI_IS_VERBOSE(mi)) {
953                         (void) fprintf(stderr, "No memory in alloc_vertex()\n");
954                 }
955                 tp->busyLoop = CELEBRATE;
956                 return v;
957         }
958         *v = *from;
959         add_unit_vec(dir, v->fived);
960         fived_to_loc(v->fived, tp, &(v->loc));
961         if (v->loc.x < 0 || v->loc.y < 0
962             || v->loc.x >= tp->width || v->loc.y >= tp->height) {
963                 v->off_screen = True;
964                 if (v->loc.x < -tp->width || v->loc.y < -tp->height
965                   || v->loc.x >= 2 * tp->width || v->loc.y >= 2 * tp->height)
966                         tp->done = True;
967         } else {
968                 v->off_screen = False;
969                 tp->fringe.n_nodes++;
970         }
971         v->n_tiles = 0;
972         v->rule_mask = (1 << N_VERTEX_RULES) - 1;
973         v->list_ptr = 0;
974         return v;
975 }
976
977 /*-
978  * Add a tile described by vtype to the side of vertex.  This must be
979  * allowed by the rules -- we do not check it here.  New vertices are
980  * allocated as necessary.  The fringe and the forced vertex pool are updated.
981  * The new tile is drawn on the display.
982  *
983  * One thing we do check here is whether the new tile causes an untiled
984  * area to become enclosed by the tiling.  If this would happen, the tile
985  * is not added.  The return value is true iff a tile was added.
986  */
987 static int
988 add_tile(ModeInfo * mi,
989          fringe_node_c * vertex, unsigned side, vertex_type_c vtype)
990 {
991         tiling_c   *tp = &tilings[MI_SCREEN(mi)];
992
993         fringe_node_c
994                 *left = (fringe_node_c *) NULL,
995                 *right = (fringe_node_c *) NULL,
996                 *far = (fringe_node_c *) NULL,
997                 *node;
998         unsigned    fc = fringe_changes(mi, vertex, side, vtype, &right, &far, &left);
999
1000         vertex_type_c
1001                 ltype = VT_LEFT(vtype),
1002                 rtype = VT_RIGHT(vtype),
1003                 ftype = VT_FAR(vtype);
1004
1005         /* By our conventions vertex->next lies to the left of vertex and
1006            vertex->prev to the right. */
1007
1008         /* This should never occur. */
1009         if (fc & FC_BAG) {
1010                 tp->done = True;
1011                 if (MI_IS_VERBOSE(mi)) {
1012                         (void) fprintf(stderr, "Weirdness in add_tile()\n");
1013                         (void) fprintf(stderr, "fc = %d, FC_BAG = %d\n", fc, FC_BAG);
1014                 }
1015         }
1016         if (side == S_LEFT) {
1017                 if (right == NULL)
1018                         if ((right = alloc_vertex(mi, vertex_dir(mi, vertex, S_LEFT) -
1019                                         vtype_angle(vtype), vertex, tp)) == NULL)
1020                                 return False;
1021                 if (far == NULL)
1022                         if ((far = alloc_vertex(mi, vertex_dir(mi, left, S_RIGHT) +
1023                                         vtype_angle(ltype), left, tp)) == NULL)
1024                                 return False;
1025         } else {
1026                 if (left == NULL)
1027                         if ((left = alloc_vertex(mi, vertex_dir(mi, vertex, S_RIGHT) +
1028                                         vtype_angle(vtype), vertex, tp)) == NULL)
1029                                 return False;
1030                 if (far == NULL)
1031                         if ((far = alloc_vertex(mi, vertex_dir(mi, right, S_LEFT) -
1032                                         vtype_angle(rtype), right, tp)) == NULL)
1033                                 return False;
1034         }
1035
1036         /* Having allocated the new vertices, but before joining them with
1037            the rest of the fringe, check if vertices with same coordinates
1038            already exist.  If any such are found, give up. */
1039         node = tp->fringe.nodes;
1040         do {
1041                 if (((fc & FC_NEW_LEFT) && fived_equal(node->fived, left->fived))
1042                     || ((fc & FC_NEW_RIGHT) && fived_equal(node->fived, right->fived))
1043                     || ((fc & FC_NEW_FAR) && fived_equal(node->fived, far->fived))) {
1044                         /* Better luck next time. */
1045                         if (fc & FC_NEW_LEFT)
1046                                 delete_vertex(mi, left, tp);
1047                         if (fc & FC_NEW_RIGHT)
1048                                 delete_vertex(mi, right, tp);
1049                         if (fc & FC_NEW_FAR)
1050                                 delete_vertex(mi, far, tp);
1051                         return False;
1052                 }
1053                 node = node->next;
1054         } while (node != tp->fringe.nodes);
1055
1056         /* Rechain. */
1057         if (!(fc & FC_CUT_THIS)) {
1058                 if (side == S_LEFT) {
1059                         vertex->next = right;
1060                         right->prev = vertex;
1061                 } else {
1062                         vertex->prev = left;
1063                         left->next = vertex;
1064                 }
1065         }
1066         if (!(fc & FC_CUT_FAR)) {
1067                 if (!(fc & FC_CUT_LEFT)) {
1068                         far->next = left;
1069                         left->prev = far;
1070                 }
1071                 if (!(fc & FC_CUT_RIGHT)) {
1072                         far->prev = right;
1073                         right->next = far;
1074                 }
1075         }
1076         draw_tile(vertex, right, far, left, vtype, mi);
1077
1078         /* Delete vertices that are no longer on the fringe.  Check the others. */
1079         if (fc & FC_CUT_THIS) {
1080                 tp->fringe.nodes = far;
1081                 delete_vertex(mi, vertex, tp);
1082         } else {
1083                 add_vtype(vertex, side, vtype);
1084                 check_vertex(mi, vertex, tp);
1085                 tp->fringe.nodes = vertex;
1086         }
1087         if (fc & FC_CUT_FAR)
1088                 delete_vertex(mi, far, tp);
1089         else {
1090                 add_vtype(far, fc & FC_CUT_RIGHT ? S_LEFT : S_RIGHT, ftype);
1091                 check_vertex(mi, far, tp);
1092         }
1093         if (fc & FC_CUT_LEFT)
1094                 delete_vertex(mi, left, tp);
1095         else {
1096                 add_vtype(left, fc & FC_CUT_FAR ? S_LEFT : S_RIGHT, ltype);
1097                 check_vertex(mi, left, tp);
1098         }
1099         if (fc & FC_CUT_RIGHT)
1100                 delete_vertex(mi, right, tp);
1101         else {
1102                 add_vtype(right, fc & FC_CUT_FAR ? S_RIGHT : S_LEFT, rtype);
1103                 check_vertex(mi, right, tp);
1104         }
1105         return True;
1106 }
1107
1108
1109 /*-
1110  * Add a forced tile to a given forced vertex.  Basically an easy job,
1111  * since we know what to add.  But it might fail if adding the tile
1112  * would cause some untiled area to become enclosed.  There is also another
1113  * more exotic culprit: we might have a dislocation.  Fortunately, they
1114  * are very rare (the PRL article reported that perfect tilings of over
1115  * 2^50 tiles had been generated).  There is a version of the algorithm
1116  * that doesn't produce dislocations, but it's a lot hairier than the
1117  * simpler version I used.
1118  */
1119 static int
1120 add_forced_tile(ModeInfo * mi, forced_node_c * node)
1121 {
1122         tiling_c   *tp = &tilings[MI_SCREEN(mi)];
1123         unsigned    side;
1124         vertex_type_c vtype;
1125         rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
1126         int         n;
1127
1128         if (node->forced_sides == (S_LEFT | S_RIGHT))
1129                 side = NRAND(2) ? S_LEFT : S_RIGHT;
1130         else
1131                 side = node->forced_sides;
1132         n = match_rules(node->vertex, hits, True);
1133         n = find_completions(node->vertex, hits, n, side, &vtype /*, True */ );
1134         if (n <= 0) {
1135                 tp->done = True;
1136                 if (MI_IS_VERBOSE(mi)) {
1137                         (void) fprintf(stderr, "Weirdness in add_forced_tile()\n");
1138                         (void) fprintf(stderr, "n = %d\n", n);
1139                 }
1140         }
1141         return add_tile(mi, node->vertex, side, vtype);
1142 }
1143
1144
1145 /*-
1146  * Whether the addition of a tile of vtype on the given side of vertex
1147  * would conform to the rules.  The efficient way to do this would be
1148  * to add the new tile and then use the same type of search as in
1149  * match_rules.  However, this function is not a performance
1150  * bottleneck (only needed for random tile additions, which are
1151  * relatively infrequent), so I will settle for a simpler implementation.
1152  */
1153 static int
1154 legal_move(fringe_node_c * vertex, unsigned side, vertex_type_c vtype)
1155 {
1156         rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
1157         vertex_type_c legal_vt[MAX_COMPL];
1158         int         n_hits, n_legal, i;
1159
1160         n_hits = match_rules(vertex, hits, False);
1161         n_legal = find_completions(vertex, hits, n_hits, side, legal_vt /*, False */ );
1162         for (i = 0; i < n_legal; i++)
1163                 if (legal_vt[i] == vtype)
1164                         return True;
1165         return False;
1166 }
1167
1168
1169 /*-
1170  * Add a randomly chosen tile to a given vertex.  This requires more checking
1171  * as we must make sure the new tile conforms to the vertex rules at every
1172  * vertex it touches. */
1173 static void
1174 add_random_tile(fringe_node_c * vertex, ModeInfo * mi)
1175 {
1176         fringe_node_c *right, *left, *far;
1177         int         i, j, n, n_hits, n_good;
1178         unsigned    side, fc, no_good, s;
1179         vertex_type_c vtypes[MAX_COMPL];
1180         rule_match_c hits[MAX_TILES_PER_VERTEX * N_VERTEX_RULES];
1181         tiling_c   *tp = &tilings[MI_SCREEN(mi)];
1182
1183         if (MI_NPIXELS(mi) > 2) {
1184                 tp->thick_color = NRAND(MI_NPIXELS(mi));
1185                 /* Insure good contrast */
1186                 tp->thin_color = (NRAND(2 * MI_NPIXELS(mi) / 3) + tp->thick_color +
1187                                   MI_NPIXELS(mi) / 6) % MI_NPIXELS(mi);
1188         } else
1189                 tp->thick_color = tp->thin_color = MI_WHITE_PIXEL(mi);
1190         n_hits = match_rules(vertex, hits, False);
1191         side = NRAND(2) ? S_LEFT : S_RIGHT;
1192         n = find_completions(vertex, hits, n_hits, side, vtypes /*, False */ );
1193         /* One answer would mean a forced tile. */
1194         if (n <= 0) {
1195                 tp->done = True;
1196                 if (MI_IS_VERBOSE(mi)) {
1197                         (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1198                         (void) fprintf(stderr, "n = %d\n", n);
1199                 }
1200         }
1201         no_good = 0;
1202         n_good = n;
1203         for (i = 0; i < n; i++) {
1204                 fc = fringe_changes(mi, vertex, side, vtypes[i], &right, &far, &left);
1205                 if (fc & FC_BAG) {
1206                         tp->done = True;
1207                         if (MI_IS_VERBOSE(mi)) {
1208                                 (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1209                                 (void) fprintf(stderr, "fc = %d, FC_BAG = %d\n", fc, FC_BAG);
1210                         }
1211                 }
1212                 if (right) {
1213                         s = (((fc & FC_CUT_FAR) && (fc & FC_CUT_LEFT)) ? S_RIGHT : S_LEFT);
1214                         if (!legal_move(right, s, VT_RIGHT(vtypes[i]))) {
1215                                 no_good |= (1 << i);
1216                                 n_good--;
1217                                 continue;
1218                         }
1219                 }
1220                 if (left) {
1221                         s = (((fc & FC_CUT_FAR) && (fc & FC_CUT_RIGHT)) ? S_LEFT : S_RIGHT);
1222                         if (!legal_move(left, s, VT_LEFT(vtypes[i]))) {
1223                                 no_good |= (1 << i);
1224                                 n_good--;
1225                                 continue;
1226                         }
1227                 }
1228                 if (far) {
1229                         s = ((fc & FC_CUT_LEFT) ? S_RIGHT : S_LEFT);
1230                         if (!legal_move(far, s, VT_FAR(vtypes[i]))) {
1231                                 no_good |= (1 << i);
1232                                 n_good--;
1233                         }
1234                 }
1235         }
1236         if (n_good <= 0) {
1237                 tp->done = True;
1238                 if (MI_IS_VERBOSE(mi)) {
1239                         (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1240                         (void) fprintf(stderr, "n_good = %d\n", n_good);
1241                 }
1242         }
1243         n = NRAND(n_good);
1244         for (i = j = 0; i <= n; i++, j++)
1245                 while (no_good & (1 << j))
1246                         j++;
1247
1248         if (!add_tile(mi, vertex, side, vtypes[j - 1])) {
1249                 tp->done = True;
1250                 if (MI_IS_VERBOSE(mi)) {
1251                         (void) fprintf(stderr, "Weirdness in add_random_tile()\n");
1252                 }
1253                 free_penrose(tp);
1254         }
1255 }
1256
1257 /* One step of the growth algorithm. */
1258 ENTRYPOINT void
1259 draw_penrose(ModeInfo * mi)
1260 {
1261         int         i = 0, n;
1262         forced_node_c *p;
1263         tiling_c   *tp;
1264
1265         if (tilings == NULL)
1266                 return;
1267         tp = &tilings[MI_SCREEN(mi)];
1268         if (tp->fringe.nodes == NULL)
1269                 return;
1270
1271         MI_IS_DRAWN(mi) = True;
1272         p = tp->forced.first;
1273         if (tp->busyLoop > 0) {
1274                 tp->busyLoop--;
1275                 return;
1276         }
1277         if (tp->done || tp->failures >= 100) {
1278                 init_penrose(mi);
1279                 return;
1280         }
1281         /* Check for the initial "2-gon". */
1282         if (tp->fringe.nodes->prev == tp->fringe.nodes->next) {
1283                 vertex_type_c vtype = (unsigned char) (VT_TOTAL_MASK & LRAND());
1284
1285                 MI_CLEARWINDOW(mi);
1286
1287                 if (!add_tile(mi, tp->fringe.nodes, S_LEFT, vtype))
1288                         free_penrose(tp);
1289                 return;
1290         }
1291         /* No visible nodes left. */
1292         if (tp->fringe.n_nodes == 0) {
1293                 tp->done = True;
1294                 tp->busyLoop = COMPLETION;      /* Just finished drawing */
1295                 return;
1296         }
1297         if (tp->forced.n_visible > 0 && tp->failures < 10) {
1298                 n = NRAND(tp->forced.n_visible);
1299                 for (;;) {
1300                         while (p->vertex->off_screen)
1301                                 p = p->next;
1302                         if (i++ < n)
1303                                 p = p->next;
1304                         else
1305                                 break;
1306                 }
1307         } else if (tp->forced.n_nodes > 0) {
1308                 n = NRAND(tp->forced.n_nodes);
1309                 while (i++ < n)
1310                         p = p->next;
1311         } else {
1312                 fringe_node_c *fringe_p = tp->fringe.nodes;
1313
1314                 n = NRAND(tp->fringe.n_nodes);
1315                 i = 0;
1316                 for (; i <= n; i++)
1317                         do {
1318                                 fringe_p = fringe_p->next;
1319                         } while (fringe_p->off_screen);
1320                 add_random_tile(fringe_p, mi);
1321                 tp->failures = 0;
1322                 return;
1323         }
1324         if (add_forced_tile(mi, p))
1325                 tp->failures = 0;
1326         else
1327                 tp->failures++;
1328 }
1329
1330
1331 ENTRYPOINT void
1332 reshape_penrose(ModeInfo * mi, int width, int height)
1333 {
1334         tiling_c   *tp = &tilings[MI_SCREEN(mi)];
1335         tp->width = width;
1336         tp->height = height;
1337 }
1338
1339 /* Total clean-up. */
1340 ENTRYPOINT void
1341 release_penrose(ModeInfo * mi)
1342 {
1343         if (tilings != NULL) {
1344                 int         screen;
1345
1346                 for (screen = 0; screen < MI_NUM_SCREENS(mi); screen++)
1347                         free_penrose(&tilings[screen]);
1348                 (void) free((void *) tilings);
1349                 tilings = (tiling_c *) NULL;
1350         }
1351 }
1352
1353 XSCREENSAVER_MODULE ("Penrose", penrose)
1354
1355 #endif /* MODE_penrose */