summaryrefslogtreecommitdiff
path: root/apps/plugins/puzzles/src/grid.c
diff options
context:
space:
mode:
Diffstat (limited to 'apps/plugins/puzzles/src/grid.c')
-rw-r--r--apps/plugins/puzzles/src/grid.c1357
1 files changed, 1029 insertions, 328 deletions
diff --git a/apps/plugins/puzzles/src/grid.c b/apps/plugins/puzzles/src/grid.c
index 5ea37439d4..04bb8a36cd 100644
--- a/apps/plugins/puzzles/src/grid.c
+++ b/apps/plugins/puzzles/src/grid.c
@@ -11,13 +11,21 @@
11#include <string.h> 11#include <string.h>
12#include <assert.h> 12#include <assert.h>
13#include <ctype.h> 13#include <ctype.h>
14#include <math.h>
15#include <float.h> 14#include <float.h>
15#include <limits.h>
16#ifdef NO_TGMATH_H
17# include <math.h>
18#else
19# include <tgmath.h>
20#endif
16 21
17#include "puzzles.h" 22#include "puzzles.h"
18#include "tree234.h" 23#include "tree234.h"
19#include "grid.h" 24#include "grid.h"
25#include "penrose-legacy.h"
20#include "penrose.h" 26#include "penrose.h"
27#include "hat.h"
28#include "spectre.h"
21 29
22/* Debugging options */ 30/* Debugging options */
23 31
@@ -36,12 +44,17 @@ void grid_free(grid *g)
36 if (g->refcount == 0) { 44 if (g->refcount == 0) {
37 int i; 45 int i;
38 for (i = 0; i < g->num_faces; i++) { 46 for (i = 0; i < g->num_faces; i++) {
39 sfree(g->faces[i].dots); 47 sfree(g->faces[i]->dots);
40 sfree(g->faces[i].edges); 48 sfree(g->faces[i]->edges);
49 sfree(g->faces[i]);
41 } 50 }
42 for (i = 0; i < g->num_dots; i++) { 51 for (i = 0; i < g->num_dots; i++) {
43 sfree(g->dots[i].faces); 52 sfree(g->dots[i]->faces);
44 sfree(g->dots[i].edges); 53 sfree(g->dots[i]->edges);
54 sfree(g->dots[i]);
55 }
56 for (i = 0; i < g->num_edges; i++) {
57 sfree(g->edges[i]);
45 } 58 }
46 sfree(g->faces); 59 sfree(g->faces);
47 sfree(g->edges); 60 sfree(g->edges);
@@ -59,6 +72,7 @@ static grid *grid_empty(void)
59 g->edges = NULL; 72 g->edges = NULL;
60 g->dots = NULL; 73 g->dots = NULL;
61 g->num_faces = g->num_edges = g->num_dots = 0; 74 g->num_faces = g->num_edges = g->num_dots = 0;
75 g->size_faces = g->size_edges = g->size_dots = 0;
62 g->refcount = 1; 76 g->refcount = 1;
63 g->lowest_x = g->lowest_y = g->highest_x = g->highest_y = 0; 77 g->lowest_x = g->lowest_y = g->highest_x = g->highest_y = 0;
64 return g; 78 return g;
@@ -116,7 +130,7 @@ grid_edge *grid_nearest_edge(grid *g, int x, int y)
116 best_edge = NULL; 130 best_edge = NULL;
117 131
118 for (i = 0; i < g->num_edges; i++) { 132 for (i = 0; i < g->num_edges; i++) {
119 grid_edge *e = &g->edges[i]; 133 grid_edge *e = g->edges[i];
120 long e2; /* squared length of edge */ 134 long e2; /* squared length of edge */
121 long a2, b2; /* squared lengths of other sides */ 135 long a2, b2; /* squared lengths of other sides */
122 double dist; 136 double dist;
@@ -185,7 +199,7 @@ xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n\n");
185 if (which & SVG_FACES) { 199 if (which & SVG_FACES) {
186 fprintf(fp, "<g>\n"); 200 fprintf(fp, "<g>\n");
187 for (i = 0; i < g->num_faces; i++) { 201 for (i = 0; i < g->num_faces; i++) {
188 grid_face *f = g->faces + i; 202 grid_face *f = g->faces[i];
189 fprintf(fp, "<polygon points=\""); 203 fprintf(fp, "<polygon points=\"");
190 for (j = 0; j < f->order; j++) { 204 for (j = 0; j < f->order; j++) {
191 grid_dot *d = f->dots[j]; 205 grid_dot *d = f->dots[j];
@@ -200,7 +214,7 @@ xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n\n");
200 if (which & SVG_EDGES) { 214 if (which & SVG_EDGES) {
201 fprintf(fp, "<g>\n"); 215 fprintf(fp, "<g>\n");
202 for (i = 0; i < g->num_edges; i++) { 216 for (i = 0; i < g->num_edges; i++) {
203 grid_edge *e = g->edges + i; 217 grid_edge *e = g->edges[i];
204 grid_dot *d1 = e->dot1, *d2 = e->dot2; 218 grid_dot *d1 = e->dot1, *d2 = e->dot2;
205 219
206 fprintf(fp, "<line x1=\"%d\" y1=\"%d\" x2=\"%d\" y2=\"%d\" " 220 fprintf(fp, "<line x1=\"%d\" y1=\"%d\" x2=\"%d\" y2=\"%d\" "
@@ -213,7 +227,7 @@ xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n\n");
213 if (which & SVG_DOTS) { 227 if (which & SVG_DOTS) {
214 fprintf(fp, "<g>\n"); 228 fprintf(fp, "<g>\n");
215 for (i = 0; i < g->num_dots; i++) { 229 for (i = 0; i < g->num_dots; i++) {
216 grid_dot *d = g->dots + i; 230 grid_dot *d = g->dots[i];
217 fprintf(fp, "<ellipse cx=\"%d\" cy=\"%d\" rx=\"%d\" ry=\"%d\" fill=\"%s\" />", 231 fprintf(fp, "<ellipse cx=\"%d\" cy=\"%d\" rx=\"%d\" ry=\"%d\" fill=\"%s\" />",
218 d->x, d->y, g->tilesize/20, g->tilesize/20, DOT_COLOUR); 232 d->x, d->y, g->tilesize/20, g->tilesize/20, DOT_COLOUR);
219 } 233 }
@@ -251,13 +265,17 @@ static void grid_debug_basic(grid *g)
251#ifdef DEBUG_GRID 265#ifdef DEBUG_GRID
252 int i; 266 int i;
253 printf("--- Basic Grid Data ---\n"); 267 printf("--- Basic Grid Data ---\n");
268 for (i = 0; i < g->num_dots; i++) {
269 grid_dot *d = g->dots[i];
270 printf("Dot %d at (%d,%d)\n", i, d->x, d->y);
271 }
254 for (i = 0; i < g->num_faces; i++) { 272 for (i = 0; i < g->num_faces; i++) {
255 grid_face *f = g->faces + i; 273 grid_face *f = g->faces[i];
256 printf("Face %d: dots[", i); 274 printf("Face %d: dots[", i);
257 int j; 275 int j;
258 for (j = 0; j < f->order; j++) { 276 for (j = 0; j < f->order; j++) {
259 grid_dot *d = f->dots[j]; 277 grid_dot *d = f->dots[j];
260 printf("%s%d", j ? "," : "", (int)(d - g->dots)); 278 printf("%s%d", j ? "," : "", (int)(d->index));
261 } 279 }
262 printf("]\n"); 280 printf("]\n");
263 } 281 }
@@ -275,38 +293,38 @@ static void grid_debug_derived(grid *g)
275 int i; 293 int i;
276 printf("--- Derived Grid Data ---\n"); 294 printf("--- Derived Grid Data ---\n");
277 for (i = 0; i < g->num_edges; i++) { 295 for (i = 0; i < g->num_edges; i++) {
278 grid_edge *e = g->edges + i; 296 grid_edge *e = g->edges[i];
279 printf("Edge %d: dots[%d,%d] faces[%d,%d]\n", 297 printf("Edge %d: dots[%d,%d] faces[%d,%d]\n",
280 i, (int)(e->dot1 - g->dots), (int)(e->dot2 - g->dots), 298 i, (int)(e->dot1->index), (int)(e->dot2->index),
281 e->face1 ? (int)(e->face1 - g->faces) : -1, 299 e->face1 ? (int)(e->face1->index) : -1,
282 e->face2 ? (int)(e->face2 - g->faces) : -1); 300 e->face2 ? (int)(e->face2->index) : -1);
283 } 301 }
284 /* faces */ 302 /* faces */
285 for (i = 0; i < g->num_faces; i++) { 303 for (i = 0; i < g->num_faces; i++) {
286 grid_face *f = g->faces + i; 304 grid_face *f = g->faces[i];
287 int j; 305 int j;
288 printf("Face %d: faces[", i); 306 printf("Face %d: faces[", i);
289 for (j = 0; j < f->order; j++) { 307 for (j = 0; j < f->order; j++) {
290 grid_edge *e = f->edges[j]; 308 grid_edge *e = f->edges[j];
291 grid_face *f2 = (e->face1 == f) ? e->face2 : e->face1; 309 grid_face *f2 = (e->face1 == f) ? e->face2 : e->face1;
292 printf("%s%d", j ? "," : "", f2 ? (int)(f2 - g->faces) : -1); 310 printf("%s%d", j ? "," : "", f2 ? f2->index : -1);
293 } 311 }
294 printf("]\n"); 312 printf("]\n");
295 } 313 }
296 /* dots */ 314 /* dots */
297 for (i = 0; i < g->num_dots; i++) { 315 for (i = 0; i < g->num_dots; i++) {
298 grid_dot *d = g->dots + i; 316 grid_dot *d = g->dots[i];
299 int j; 317 int j;
300 printf("Dot %d: dots[", i); 318 printf("Dot %d: dots[", i);
301 for (j = 0; j < d->order; j++) { 319 for (j = 0; j < d->order; j++) {
302 grid_edge *e = d->edges[j]; 320 grid_edge *e = d->edges[j];
303 grid_dot *d2 = (e->dot1 == d) ? e->dot2 : e->dot1; 321 grid_dot *d2 = (e->dot1 == d) ? e->dot2 : e->dot1;
304 printf("%s%d", j ? "," : "", (int)(d2 - g->dots)); 322 printf("%s%d", j ? "," : "", d2->index);
305 } 323 }
306 printf("] faces["); 324 printf("] faces[");
307 for (j = 0; j < d->order; j++) { 325 for (j = 0; j < d->order; j++) {
308 grid_face *f = d->faces[j]; 326 grid_face *f = d->faces[j];
309 printf("%s%d", j ? "," : "", f ? (int)(f - g->faces) : -1); 327 printf("%s%d", j ? "," : "", f ? f->index : -1);
310 } 328 }
311 printf("]\n"); 329 printf("]\n");
312 } 330 }
@@ -324,21 +342,23 @@ static int grid_edge_bydots_cmpfn(void *v1, void *v2)
324 grid_edge *b = v2; 342 grid_edge *b = v2;
325 grid_dot *da, *db; 343 grid_dot *da, *db;
326 344
327 /* Pointer subtraction is valid here, because all dots point into the 345 /* Edges are not "normalised" - the 2 dots could be stored in any order,
328 * same dot-list (g->dots).
329 * Edges are not "normalised" - the 2 dots could be stored in any order,
330 * so we need to take this into account when comparing edges. */ 346 * so we need to take this into account when comparing edges. */
331 347
332 /* Compare first dots */ 348 /* Compare first dots */
333 da = (a->dot1 < a->dot2) ? a->dot1 : a->dot2; 349 da = (a->dot1 < a->dot2) ? a->dot1 : a->dot2;
334 db = (b->dot1 < b->dot2) ? b->dot1 : b->dot2; 350 db = (b->dot1 < b->dot2) ? b->dot1 : b->dot2;
335 if (da != db) 351 if (da->index < db->index)
336 return db - da; 352 return -1;
353 if (da->index > db->index)
354 return +1;
337 /* Compare last dots */ 355 /* Compare last dots */
338 da = (a->dot1 < a->dot2) ? a->dot2 : a->dot1; 356 da = (a->dot1 < a->dot2) ? a->dot2 : a->dot1;
339 db = (b->dot1 < b->dot2) ? b->dot2 : b->dot1; 357 db = (b->dot1 < b->dot2) ? b->dot2 : b->dot1;
340 if (da != db) 358 if (da->index < db->index)
341 return db - da; 359 return -1;
360 if (da->index > db->index)
361 return +1;
342 362
343 return 0; 363 return 0;
344} 364}
@@ -358,7 +378,7 @@ static int grid_edge_bydots_cmpfn(void *v1, void *v2)
358static void grid_trim_vigorously(grid *g) 378static void grid_trim_vigorously(grid *g)
359{ 379{
360 int *dotpairs, *faces, *dots; 380 int *dotpairs, *faces, *dots;
361 int *dsf; 381 DSF *dsf;
362 int i, j, k, size, newfaces, newdots; 382 int i, j, k, size, newfaces, newdots;
363 383
364 /* 384 /*
@@ -371,10 +391,10 @@ static void grid_trim_vigorously(grid *g)
371 for (j = 0; j < g->num_dots; j++) 391 for (j = 0; j < g->num_dots; j++)
372 dotpairs[i*g->num_dots+j] = -1; 392 dotpairs[i*g->num_dots+j] = -1;
373 for (i = 0; i < g->num_faces; i++) { 393 for (i = 0; i < g->num_faces; i++) {
374 grid_face *f = g->faces + i; 394 grid_face *f = g->faces[i];
375 int dot0 = f->dots[f->order-1] - g->dots; 395 int dot0 = f->dots[f->order-1]->index;
376 for (j = 0; j < f->order; j++) { 396 for (j = 0; j < f->order; j++) {
377 int dot1 = f->dots[j] - g->dots; 397 int dot1 = f->dots[j]->index;
378 dotpairs[dot0 * g->num_dots + dot1] = i; 398 dotpairs[dot0 * g->num_dots + dot1] = i;
379 dot0 = dot1; 399 dot0 = dot1;
380 } 400 }
@@ -398,7 +418,7 @@ static void grid_trim_vigorously(grid *g)
398 * Now identify connected pairs of landlocked dots, and form a dsf 418 * Now identify connected pairs of landlocked dots, and form a dsf
399 * unifying them. 419 * unifying them.
400 */ 420 */
401 dsf = snew_dsf(g->num_dots); 421 dsf = dsf_new(g->num_dots);
402 for (i = 0; i < g->num_dots; i++) 422 for (i = 0; i < g->num_dots; i++)
403 for (j = 0; j < i; j++) 423 for (j = 0; j < i; j++)
404 if (dots[i] && dots[j] && 424 if (dots[i] && dots[j] &&
@@ -434,60 +454,52 @@ static void grid_trim_vigorously(grid *g)
434 for (i = 0; i < g->num_dots; i++) 454 for (i = 0; i < g->num_dots; i++)
435 dots[i] = 0; 455 dots[i] = 0;
436 for (i = 0; i < g->num_faces; i++) { 456 for (i = 0; i < g->num_faces; i++) {
437 grid_face *f = g->faces + i; 457 grid_face *f = g->faces[i];
438 bool keep = false; 458 bool keep = false;
439 for (k = 0; k < f->order; k++) 459 for (k = 0; k < f->order; k++)
440 if (dsf_canonify(dsf, f->dots[k] - g->dots) == j) 460 if (dsf_canonify(dsf, f->dots[k]->index) == j)
441 keep = true; 461 keep = true;
442 if (keep) { 462 if (keep) {
443 faces[i] = 1; 463 faces[i] = 1;
444 for (k = 0; k < f->order; k++) 464 for (k = 0; k < f->order; k++)
445 dots[f->dots[k]-g->dots] = 1; 465 dots[f->dots[k]->index] = 1;
446 } 466 }
447 } 467 }
448 468
449 /* 469 /*
450 * Work out the new indices of those faces and dots, when we 470 * Compact the faces array, rewriting the faces' indices and
451 * compact the arrays containing them. 471 * freeing the unwanted ones.
452 */
453 for (i = newfaces = 0; i < g->num_faces; i++)
454 faces[i] = (faces[i] ? newfaces++ : -1);
455 for (i = newdots = 0; i < g->num_dots; i++)
456 dots[i] = (dots[i] ? newdots++ : -1);
457
458 /*
459 * Free the dynamically allocated 'dots' pointer lists in faces
460 * we're going to discard.
461 */ 472 */
462 for (i = 0; i < g->num_faces; i++) 473 for (i = newfaces = 0; i < g->num_faces; i++) {
463 if (faces[i] < 0) 474 grid_face *f = g->faces[i];
464 sfree(g->faces[i].dots); 475 if (faces[i]) {
476 f->index = newfaces++;
477 g->faces[f->index] = f;
478 } else {
479 sfree(f->dots);
480 sfree(f);
481 }
482 }
483 g->num_faces = newfaces;
465 484
466 /* 485 /*
467 * Go through and compact the arrays. 486 * Compact the dots array, similarly.
468 */ 487 */
469 for (i = 0; i < g->num_dots; i++) 488 for (i = newdots = 0; i < g->num_dots; i++) {
470 if (dots[i] >= 0) { 489 grid_dot *d = g->dots[i];
471 grid_dot *dnew = g->dots + dots[i], *dold = g->dots + i; 490 if (dots[i]) {
472 *dnew = *dold; /* structure copy */ 491 d->index = newdots++;
473 } 492 g->dots[d->index] = d;
474 for (i = 0; i < g->num_faces; i++) 493 } else {
475 if (faces[i] >= 0) { 494 sfree(d->edges);
476 grid_face *fnew = g->faces + faces[i], *fold = g->faces + i; 495 sfree(d->faces);
477 *fnew = *fold; /* structure copy */ 496 sfree(d);
478 for (j = 0; j < fnew->order; j++) {
479 /*
480 * Reindex the dots in this face.
481 */
482 k = fnew->dots[j] - g->dots;
483 fnew->dots[j] = g->dots + dots[k];
484 }
485 } 497 }
486 g->num_faces = newfaces; 498 }
487 g->num_dots = newdots; 499 g->num_dots = newdots;
488 500
489 sfree(dotpairs); 501 sfree(dotpairs);
490 sfree(dsf); 502 dsf_free(dsf);
491 sfree(dots); 503 sfree(dots);
492 sfree(faces); 504 sfree(faces);
493} 505}
@@ -505,7 +517,6 @@ static void grid_make_consistent(grid *g)
505{ 517{
506 int i; 518 int i;
507 tree234 *incomplete_edges; 519 tree234 *incomplete_edges;
508 grid_edge *next_new_edge; /* Where new edge will go into g->edges */
509 520
510 grid_debug_basic(g); 521 grid_debug_basic(g);
511 522
@@ -513,14 +524,6 @@ static void grid_make_consistent(grid *g)
513 * Generate edges 524 * Generate edges
514 */ 525 */
515 526
516 /* We know how many dots and faces there are, so we can find the exact
517 * number of edges from Euler's polyhedral formula: F + V = E + 2 .
518 * We use "-1", not "-2" here, because Euler's formula includes the
519 * infinite face, which we don't count. */
520 g->num_edges = g->num_faces + g->num_dots - 1;
521 g->edges = snewn(g->num_edges, grid_edge);
522 next_new_edge = g->edges;
523
524 /* Iterate over faces, and over each face's dots, generating edges as we 527 /* Iterate over faces, and over each face's dots, generating edges as we
525 * go. As we find each new edge, we can immediately fill in the edge's 528 * go. As we find each new edge, we can immediately fill in the edge's
526 * dots, but only one of the edge's faces. Later on in the iteration, we 529 * dots, but only one of the edge's faces. Later on in the iteration, we
@@ -530,7 +533,7 @@ static void grid_make_consistent(grid *g)
530 * their dots. */ 533 * their dots. */
531 incomplete_edges = newtree234(grid_edge_bydots_cmpfn); 534 incomplete_edges = newtree234(grid_edge_bydots_cmpfn);
532 for (i = 0; i < g->num_faces; i++) { 535 for (i = 0; i < g->num_faces; i++) {
533 grid_face *f = g->faces + i; 536 grid_face *f = g->faces[i];
534 int j; 537 int j;
535 for (j = 0; j < f->order; j++) { 538 for (j = 0; j < f->order; j++) {
536 grid_edge e; /* fake edge for searching */ 539 grid_edge e; /* fake edge for searching */
@@ -548,18 +551,28 @@ static void grid_make_consistent(grid *g)
548 * Edge is already removed from incomplete_edges. */ 551 * Edge is already removed from incomplete_edges. */
549 edge_found->face2 = f; 552 edge_found->face2 = f;
550 } else { 553 } else {
551 assert(next_new_edge - g->edges < g->num_edges); 554 grid_edge *new_edge = snew(grid_edge);
552 next_new_edge->dot1 = e.dot1; 555 new_edge->dot1 = e.dot1;
553 next_new_edge->dot2 = e.dot2; 556 new_edge->dot2 = e.dot2;
554 next_new_edge->face1 = f; 557 new_edge->face1 = f;
555 next_new_edge->face2 = NULL; /* potentially infinite face */ 558 new_edge->face2 = NULL; /* potentially infinite face */
556 add234(incomplete_edges, next_new_edge); 559 add234(incomplete_edges, new_edge);
557 ++next_new_edge; 560
561 /* And add it to g->edges. */
562 if (g->num_edges >= g->size_edges) {
563 int increment = g->num_edges / 4 + 128;
564 g->size_edges = (increment < INT_MAX - g->num_edges ?
565 g->num_edges + increment : INT_MAX);
566 g->edges = sresize(g->edges, g->size_edges, grid_edge *);
567 }
568 assert(g->num_edges < INT_MAX);
569 new_edge->index = g->num_edges++;
570 g->edges[new_edge->index] = new_edge;
558 } 571 }
559 } 572 }
560 } 573 }
561 freetree234(incomplete_edges); 574 freetree234(incomplete_edges);
562 575
563 /* ====== Stage 2 ====== 576 /* ====== Stage 2 ======
564 * For each face, build its edge list. 577 * For each face, build its edge list.
565 */ 578 */
@@ -567,7 +580,7 @@ static void grid_make_consistent(grid *g)
567 /* Allocate space for each edge list. Can do this, because each face's 580 /* Allocate space for each edge list. Can do this, because each face's
568 * edge-list is the same size as its dot-list. */ 581 * edge-list is the same size as its dot-list. */
569 for (i = 0; i < g->num_faces; i++) { 582 for (i = 0; i < g->num_faces; i++) {
570 grid_face *f = g->faces + i; 583 grid_face *f = g->faces[i];
571 int j; 584 int j;
572 f->edges = snewn(f->order, grid_edge*); 585 f->edges = snewn(f->order, grid_edge*);
573 /* Preload with NULLs, to help detect potential bugs. */ 586 /* Preload with NULLs, to help detect potential bugs. */
@@ -579,7 +592,7 @@ static void grid_make_consistent(grid *g)
579 * the face's edge-list, after finding where it should go in the 592 * the face's edge-list, after finding where it should go in the
580 * sequence. */ 593 * sequence. */
581 for (i = 0; i < g->num_edges; i++) { 594 for (i = 0; i < g->num_edges; i++) {
582 grid_edge *e = g->edges + i; 595 grid_edge *e = g->edges[i];
583 int j; 596 int j;
584 for (j = 0; j < 2; j++) { 597 for (j = 0; j < 2; j++) {
585 grid_face *f = j ? e->face2 : e->face1; 598 grid_face *f = j ? e->face2 : e->face1;
@@ -641,16 +654,16 @@ static void grid_make_consistent(grid *g)
641 * allocate the right space for these lists. Pre-compute the sizes by 654 * allocate the right space for these lists. Pre-compute the sizes by
642 * iterating over each edge and recording a tally against each dot. */ 655 * iterating over each edge and recording a tally against each dot. */
643 for (i = 0; i < g->num_dots; i++) { 656 for (i = 0; i < g->num_dots; i++) {
644 g->dots[i].order = 0; 657 g->dots[i]->order = 0;
645 } 658 }
646 for (i = 0; i < g->num_edges; i++) { 659 for (i = 0; i < g->num_edges; i++) {
647 grid_edge *e = g->edges + i; 660 grid_edge *e = g->edges[i];
648 ++(e->dot1->order); 661 ++(e->dot1->order);
649 ++(e->dot2->order); 662 ++(e->dot2->order);
650 } 663 }
651 /* Now we have the sizes, pre-allocate the edge and face lists. */ 664 /* Now we have the sizes, pre-allocate the edge and face lists. */
652 for (i = 0; i < g->num_dots; i++) { 665 for (i = 0; i < g->num_dots; i++) {
653 grid_dot *d = g->dots + i; 666 grid_dot *d = g->dots[i];
654 int j; 667 int j;
655 assert(d->order >= 2); /* sanity check */ 668 assert(d->order >= 2); /* sanity check */
656 d->edges = snewn(d->order, grid_edge*); 669 d->edges = snewn(d->order, grid_edge*);
@@ -663,7 +676,7 @@ static void grid_make_consistent(grid *g)
663 /* For each dot, need to find a face that touches it, so we can seed 676 /* For each dot, need to find a face that touches it, so we can seed
664 * the edge-face-edge-face process around each dot. */ 677 * the edge-face-edge-face process around each dot. */
665 for (i = 0; i < g->num_faces; i++) { 678 for (i = 0; i < g->num_faces; i++) {
666 grid_face *f = g->faces + i; 679 grid_face *f = g->faces[i];
667 int j; 680 int j;
668 for (j = 0; j < f->order; j++) { 681 for (j = 0; j < f->order; j++) {
669 grid_dot *d = f->dots[j]; 682 grid_dot *d = f->dots[j];
@@ -677,7 +690,7 @@ static void grid_make_consistent(grid *g)
677 * blocks progress. But there's only one such face, so we will 690 * blocks progress. But there's only one such face, so we will
678 * succeed in finding every edge and face this way. */ 691 * succeed in finding every edge and face this way. */
679 for (i = 0; i < g->num_dots; i++) { 692 for (i = 0; i < g->num_dots; i++) {
680 grid_dot *d = g->dots + i; 693 grid_dot *d = g->dots[i];
681 int current_face1 = 0; /* ascends clockwise */ 694 int current_face1 = 0; /* ascends clockwise */
682 int current_face2 = 0; /* descends anticlockwise */ 695 int current_face2 = 0; /* descends anticlockwise */
683 696
@@ -774,7 +787,7 @@ static void grid_make_consistent(grid *g)
774 787
775 /* Bounding rectangle */ 788 /* Bounding rectangle */
776 for (i = 0; i < g->num_dots; i++) { 789 for (i = 0; i < g->num_dots; i++) {
777 grid_dot *d = g->dots + i; 790 grid_dot *d = g->dots[i];
778 if (i == 0) { 791 if (i == 0) {
779 g->lowest_x = g->highest_x = d->x; 792 g->lowest_x = g->highest_x = d->x;
780 g->lowest_y = g->highest_y = d->y; 793 g->lowest_y = g->highest_y = d->y;
@@ -802,36 +815,52 @@ static int grid_point_cmp_fn(void *v1, void *v2)
802 else 815 else
803 return p2->x - p1->x; 816 return p2->x - p1->x;
804} 817}
805/* Add a new face to the grid, with its dot list allocated. 818/* Add a new face to the grid, with its dot list allocated. */
806 * Assumes there's enough space allocated for the new face in grid->faces */
807static void grid_face_add_new(grid *g, int face_size) 819static void grid_face_add_new(grid *g, int face_size)
808{ 820{
809 int i; 821 int i;
810 grid_face *new_face = g->faces + g->num_faces; 822 grid_face *new_face = snew(grid_face);
823 assert(g->num_faces < INT_MAX);
824 if (g->num_faces >= g->size_faces) {
825 int increment = g->num_faces / 4 + 128;
826 g->size_faces = (increment < INT_MAX - g->num_faces ?
827 g->num_faces + increment : INT_MAX);
828 g->faces = sresize(g->faces, g->size_faces, grid_face *);
829 }
830 new_face->index = g->num_faces++;
831 g->faces[new_face->index] = new_face;
832
811 new_face->order = face_size; 833 new_face->order = face_size;
812 new_face->dots = snewn(face_size, grid_dot*); 834 new_face->dots = snewn(face_size, grid_dot*);
813 for (i = 0; i < face_size; i++) 835 for (i = 0; i < face_size; i++)
814 new_face->dots[i] = NULL; 836 new_face->dots[i] = NULL;
815 new_face->edges = NULL; 837 new_face->edges = NULL;
816 new_face->has_incentre = false; 838 new_face->has_incentre = false;
817 g->num_faces++;
818} 839}
819/* Assumes dot list has enough space */
820static grid_dot *grid_dot_add_new(grid *g, int x, int y) 840static grid_dot *grid_dot_add_new(grid *g, int x, int y)
821{ 841{
822 grid_dot *new_dot = g->dots + g->num_dots; 842 grid_dot *new_dot = snew(grid_dot);
843 if (g->num_dots >= g->size_dots) {
844 int increment = g->num_dots / 4 + 128;
845 g->size_dots = (increment < INT_MAX - g->num_dots ?
846 g->num_dots + increment : INT_MAX);
847 g->dots = sresize(g->dots, g->size_dots, grid_dot *);
848 }
849 assert(g->num_dots < INT_MAX);
850 new_dot->index = g->num_dots++;
851 g->dots[new_dot->index] = new_dot;
852
823 new_dot->order = 0; 853 new_dot->order = 0;
824 new_dot->edges = NULL; 854 new_dot->edges = NULL;
825 new_dot->faces = NULL; 855 new_dot->faces = NULL;
826 new_dot->x = x; 856 new_dot->x = x;
827 new_dot->y = y; 857 new_dot->y = y;
828 g->num_dots++; 858
829 return new_dot; 859 return new_dot;
830} 860}
831/* Retrieve a dot with these (x,y) coordinates. Either return an existing dot 861/* Retrieve a dot with these (x,y) coordinates. Either return an existing dot
832 * in the dot_list, or add a new dot to the grid (and the dot_list) and 862 * in the dot_list, or add a new dot to the grid (and the dot_list) and
833 * return that. 863 * return that. */
834 * Assumes g->dots has enough capacity allocated */
835static grid_dot *grid_get_dot(grid *g, tree234 *dot_list, int x, int y) 864static grid_dot *grid_get_dot(grid *g, tree234 *dot_list, int x, int y)
836{ 865{
837 grid_dot test, *ret; 866 grid_dot test, *ret;
@@ -855,7 +884,7 @@ static grid_dot *grid_get_dot(grid *g, tree234 *dot_list, int x, int y)
855 * previously been added, with the required number of dots allocated) */ 884 * previously been added, with the required number of dots allocated) */
856static void grid_face_set_dot(grid *g, grid_dot *d, int position) 885static void grid_face_set_dot(grid *g, grid_dot *d, int position)
857{ 886{
858 grid_face *last_face = g->faces + g->num_faces - 1; 887 grid_face *last_face = g->faces[g->num_faces - 1];
859 last_face->dots[position] = d; 888 last_face->dots[position] = d;
860} 889}
861 890
@@ -1388,6 +1417,15 @@ void grid_find_incentre(grid_face *f)
1388 1417
1389#define SQUARE_TILESIZE 20 1418#define SQUARE_TILESIZE 20
1390 1419
1420static const char *grid_validate_params_square(int width, int height)
1421{
1422 if (width > INT_MAX / SQUARE_TILESIZE || /* xextent */
1423 height > INT_MAX / SQUARE_TILESIZE || /* yextent */
1424 width + 1 > INT_MAX / (height + 1)) /* max_dots */
1425 return "Grid size must not be unreasonably large";
1426 return NULL;
1427}
1428
1391static void grid_size_square(int width, int height, 1429static void grid_size_square(int width, int height,
1392 int *tilesize, int *xextent, int *yextent) 1430 int *tilesize, int *xextent, int *yextent)
1393{ 1431{
@@ -1404,16 +1442,10 @@ static grid *grid_new_square(int width, int height, const char *desc)
1404 /* Side length */ 1442 /* Side length */
1405 int a = SQUARE_TILESIZE; 1443 int a = SQUARE_TILESIZE;
1406 1444
1407 /* Upper bounds - don't have to be exact */
1408 int max_faces = width * height;
1409 int max_dots = (width + 1) * (height + 1);
1410
1411 tree234 *points; 1445 tree234 *points;
1412 1446
1413 grid *g = grid_empty(); 1447 grid *g = grid_empty();
1414 g->tilesize = a; 1448 g->tilesize = a;
1415 g->faces = snewn(max_faces, grid_face);
1416 g->dots = snewn(max_dots, grid_dot);
1417 1449
1418 points = newtree234(grid_point_cmp_fn); 1450 points = newtree234(grid_point_cmp_fn);
1419 1451
@@ -1438,8 +1470,6 @@ static grid *grid_new_square(int width, int height, const char *desc)
1438 } 1470 }
1439 1471
1440 freetree234(points); 1472 freetree234(points);
1441 assert(g->num_faces <= max_faces);
1442 assert(g->num_dots <= max_dots);
1443 1473
1444 grid_make_consistent(g); 1474 grid_make_consistent(g);
1445 return g; 1475 return g;
@@ -1450,6 +1480,18 @@ static grid *grid_new_square(int width, int height, const char *desc)
1450#define HONEY_A 15 1480#define HONEY_A 15
1451#define HONEY_B 26 1481#define HONEY_B 26
1452 1482
1483static const char *grid_validate_params_honeycomb(int width, int height)
1484{
1485 int a = HONEY_A;
1486 int b = HONEY_B;
1487
1488 if (width - 1 > (INT_MAX - 4*a) / (3 * a) || /* xextent */
1489 height - 1 > (INT_MAX - 3*b) / (2 * b) || /* yextent */
1490 width + 1 > INT_MAX / 2 / (height + 1)) /* max_dots */
1491 return "Grid size must not be unreasonably large";
1492 return NULL;
1493}
1494
1453static void grid_size_honeycomb(int width, int height, 1495static void grid_size_honeycomb(int width, int height,
1454 int *tilesize, int *xextent, int *yextent) 1496 int *tilesize, int *xextent, int *yextent)
1455{ 1497{
@@ -1467,16 +1509,10 @@ static grid *grid_new_honeycomb(int width, int height, const char *desc)
1467 int a = HONEY_A; 1509 int a = HONEY_A;
1468 int b = HONEY_B; 1510 int b = HONEY_B;
1469 1511
1470 /* Upper bounds - don't have to be exact */
1471 int max_faces = width * height;
1472 int max_dots = 2 * (width + 1) * (height + 1);
1473
1474 tree234 *points; 1512 tree234 *points;
1475 1513
1476 grid *g = grid_empty(); 1514 grid *g = grid_empty();
1477 g->tilesize = HONEY_TILESIZE; 1515 g->tilesize = HONEY_TILESIZE;
1478 g->faces = snewn(max_faces, grid_face);
1479 g->dots = snewn(max_dots, grid_dot);
1480 1516
1481 points = newtree234(grid_point_cmp_fn); 1517 points = newtree234(grid_point_cmp_fn);
1482 1518
@@ -1507,8 +1543,6 @@ static grid *grid_new_honeycomb(int width, int height, const char *desc)
1507 } 1543 }
1508 1544
1509 freetree234(points); 1545 freetree234(points);
1510 assert(g->num_faces <= max_faces);
1511 assert(g->num_dots <= max_dots);
1512 1546
1513 grid_make_consistent(g); 1547 grid_make_consistent(g);
1514 return g; 1548 return g;
@@ -1519,6 +1553,18 @@ static grid *grid_new_honeycomb(int width, int height, const char *desc)
1519#define TRIANGLE_VEC_X 15 1553#define TRIANGLE_VEC_X 15
1520#define TRIANGLE_VEC_Y 26 1554#define TRIANGLE_VEC_Y 26
1521 1555
1556static const char *grid_validate_params_triangular(int width, int height)
1557{
1558 int vec_x = TRIANGLE_VEC_X;
1559 int vec_y = TRIANGLE_VEC_Y;
1560
1561 if (width > INT_MAX / (2 * vec_x) - 1 || /* xextent */
1562 height > INT_MAX / vec_y || /* yextent */
1563 width + 1 > INT_MAX / 4 / (height + 1)) /* max_dots */
1564 return "Grid size must not be unreasonably large";
1565 return NULL;
1566}
1567
1522static void grid_size_triangular(int width, int height, 1568static void grid_size_triangular(int width, int height,
1523 int *tilesize, int *xextent, int *yextent) 1569 int *tilesize, int *xextent, int *yextent)
1524{ 1570{
@@ -1582,16 +1628,18 @@ static grid *grid_new_triangular(int width, int height, const char *desc)
1582 * 5x6t1:a022a212h1a1d1a12c2b11a012b1a20d1a0a12e 1628 * 5x6t1:a022a212h1a1d1a12c2b11a012b1a20d1a0a12e
1583 */ 1629 */
1584 1630
1585 g->num_faces = width * height * 2; 1631 g->num_faces = g->size_faces = width * height * 2;
1586 g->num_dots = (width + 1) * (height + 1); 1632 g->num_dots = g->size_dots = (width + 1) * (height + 1);
1587 g->faces = snewn(g->num_faces, grid_face); 1633 g->faces = snewn(g->size_faces, grid_face *);
1588 g->dots = snewn(g->num_dots, grid_dot); 1634 g->dots = snewn(g->size_dots, grid_dot *);
1589 1635
1590 /* generate dots */ 1636 /* generate dots */
1591 index = 0; 1637 index = 0;
1592 for (y = 0; y <= height; y++) { 1638 for (y = 0; y <= height; y++) {
1593 for (x = 0; x <= width; x++) { 1639 for (x = 0; x <= width; x++) {
1594 grid_dot *d = g->dots + index; 1640 grid_dot *d = snew(grid_dot);
1641 d->index = index;
1642 g->dots[d->index] = d;
1595 /* odd rows are offset to the right */ 1643 /* odd rows are offset to the right */
1596 d->order = 0; 1644 d->order = 0;
1597 d->edges = NULL; 1645 d->edges = NULL;
@@ -1607,8 +1655,11 @@ static grid *grid_new_triangular(int width, int height, const char *desc)
1607 for (y = 0; y < height; y++) { 1655 for (y = 0; y < height; y++) {
1608 for (x = 0; x < width; x++) { 1656 for (x = 0; x < width; x++) {
1609 /* initialise two faces for this (x,y) */ 1657 /* initialise two faces for this (x,y) */
1610 grid_face *f1 = g->faces + index; 1658 grid_face *f1 = snew(grid_face), *f2 = snew(grid_face);
1611 grid_face *f2 = f1 + 1; 1659 f1->index = index;
1660 f2->index = index + 1;
1661 g->faces[f1->index] = f1;
1662 g->faces[f2->index] = f2;
1612 f1->edges = NULL; 1663 f1->edges = NULL;
1613 f1->order = 3; 1664 f1->order = 3;
1614 f1->dots = snewn(f1->order, grid_dot*); 1665 f1->dots = snewn(f1->order, grid_dot*);
@@ -1621,19 +1672,19 @@ static grid *grid_new_triangular(int width, int height, const char *desc)
1621 /* face descriptions depend on whether the row-number is 1672 /* face descriptions depend on whether the row-number is
1622 * odd or even */ 1673 * odd or even */
1623 if (y % 2) { 1674 if (y % 2) {
1624 f1->dots[0] = g->dots + y * w + x; 1675 f1->dots[0] = g->dots[y * w + x];
1625 f1->dots[1] = g->dots + (y + 1) * w + x + 1; 1676 f1->dots[1] = g->dots[(y + 1) * w + x + 1];
1626 f1->dots[2] = g->dots + (y + 1) * w + x; 1677 f1->dots[2] = g->dots[(y + 1) * w + x];
1627 f2->dots[0] = g->dots + y * w + x; 1678 f2->dots[0] = g->dots[y * w + x];
1628 f2->dots[1] = g->dots + y * w + x + 1; 1679 f2->dots[1] = g->dots[y * w + x + 1];
1629 f2->dots[2] = g->dots + (y + 1) * w + x + 1; 1680 f2->dots[2] = g->dots[(y + 1) * w + x + 1];
1630 } else { 1681 } else {
1631 f1->dots[0] = g->dots + y * w + x; 1682 f1->dots[0] = g->dots[y * w + x];
1632 f1->dots[1] = g->dots + y * w + x + 1; 1683 f1->dots[1] = g->dots[y * w + x + 1];
1633 f1->dots[2] = g->dots + (y + 1) * w + x; 1684 f1->dots[2] = g->dots[(y + 1) * w + x];
1634 f2->dots[0] = g->dots + y * w + x + 1; 1685 f2->dots[0] = g->dots[y * w + x + 1];
1635 f2->dots[1] = g->dots + (y + 1) * w + x + 1; 1686 f2->dots[1] = g->dots[(y + 1) * w + x + 1];
1636 f2->dots[2] = g->dots + (y + 1) * w + x; 1687 f2->dots[2] = g->dots[(y + 1) * w + x];
1637 } 1688 }
1638 index += 2; 1689 index += 2;
1639 } 1690 }
@@ -1650,12 +1701,6 @@ static grid *grid_new_triangular(int width, int height, const char *desc)
1650 * 5x6t1:0_a1212c22c2a02a2f22a0c12a110d0e1c0c0a101121a1 1701 * 5x6t1:0_a1212c22c2a02a2f22a0c12a110d0e1c0c0a101121a1
1651 */ 1702 */
1652 tree234 *points = newtree234(grid_point_cmp_fn); 1703 tree234 *points = newtree234(grid_point_cmp_fn);
1653 /* Upper bounds - don't have to be exact */
1654 int max_faces = height * (2*width+1);
1655 int max_dots = (height+1) * (width+1) * 4;
1656
1657 g->faces = snewn(max_faces, grid_face);
1658 g->dots = snewn(max_dots, grid_dot);
1659 1704
1660 for (y = 0; y < height; y++) { 1705 for (y = 0; y < height; y++) {
1661 /* 1706 /*
@@ -1703,8 +1748,6 @@ static grid *grid_new_triangular(int width, int height, const char *desc)
1703 } 1748 }
1704 1749
1705 freetree234(points); 1750 freetree234(points);
1706 assert(g->num_faces <= max_faces);
1707 assert(g->num_dots <= max_dots);
1708 } 1751 }
1709 1752
1710 grid_make_consistent(g); 1753 grid_make_consistent(g);
@@ -1716,6 +1759,19 @@ static grid *grid_new_triangular(int width, int height, const char *desc)
1716#define SNUBSQUARE_A 15 1759#define SNUBSQUARE_A 15
1717#define SNUBSQUARE_B 26 1760#define SNUBSQUARE_B 26
1718 1761
1762static const char *grid_validate_params_snubsquare(int width, int height)
1763{
1764 int a = SNUBSQUARE_A;
1765 int b = SNUBSQUARE_B;
1766
1767 if (width-1 > (INT_MAX - (a + b)) / (a+b) || /* xextent */
1768 height > (INT_MAX - (a + b)) / (a+b) || /* yextent */
1769 width > INT_MAX / 3 / height || /* max_faces */
1770 width + 1 > INT_MAX / 2 / (height + 1)) /* max_dots */
1771 return "Grid size must not be unreasonably large";
1772 return NULL;
1773}
1774
1719static void grid_size_snubsquare(int width, int height, 1775static void grid_size_snubsquare(int width, int height,
1720 int *tilesize, int *xextent, int *yextent) 1776 int *tilesize, int *xextent, int *yextent)
1721{ 1777{
@@ -1733,16 +1789,10 @@ static grid *grid_new_snubsquare(int width, int height, const char *desc)
1733 int a = SNUBSQUARE_A; 1789 int a = SNUBSQUARE_A;
1734 int b = SNUBSQUARE_B; 1790 int b = SNUBSQUARE_B;
1735 1791
1736 /* Upper bounds - don't have to be exact */
1737 int max_faces = 3 * width * height;
1738 int max_dots = 2 * (width + 1) * (height + 1);
1739
1740 tree234 *points; 1792 tree234 *points;
1741 1793
1742 grid *g = grid_empty(); 1794 grid *g = grid_empty();
1743 g->tilesize = SNUBSQUARE_TILESIZE; 1795 g->tilesize = SNUBSQUARE_TILESIZE;
1744 g->faces = snewn(max_faces, grid_face);
1745 g->dots = snewn(max_dots, grid_dot);
1746 1796
1747 points = newtree234(grid_point_cmp_fn); 1797 points = newtree234(grid_point_cmp_fn);
1748 1798
@@ -1818,8 +1868,6 @@ static grid *grid_new_snubsquare(int width, int height, const char *desc)
1818 } 1868 }
1819 1869
1820 freetree234(points); 1870 freetree234(points);
1821 assert(g->num_faces <= max_faces);
1822 assert(g->num_dots <= max_dots);
1823 1871
1824 grid_make_consistent(g); 1872 grid_make_consistent(g);
1825 return g; 1873 return g;
@@ -1830,6 +1878,18 @@ static grid *grid_new_snubsquare(int width, int height, const char *desc)
1830#define CAIRO_A 14 1878#define CAIRO_A 14
1831#define CAIRO_B 31 1879#define CAIRO_B 31
1832 1880
1881static const char *grid_validate_params_cairo(int width, int height)
1882{
1883 int b = CAIRO_B; /* a unused in determining grid size. */
1884
1885 if (width - 1 > (INT_MAX - 2*b) / (2*b) || /* xextent */
1886 height - 1 > (INT_MAX - 2*b) / (2*b) || /* yextent */
1887 width > INT_MAX / 2 / height || /* max_faces */
1888 width + 1 > INT_MAX / 3 / (height + 1)) /* max_dots */
1889 return "Grid size must not be unreasonably large";
1890 return NULL;
1891}
1892
1833static void grid_size_cairo(int width, int height, 1893static void grid_size_cairo(int width, int height,
1834 int *tilesize, int *xextent, int *yextent) 1894 int *tilesize, int *xextent, int *yextent)
1835{ 1895{
@@ -1846,16 +1906,10 @@ static grid *grid_new_cairo(int width, int height, const char *desc)
1846 int a = CAIRO_A; 1906 int a = CAIRO_A;
1847 int b = CAIRO_B; 1907 int b = CAIRO_B;
1848 1908
1849 /* Upper bounds - don't have to be exact */
1850 int max_faces = 2 * width * height;
1851 int max_dots = 3 * (width + 1) * (height + 1);
1852
1853 tree234 *points; 1909 tree234 *points;
1854 1910
1855 grid *g = grid_empty(); 1911 grid *g = grid_empty();
1856 g->tilesize = CAIRO_TILESIZE; 1912 g->tilesize = CAIRO_TILESIZE;
1857 g->faces = snewn(max_faces, grid_face);
1858 g->dots = snewn(max_dots, grid_dot);
1859 1913
1860 points = newtree234(grid_point_cmp_fn); 1914 points = newtree234(grid_point_cmp_fn);
1861 1915
@@ -1924,8 +1978,6 @@ static grid *grid_new_cairo(int width, int height, const char *desc)
1924 } 1978 }
1925 1979
1926 freetree234(points); 1980 freetree234(points);
1927 assert(g->num_faces <= max_faces);
1928 assert(g->num_dots <= max_dots);
1929 1981
1930 grid_make_consistent(g); 1982 grid_make_consistent(g);
1931 return g; 1983 return g;
@@ -1936,6 +1988,18 @@ static grid *grid_new_cairo(int width, int height, const char *desc)
1936#define GREATHEX_A 15 1988#define GREATHEX_A 15
1937#define GREATHEX_B 26 1989#define GREATHEX_B 26
1938 1990
1991static const char *grid_validate_params_greathexagonal(int width, int height)
1992{
1993 int a = GREATHEX_A;
1994 int b = GREATHEX_B;
1995
1996 if (width-1 > (INT_MAX - 4*a) / (3*a + b) || /* xextent */
1997 height-1 > (INT_MAX - (3*b + a)) / (2*a + 2*b) || /* yextent */
1998 width + 1 > INT_MAX / 6 / (height + 1)) /* max_faces */
1999 return "Grid size must not be unreasonably large";
2000 return NULL;
2001}
2002
1939static void grid_size_greathexagonal(int width, int height, 2003static void grid_size_greathexagonal(int width, int height,
1940 int *tilesize, int *xextent, int *yextent) 2004 int *tilesize, int *xextent, int *yextent)
1941{ 2005{
@@ -1953,16 +2017,10 @@ static grid *grid_new_greathexagonal(int width, int height, const char *desc)
1953 int a = GREATHEX_A; 2017 int a = GREATHEX_A;
1954 int b = GREATHEX_B; 2018 int b = GREATHEX_B;
1955 2019
1956 /* Upper bounds - don't have to be exact */
1957 int max_faces = 6 * (width + 1) * (height + 1);
1958 int max_dots = 6 * width * height;
1959
1960 tree234 *points; 2020 tree234 *points;
1961 2021
1962 grid *g = grid_empty(); 2022 grid *g = grid_empty();
1963 g->tilesize = GREATHEX_TILESIZE; 2023 g->tilesize = GREATHEX_TILESIZE;
1964 g->faces = snewn(max_faces, grid_face);
1965 g->dots = snewn(max_dots, grid_dot);
1966 2024
1967 points = newtree234(grid_point_cmp_fn); 2025 points = newtree234(grid_point_cmp_fn);
1968 2026
@@ -2054,8 +2112,6 @@ static grid *grid_new_greathexagonal(int width, int height, const char *desc)
2054 } 2112 }
2055 2113
2056 freetree234(points); 2114 freetree234(points);
2057 assert(g->num_faces <= max_faces);
2058 assert(g->num_dots <= max_dots);
2059 2115
2060 grid_make_consistent(g); 2116 grid_make_consistent(g);
2061 return g; 2117 return g;
@@ -2066,6 +2122,18 @@ static grid *grid_new_greathexagonal(int width, int height, const char *desc)
2066#define KAGOME_A 15 2122#define KAGOME_A 15
2067#define KAGOME_B 26 2123#define KAGOME_B 26
2068 2124
2125static const char *grid_validate_params_kagome(int width, int height)
2126{
2127 int a = KAGOME_A;
2128 int b = KAGOME_B;
2129
2130 if (width-1 > (INT_MAX - 6*a) / (4*a) || /* xextent */
2131 height-1 > (INT_MAX - 2*b) / (2*b) || /* yextent */
2132 width + 1 > INT_MAX / 6 / (height + 1)) /* max_faces */
2133 return "Grid size must not be unreasonably large";
2134 return NULL;
2135}
2136
2069static void grid_size_kagome(int width, int height, 2137static void grid_size_kagome(int width, int height,
2070 int *tilesize, int *xextent, int *yextent) 2138 int *tilesize, int *xextent, int *yextent)
2071{ 2139{
@@ -2083,16 +2151,10 @@ static grid *grid_new_kagome(int width, int height, const char *desc)
2083 int a = KAGOME_A; 2151 int a = KAGOME_A;
2084 int b = KAGOME_B; 2152 int b = KAGOME_B;
2085 2153
2086 /* Upper bounds - don't have to be exact */
2087 int max_faces = 6 * (width + 1) * (height + 1);
2088 int max_dots = 6 * width * height;
2089
2090 tree234 *points; 2154 tree234 *points;
2091 2155
2092 grid *g = grid_empty(); 2156 grid *g = grid_empty();
2093 g->tilesize = KAGOME_TILESIZE; 2157 g->tilesize = KAGOME_TILESIZE;
2094 g->faces = snewn(max_faces, grid_face);
2095 g->dots = snewn(max_dots, grid_dot);
2096 2158
2097 points = newtree234(grid_point_cmp_fn); 2159 points = newtree234(grid_point_cmp_fn);
2098 2160
@@ -2150,8 +2212,6 @@ static grid *grid_new_kagome(int width, int height, const char *desc)
2150 } 2212 }
2151 2213
2152 freetree234(points); 2214 freetree234(points);
2153 assert(g->num_faces <= max_faces);
2154 assert(g->num_dots <= max_dots);
2155 2215
2156 grid_make_consistent(g); 2216 grid_make_consistent(g);
2157 return g; 2217 return g;
@@ -2162,6 +2222,18 @@ static grid *grid_new_kagome(int width, int height, const char *desc)
2162#define OCTAGONAL_A 29 2222#define OCTAGONAL_A 29
2163#define OCTAGONAL_B 41 2223#define OCTAGONAL_B 41
2164 2224
2225static const char *grid_validate_params_octagonal(int width, int height)
2226{
2227 int a = OCTAGONAL_A;
2228 int b = OCTAGONAL_B;
2229
2230 if (width > INT_MAX / (2*a + b) || /* xextent */
2231 height > INT_MAX / (2*a + b) || /* yextent */
2232 height + 1 > INT_MAX / 4 / (width + 1)) /* max_dots */
2233 return "Grid size must not be unreasonably large";
2234 return NULL;
2235}
2236
2165static void grid_size_octagonal(int width, int height, 2237static void grid_size_octagonal(int width, int height,
2166 int *tilesize, int *xextent, int *yextent) 2238 int *tilesize, int *xextent, int *yextent)
2167{ 2239{
@@ -2179,16 +2251,10 @@ static grid *grid_new_octagonal(int width, int height, const char *desc)
2179 int a = OCTAGONAL_A; 2251 int a = OCTAGONAL_A;
2180 int b = OCTAGONAL_B; 2252 int b = OCTAGONAL_B;
2181 2253
2182 /* Upper bounds - don't have to be exact */
2183 int max_faces = 2 * width * height;
2184 int max_dots = 4 * (width + 1) * (height + 1);
2185
2186 tree234 *points; 2254 tree234 *points;
2187 2255
2188 grid *g = grid_empty(); 2256 grid *g = grid_empty();
2189 g->tilesize = OCTAGONAL_TILESIZE; 2257 g->tilesize = OCTAGONAL_TILESIZE;
2190 g->faces = snewn(max_faces, grid_face);
2191 g->dots = snewn(max_dots, grid_dot);
2192 2258
2193 points = newtree234(grid_point_cmp_fn); 2259 points = newtree234(grid_point_cmp_fn);
2194 2260
@@ -2233,8 +2299,6 @@ static grid *grid_new_octagonal(int width, int height, const char *desc)
2233 } 2299 }
2234 2300
2235 freetree234(points); 2301 freetree234(points);
2236 assert(g->num_faces <= max_faces);
2237 assert(g->num_dots <= max_dots);
2238 2302
2239 grid_make_consistent(g); 2303 grid_make_consistent(g);
2240 return g; 2304 return g;
@@ -2245,6 +2309,18 @@ static grid *grid_new_octagonal(int width, int height, const char *desc)
2245#define KITE_A 15 2309#define KITE_A 15
2246#define KITE_B 26 2310#define KITE_B 26
2247 2311
2312static const char *grid_validate_params_kites(int width, int height)
2313{
2314 int a = KITE_A;
2315 int b = KITE_B;
2316
2317 if (width > (INT_MAX - 2*b) / (4*b) || /* xextent */
2318 height - 1 > (INT_MAX - 8*a) / (6*a) || /* yextent */
2319 width + 1 > INT_MAX / 6 / (height + 1)) /* max_dots */
2320 return "Grid size must not be unreasonably large";
2321 return NULL;
2322}
2323
2248static void grid_size_kites(int width, int height, 2324static void grid_size_kites(int width, int height,
2249 int *tilesize, int *xextent, int *yextent) 2325 int *tilesize, int *xextent, int *yextent)
2250{ 2326{
@@ -2262,16 +2338,10 @@ static grid *grid_new_kites(int width, int height, const char *desc)
2262 int a = KITE_A; 2338 int a = KITE_A;
2263 int b = KITE_B; 2339 int b = KITE_B;
2264 2340
2265 /* Upper bounds - don't have to be exact */
2266 int max_faces = 6 * width * height;
2267 int max_dots = 6 * (width + 1) * (height + 1);
2268
2269 tree234 *points; 2341 tree234 *points;
2270 2342
2271 grid *g = grid_empty(); 2343 grid *g = grid_empty();
2272 g->tilesize = KITE_TILESIZE; 2344 g->tilesize = KITE_TILESIZE;
2273 g->faces = snewn(max_faces, grid_face);
2274 g->dots = snewn(max_dots, grid_dot);
2275 2345
2276 points = newtree234(grid_point_cmp_fn); 2346 points = newtree234(grid_point_cmp_fn);
2277 2347
@@ -2353,8 +2423,6 @@ static grid *grid_new_kites(int width, int height, const char *desc)
2353 } 2423 }
2354 2424
2355 freetree234(points); 2425 freetree234(points);
2356 assert(g->num_faces <= max_faces);
2357 assert(g->num_dots <= max_dots);
2358 2426
2359 grid_make_consistent(g); 2427 grid_make_consistent(g);
2360 return g; 2428 return g;
@@ -2367,6 +2435,20 @@ static grid *grid_new_kites(int width, int height, const char *desc)
2367#define FLORET_PX 75 2435#define FLORET_PX 75
2368#define FLORET_PY -26 2436#define FLORET_PY -26
2369 2437
2438static const char *grid_validate_params_floret(int width, int height)
2439{
2440 int px = FLORET_PX, py = FLORET_PY; /* |( 75, -26)| = 79.43 */
2441 int qx = 4*px/5, qy = -py*2; /* |( 60, 52)| = 79.40 */
2442 int ry = qy-py;
2443 /* rx unused in determining grid size. */
2444
2445 if (width - 1 > (INT_MAX - (4*qx + 2*px)) / ((6*px+3*qx)/2) ||/* xextent */
2446 height - 1 > (INT_MAX - (4*qy + 2*ry)) / (5*qy-4*py) || /* yextent */
2447 width + 1 > INT_MAX / 9 / (height + 1)) /* max_dots */
2448 return "Grid size must not be unreasonably large";
2449 return NULL;
2450}
2451
2370static void grid_size_floret(int width, int height, 2452static void grid_size_floret(int width, int height,
2371 int *tilesize, int *xextent, int *yextent) 2453 int *tilesize, int *xextent, int *yextent)
2372{ 2454{
@@ -2393,16 +2475,10 @@ static grid *grid_new_floret(int width, int height, const char *desc)
2393 int qx = 4*px/5, qy = -py*2; /* |( 60, 52)| = 79.40 */ 2475 int qx = 4*px/5, qy = -py*2; /* |( 60, 52)| = 79.40 */
2394 int rx = qx-px, ry = qy-py; /* |(-15, 78)| = 79.38 */ 2476 int rx = qx-px, ry = qy-py; /* |(-15, 78)| = 79.38 */
2395 2477
2396 /* Upper bounds - don't have to be exact */
2397 int max_faces = 6 * width * height;
2398 int max_dots = 9 * (width + 1) * (height + 1);
2399
2400 tree234 *points; 2478 tree234 *points;
2401 2479
2402 grid *g = grid_empty(); 2480 grid *g = grid_empty();
2403 g->tilesize = FLORET_TILESIZE; 2481 g->tilesize = FLORET_TILESIZE;
2404 g->faces = snewn(max_faces, grid_face);
2405 g->dots = snewn(max_dots, grid_dot);
2406 2482
2407 points = newtree234(grid_point_cmp_fn); 2483 points = newtree234(grid_point_cmp_fn);
2408 2484
@@ -2463,8 +2539,6 @@ static grid *grid_new_floret(int width, int height, const char *desc)
2463 } 2539 }
2464 2540
2465 freetree234(points); 2541 freetree234(points);
2466 assert(g->num_faces <= max_faces);
2467 assert(g->num_dots <= max_dots);
2468 2542
2469 grid_make_consistent(g); 2543 grid_make_consistent(g);
2470 return g; 2544 return g;
@@ -2476,6 +2550,18 @@ static grid *grid_new_floret(int width, int height, const char *desc)
2476#define DODEC_A 15 2550#define DODEC_A 15
2477#define DODEC_B 26 2551#define DODEC_B 26
2478 2552
2553static const char *grid_validate_params_dodecagonal(int width, int height)
2554{
2555 int a = DODEC_A;
2556 int b = DODEC_B;
2557
2558 if (width - 1 > (INT_MAX - 3*(2*a + b)) / (4*a + 2*b) || /* xextent */
2559 height - 1 > (INT_MAX - 2*(2*a + b)) / (3*a + 2*b) || /* yextent */
2560 width > INT_MAX / 14 / height) /* max_dots */
2561 return "Grid size must not be unreasonably large";
2562 return NULL;
2563}
2564
2479static void grid_size_dodecagonal(int width, int height, 2565static void grid_size_dodecagonal(int width, int height,
2480 int *tilesize, int *xextent, int *yextent) 2566 int *tilesize, int *xextent, int *yextent)
2481{ 2567{
@@ -2493,16 +2579,10 @@ static grid *grid_new_dodecagonal(int width, int height, const char *desc)
2493 int a = DODEC_A; 2579 int a = DODEC_A;
2494 int b = DODEC_B; 2580 int b = DODEC_B;
2495 2581
2496 /* Upper bounds - don't have to be exact */
2497 int max_faces = 3 * width * height;
2498 int max_dots = 14 * width * height;
2499
2500 tree234 *points; 2582 tree234 *points;
2501 2583
2502 grid *g = grid_empty(); 2584 grid *g = grid_empty();
2503 g->tilesize = DODEC_TILESIZE; 2585 g->tilesize = DODEC_TILESIZE;
2504 g->faces = snewn(max_faces, grid_face);
2505 g->dots = snewn(max_dots, grid_dot);
2506 2586
2507 points = newtree234(grid_point_cmp_fn); 2587 points = newtree234(grid_point_cmp_fn);
2508 2588
@@ -2549,13 +2629,23 @@ static grid *grid_new_dodecagonal(int width, int height, const char *desc)
2549 } 2629 }
2550 2630
2551 freetree234(points); 2631 freetree234(points);
2552 assert(g->num_faces <= max_faces);
2553 assert(g->num_dots <= max_dots);
2554 2632
2555 grid_make_consistent(g); 2633 grid_make_consistent(g);
2556 return g; 2634 return g;
2557} 2635}
2558 2636
2637static const char *grid_validate_params_greatdodecagonal(int width, int height)
2638{
2639 int a = DODEC_A;
2640 int b = DODEC_B;
2641
2642 if (width - 1 > (INT_MAX - (2*(2*a + b) + 3*a + b)) / (6*a + 2*b) ||
2643 height - 1 > (INT_MAX - 2*(2*a + b)) / (3*a + 3*b) || /* yextent */
2644 width > INT_MAX / 200 / height) /* max_dots */
2645 return "Grid size must not be unreasonably large";
2646 return NULL;
2647}
2648
2559static void grid_size_greatdodecagonal(int width, int height, 2649static void grid_size_greatdodecagonal(int width, int height,
2560 int *tilesize, int *xextent, int *yextent) 2650 int *tilesize, int *xextent, int *yextent)
2561{ 2651{
@@ -2574,16 +2664,10 @@ static grid *grid_new_greatdodecagonal(int width, int height, const char *desc)
2574 int a = DODEC_A; 2664 int a = DODEC_A;
2575 int b = DODEC_B; 2665 int b = DODEC_B;
2576 2666
2577 /* Upper bounds - don't have to be exact */
2578 int max_faces = 30 * width * height;
2579 int max_dots = 200 * width * height;
2580
2581 tree234 *points; 2667 tree234 *points;
2582 2668
2583 grid *g = grid_empty(); 2669 grid *g = grid_empty();
2584 g->tilesize = DODEC_TILESIZE; 2670 g->tilesize = DODEC_TILESIZE;
2585 g->faces = snewn(max_faces, grid_face);
2586 g->dots = snewn(max_dots, grid_dot);
2587 2671
2588 points = newtree234(grid_point_cmp_fn); 2672 points = newtree234(grid_point_cmp_fn);
2589 2673
@@ -2663,13 +2747,24 @@ static grid *grid_new_greatdodecagonal(int width, int height, const char *desc)
2663 } 2747 }
2664 2748
2665 freetree234(points); 2749 freetree234(points);
2666 assert(g->num_faces <= max_faces);
2667 assert(g->num_dots <= max_dots);
2668 2750
2669 grid_make_consistent(g); 2751 grid_make_consistent(g);
2670 return g; 2752 return g;
2671} 2753}
2672 2754
2755static const char *grid_validate_params_greatgreatdodecagonal(
2756 int width, int height)
2757{
2758 int a = DODEC_A;
2759 int b = DODEC_B;
2760
2761 if (width-1 > (INT_MAX - (2*(2*a + b) + 2*a + 2*b)) / (4*a + 4*b) ||
2762 height-1 > (INT_MAX - 2*(2*a + b)) / (6*a + 2*b) || /* yextent */
2763 width > INT_MAX / 300 / height) /* max_dots */
2764 return "Grid size must not be unreasonably large";
2765 return NULL;
2766}
2767
2673static void grid_size_greatgreatdodecagonal(int width, int height, 2768static void grid_size_greatgreatdodecagonal(int width, int height,
2674 int *tilesize, int *xextent, int *yextent) 2769 int *tilesize, int *xextent, int *yextent)
2675{ 2770{
@@ -2688,16 +2783,10 @@ static grid *grid_new_greatgreatdodecagonal(int width, int height, const char *d
2688 int a = DODEC_A; 2783 int a = DODEC_A;
2689 int b = DODEC_B; 2784 int b = DODEC_B;
2690 2785
2691 /* Upper bounds - don't have to be exact */
2692 int max_faces = 50 * width * height;
2693 int max_dots = 300 * width * height;
2694
2695 tree234 *points; 2786 tree234 *points;
2696 2787
2697 grid *g = grid_empty(); 2788 grid *g = grid_empty();
2698 g->tilesize = DODEC_TILESIZE; 2789 g->tilesize = DODEC_TILESIZE;
2699 g->faces = snewn(max_faces, grid_face);
2700 g->dots = snewn(max_dots, grid_dot);
2701 2790
2702 points = newtree234(grid_point_cmp_fn); 2791 points = newtree234(grid_point_cmp_fn);
2703 2792
@@ -2747,7 +2836,7 @@ static grid *grid_new_greatgreatdodecagonal(int width, int height, const char *d
2747 d = grid_get_dot(g, points, px + (2*a + 2*b), py - 2*a); grid_face_set_dot(g, d, 5); 2836 d = grid_get_dot(g, points, px + (2*a + 2*b), py - 2*a); grid_face_set_dot(g, d, 5);
2748 } 2837 }
2749 2838
2750 /* hexagon on bottom right of dodecagon */ 2839 /* hexagon on bottom right of dodecagon */
2751 if ((y < height - 1) && (x < width - 1 || !(y % 2))) { 2840 if ((y < height - 1) && (x < width - 1 || !(y % 2))) {
2752 grid_face_add_new(g, 6); 2841 grid_face_add_new(g, 6);
2753 d = grid_get_dot(g, points, px + (a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 0); 2842 d = grid_get_dot(g, points, px + (a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 0);
@@ -2832,29 +2921,165 @@ static grid *grid_new_greatgreatdodecagonal(int width, int height, const char *d
2832 } 2921 }
2833 2922
2834 freetree234(points); 2923 freetree234(points);
2835 assert(g->num_faces <= max_faces);
2836 assert(g->num_dots <= max_dots);
2837 2924
2838 grid_make_consistent(g); 2925 grid_make_consistent(g);
2839 return g; 2926 return g;
2840} 2927}
2841 2928
2842typedef struct setface_ctx 2929static const char *grid_validate_params_compassdodecagonal(
2930 int width, int height)
2931{
2932 int a = DODEC_A;
2933 int b = DODEC_B;
2934
2935 if (width > INT_MAX / (4*a + 2*b) || /* xextent */
2936 height > INT_MAX / (4*a + 2*b) || /* yextent */
2937 width > INT_MAX / 18 / height) /* max_dots */
2938 return "Grid must not be unreasonably large";
2939 return NULL;
2940}
2941
2942static void grid_size_compassdodecagonal(int width, int height,
2943 int *tilesize, int *xextent, int *yextent)
2944{
2945 int a = DODEC_A;
2946 int b = DODEC_B;
2947
2948 *tilesize = DODEC_TILESIZE;
2949 *xextent = (4*a + 2*b) * width;
2950 *yextent = (4*a + 2*b) * height;
2951}
2952
2953static grid *grid_new_compassdodecagonal(int width, int height, const char *desc)
2843{ 2954{
2955 int x, y;
2956 /* Vector for side of triangle - ratio is close to sqrt(3) */
2957 int a = DODEC_A;
2958 int b = DODEC_B;
2959
2960 tree234 *points;
2961
2962 grid *g = grid_empty();
2963 g->tilesize = DODEC_TILESIZE;
2964
2965 points = newtree234(grid_point_cmp_fn);
2966
2967 for (y = 0; y < height; y++) {
2968 for (x = 0; x < width; x++) {
2969 grid_dot *d;
2970 /* centre of dodecagon */
2971 int px = (4*a + 2*b) * x;
2972 int py = (4*a + 2*b) * y;
2973
2974 /* dodecagon */
2975 grid_face_add_new(g, 12);
2976 d = grid_get_dot(g, points, px + ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 0);
2977 d = grid_get_dot(g, points, px + ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 1);
2978 d = grid_get_dot(g, points, px + (2*a + b), py - ( a )); grid_face_set_dot(g, d, 2);
2979 d = grid_get_dot(g, points, px + (2*a + b), py + ( a )); grid_face_set_dot(g, d, 3);
2980 d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 4);
2981 d = grid_get_dot(g, points, px + ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 5);
2982 d = grid_get_dot(g, points, px - ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 6);
2983 d = grid_get_dot(g, points, px - ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 7);
2984 d = grid_get_dot(g, points, px - (2*a + b), py + ( a )); grid_face_set_dot(g, d, 8);
2985 d = grid_get_dot(g, points, px - (2*a + b), py - ( a )); grid_face_set_dot(g, d, 9);
2986 d = grid_get_dot(g, points, px - ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 10);
2987 d = grid_get_dot(g, points, px - ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 11);
2988
2989 if (x < width - 1 && y < height - 1) {
2990 /* north triangle */
2991 grid_face_add_new(g, 3);
2992 d = grid_get_dot(g, points, px + (2*a + b), py + ( a )); grid_face_set_dot(g, d, 0);
2993 d = grid_get_dot(g, points, px + (3*a + b), py + ( a + b)); grid_face_set_dot(g, d, 1);
2994 d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 2);
2995
2996 /* east triangle */
2997 grid_face_add_new(g, 3);
2998 d = grid_get_dot(g, points, px + (3*a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 0);
2999 d = grid_get_dot(g, points, px + (3*a + b), py + (3*a + b)); grid_face_set_dot(g, d, 1);
3000 d = grid_get_dot(g, points, px + (3*a + b), py + ( a + b)); grid_face_set_dot(g, d, 2);
3001
3002 /* south triangle */
3003 grid_face_add_new(g, 3);
3004 d = grid_get_dot(g, points, px + (3*a + b), py + (3*a + b)); grid_face_set_dot(g, d, 0);
3005 d = grid_get_dot(g, points, px + (2*a + b), py + (3*a + 2*b)); grid_face_set_dot(g, d, 1);
3006 d = grid_get_dot(g, points, px + ( a + b), py + (3*a + b)); grid_face_set_dot(g, d, 2);
3007
3008 /* west triangle */
3009 grid_face_add_new(g, 3);
3010 d = grid_get_dot(g, points, px + (a + b), py + ( a + b)); grid_face_set_dot(g, d, 0);
3011 d = grid_get_dot(g, points, px + (a + b), py + (3*a + b)); grid_face_set_dot(g, d, 1);
3012 d = grid_get_dot(g, points, px + (a ), py + (2*a + b)); grid_face_set_dot(g, d, 2);
3013
3014 /* square in center */
3015 grid_face_add_new(g, 4);
3016 d = grid_get_dot(g, points, px + (3*a + b), py + ( a + b)); grid_face_set_dot(g, d, 0);
3017 d = grid_get_dot(g, points, px + (3*a + b), py + (3*a + b)); grid_face_set_dot(g, d, 1);
3018 d = grid_get_dot(g, points, px + ( a + b), py + (3*a + b)); grid_face_set_dot(g, d, 2);
3019 d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 3);
3020 }
3021 }
3022 }
3023
3024 freetree234(points);
3025
3026 grid_make_consistent(g);
3027 return g;
3028}
3029
3030/*
3031 * Penrose tilings. For historical reasons, we support two totally
3032 * different generation algorithms: the legacy one is only supported
3033 * by grid_new_penrose, for backwards compatibility with game
3034 * descriptions generated before we switched. New grid generation uses
3035 * only the new system.
3036 */
3037
3038#define PENROSE_TILESIZE 100
3039
3040static const char *grid_validate_params_penrose(int width, int height)
3041{
3042 int l = PENROSE_TILESIZE;
3043
3044 if (width > INT_MAX / l || /* xextent */
3045 height > INT_MAX / l || /* yextent */
3046 width > INT_MAX / (3 * 3 * 4 * height)) /* max_dots */
3047 return "Grid must not be unreasonably large";
3048 return NULL;
3049}
3050
3051static void grid_size_penrose(int width, int height,
3052 int *tilesize, int *xextent, int *yextent)
3053{
3054 int l = PENROSE_TILESIZE;
3055
3056 *tilesize = l;
3057 *xextent = l * width;
3058 *yextent = l * height;
3059}
3060
3061/*
3062 * Legacy generation by selecting a patch of tiling from the expansion
3063 * of a big triangle.
3064 */
3065
3066typedef struct penrose_legacy_set_faces_ctx {
2844 int xmin, xmax, ymin, ymax; 3067 int xmin, xmax, ymin, ymax;
2845 3068
2846 grid *g; 3069 grid *g;
2847 tree234 *points; 3070 tree234 *points;
2848} setface_ctx; 3071} penrose_legacy_set_faces_ctx;
2849 3072
2850static double round_int_nearest_away(double r) 3073static double round_int_nearest_away(double r)
2851{ 3074{
2852 return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5); 3075 return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5);
2853} 3076}
2854 3077
2855static int set_faces(penrose_state *state, vector *vs, int n, int depth) 3078static int penrose_legacy_set_faces(penrose_legacy_state *state, vector *vs,
3079 int n, int depth)
2856{ 3080{
2857 setface_ctx *sf_ctx = (setface_ctx *)state->ctx; 3081 penrose_legacy_set_faces_ctx *sf_ctx =
3082 (penrose_legacy_set_faces_ctx *)state->ctx;
2858 int i; 3083 int i;
2859 int xs[4], ys[4]; 3084 int xs[4], ys[4];
2860 3085
@@ -2864,7 +3089,7 @@ static int set_faces(penrose_state *state, vector *vs, int n, int depth)
2864#endif 3089#endif
2865 3090
2866 for (i = 0; i < n; i++) { 3091 for (i = 0; i < n; i++) {
2867 double tx = v_x(vs, i), ty = v_y(vs, i); 3092 double tx = penrose_legacy_vx(vs, i), ty = penrose_legacy_vy(vs, i);
2868 3093
2869 xs[i] = (int)round_int_nearest_away(tx); 3094 xs[i] = (int)round_int_nearest_away(tx);
2870 ys[i] = (int)round_int_nearest_away(ty); 3095 ys[i] = (int)round_int_nearest_away(ty);
@@ -2875,88 +3100,24 @@ static int set_faces(penrose_state *state, vector *vs, int n, int depth)
2875 3100
2876 grid_face_add_new(sf_ctx->g, n); 3101 grid_face_add_new(sf_ctx->g, n);
2877 debug(("penrose: new face l=%f gen=%d...", 3102 debug(("penrose: new face l=%f gen=%d...",
2878 penrose_side_length(state->start_size, depth), depth)); 3103 penrose_legacy_side_length(state->start_size, depth), depth));
2879 for (i = 0; i < n; i++) { 3104 for (i = 0; i < n; i++) {
2880 grid_dot *d = grid_get_dot(sf_ctx->g, sf_ctx->points, 3105 grid_dot *d = grid_get_dot(sf_ctx->g, sf_ctx->points,
2881 xs[i], ys[i]); 3106 xs[i], ys[i]);
2882 grid_face_set_dot(sf_ctx->g, d, i); 3107 grid_face_set_dot(sf_ctx->g, d, i);
2883 debug((" ... dot 0x%x (%d,%d) (was %2.2f,%2.2f)", 3108 debug((" ... dot 0x%x (%d,%d) (was %2.2f,%2.2f)",
2884 d, d->x, d->y, v_x(vs, i), v_y(vs, i))); 3109 d, d->x, d->y, penrose_legacy_vx(vs, i),
3110 penrose_legacy_vy(vs, i)));
2885 } 3111 }
2886 3112
2887 return 0; 3113 return 0;
2888} 3114}
2889 3115
2890#define PENROSE_TILESIZE 100 3116static grid *grid_new_penrose_legacy(int width, int height, int which,
2891 3117 const char *desc);
2892static void grid_size_penrose(int width, int height,
2893 int *tilesize, int *xextent, int *yextent)
2894{
2895 int l = PENROSE_TILESIZE;
2896
2897 *tilesize = l;
2898 *xextent = l * width;
2899 *yextent = l * height;
2900}
2901
2902static grid *grid_new_penrose(int width, int height, int which, const char *desc); /* forward reference */
2903
2904static char *grid_new_desc_penrose(grid_type type, int width, int height, random_state *rs)
2905{
2906 int tilesize = PENROSE_TILESIZE, startsz, depth, xoff, yoff, aoff;
2907 double outer_radius;
2908 int inner_radius;
2909 char gd[255];
2910 int which = (type == GRID_PENROSE_P2 ? PENROSE_P2 : PENROSE_P3);
2911 grid *g;
2912
2913 while (1) {
2914 /* We want to produce a random bit of penrose tiling, so we
2915 * calculate a random offset (within the patch that penrose.c
2916 * calculates for us) and an angle (multiple of 36) to rotate
2917 * the patch. */
2918
2919 penrose_calculate_size(which, tilesize, width, height,
2920 &outer_radius, &startsz, &depth);
2921
2922 /* Calculate radius of (circumcircle of) patch, subtract from
2923 * radius calculated. */
2924 inner_radius = (int)(outer_radius - sqrt(width*width + height*height));
2925
2926 /* Pick a random offset (the easy way: choose within outer
2927 * square, discarding while it's outside the circle) */
2928 do {
2929 xoff = random_upto(rs, 2*inner_radius) - inner_radius;
2930 yoff = random_upto(rs, 2*inner_radius) - inner_radius;
2931 } while (sqrt(xoff*xoff+yoff*yoff) > inner_radius);
2932
2933 aoff = random_upto(rs, 360/36) * 36;
2934
2935 debug(("grid_desc: ts %d, %dx%d patch, orad %2.2f irad %d",
2936 tilesize, width, height, outer_radius, inner_radius));
2937 debug((" -> xoff %d yoff %d aoff %d", xoff, yoff, aoff));
2938
2939 sprintf(gd, "G%d,%d,%d", xoff, yoff, aoff);
2940
2941 /*
2942 * Now test-generate our grid, to make sure it actually
2943 * produces something.
2944 */
2945 g = grid_new_penrose(width, height, which, gd);
2946 if (g) {
2947 grid_free(g);
2948 break;
2949 }
2950 /* If not, go back to the top of this while loop and try again
2951 * with a different random offset. */
2952 }
2953
2954 return dupstr(gd);
2955}
2956 3118
2957static const char *grid_validate_desc_penrose(grid_type type, 3119static const char *grid_validate_desc_penrose_legacy(
2958 int width, int height, 3120 grid_type type, int width, int height, const char *desc)
2959 const char *desc)
2960{ 3121{
2961 int tilesize = PENROSE_TILESIZE, startsz, depth, xoff, yoff, aoff, inner_radius; 3122 int tilesize = PENROSE_TILESIZE, startsz, depth, xoff, yoff, aoff, inner_radius;
2962 double outer_radius; 3123 double outer_radius;
@@ -2966,8 +3127,8 @@ static const char *grid_validate_desc_penrose(grid_type type,
2966 if (!desc) 3127 if (!desc)
2967 return "Missing grid description string."; 3128 return "Missing grid description string.";
2968 3129
2969 penrose_calculate_size(which, tilesize, width, height, 3130 penrose_legacy_calculate_size(which, tilesize, width, height,
2970 &outer_radius, &startsz, &depth); 3131 &outer_radius, &startsz, &depth);
2971 inner_radius = (int)(outer_radius - sqrt(width*width + height*height)); 3132 inner_radius = (int)(outer_radius - sqrt(width*width + height*height));
2972 3133
2973 if (sscanf(desc, "G%d,%d,%d", &xoff, &yoff, &aoff) != 3) 3134 if (sscanf(desc, "G%d,%d,%d", &xoff, &yoff, &aoff) != 3)
@@ -2982,7 +3143,7 @@ static const char *grid_validate_desc_penrose(grid_type type,
2982 * Test-generate to ensure these parameters don't end us up with 3143 * Test-generate to ensure these parameters don't end us up with
2983 * no grid at all. 3144 * no grid at all.
2984 */ 3145 */
2985 g = grid_new_penrose(width, height, which, desc); 3146 g = grid_new_penrose_legacy(width, height, which, desc);
2986 if (!g) 3147 if (!g)
2987 return "Patch coordinates do not identify a usable grid fragment"; 3148 return "Patch coordinates do not identify a usable grid fragment";
2988 grid_free(g); 3149 grid_free(g);
@@ -2990,40 +3151,30 @@ static const char *grid_validate_desc_penrose(grid_type type,
2990 return NULL; 3151 return NULL;
2991} 3152}
2992 3153
2993/* 3154static grid *grid_new_penrose_legacy(int width, int height, int which,
2994 * We're asked for a grid of a particular size, and we generate enough 3155 const char *desc)
2995 * of the tiling so we can be sure to have enough random grid from which
2996 * to pick.
2997 */
2998
2999static grid *grid_new_penrose(int width, int height, int which, const char *desc)
3000{ 3156{
3001 int max_faces, max_dots, tilesize = PENROSE_TILESIZE; 3157 int tilesize = PENROSE_TILESIZE;
3002 int xsz, ysz, xoff, yoff, aoff; 3158 int xsz, ysz, xoff, yoff, aoff;
3003 double rradius; 3159 double rradius;
3004 3160
3005 tree234 *points; 3161 tree234 *points;
3006 grid *g; 3162 grid *g;
3007 3163
3008 penrose_state ps; 3164 penrose_legacy_state ps;
3009 setface_ctx sf_ctx; 3165 penrose_legacy_set_faces_ctx sf_ctx;
3010 3166
3011 penrose_calculate_size(which, tilesize, width, height, 3167 penrose_legacy_calculate_size(which, tilesize, width, height,
3012 &rradius, &ps.start_size, &ps.max_depth); 3168 &rradius, &ps.start_size, &ps.max_depth);
3013 3169
3014 debug(("penrose: w%d h%d, tile size %d, start size %d, depth %d", 3170 debug(("penrose: w%d h%d, tile size %d, start size %d, depth %d",
3015 width, height, tilesize, ps.start_size, ps.max_depth)); 3171 width, height, tilesize, ps.start_size, ps.max_depth));
3016 3172
3017 ps.new_tile = set_faces; 3173 ps.new_tile = penrose_legacy_set_faces;
3018 ps.ctx = &sf_ctx; 3174 ps.ctx = &sf_ctx;
3019 3175
3020 max_faces = (width*3) * (height*3); /* somewhat paranoid... */
3021 max_dots = max_faces * 4; /* ditto... */
3022
3023 g = grid_empty(); 3176 g = grid_empty();
3024 g->tilesize = tilesize; 3177 g->tilesize = tilesize;
3025 g->faces = snewn(max_faces, grid_face);
3026 g->dots = snewn(max_dots, grid_dot);
3027 3178
3028 points = newtree234(grid_point_cmp_fn); 3179 points = newtree234(grid_point_cmp_fn);
3029 3180
@@ -3051,11 +3202,9 @@ static grid *grid_new_penrose(int width, int height, int which, const char *desc
3051 debug(("penrose: x range (%f --> %f), y range (%f --> %f)", 3202 debug(("penrose: x range (%f --> %f), y range (%f --> %f)",
3052 sf_ctx.xmin, sf_ctx.xmax, sf_ctx.ymin, sf_ctx.ymax)); 3203 sf_ctx.xmin, sf_ctx.xmax, sf_ctx.ymin, sf_ctx.ymax));
3053 3204
3054 penrose(&ps, which, aoff); 3205 penrose_legacy(&ps, which, aoff);
3055 3206
3056 freetree234(points); 3207 freetree234(points);
3057 assert(g->num_faces <= max_faces);
3058 assert(g->num_dots <= max_dots);
3059 3208
3060 debug(("penrose: %d faces total (equivalent to %d wide by %d high)", 3209 debug(("penrose: %d faces total (equivalent to %d wide by %d high)",
3061 g->num_faces, g->num_faces/height, g->num_faces/width)); 3210 g->num_faces, g->num_faces/height, g->num_faces/width));
@@ -3091,6 +3240,223 @@ static grid *grid_new_penrose(int width, int height, int which, const char *desc
3091 return g; 3240 return g;
3092} 3241}
3093 3242
3243/*
3244 * Combinatorial-coordinate generation.
3245 *
3246 * We receive coordinates from the generator in the form of x,y pairs
3247 * each of which is an integer combination of 1 and sqrt(5), but those
3248 * pairs have different scale units in the x and y directions. The
3249 * scale units are 1/4 for x and sin(pi/5)/2 for y, which makes their
3250 * ratio equal to 2 sin(pi/5) ~= 1.1756. We fudge that irrational
3251 * aspect ratio into a rational approximation, by simply taking a pair
3252 * of integer scale factors for the x and y dimensions; this distorts
3253 * the output tiling slightly, but the distortion is consistent, and
3254 * doesn't accumulate over a large patch of tiling, so it won't make
3255 * anything end up totally out of place.
3256 *
3257 * (However, we compute the subsequent combination of 1 and sqrt(5)
3258 * exactly, because using an approximation to sqrt(5) _could_ mean
3259 * that in a sufficiently large patch of tiling two such combinations
3260 * ended up misordered.)
3261 *
3262 * Adding to the confusion, we also flip round the x and y
3263 * coordinates, because it's slightly nicer to have vertical edges in
3264 * the tiling rather than horizontal ones. (Both for aesthetics, and
3265 * also because if two P3 thin rhombs are separated by a horizontal
3266 * line and both contain numeric clues then the clue numbers look a
3267 * bit crowded, due to digits being taller than they are wide.)
3268 *
3269 * Finally, we have different base unit sizes for the two tiling
3270 * types, because sensible sizes for the two are actually different.
3271 * Each of P2 and P3 can be subdivided into the other, via dividing
3272 * the larger triangle type in two, so that L large and S small become
3273 * L+S large and L small. In the limit, this means that you expect the
3274 * number of triangles (hence tiles) to grow by a factor of phi in
3275 * each of those subdivisions (and hence by a factor of phi^2 in a
3276 * full subdivision of P2 to a finer P2). So a sensible size ratio
3277 * between the two tilings is one that makes them fit about the same
3278 * number of tiles into the same area - and since tile area is
3279 * proportional to _square_ of length, it follows that the P2 and P3
3280 * length unit should differ by a factor of sqrt(phi).
3281 */
3282#define PENROSE_XUNIT_P2 37
3283#define PENROSE_YUNIT_P2 44
3284#define PENROSE_XUNIT_P3 30
3285#define PENROSE_YUNIT_P3 35
3286
3287struct size { int w, h; };
3288static struct size api_size_penrose(int width, int height, int which)
3289{
3290 int xunit = (which == PENROSE_P2 ? PENROSE_XUNIT_P2 : PENROSE_XUNIT_P3);
3291 int yunit = (which == PENROSE_P2 ? PENROSE_YUNIT_P2 : PENROSE_YUNIT_P3);
3292 struct size size = {
3293 width * PENROSE_TILESIZE / yunit,
3294 height * PENROSE_TILESIZE / xunit,
3295 };
3296 return size;
3297}
3298
3299static grid *grid_new_penrose(int width, int height, int which,
3300 const char *desc); /* forward reference */
3301
3302static char *grid_new_desc_penrose(grid_type type, int width, int height,
3303 random_state *rs)
3304{
3305 char *buf;
3306 struct PenrosePatchParams params;
3307 int which = (type == GRID_PENROSE_P2 ? PENROSE_P2 : PENROSE_P3);
3308 struct size size = api_size_penrose(width, height, which);
3309
3310 penrose_tiling_randomise(&params, which, size.h, size.w, rs);
3311
3312 buf = snewn(params.ncoords + 3, char);
3313 buf[0] = '0' + params.orientation;
3314 buf[1] = '0' + params.start_vertex;
3315 memcpy(buf + 2, params.coords, params.ncoords);
3316 buf[2 + params.ncoords] = '\0';
3317
3318 sfree(params.coords);
3319 return buf;
3320}
3321
3322/* Shared code between validating and reading grid descs.
3323 * Always allocates params->coords, whether or not it returns an error. */
3324static const char *grid_desc_to_penrose_params(
3325 const char *desc, int which, struct PenrosePatchParams *params)
3326{
3327 int i;
3328
3329 if (!*desc)
3330 return "empty grid description";
3331
3332 params->ncoords = strlen(desc) - 2;
3333 params->coords = snewn(params->ncoords, char);
3334
3335 {
3336 char c = desc[0];
3337 if (isdigit((unsigned char)c))
3338 params->orientation = c - '0';
3339 else
3340 return "expected digit at start of grid description";
3341
3342 c = desc[1];
3343 if (c >= '0' && c < '3')
3344 params->start_vertex = c - '0';
3345 else
3346 return "expected digit as second char of grid description";
3347 }
3348
3349 for (i = 0; i < params->ncoords; i++) {
3350 char c = desc[i+2];
3351 if (!penrose_valid_letter(c, which))
3352 return "expected tile letter in grid description";
3353 params->coords[i] = c;
3354 }
3355
3356 return NULL;
3357}
3358
3359static const char *grid_validate_desc_penrose(grid_type type,
3360 int width, int height,
3361 const char *desc)
3362{
3363 struct PenrosePatchParams params;
3364 const char *error = NULL;
3365 int which = (type == GRID_PENROSE_P2 ? PENROSE_P2 : PENROSE_P3);
3366
3367 if (!desc)
3368 return "Missing grid description string.";
3369
3370 if (*desc == 'G')
3371 return grid_validate_desc_penrose_legacy(type, width, height, desc);
3372
3373 error = grid_desc_to_penrose_params(desc, which, &params);
3374 if (!error)
3375 error = penrose_tiling_params_invalid(&params, which);
3376
3377 sfree(params.coords);
3378 return error;
3379}
3380
3381struct penrosecontext {
3382 grid *g;
3383 tree234 *points;
3384 int xunit, yunit;
3385};
3386
3387static void grid_penrose_callback(void *vctx, const int *coords)
3388{
3389 struct penrosecontext *ctx = (struct penrosecontext *)vctx;
3390 size_t i;
3391
3392 grid_face_add_new(ctx->g, 4);
3393 for (i = 0; i < 4; i++) {
3394 grid_dot *d = grid_get_dot(
3395 ctx->g, ctx->points,
3396 coords[4*i+2] * ctx->yunit + n_times_root_k(
3397 coords[4*i+3] * ctx->yunit, 5),
3398 coords[4*i+0] * ctx->xunit + n_times_root_k(
3399 coords[4*i+1] * ctx->xunit, 5));
3400 grid_face_set_dot(ctx->g, d, i);
3401 }
3402}
3403
3404static grid *grid_new_penrose(int width, int height, int which,
3405 const char *desc)
3406{
3407 struct PenrosePatchParams params;
3408 const char *error = NULL;
3409 struct penrosecontext ctx[1];
3410 struct size size;
3411
3412 if (*desc == 'G')
3413 return grid_new_penrose_legacy(width, height, which, desc);
3414
3415 error = grid_desc_to_penrose_params(desc, which, &params);
3416 assert(error == NULL && "grid_validate_desc_penrose should have failed");
3417
3418 ctx->g = grid_empty();
3419 ctx->g->tilesize = PENROSE_TILESIZE;
3420
3421 ctx->points = newtree234(grid_point_cmp_fn);
3422
3423 ctx->xunit = (which == PENROSE_P2 ? PENROSE_XUNIT_P2 : PENROSE_XUNIT_P3);
3424 ctx->yunit = (which == PENROSE_P2 ? PENROSE_YUNIT_P2 : PENROSE_YUNIT_P3);
3425
3426 size = api_size_penrose(width, height, which);
3427 penrose_tiling_generate(&params, size.h, size.w,
3428 grid_penrose_callback, ctx);
3429
3430 freetree234(ctx->points);
3431 sfree(params.coords);
3432
3433 grid_trim_vigorously(ctx->g);
3434 grid_make_consistent(ctx->g);
3435
3436 /*
3437 * Centre the grid in its originally promised rectangle.
3438 */
3439 {
3440 int w = width * PENROSE_TILESIZE, h = height * PENROSE_TILESIZE;
3441 ctx->g->lowest_x -= (w - (ctx->g->highest_x - ctx->g->lowest_x))/2;
3442 ctx->g->lowest_y -= (h - (ctx->g->highest_y - ctx->g->lowest_y))/2;
3443 ctx->g->highest_x = ctx->g->lowest_x + w;
3444 ctx->g->highest_y = ctx->g->lowest_y + h;
3445 }
3446
3447 return ctx->g;
3448}
3449
3450static const char *grid_validate_params_penrose_p2_kite(int width, int height)
3451{
3452 return grid_validate_params_penrose(width, height);
3453}
3454
3455static const char *grid_validate_params_penrose_p3_thick(int width, int height)
3456{
3457 return grid_validate_params_penrose(width, height);
3458}
3459
3094static void grid_size_penrose_p2_kite(int width, int height, 3460static void grid_size_penrose_p2_kite(int width, int height,
3095 int *tilesize, int *xextent, int *yextent) 3461 int *tilesize, int *xextent, int *yextent)
3096{ 3462{
@@ -3113,18 +3479,349 @@ static grid *grid_new_penrose_p3_thick(int width, int height, const char *desc)
3113 return grid_new_penrose(width, height, PENROSE_P3, desc); 3479 return grid_new_penrose(width, height, PENROSE_P3, desc);
3114} 3480}
3115 3481
3482#define HATS_TILESIZE 32
3483#define HATS_XSQUARELEN 4
3484#define HATS_YSQUARELEN 6
3485#define HATS_XUNIT 14
3486#define HATS_YUNIT 8
3487
3488static const char *grid_validate_params_hats(
3489 int width, int height)
3490{
3491 int l = HATS_TILESIZE;
3492
3493 if (width > INT_MAX / l || /* xextent */
3494 height > INT_MAX / l || /* yextent */
3495 width > INT_MAX / (6 * height)) /* max_dots */
3496 return "Grid must not be unreasonably large";
3497 return NULL;
3498}
3499
3500static void grid_size_hats(int width, int height,
3501 int *tilesize, int *xextent, int *yextent)
3502{
3503 *tilesize = HATS_TILESIZE;
3504 *xextent = width * HATS_XUNIT * HATS_XSQUARELEN;
3505 *yextent = height * HATS_YUNIT * HATS_YSQUARELEN;
3506}
3507
3508static char *grid_new_desc_hats(
3509 grid_type type, int width, int height, random_state *rs)
3510{
3511 char *buf, *p;
3512 size_t bufmax, i;
3513 struct HatPatchParams hp;
3514
3515 hat_tiling_randomise(&hp, width, height, rs);
3516
3517 bufmax = 3 * hp.ncoords + 2;
3518 buf = snewn(bufmax, char);
3519 p = buf;
3520 for (i = 0; i < hp.ncoords; i++) {
3521 assert(hp.coords[i] < 100); /* at most 2 digits */
3522 assert(p - buf <= bufmax-4); /* room for 2 digits, comma and NUL */
3523 p += sprintf(p, "%d,", (int)hp.coords[i]);
3524 }
3525 assert(p - buf <= bufmax-2); /* room for final letter and NUL */
3526 p[0] = hp.final_metatile;
3527 p[1] = '\0';
3528
3529 sfree(hp.coords);
3530 return buf;
3531}
3532
3533/* Shared code between validating and reading grid descs.
3534 * Always allocates hp->coords, whether or not it returns an error. */
3535static const char *grid_desc_to_hat_params(
3536 const char *desc, struct HatPatchParams *hp)
3537{
3538 size_t maxcoords;
3539 const char *p = desc;
3540
3541 maxcoords = (strlen(desc) + 1) / 2;
3542 hp->coords = snewn(maxcoords, unsigned char);
3543 hp->ncoords = 0;
3544
3545 while (isdigit((unsigned char)*p)) {
3546 const char *p_orig = p;
3547 int n = atoi(p);
3548 while (*p && isdigit((unsigned char)*p)) p++;
3549 if (*p != ',')
3550 return "expected ',' in grid description";
3551 if (p - p_orig > 2 || n > 0xFF)
3552 return "too-large coordinate in grid description";
3553 p++; /* eat the comma */
3554
3555 /* This assert should be guaranteed by the way we calculated
3556 * maxcoords, so a failure of this check is a bug in this
3557 * function, not an indication of an invalid input string */
3558 assert(hp->ncoords < maxcoords);
3559 hp->coords[hp->ncoords++] = n;
3560 }
3561
3562 if (*p == 'H' || *p == 'T' || *p == 'P' || *p == 'F')
3563 hp->final_metatile = *p;
3564 else
3565 return "invalid character in grid description";
3566
3567 return NULL;
3568}
3569
3570static const char *grid_validate_desc_hats(
3571 grid_type type, int width, int height, const char *desc)
3572{
3573 struct HatPatchParams hp;
3574 const char *error = NULL;
3575
3576 if (!desc)
3577 return "Missing grid description string.";
3578
3579 error = grid_desc_to_hat_params(desc, &hp);
3580 if (!error)
3581 error = hat_tiling_params_invalid(&hp);
3582
3583 sfree(hp.coords);
3584 return error;
3585}
3586
3587struct hatcontext {
3588 grid *g;
3589 tree234 *points;
3590};
3591
3592static void grid_hats_callback(void *vctx, size_t nvertices, int *coords)
3593{
3594 struct hatcontext *ctx = (struct hatcontext *)vctx;
3595 size_t i;
3596
3597 grid_face_add_new(ctx->g, nvertices);
3598 for (i = 0; i < nvertices; i++) {
3599 grid_dot *d = grid_get_dot(
3600 ctx->g, ctx->points,
3601 coords[2*i] * HATS_XUNIT,
3602 coords[2*i+1] * HATS_YUNIT);
3603 grid_face_set_dot(ctx->g, d, i);
3604 }
3605}
3606
3607static grid *grid_new_hats(int width, int height, const char *desc)
3608{
3609 struct HatPatchParams hp;
3610 const char *error = NULL;
3611
3612 error = grid_desc_to_hat_params(desc, &hp);
3613 assert(error == NULL && "grid_validate_desc_hats should have failed");
3614
3615 struct hatcontext ctx[1];
3616
3617 ctx->g = grid_empty();
3618 ctx->g->tilesize = HATS_TILESIZE;
3619
3620 ctx->points = newtree234(grid_point_cmp_fn);
3621
3622 hat_tiling_generate(&hp, width, height, grid_hats_callback, ctx);
3623
3624 freetree234(ctx->points);
3625 sfree(hp.coords);
3626
3627 grid_trim_vigorously(ctx->g);
3628 grid_make_consistent(ctx->g);
3629 return ctx->g;
3630}
3631
3632#define SPECTRE_TILESIZE 32
3633#define SPECTRE_SQUARELEN 7
3634#define SPECTRE_UNIT 8
3635
3636static const char *grid_validate_params_spectres(
3637 int width, int height)
3638{
3639 int l = SPECTRE_UNIT * SPECTRE_SQUARELEN;
3640
3641 if (width > INT_MAX / l || /* xextent */
3642 height > INT_MAX / l || /* yextent */
3643 width > (INT_MAX / SPECTRE_SQUARELEN /
3644 SPECTRE_SQUARELEN / height)) /* max_faces */
3645 return "Grid must not be unreasonably large";
3646 return NULL;
3647}
3648
3649static void grid_size_spectres(int width, int height,
3650 int *tilesize, int *xextent, int *yextent)
3651{
3652 *tilesize = SPECTRE_TILESIZE;
3653 *xextent = width * SPECTRE_UNIT * SPECTRE_SQUARELEN;
3654 *yextent = height * SPECTRE_UNIT * SPECTRE_SQUARELEN;
3655}
3656
3657static char *grid_new_desc_spectres(
3658 grid_type type, int width, int height, random_state *rs)
3659{
3660 char *buf;
3661 size_t i;
3662 struct SpectrePatchParams sp;
3663
3664 spectre_tiling_randomise(&sp, width * SPECTRE_SQUARELEN,
3665 height * SPECTRE_SQUARELEN, rs);
3666
3667 buf = snewn(sp.ncoords + 3, char);
3668 buf[0] = (sp.orientation < 10 ? '0' + sp.orientation :
3669 'A' + sp.orientation - 10);
3670 for (i = 0; i < sp.ncoords; i++) {
3671 assert(sp.coords[i] < 10); /* all indices are 1 digit */
3672 buf[i+1] = '0' + sp.coords[i];
3673 }
3674 buf[sp.ncoords+1] = sp.final_hex;
3675 buf[sp.ncoords+2] = '\0';
3676
3677 sfree(sp.coords);
3678 return buf;
3679}
3680
3681/* Shared code between validating and reading grid descs.
3682 * Always allocates sp->coords, whether or not it returns an error. */
3683static const char *grid_desc_to_spectre_params(
3684 const char *desc, struct SpectrePatchParams *sp)
3685{
3686 size_t i;
3687
3688 if (!*desc)
3689 return "empty grid description";
3690
3691 sp->ncoords = strlen(desc) - 2;
3692 sp->coords = snewn(sp->ncoords, unsigned char);
3693
3694 {
3695 char c = desc[0];
3696 if (isdigit((unsigned char)c))
3697 sp->orientation = c - '0';
3698 else if (c == 'A' || c == 'B')
3699 sp->orientation = 10 + c - 'A';
3700 else
3701 return "expected digit or A,B at start of grid description";
3702 }
3703
3704 for (i = 0; i < sp->ncoords; i++) {
3705 char c = desc[i+1];
3706 if (!isdigit((unsigned char)c))
3707 return "expected digit in grid description";
3708 sp->coords[i] = c - '0';
3709 }
3710
3711 sp->final_hex = desc[sp->ncoords+1];
3712
3713 return NULL;
3714}
3715
3716static const char *grid_validate_desc_spectres(
3717 grid_type type, int width, int height, const char *desc)
3718{
3719 struct SpectrePatchParams sp;
3720 const char *error = NULL;
3721
3722 if (!desc)
3723 return "Missing grid description string.";
3724
3725 error = grid_desc_to_spectre_params(desc, &sp);
3726 if (!error)
3727 error = spectre_tiling_params_invalid(&sp);
3728
3729 sfree(sp.coords);
3730 return error;
3731}
3732
3733struct spectrecontext {
3734 grid *g;
3735 tree234 *points;
3736};
3737
3738static void grid_spectres_callback(void *vctx, const int *coords)
3739{
3740 struct spectrecontext *ctx = (struct spectrecontext *)vctx;
3741 size_t i;
3742
3743 grid_face_add_new(ctx->g, SPECTRE_NVERTICES);
3744 for (i = 0; i < SPECTRE_NVERTICES; i++) {
3745 grid_dot *d = grid_get_dot(
3746 ctx->g, ctx->points,
3747 (coords[4*i+0] * SPECTRE_UNIT +
3748 n_times_root_k(coords[4*i+1] * SPECTRE_UNIT, 3)),
3749 (coords[4*i+2] * SPECTRE_UNIT +
3750 n_times_root_k(coords[4*i+3] * SPECTRE_UNIT, 3)));
3751 grid_face_set_dot(ctx->g, d, i);
3752 }
3753}
3754
3755static grid *grid_new_spectres(int width, int height, const char *desc)
3756{
3757 struct SpectrePatchParams sp;
3758 const char *error = NULL;
3759 int width2 = width * SPECTRE_SQUARELEN;
3760 int height2 = height * SPECTRE_SQUARELEN;
3761
3762 error = grid_desc_to_spectre_params(desc, &sp);
3763 assert(error == NULL && "grid_validate_desc_spectres should have failed");
3764
3765 struct spectrecontext ctx[1];
3766
3767 ctx->g = grid_empty();
3768 ctx->g->tilesize = SPECTRE_TILESIZE;
3769
3770 ctx->points = newtree234(grid_point_cmp_fn);
3771
3772 spectre_tiling_generate(&sp, width2, height2, grid_spectres_callback, ctx);
3773
3774 freetree234(ctx->points);
3775 sfree(sp.coords);
3776
3777 grid_trim_vigorously(ctx->g);
3778 grid_make_consistent(ctx->g);
3779
3780 /*
3781 * As with the Penrose tiling, we're likely to have different
3782 * sized margins due to the lack of a neat grid that this tiling
3783 * fits on. So now we know what tiles we're left with, recentre
3784 * them.
3785 */
3786 {
3787 int w = width2 * SPECTRE_UNIT, h = height2 * SPECTRE_UNIT;
3788 ctx->g->lowest_x -= (w - (ctx->g->highest_x - ctx->g->lowest_x))/2;
3789 ctx->g->lowest_y -= (h - (ctx->g->highest_y - ctx->g->lowest_y))/2;
3790 ctx->g->highest_x = ctx->g->lowest_x + w;
3791 ctx->g->highest_y = ctx->g->lowest_y + h;
3792 }
3793
3794 return ctx->g;
3795}
3796
3116/* ----------- End of grid generators ------------- */ 3797/* ----------- End of grid generators ------------- */
3117 3798
3799#define FNVAL(upper,lower) &grid_validate_params_ ## lower,
3118#define FNNEW(upper,lower) &grid_new_ ## lower, 3800#define FNNEW(upper,lower) &grid_new_ ## lower,
3119#define FNSZ(upper,lower) &grid_size_ ## lower, 3801#define FNSZ(upper,lower) &grid_size_ ## lower,
3120 3802
3803static const char *(*(grid_validate_paramses[]))(int, int) =
3804 { GRIDGEN_LIST(FNVAL) };
3121static grid *(*(grid_news[]))(int, int, const char*) = { GRIDGEN_LIST(FNNEW) }; 3805static grid *(*(grid_news[]))(int, int, const char*) = { GRIDGEN_LIST(FNNEW) };
3122static void(*(grid_sizes[]))(int, int, int*, int*, int*) = { GRIDGEN_LIST(FNSZ) }; 3806static void(*(grid_sizes[]))(int, int, int*, int*, int*) = { GRIDGEN_LIST(FNSZ) };
3123 3807
3808/* Work out if a grid can be made, and complain if not. */
3809
3810const char *grid_validate_params(grid_type type, int width, int height)
3811{
3812 if (width <= 0 || height <= 0)
3813 return "Width and height must both be positive";
3814 return grid_validate_paramses[type](width, height);
3815}
3816
3124char *grid_new_desc(grid_type type, int width, int height, random_state *rs) 3817char *grid_new_desc(grid_type type, int width, int height, random_state *rs)
3125{ 3818{
3126 if (type == GRID_PENROSE_P2 || type == GRID_PENROSE_P3) { 3819 if (type == GRID_PENROSE_P2 || type == GRID_PENROSE_P3) {
3127 return grid_new_desc_penrose(type, width, height, rs); 3820 return grid_new_desc_penrose(type, width, height, rs);
3821 } else if (type == GRID_HATS) {
3822 return grid_new_desc_hats(type, width, height, rs);
3823 } else if (type == GRID_SPECTRES) {
3824 return grid_new_desc_spectres(type, width, height, rs);
3128 } else if (type == GRID_TRIANGULAR) { 3825 } else if (type == GRID_TRIANGULAR) {
3129 return dupstr("0"); /* up-to-date version of triangular grid */ 3826 return dupstr("0"); /* up-to-date version of triangular grid */
3130 } else { 3827 } else {
@@ -3137,6 +3834,10 @@ const char *grid_validate_desc(grid_type type, int width, int height,
3137{ 3834{
3138 if (type == GRID_PENROSE_P2 || type == GRID_PENROSE_P3) { 3835 if (type == GRID_PENROSE_P2 || type == GRID_PENROSE_P3) {
3139 return grid_validate_desc_penrose(type, width, height, desc); 3836 return grid_validate_desc_penrose(type, width, height, desc);
3837 } else if (type == GRID_HATS) {
3838 return grid_validate_desc_hats(type, width, height, desc);
3839 } else if (type == GRID_SPECTRES) {
3840 return grid_validate_desc_spectres(type, width, height, desc);
3140 } else if (type == GRID_TRIANGULAR) { 3841 } else if (type == GRID_TRIANGULAR) {
3141 return grid_validate_desc_triangular(type, width, height, desc); 3842 return grid_validate_desc_triangular(type, width, height, desc);
3142 } else { 3843 } else {
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-12 17:38:26 +0000