grid.c

   1 /*
   2  * (c) Lambros Lambrou 2008
   3  *
   4  * Code for working with general grids, which can be any planar graph
   5  * with faces, edges and vertices (dots).  Includes generators for a few
   6  * types of grid, including square, hexagonal, triangular and others.
   7  */
   8
   9 #include <stdio.h>
  10 #include <stdlib.h>
  11 #include <string.h>
  12 #include <assert.h>
  13 #include <ctype.h>
  14 #include <math.h>
  15
  16 #include "puzzles.h"
  17 #include "tree234.h"
  18 #include "grid.h"
  19
  20 /* Debugging options */
  21
  22 /*
  23 #define DEBUG_GRID
  24 */
  25
  26 /* ----------------------------------------------------------------------
  27  * Deallocate or dereference a grid
  28  */
  29 void grid_free(grid *g)
  30 {
  31     assert(g->refcount);
  32
  33     g->refcount--;
  34     if (g->refcount == 0) {
  35         int i;
  36         for (i = 0; i < g->num_faces; i++) {
  37             sfree(g->faces[i].dots);
  38             sfree(g->faces[i].edges);
  39         }
  40         for (i = 0; i < g->num_dots; i++) {
  41             sfree(g->dots[i].faces);
  42             sfree(g->dots[i].edges);
  43         }
  44         sfree(g->faces);
  45         sfree(g->edges);
  46         sfree(g->dots);
  47         sfree(g);
  48     }
  49 }
  50
  51 /* Used by the other grid generators.  Create a brand new grid with nothing
  52  * initialised (all lists are NULL) */
  53 static grid *grid_new(void)
  54 {
  55     grid *g = snew(grid);
  56     g->faces = NULL;
  57     g->edges = NULL;
  58     g->dots = NULL;
  59     g->num_faces = g->num_edges = g->num_dots = 0;
  60     g->refcount = 1;
  61     g->lowest_x = g->lowest_y = g->highest_x = g->highest_y = 0;
  62     return g;
  63 }
  64
  65 /* Helper function to calculate perpendicular distance from
  66  * a point P to a line AB.  A and B mustn't be equal here.
  67  *
  68  * Well-known formula for area A of a triangle:
  69  *                             /  1   1   1 \
  70  * 2A = determinant of matrix  | px  ax  bx |
  71  *                             \ py  ay  by /
  72  *
  73  * Also well-known: 2A = base * height
  74  *                     = perpendicular distance * line-length.
  75  *
  76  * Combining gives: distance = determinant / line-length(a,b)
  77  */
  78 static double point_line_distance(long px, long py,
  79                                   long ax, long ay,
  80                                   long bx, long by)
  81 {
  82     long det = ax*by - bx*ay + bx*py - px*by + px*ay - ax*py;
  83     double len;
  84     det = max(det, -det);
  85     len = sqrt(SQ(ax - bx) + SQ(ay - by));
  86     return det / len;
  87 }
  88
  89 /* Determine nearest edge to where the user clicked.
  90  * (x, y) is the clicked location, converted to grid coordinates.
  91  * Returns the nearest edge, or NULL if no edge is reasonably
  92  * near the position.
  93  *
  94  * Just judging edges by perpendicular distance is not quite right -
  95  * the edge might be "off to one side". So we insist that the triangle
  96  * with (x,y) has acute angles at the edge's dots.
  97  *
  98  *     edge1
  99  *  *---------*------
 100  *            |
 101  *            |      *(x,y)
 102  *      edge2 |
 103  *            |   edge2 is OK, but edge1 is not, even though
 104  *            |   edge1 is perpendicularly closer to (x,y)
 105  *            *
 106  *
 107  */
 108 grid_edge *grid_nearest_edge(grid *g, int x, int y)
 109 {
 110     grid_edge *best_edge;
 111     double best_distance = 0;
 112     int i;
 113
 114     best_edge = NULL;
 115
 116     for (i = 0; i < g->num_edges; i++) {
 117         grid_edge *e = &g->edges[i];
 118         long e2; /* squared length of edge */
 119         long a2, b2; /* squared lengths of other sides */
 120         double dist;
 121
 122         /* See if edge e is eligible - the triangle must have acute angles
 123          * at the edge's dots.
 124          * Pythagoras formula h^2 = a^2 + b^2 detects right-angles,
 125          * so detect acute angles by testing for h^2 < a^2 + b^2 */
 126         e2 = SQ((long)e->dot1->x - (long)e->dot2->x) + SQ((long)e->dot1->y - (long)e->dot2->y);
 127         a2 = SQ((long)e->dot1->x - (long)x) + SQ((long)e->dot1->y - (long)y);
 128         b2 = SQ((long)e->dot2->x - (long)x) + SQ((long)e->dot2->y - (long)y);
 129         if (a2 >= e2 + b2) continue;
 130         if (b2 >= e2 + a2) continue;
 131
 132         /* e is eligible so far.  Now check the edge is reasonably close
 133          * to where the user clicked.  Don't want to toggle an edge if the
 134          * click was way off the grid.
 135          * There is room for experimentation here.  We could check the
 136          * perpendicular distance is within a certain fraction of the length
 137          * of the edge.  That amounts to testing a rectangular region around
 138          * the edge.
 139          * Alternatively, we could check that the angle at the point is obtuse.
 140          * That would amount to testing a circular region with the edge as
 141          * diameter. */
 142         dist = point_line_distance((long)x, (long)y,
 143                                    (long)e->dot1->x, (long)e->dot1->y,
 144                                    (long)e->dot2->x, (long)e->dot2->y);
 145         /* Is dist more than half edge length ? */
 146         if (4 * SQ(dist) > e2)
 147             continue;
 148
 149         if (best_edge == NULL || dist < best_distance) {
 150             best_edge = e;
 151             best_distance = dist;
 152         }
 153     }
 154     return best_edge;
 155 }
 156
 157 /* ----------------------------------------------------------------------
 158  * Grid generation
 159  */
 160
 161 #ifdef DEBUG_GRID
 162 /* Show the basic grid information, before doing grid_make_consistent */
 163 static void grid_print_basic(grid *g)
 164 {
 165     /* TODO: Maybe we should generate an SVG image of the dots and lines
 166      * of the grid here, before grid_make_consistent.
 167      * Would help with debugging grid generation. */
 168     int i;
 169     printf("--- Basic Grid Data ---\n");
 170     for (i = 0; i < g->num_faces; i++) {
 171         grid_face *f = g->faces + i;
 172         printf("Face %d: dots[", i);
 173         int j;
 174         for (j = 0; j < f->order; j++) {
 175             grid_dot *d = f->dots[j];
 176             printf("%s%d", j ? "," : "", (int)(d - g->dots));
 177         }
 178         printf("]\n");
 179     }
 180 }
 181 /* Show the derived grid information, computed by grid_make_consistent */
 182 static void grid_print_derived(grid *g)
 183 {
 184     /* edges */
 185     int i;
 186     printf("--- Derived Grid Data ---\n");
 187     for (i = 0; i < g->num_edges; i++) {
 188         grid_edge *e = g->edges + i;
 189         printf("Edge %d: dots[%d,%d] faces[%d,%d]\n",
 190             i, (int)(e->dot1 - g->dots), (int)(e->dot2 - g->dots),
 191             e->face1 ? (int)(e->face1 - g->faces) : -1,
 192             e->face2 ? (int)(e->face2 - g->faces) : -1);
 193     }
 194     /* faces */
 195     for (i = 0; i < g->num_faces; i++) {
 196         grid_face *f = g->faces + i;
 197         int j;
 198         printf("Face %d: faces[", i);
 199         for (j = 0; j < f->order; j++) {
 200             grid_edge *e = f->edges[j];
 201             grid_face *f2 = (e->face1 == f) ? e->face2 : e->face1;
 202             printf("%s%d", j ? "," : "", f2 ? (int)(f2 - g->faces) : -1);
 203         }
 204         printf("]\n");
 205     }
 206     /* dots */
 207     for (i = 0; i < g->num_dots; i++) {
 208         grid_dot *d = g->dots + i;
 209         int j;
 210         printf("Dot %d: dots[", i);
 211         for (j = 0; j < d->order; j++) {
 212             grid_edge *e = d->edges[j];
 213             grid_dot *d2 = (e->dot1 == d) ? e->dot2 : e->dot1;
 214             printf("%s%d", j ? "," : "", (int)(d2 - g->dots));
 215         }
 216         printf("] faces[");
 217         for (j = 0; j < d->order; j++) {
 218             grid_face *f = d->faces[j];
 219             printf("%s%d", j ? "," : "", f ? (int)(f - g->faces) : -1);
 220         }
 221         printf("]\n");
 222     }
 223 }
 224 #endif /* DEBUG_GRID */
 225
 226 /* Helper function for building incomplete-edges list in
 227  * grid_make_consistent() */
 228 static int grid_edge_bydots_cmpfn(void *v1, void *v2)
 229 {
 230     grid_edge *a = v1;
 231     grid_edge *b = v2;
 232     grid_dot *da, *db;
 233
 234     /* Pointer subtraction is valid here, because all dots point into the
 235      * same dot-list (g->dots).
 236      * Edges are not "normalised" - the 2 dots could be stored in any order,
 237      * so we need to take this into account when comparing edges. */
 238
 239     /* Compare first dots */
 240     da = (a->dot1 < a->dot2) ? a->dot1 : a->dot2;
 241     db = (b->dot1 < b->dot2) ? b->dot1 : b->dot2;
 242     if (da != db)
 243         return db - da;
 244     /* Compare last dots */
 245     da = (a->dot1 < a->dot2) ? a->dot2 : a->dot1;
 246     db = (b->dot1 < b->dot2) ? b->dot2 : b->dot1;
 247     if (da != db)
 248         return db - da;
 249
 250     return 0;
 251 }
 252
 253 /* Input: grid has its dots and faces initialised:
 254  * - dots have (optionally) x and y coordinates, but no edges or faces
 255  * (pointers are NULL).
 256  * - edges not initialised at all
 257  * - faces initialised and know which dots they have (but no edges yet).  The
 258  * dots around each face are assumed to be clockwise.
 259  *
 260  * Output: grid is complete and valid with all relationships defined.
 261  */
 262 static void grid_make_consistent(grid *g)
 263 {
 264     int i;
 265     tree234 *incomplete_edges;
 266     grid_edge *next_new_edge; /* Where new edge will go into g->edges */
 267
 268 #ifdef DEBUG_GRID
 269     grid_print_basic(g);
 270 #endif
 271
 272     /* ====== Stage 1 ======
 273      * Generate edges
 274      */
 275
 276     /* We know how many dots and faces there are, so we can find the exact
 277      * number of edges from Euler's polyhedral formula: F + V = E + 2 .
 278      * We use "-1", not "-2" here, because Euler's formula includes the
 279      * infinite face, which we don't count. */
 280     g->num_edges = g->num_faces + g->num_dots - 1;
 281     g->edges = snewn(g->num_edges, grid_edge);
 282     next_new_edge = g->edges;
 283
 284     /* Iterate over faces, and over each face's dots, generating edges as we
 285      * go.  As we find each new edge, we can immediately fill in the edge's
 286      * dots, but only one of the edge's faces.  Later on in the iteration, we
 287      * will find the same edge again (unless it's on the border), but we will
 288      * know the other face.
 289      * For efficiency, maintain a list of the incomplete edges, sorted by
 290      * their dots. */
 291     incomplete_edges = newtree234(grid_edge_bydots_cmpfn);
 292     for (i = 0; i < g->num_faces; i++) {
 293         grid_face *f = g->faces + i;
 294         int j;
 295         for (j = 0; j < f->order; j++) {
 296             grid_edge e; /* fake edge for searching */
 297             grid_edge *edge_found;
 298             int j2 = j + 1;
 299             if (j2 == f->order)
 300                 j2 = 0;
 301             e.dot1 = f->dots[j];
 302             e.dot2 = f->dots[j2];
 303             /* Use del234 instead of find234, because we always want to
 304              * remove the edge if found */
 305             edge_found = del234(incomplete_edges, &e);
 306             if (edge_found) {
 307                 /* This edge already added, so fill out missing face.
 308                  * Edge is already removed from incomplete_edges. */
 309                 edge_found->face2 = f;
 310             } else {
 311                 assert(next_new_edge - g->edges < g->num_edges);
 312                 next_new_edge->dot1 = e.dot1;
 313                 next_new_edge->dot2 = e.dot2;
 314                 next_new_edge->face1 = f;
 315                 next_new_edge->face2 = NULL; /* potentially infinite face */
 316                 add234(incomplete_edges, next_new_edge);
 317                 ++next_new_edge;
 318             }
 319         }
 320     }
 321     freetree234(incomplete_edges);
 322
 323     /* ====== Stage 2 ======
 324      * For each face, build its edge list.
 325      */
 326
 327     /* Allocate space for each edge list.  Can do this, because each face's
 328      * edge-list is the same size as its dot-list. */
 329     for (i = 0; i < g->num_faces; i++) {
 330         grid_face *f = g->faces + i;
 331         int j;
 332         f->edges = snewn(f->order, grid_edge*);
 333         /* Preload with NULLs, to help detect potential bugs. */
 334         for (j = 0; j < f->order; j++)
 335             f->edges[j] = NULL;
 336     }
 337
 338     /* Iterate over each edge, and over both its faces.  Add this edge to
 339      * the face's edge-list, after finding where it should go in the
 340      * sequence. */
 341     for (i = 0; i < g->num_edges; i++) {
 342         grid_edge *e = g->edges + i;
 343         int j;
 344         for (j = 0; j < 2; j++) {
 345             grid_face *f = j ? e->face2 : e->face1;
 346             int k, k2;
 347             if (f == NULL) continue;
 348             /* Find one of the dots around the face */
 349             for (k = 0; k < f->order; k++) {
 350                 if (f->dots[k] == e->dot1)
 351                     break; /* found dot1 */
 352             }
 353             assert(k != f->order); /* Must find the dot around this face */
 354
 355             /* Labelling scheme: as we walk clockwise around the face,
 356              * starting at dot0 (f->dots[0]), we hit:
 357              * (dot0), edge0, dot1, edge1, dot2,...
 358              *
 359              *     0
 360              *  0-----1
 361              *        |
 362              *        |1
 363              *        |
 364              *  3-----2
 365              *     2
 366              *
 367              * Therefore, edgeK joins dotK and dot{K+1}
 368              */
 369
 370             /* Around this face, either the next dot or the previous dot
 371              * must be e->dot2.  Otherwise the edge is wrong. */
 372             k2 = k + 1;
 373             if (k2 == f->order)
 374                 k2 = 0;
 375             if (f->dots[k2] == e->dot2) {
 376                 /* dot1(k) and dot2(k2) go clockwise around this face, so add
 377                  * this edge at position k (see diagram). */
 378                 assert(f->edges[k] == NULL);
 379                 f->edges[k] = e;
 380                 continue;
 381             }
 382             /* Try previous dot */
 383             k2 = k - 1;
 384             if (k2 == -1)
 385                 k2 = f->order - 1;
 386             if (f->dots[k2] == e->dot2) {
 387                 /* dot1(k) and dot2(k2) go anticlockwise around this face. */
 388                 assert(f->edges[k2] == NULL);
 389                 f->edges[k2] = e;
 390                 continue;
 391             }
 392             assert(!"Grid broken: bad edge-face relationship");
 393         }
 394     }
 395
 396     /* ====== Stage 3 ======
 397      * For each dot, build its edge-list and face-list.
 398      */
 399
 400     /* We don't know how many edges/faces go around each dot, so we can't
 401      * allocate the right space for these lists.  Pre-compute the sizes by
 402      * iterating over each edge and recording a tally against each dot. */
 403     for (i = 0; i < g->num_dots; i++) {
 404         g->dots[i].order = 0;
 405     }
 406     for (i = 0; i < g->num_edges; i++) {
 407         grid_edge *e = g->edges + i;
 408         ++(e->dot1->order);
 409         ++(e->dot2->order);
 410     }
 411     /* Now we have the sizes, pre-allocate the edge and face lists. */
 412     for (i = 0; i < g->num_dots; i++) {
 413         grid_dot *d = g->dots + i;
 414         int j;
 415         assert(d->order >= 2); /* sanity check */
 416         d->edges = snewn(d->order, grid_edge*);
 417         d->faces = snewn(d->order, grid_face*);
 418         for (j = 0; j < d->order; j++) {
 419             d->edges[j] = NULL;
 420             d->faces[j] = NULL;
 421         }
 422     }
 423     /* For each dot, need to find a face that touches it, so we can seed
 424      * the edge-face-edge-face process around each dot. */
 425     for (i = 0; i < g->num_faces; i++) {
 426         grid_face *f = g->faces + i;
 427         int j;
 428         for (j = 0; j < f->order; j++) {
 429             grid_dot *d = f->dots[j];
 430             d->faces[0] = f;
 431         }
 432     }
 433     /* Each dot now has a face in its first slot.  Generate the remaining
 434      * faces and edges around the dot, by searching both clockwise and
 435      * anticlockwise from the first face.  Need to do both directions,
 436      * because of the possibility of hitting the infinite face, which
 437      * blocks progress.  But there's only one such face, so we will
 438      * succeed in finding every edge and face this way. */
 439     for (i = 0; i < g->num_dots; i++) {
 440         grid_dot *d = g->dots + i;
 441         int current_face1 = 0; /* ascends clockwise */
 442         int current_face2 = 0; /* descends anticlockwise */
 443
 444         /* Labelling scheme: as we walk clockwise around the dot, starting
 445          * at face0 (d->faces[0]), we hit:
 446          * (face0), edge0, face1, edge1, face2,...
 447          *
 448          *       0
 449          *       |
 450          *    0  |  1
 451          *       |
 452          *  -----d-----1
 453          *       |
 454          *       |  2
 455          *       |
 456          *       2
 457          *
 458          * So, for example, face1 should be joined to edge0 and edge1,
 459          * and those edges should appear in an anticlockwise sense around
 460          * that face (see diagram). */
 461
 462         /* clockwise search */
 463         while (TRUE) {
 464             grid_face *f = d->faces[current_face1];
 465             grid_edge *e;
 466             int j;
 467             assert(f != NULL);
 468             /* find dot around this face */
 469             for (j = 0; j < f->order; j++) {
 470                 if (f->dots[j] == d)
 471                     break;
 472             }
 473             assert(j != f->order); /* must find dot */
 474
 475             /* Around f, required edge is anticlockwise from the dot.  See
 476              * the other labelling scheme higher up, for why we subtract 1
 477              * from j. */
 478             j--;
 479             if (j == -1)
 480                 j = f->order - 1;
 481             e = f->edges[j];
 482             d->edges[current_face1] = e; /* set edge */
 483             current_face1++;
 484             if (current_face1 == d->order)
 485                 break;
 486             else {
 487                 /* set face */
 488                 d->faces[current_face1] =
 489                     (e->face1 == f) ? e->face2 : e->face1;
 490                 if (d->faces[current_face1] == NULL)
 491                     break; /* cannot progress beyond infinite face */
 492             }
 493         }
 494         /* If the clockwise search made it all the way round, don't need to
 495          * bother with the anticlockwise search. */
 496         if (current_face1 == d->order)
 497             continue; /* this dot is complete, move on to next dot */
 498
 499         /* anticlockwise search */
 500         while (TRUE) {
 501             grid_face *f = d->faces[current_face2];
 502             grid_edge *e;
 503             int j;
 504             assert(f != NULL);
 505             /* find dot around this face */
 506             for (j = 0; j < f->order; j++) {
 507                 if (f->dots[j] == d)
 508                     break;
 509             }
 510             assert(j != f->order); /* must find dot */
 511
 512             /* Around f, required edge is clockwise from the dot. */
 513             e = f->edges[j];
 514
 515             current_face2--;
 516             if (current_face2 == -1)
 517                 current_face2 = d->order - 1;
 518             d->edges[current_face2] = e; /* set edge */
 519
 520             /* set face */
 521             if (current_face2 == current_face1)
 522                 break;
 523             d->faces[current_face2] =
 524                     (e->face1 == f) ? e->face2 : e->face1;
 525             /* There's only 1 infinite face, so we must get all the way
 526              * to current_face1 before we hit it. */
 527             assert(d->faces[current_face2]);
 528         }
 529     }
 530
 531     /* ====== Stage 4 ======
 532      * Compute other grid settings
 533      */
 534
 535     /* Bounding rectangle */
 536     for (i = 0; i < g->num_dots; i++) {
 537         grid_dot *d = g->dots + i;
 538         if (i == 0) {
 539             g->lowest_x = g->highest_x = d->x;
 540             g->lowest_y = g->highest_y = d->y;
 541         } else {
 542             g->lowest_x = min(g->lowest_x, d->x);
 543             g->highest_x = max(g->highest_x, d->x);
 544             g->lowest_y = min(g->lowest_y, d->y);
 545             g->highest_y = max(g->highest_y, d->y);
 546         }
 547     }
 548
 549 #ifdef DEBUG_GRID
 550     grid_print_derived(g);
 551 #endif
 552 }
 553
 554 /* Helpers for making grid-generation easier.  These functions are only
 555  * intended for use during grid generation. */
 556
 557 /* Comparison function for the (tree234) sorted dot list */
 558 static int grid_point_cmp_fn(void *v1, void *v2)
 559 {
 560     grid_dot *p1 = v1;
 561     grid_dot *p2 = v2;
 562     if (p1->y != p2->y)
 563         return p2->y - p1->y;
 564     else
 565         return p2->x - p1->x;
 566 }
 567 /* Add a new face to the grid, with its dot list allocated.
 568  * Assumes there's enough space allocated for the new face in grid->faces */
 569 static void grid_face_add_new(grid *g, int face_size)
 570 {
 571     int i;
 572     grid_face *new_face = g->faces + g->num_faces;
 573     new_face->order = face_size;
 574     new_face->dots = snewn(face_size, grid_dot*);
 575     for (i = 0; i < face_size; i++)
 576         new_face->dots[i] = NULL;
 577     new_face->edges = NULL;
 578     g->num_faces++;
 579 }
 580 /* Assumes dot list has enough space */
 581 static grid_dot *grid_dot_add_new(grid *g, int x, int y)
 582 {
 583     grid_dot *new_dot = g->dots + g->num_dots;
 584     new_dot->order = 0;
 585     new_dot->edges = NULL;
 586     new_dot->faces = NULL;
 587     new_dot->x = x;
 588     new_dot->y = y;
 589     g->num_dots++;
 590     return new_dot;
 591 }
 592 /* Retrieve a dot with these (x,y) coordinates.  Either return an existing dot
 593  * in the dot_list, or add a new dot to the grid (and the dot_list) and
 594  * return that.
 595  * Assumes g->dots has enough capacity allocated */
 596 static grid_dot *grid_get_dot(grid *g, tree234 *dot_list, int x, int y)
 597 {
 598     grid_dot test, *ret;
 599
 600     test.order = 0;
 601     test.edges = NULL;
 602     test.faces = NULL;
 603     test.x = x;
 604     test.y = y;
 605     ret = find234(dot_list, &test, NULL);
 606     if (ret)
 607         return ret;
 608
 609     ret = grid_dot_add_new(g, x, y);
 610     add234(dot_list, ret);
 611     return ret;
 612 }
 613
 614 /* Sets the last face of the grid to include this dot, at this position
 615  * around the face. Assumes num_faces is at least 1 (a new face has
 616  * previously been added, with the required number of dots allocated) */
 617 static void grid_face_set_dot(grid *g, grid_dot *d, int position)
 618 {
 619     grid_face *last_face = g->faces + g->num_faces - 1;
 620     last_face->dots[position] = d;
 621 }
 622
 623 /* ------ Generate various types of grid ------ */
 624
 625 /* General method is to generate faces, by calculating their dot coordinates.
 626  * As new faces are added, we keep track of all the dots so we can tell when
 627  * a new face reuses an existing dot.  For example, two squares touching at an
 628  * edge would generate six unique dots: four dots from the first face, then
 629  * two additional dots for the second face, because we detect the other two
 630  * dots have already been taken up.  This list is stored in a tree234
 631  * called "points".  No extra memory-allocation needed here - we store the
 632  * actual grid_dot* pointers, which all point into the g->dots list.
 633  * For this reason, we have to calculate coordinates in such a way as to
 634  * eliminate any rounding errors, so we can detect when a dot on one
 635  * face precisely lands on a dot of a different face.  No floating-point
 636  * arithmetic here!
 637  */
 638
 639 grid *grid_new_square(int width, int height)
 640 {
 641     int x, y;
 642     /* Side length */
 643     int a = 20;
 644
 645     /* Upper bounds - don't have to be exact */
 646     int max_faces = width * height;
 647     int max_dots = (width + 1) * (height + 1);
 648
 649     tree234 *points;
 650
 651     grid *g = grid_new();
 652     g->tilesize = a;
 653     g->faces = snewn(max_faces, grid_face);
 654     g->dots = snewn(max_dots, grid_dot);
 655
 656     points = newtree234(grid_point_cmp_fn);
 657
 658     /* generate square faces */
 659     for (y = 0; y < height; y++) {
 660         for (x = 0; x < width; x++) {
 661             grid_dot *d;
 662             /* face position */
 663             int px = a * x;
 664             int py = a * y;
 665
 666             grid_face_add_new(g, 4);
 667             d = grid_get_dot(g, points, px, py);
 668             grid_face_set_dot(g, d, 0);
 669             d = grid_get_dot(g, points, px + a, py);
 670             grid_face_set_dot(g, d, 1);
 671             d = grid_get_dot(g, points, px + a, py + a);
 672             grid_face_set_dot(g, d, 2);
 673             d = grid_get_dot(g, points, px, py + a);
 674             grid_face_set_dot(g, d, 3);
 675         }
 676     }
 677
 678     freetree234(points);
 679     assert(g->num_faces <= max_faces);
 680     assert(g->num_dots <= max_dots);
 681
 682     grid_make_consistent(g);
 683     return g;
 684 }
 685
 686 grid *grid_new_honeycomb(int width, int height)
 687 {
 688     int x, y;
 689     /* Vector for side of hexagon - ratio is close to sqrt(3) */
 690     int a = 15;
 691     int b = 26;
 692
 693     /* Upper bounds - don't have to be exact */
 694     int max_faces = width * height;
 695     int max_dots = 2 * (width + 1) * (height + 1);
 696
 697     tree234 *points;
 698
 699     grid *g = grid_new();
 700     g->tilesize = 3 * a;
 701     g->faces = snewn(max_faces, grid_face);
 702     g->dots = snewn(max_dots, grid_dot);
 703
 704     points = newtree234(grid_point_cmp_fn);
 705
 706     /* generate hexagonal faces */
 707     for (y = 0; y < height; y++) {
 708         for (x = 0; x < width; x++) {
 709             grid_dot *d;
 710             /* face centre */
 711             int cx = 3 * a * x;
 712             int cy = 2 * b * y;
 713             if (x % 2)
 714                 cy += b;
 715             grid_face_add_new(g, 6);
 716
 717             d = grid_get_dot(g, points, cx - a, cy - b);
 718             grid_face_set_dot(g, d, 0);
 719             d = grid_get_dot(g, points, cx + a, cy - b);
 720             grid_face_set_dot(g, d, 1);
 721             d = grid_get_dot(g, points, cx + 2*a, cy);
 722             grid_face_set_dot(g, d, 2);
 723             d = grid_get_dot(g, points, cx + a, cy + b);
 724             grid_face_set_dot(g, d, 3);
 725             d = grid_get_dot(g, points, cx - a, cy + b);
 726             grid_face_set_dot(g, d, 4);
 727             d = grid_get_dot(g, points, cx - 2*a, cy);
 728             grid_face_set_dot(g, d, 5);
 729         }
 730     }
 731
 732     freetree234(points);
 733     assert(g->num_faces <= max_faces);
 734     assert(g->num_dots <= max_dots);
 735
 736     grid_make_consistent(g);
 737     return g;
 738 }
 739
 740 /* Doesn't use the previous method of generation, it pre-dates it!
 741  * A triangular grid is just about simple enough to do by "brute force" */
 742 grid *grid_new_triangular(int width, int height)
 743 {
 744     int x,y;
 745
 746     /* Vector for side of triangle - ratio is close to sqrt(3) */
 747     int vec_x = 15;
 748     int vec_y = 26;
 749
 750     int index;
 751
 752     /* convenient alias */
 753     int w = width + 1;
 754
 755     grid *g = grid_new();
 756     g->tilesize = 18; /* adjust to your taste */
 757
 758     g->num_faces = width * height * 2;
 759     g->num_dots = (width + 1) * (height + 1);
 760     g->faces = snewn(g->num_faces, grid_face);
 761     g->dots = snewn(g->num_dots, grid_dot);
 762
 763     /* generate dots */
 764     index = 0;
 765     for (y = 0; y <= height; y++) {
 766         for (x = 0; x <= width; x++) {
 767             grid_dot *d = g->dots + index;
 768             /* odd rows are offset to the right */
 769             d->order = 0;
 770             d->edges = NULL;
 771             d->faces = NULL;
 772             d->x = x * 2 * vec_x + ((y % 2) ? vec_x : 0);
 773             d->y = y * vec_y;
 774             index++;
 775         }
 776     }
 777
 778     /* generate faces */
 779     index = 0;
 780     for (y = 0; y < height; y++) {
 781         for (x = 0; x < width; x++) {
 782             /* initialise two faces for this (x,y) */
 783             grid_face *f1 = g->faces + index;
 784             grid_face *f2 = f1 + 1;
 785             f1->edges = NULL;
 786             f1->order = 3;
 787             f1->dots = snewn(f1->order, grid_dot*);
 788             f2->edges = NULL;
 789             f2->order = 3;
 790             f2->dots = snewn(f2->order, grid_dot*);
 791
 792             /* face descriptions depend on whether the row-number is
 793              * odd or even */
 794             if (y % 2) {
 795                 f1->dots[0] = g->dots + y       * w + x;
 796                 f1->dots[1] = g->dots + (y + 1) * w + x + 1;
 797                 f1->dots[2] = g->dots + (y + 1) * w + x;
 798                 f2->dots[0] = g->dots + y       * w + x;
 799                 f2->dots[1] = g->dots + y       * w + x + 1;
 800                 f2->dots[2] = g->dots + (y + 1) * w + x + 1;
 801             } else {
 802                 f1->dots[0] = g->dots + y       * w + x;
 803                 f1->dots[1] = g->dots + y       * w + x + 1;
 804                 f1->dots[2] = g->dots + (y + 1) * w + x;
 805                 f2->dots[0] = g->dots + y       * w + x + 1;
 806                 f2->dots[1] = g->dots + (y + 1) * w + x + 1;
 807                 f2->dots[2] = g->dots + (y + 1) * w + x;
 808             }
 809             index += 2;
 810         }
 811     }
 812
 813     grid_make_consistent(g);
 814     return g;
 815 }
 816
 817 grid *grid_new_snubsquare(int width, int height)
 818 {
 819     int x, y;
 820     /* Vector for side of triangle - ratio is close to sqrt(3) */
 821     int a = 15;
 822     int b = 26;
 823
 824     /* Upper bounds - don't have to be exact */
 825     int max_faces = 3 * width * height;
 826     int max_dots = 2 * (width + 1) * (height + 1);
 827
 828     tree234 *points;
 829
 830     grid *g = grid_new();
 831     g->tilesize = 18;
 832     g->faces = snewn(max_faces, grid_face);
 833     g->dots = snewn(max_dots, grid_dot);
 834
 835     points = newtree234(grid_point_cmp_fn);
 836
 837     for (y = 0; y < height; y++) {
 838         for (x = 0; x < width; x++) {
 839             grid_dot *d;
 840             /* face position */
 841             int px = (a + b) * x;
 842             int py = (a + b) * y;
 843
 844             /* generate square faces */
 845             grid_face_add_new(g, 4);
 846             if ((x + y) % 2) {
 847                 d = grid_get_dot(g, points, px + a, py);
 848                 grid_face_set_dot(g, d, 0);
 849                 d = grid_get_dot(g, points, px + a + b, py + a);
 850                 grid_face_set_dot(g, d, 1);
 851                 d = grid_get_dot(g, points, px + b, py + a + b);
 852                 grid_face_set_dot(g, d, 2);
 853                 d = grid_get_dot(g, points, px, py + b);
 854                 grid_face_set_dot(g, d, 3);
 855             } else {
 856                 d = grid_get_dot(g, points, px + b, py);
 857                 grid_face_set_dot(g, d, 0);
 858                 d = grid_get_dot(g, points, px + a + b, py + b);
 859                 grid_face_set_dot(g, d, 1);
 860                 d = grid_get_dot(g, points, px + a, py + a + b);
 861                 grid_face_set_dot(g, d, 2);
 862                 d = grid_get_dot(g, points, px, py + a);
 863                 grid_face_set_dot(g, d, 3);
 864             }
 865
 866             /* generate up/down triangles */
 867             if (x > 0) {
 868                 grid_face_add_new(g, 3);
 869                 if ((x + y) % 2) {
 870                     d = grid_get_dot(g, points, px + a, py);
 871                     grid_face_set_dot(g, d, 0);
 872                     d = grid_get_dot(g, points, px, py + b);
 873                     grid_face_set_dot(g, d, 1);
 874                     d = grid_get_dot(g, points, px - a, py);
 875                     grid_face_set_dot(g, d, 2);
 876                 } else {
 877                     d = grid_get_dot(g, points, px, py + a);
 878                     grid_face_set_dot(g, d, 0);
 879                     d = grid_get_dot(g, points, px + a, py + a + b);
 880                     grid_face_set_dot(g, d, 1);
 881                     d = grid_get_dot(g, points, px - a, py + a + b);
 882                     grid_face_set_dot(g, d, 2);
 883                 }
 884             }
 885
 886             /* generate left/right triangles */
 887             if (y > 0) {
 888                 grid_face_add_new(g, 3);
 889                 if ((x + y) % 2) {
 890                     d = grid_get_dot(g, points, px + a, py);
 891                     grid_face_set_dot(g, d, 0);
 892                     d = grid_get_dot(g, points, px + a + b, py - a);
 893                     grid_face_set_dot(g, d, 1);
 894                     d = grid_get_dot(g, points, px + a + b, py + a);
 895                     grid_face_set_dot(g, d, 2);
 896                 } else {
 897                     d = grid_get_dot(g, points, px, py - a);
 898                     grid_face_set_dot(g, d, 0);
 899                     d = grid_get_dot(g, points, px + b, py);
 900                     grid_face_set_dot(g, d, 1);
 901                     d = grid_get_dot(g, points, px, py + a);
 902                     grid_face_set_dot(g, d, 2);
 903                 }
 904             }
 905         }
 906     }
 907
 908     freetree234(points);
 909     assert(g->num_faces <= max_faces);
 910     assert(g->num_dots <= max_dots);
 911
 912     grid_make_consistent(g);
 913     return g;
 914 }
 915
 916 grid *grid_new_cairo(int width, int height)
 917 {
 918     int x, y;
 919     /* Vector for side of pentagon - ratio is close to (4+sqrt(7))/3 */
 920     int a = 14;
 921     int b = 31;
 922
 923     /* Upper bounds - don't have to be exact */
 924     int max_faces = 2 * width * height;
 925     int max_dots = 3 * (width + 1) * (height + 1);
 926
 927     tree234 *points;
 928
 929     grid *g = grid_new();
 930     g->tilesize = 40;
 931     g->faces = snewn(max_faces, grid_face);
 932     g->dots = snewn(max_dots, grid_dot);
 933
 934     points = newtree234(grid_point_cmp_fn);
 935
 936     for (y = 0; y < height; y++) {
 937         for (x = 0; x < width; x++) {
 938             grid_dot *d;
 939             /* cell position */
 940             int px = 2 * b * x;
 941             int py = 2 * b * y;
 942
 943             /* horizontal pentagons */
 944             if (y > 0) {
 945                 grid_face_add_new(g, 5);
 946                 if ((x + y) % 2) {
 947                     d = grid_get_dot(g, points, px + a, py - b);
 948                     grid_face_set_dot(g, d, 0);
 949                     d = grid_get_dot(g, points, px + 2*b - a, py - b);
 950                     grid_face_set_dot(g, d, 1);
 951                     d = grid_get_dot(g, points, px + 2*b, py);
 952                     grid_face_set_dot(g, d, 2);
 953                     d = grid_get_dot(g, points, px + b, py + a);
 954                     grid_face_set_dot(g, d, 3);
 955                     d = grid_get_dot(g, points, px, py);
 956                     grid_face_set_dot(g, d, 4);
 957                 } else {
 958                     d = grid_get_dot(g, points, px, py);
 959                     grid_face_set_dot(g, d, 0);
 960                     d = grid_get_dot(g, points, px + b, py - a);
 961                     grid_face_set_dot(g, d, 1);
 962                     d = grid_get_dot(g, points, px + 2*b, py);
 963                     grid_face_set_dot(g, d, 2);
 964                     d = grid_get_dot(g, points, px + 2*b - a, py + b);
 965                     grid_face_set_dot(g, d, 3);
 966                     d = grid_get_dot(g, points, px + a, py + b);
 967                     grid_face_set_dot(g, d, 4);
 968                 }
 969             }
 970             /* vertical pentagons */
 971             if (x > 0) {
 972                 grid_face_add_new(g, 5);
 973                 if ((x + y) % 2) {
 974                     d = grid_get_dot(g, points, px, py);
 975                     grid_face_set_dot(g, d, 0);
 976                     d = grid_get_dot(g, points, px + b, py + a);
 977                     grid_face_set_dot(g, d, 1);
 978                     d = grid_get_dot(g, points, px + b, py + 2*b - a);
 979                     grid_face_set_dot(g, d, 2);
 980                     d = grid_get_dot(g, points, px, py + 2*b);
 981                     grid_face_set_dot(g, d, 3);
 982                     d = grid_get_dot(g, points, px - a, py + b);
 983                     grid_face_set_dot(g, d, 4);
 984                 } else {
 985                     d = grid_get_dot(g, points, px, py);
 986                     grid_face_set_dot(g, d, 0);
 987                     d = grid_get_dot(g, points, px + a, py + b);
 988                     grid_face_set_dot(g, d, 1);
 989                     d = grid_get_dot(g, points, px, py + 2*b);
 990                     grid_face_set_dot(g, d, 2);
 991                     d = grid_get_dot(g, points, px - b, py + 2*b - a);
 992                     grid_face_set_dot(g, d, 3);
 993                     d = grid_get_dot(g, points, px - b, py + a);
 994                     grid_face_set_dot(g, d, 4);
 995                 }
 996             }
 997         }
 998     }
 999
1000     freetree234(points);
1001     assert(g->num_faces <= max_faces);
1002     assert(g->num_dots <= max_dots);
1003
1004     grid_make_consistent(g);
1005     return g;
1006 }
1007
1008 grid *grid_new_greathexagonal(int width, int height)
1009 {
1010     int x, y;
1011     /* Vector for side of triangle - ratio is close to sqrt(3) */
1012     int a = 15;
1013     int b = 26;
1014
1015     /* Upper bounds - don't have to be exact */
1016     int max_faces = 6 * (width + 1) * (height + 1);
1017     int max_dots = 6 * width * height;
1018
1019     tree234 *points;
1020
1021     grid *g = grid_new();
1022     g->tilesize = 18;
1023     g->faces = snewn(max_faces, grid_face);
1024     g->dots = snewn(max_dots, grid_dot);
1025
1026     points = newtree234(grid_point_cmp_fn);
1027
1028     for (y = 0; y < height; y++) {
1029         for (x = 0; x < width; x++) {
1030             grid_dot *d;
1031             /* centre of hexagon */
1032             int px = (3*a + b) * x;
1033             int py = (2*a + 2*b) * y;
1034             if (x % 2)
1035                 py += a + b;
1036
1037             /* hexagon */
1038             grid_face_add_new(g, 6);
1039             d = grid_get_dot(g, points, px - a, py - b);
1040             grid_face_set_dot(g, d, 0);
1041             d = grid_get_dot(g, points, px + a, py - b);
1042             grid_face_set_dot(g, d, 1);
1043             d = grid_get_dot(g, points, px + 2*a, py);
1044             grid_face_set_dot(g, d, 2);
1045             d = grid_get_dot(g, points, px + a, py + b);
1046             grid_face_set_dot(g, d, 3);
1047             d = grid_get_dot(g, points, px - a, py + b);
1048             grid_face_set_dot(g, d, 4);
1049             d = grid_get_dot(g, points, px - 2*a, py);
1050             grid_face_set_dot(g, d, 5);
1051
1052             /* square below hexagon */
1053             if (y < height - 1) {
1054                 grid_face_add_new(g, 4);
1055                 d = grid_get_dot(g, points, px - a, py + b);
1056                 grid_face_set_dot(g, d, 0);
1057                 d = grid_get_dot(g, points, px + a, py + b);
1058                 grid_face_set_dot(g, d, 1);
1059                 d = grid_get_dot(g, points, px + a, py + 2*a + b);
1060                 grid_face_set_dot(g, d, 2);
1061                 d = grid_get_dot(g, points, px - a, py + 2*a + b);
1062                 grid_face_set_dot(g, d, 3);
1063             }
1064
1065             /* square below right */
1066             if ((x < width - 1) && (((x % 2) == 0) || (y < height - 1))) {
1067                 grid_face_add_new(g, 4);
1068                 d = grid_get_dot(g, points, px + 2*a, py);
1069                 grid_face_set_dot(g, d, 0);
1070                 d = grid_get_dot(g, points, px + 2*a + b, py + a);
1071                 grid_face_set_dot(g, d, 1);
1072                 d = grid_get_dot(g, points, px + a + b, py + a + b);
1073                 grid_face_set_dot(g, d, 2);
1074                 d = grid_get_dot(g, points, px + a, py + b);
1075                 grid_face_set_dot(g, d, 3);
1076             }
1077
1078             /* square below left */
1079             if ((x > 0) && (((x % 2) == 0) || (y < height - 1))) {
1080                 grid_face_add_new(g, 4);
1081                 d = grid_get_dot(g, points, px - 2*a, py);
1082                 grid_face_set_dot(g, d, 0);
1083                 d = grid_get_dot(g, points, px - a, py + b);
1084                 grid_face_set_dot(g, d, 1);
1085                 d = grid_get_dot(g, points, px - a - b, py + a + b);
1086                 grid_face_set_dot(g, d, 2);
1087                 d = grid_get_dot(g, points, px - 2*a - b, py + a);
1088                 grid_face_set_dot(g, d, 3);
1089             }
1090
1091             /* Triangle below right */
1092             if ((x < width - 1) && (y < height - 1)) {
1093                 grid_face_add_new(g, 3);
1094                 d = grid_get_dot(g, points, px + a, py + b);
1095                 grid_face_set_dot(g, d, 0);
1096                 d = grid_get_dot(g, points, px + a + b, py + a + b);
1097                 grid_face_set_dot(g, d, 1);
1098                 d = grid_get_dot(g, points, px + a, py + 2*a + b);
1099                 grid_face_set_dot(g, d, 2);
1100             }
1101
1102             /* Triangle below left */
1103             if ((x > 0) && (y < height - 1)) {
1104                 grid_face_add_new(g, 3);
1105                 d = grid_get_dot(g, points, px - a, py + b);
1106                 grid_face_set_dot(g, d, 0);
1107                 d = grid_get_dot(g, points, px - a, py + 2*a + b);
1108                 grid_face_set_dot(g, d, 1);
1109                 d = grid_get_dot(g, points, px - a - b, py + a + b);
1110                 grid_face_set_dot(g, d, 2);
1111             }
1112         }
1113     }
1114
1115     freetree234(points);
1116     assert(g->num_faces <= max_faces);
1117     assert(g->num_dots <= max_dots);
1118
1119     grid_make_consistent(g);
1120     return g;
1121 }
1122
1123 grid *grid_new_octagonal(int width, int height)
1124 {
1125     int x, y;
1126     /* b/a approx sqrt(2) */
1127     int a = 29;
1128     int b = 41;
1129
1130     /* Upper bounds - don't have to be exact */
1131     int max_faces = 2 * width * height;
1132     int max_dots = 4 * (width + 1) * (height + 1);
1133
1134     tree234 *points;
1135
1136     grid *g = grid_new();
1137     g->tilesize = 40;
1138     g->faces = snewn(max_faces, grid_face);
1139     g->dots = snewn(max_dots, grid_dot);
1140
1141     points = newtree234(grid_point_cmp_fn);
1142
1143     for (y = 0; y < height; y++) {
1144         for (x = 0; x < width; x++) {
1145             grid_dot *d;
1146             /* cell position */
1147             int px = (2*a + b) * x;
1148             int py = (2*a + b) * y;
1149             /* octagon */
1150             grid_face_add_new(g, 8);
1151             d = grid_get_dot(g, points, px + a, py);
1152             grid_face_set_dot(g, d, 0);
1153             d = grid_get_dot(g, points, px + a + b, py);
1154             grid_face_set_dot(g, d, 1);
1155             d = grid_get_dot(g, points, px + 2*a + b, py + a);
1156             grid_face_set_dot(g, d, 2);
1157             d = grid_get_dot(g, points, px + 2*a + b, py + a + b);
1158             grid_face_set_dot(g, d, 3);
1159             d = grid_get_dot(g, points, px + a + b, py + 2*a + b);
1160             grid_face_set_dot(g, d, 4);
1161             d = grid_get_dot(g, points, px + a, py + 2*a + b);
1162             grid_face_set_dot(g, d, 5);
1163             d = grid_get_dot(g, points, px, py + a + b);
1164             grid_face_set_dot(g, d, 6);
1165             d = grid_get_dot(g, points, px, py + a);
1166             grid_face_set_dot(g, d, 7);
1167
1168             /* diamond */
1169             if ((x > 0) && (y > 0)) {
1170                 grid_face_add_new(g, 4);
1171                 d = grid_get_dot(g, points, px, py - a);
1172                 grid_face_set_dot(g, d, 0);
1173                 d = grid_get_dot(g, points, px + a, py);
1174                 grid_face_set_dot(g, d, 1);
1175                 d = grid_get_dot(g, points, px, py + a);
1176                 grid_face_set_dot(g, d, 2);
1177                 d = grid_get_dot(g, points, px - a, py);
1178                 grid_face_set_dot(g, d, 3);
1179             }
1180         }
1181     }
1182
1183     freetree234(points);
1184     assert(g->num_faces <= max_faces);
1185     assert(g->num_dots <= max_dots);
1186
1187     grid_make_consistent(g);
1188     return g;
1189 }
1190
1191 grid *grid_new_kites(int width, int height)
1192 {
1193     int x, y;
1194     /* b/a approx sqrt(3) */
1195     int a = 15;
1196     int b = 26;
1197
1198     /* Upper bounds - don't have to be exact */
1199     int max_faces = 6 * width * height;
1200     int max_dots = 6 * (width + 1) * (height + 1);
1201
1202     tree234 *points;
1203
1204     grid *g = grid_new();
1205     g->tilesize = 40;
1206     g->faces = snewn(max_faces, grid_face);
1207     g->dots = snewn(max_dots, grid_dot);
1208
1209     points = newtree234(grid_point_cmp_fn);
1210
1211     for (y = 0; y < height; y++) {
1212         for (x = 0; x < width; x++) {
1213             grid_dot *d;
1214             /* position of order-6 dot */
1215             int px = 4*b * x;
1216             int py = 6*a * y;
1217             if (y % 2)
1218                 px += 2*b;
1219
1220             /* kite pointing up-left */
1221             grid_face_add_new(g, 4);
1222             d = grid_get_dot(g, points, px, py);
1223             grid_face_set_dot(g, d, 0);
1224             d = grid_get_dot(g, points, px + 2*b, py);
1225             grid_face_set_dot(g, d, 1);
1226             d = grid_get_dot(g, points, px + 2*b, py + 2*a);
1227             grid_face_set_dot(g, d, 2);
1228             d = grid_get_dot(g, points, px + b, py + 3*a);
1229             grid_face_set_dot(g, d, 3);
1230
1231             /* kite pointing up */
1232             grid_face_add_new(g, 4);
1233             d = grid_get_dot(g, points, px, py);
1234             grid_face_set_dot(g, d, 0);
1235             d = grid_get_dot(g, points, px + b, py + 3*a);
1236             grid_face_set_dot(g, d, 1);
1237             d = grid_get_dot(g, points, px, py + 4*a);
1238             grid_face_set_dot(g, d, 2);
1239             d = grid_get_dot(g, points, px - b, py + 3*a);
1240             grid_face_set_dot(g, d, 3);
1241
1242             /* kite pointing up-right */
1243             grid_face_add_new(g, 4);
1244             d = grid_get_dot(g, points, px, py);
1245             grid_face_set_dot(g, d, 0);
1246             d = grid_get_dot(g, points, px - b, py + 3*a);
1247             grid_face_set_dot(g, d, 1);
1248             d = grid_get_dot(g, points, px - 2*b, py + 2*a);
1249             grid_face_set_dot(g, d, 2);
1250             d = grid_get_dot(g, points, px - 2*b, py);
1251             grid_face_set_dot(g, d, 3);
1252
1253             /* kite pointing down-right */
1254             grid_face_add_new(g, 4);
1255             d = grid_get_dot(g, points, px, py);
1256             grid_face_set_dot(g, d, 0);
1257             d = grid_get_dot(g, points, px - 2*b, py);
1258             grid_face_set_dot(g, d, 1);
1259             d = grid_get_dot(g, points, px - 2*b, py - 2*a);
1260             grid_face_set_dot(g, d, 2);
1261             d = grid_get_dot(g, points, px - b, py - 3*a);
1262             grid_face_set_dot(g, d, 3);
1263
1264             /* kite pointing down */
1265             grid_face_add_new(g, 4);
1266             d = grid_get_dot(g, points, px, py);
1267             grid_face_set_dot(g, d, 0);
1268             d = grid_get_dot(g, points, px - b, py - 3*a);
1269             grid_face_set_dot(g, d, 1);
1270             d = grid_get_dot(g, points, px, py - 4*a);
1271             grid_face_set_dot(g, d, 2);
1272             d = grid_get_dot(g, points, px + b, py - 3*a);
1273             grid_face_set_dot(g, d, 3);
1274
1275             /* kite pointing down-left */
1276             grid_face_add_new(g, 4);
1277             d = grid_get_dot(g, points, px, py);
1278             grid_face_set_dot(g, d, 0);
1279             d = grid_get_dot(g, points, px + b, py - 3*a);
1280             grid_face_set_dot(g, d, 1);
1281             d = grid_get_dot(g, points, px + 2*b, py - 2*a);
1282             grid_face_set_dot(g, d, 2);
1283             d = grid_get_dot(g, points, px + 2*b, py);
1284             grid_face_set_dot(g, d, 3);
1285         }
1286     }
1287
1288     freetree234(points);
1289     assert(g->num_faces <= max_faces);
1290     assert(g->num_dots <= max_dots);
1291
1292     grid_make_consistent(g);
1293     return g;
1294 }
1295
1296 grid *grid_new_floret(int width, int height)
1297 {
1298     int x, y;
1299     /* Vectors for sides; weird numbers needed to keep puzzle aligned with window
1300      * -py/px is close to tan(30 - atan(sqrt(3)/9))
1301      * using py=26 makes everything lean to the left, rather than right
1302      */
1303     int px = 75, py = -26;       /* |( 75, -26)| = 79.43 */
1304     int qx = 4*px/5, qy = -py*2; /* |( 60,  52)| = 79.40 */
1305     int rx = qx-px, ry = qy-py;  /* |(-15,  78)| = 79.38 */
1306
1307     /* Upper bounds - don't have to be exact */
1308     int max_faces = 6 * width * height;
1309     int max_dots = 9 * (width + 1) * (height + 1);
1310
1311     tree234 *points;
1312
1313     grid *g = grid_new();
1314     g->tilesize = 2 * px;
1315     g->faces = snewn(max_faces, grid_face);
1316     g->dots = snewn(max_dots, grid_dot);
1317
1318     points = newtree234(grid_point_cmp_fn);
1319
1320     /* generate pentagonal faces */
1321     for (y = 0; y < height; y++) {
1322         for (x = 0; x < width; x++) {
1323             grid_dot *d;
1324             /* face centre */
1325             int cx = (6*px+3*qx)/2 * x;
1326             int cy = (4*py-5*qy) * y;
1327             if (x % 2)
1328                 cy -= (4*py-5*qy)/2;
1329             else if (y && y == height-1)
1330                 continue; /* make better looking grids?  try 3x3 for instance */
1331
1332             grid_face_add_new(g, 5);
1333             d = grid_get_dot(g, points, cx        , cy        ); grid_face_set_dot(g, d, 0);
1334             d = grid_get_dot(g, points, cx+2*rx   , cy+2*ry   ); grid_face_set_dot(g, d, 1);
1335             d = grid_get_dot(g, points, cx+2*rx+qx, cy+2*ry+qy); grid_face_set_dot(g, d, 2);
1336             d = grid_get_dot(g, points, cx+2*qx+rx, cy+2*qy+ry); grid_face_set_dot(g, d, 3);
1337             d = grid_get_dot(g, points, cx+2*qx   , cy+2*qy   ); grid_face_set_dot(g, d, 4);
1338
1339             grid_face_add_new(g, 5);
1340             d = grid_get_dot(g, points, cx        , cy        ); grid_face_set_dot(g, d, 0);
1341             d = grid_get_dot(g, points, cx+2*qx   , cy+2*qy   ); grid_face_set_dot(g, d, 1);
1342             d = grid_get_dot(g, points, cx+2*qx+px, cy+2*qy+py); grid_face_set_dot(g, d, 2);
1343             d = grid_get_dot(g, points, cx+2*px+qx, cy+2*py+qy); grid_face_set_dot(g, d, 3);
1344             d = grid_get_dot(g, points, cx+2*px   , cy+2*py   ); grid_face_set_dot(g, d, 4);
1345
1346             grid_face_add_new(g, 5);
1347             d = grid_get_dot(g, points, cx        , cy        ); grid_face_set_dot(g, d, 0);
1348             d = grid_get_dot(g, points, cx+2*px   , cy+2*py   ); grid_face_set_dot(g, d, 1);
1349             d = grid_get_dot(g, points, cx+2*px-rx, cy+2*py-ry); grid_face_set_dot(g, d, 2);
1350             d = grid_get_dot(g, points, cx-2*rx+px, cy-2*ry+py); grid_face_set_dot(g, d, 3);
1351             d = grid_get_dot(g, points, cx-2*rx   , cy-2*ry   ); grid_face_set_dot(g, d, 4);
1352
1353             grid_face_add_new(g, 5);
1354             d = grid_get_dot(g, points, cx        , cy        ); grid_face_set_dot(g, d, 0);
1355             d = grid_get_dot(g, points, cx-2*rx   , cy-2*ry   ); grid_face_set_dot(g, d, 1);
1356             d = grid_get_dot(g, points, cx-2*rx-qx, cy-2*ry-qy); grid_face_set_dot(g, d, 2);
1357             d = grid_get_dot(g, points, cx-2*qx-rx, cy-2*qy-ry); grid_face_set_dot(g, d, 3);
1358             d = grid_get_dot(g, points, cx-2*qx   , cy-2*qy   ); grid_face_set_dot(g, d, 4);
1359
1360             grid_face_add_new(g, 5);
1361             d = grid_get_dot(g, points, cx        , cy        ); grid_face_set_dot(g, d, 0);
1362             d = grid_get_dot(g, points, cx-2*qx   , cy-2*qy   ); grid_face_set_dot(g, d, 1);
1363             d = grid_get_dot(g, points, cx-2*qx-px, cy-2*qy-py); grid_face_set_dot(g, d, 2);
1364             d = grid_get_dot(g, points, cx-2*px-qx, cy-2*py-qy); grid_face_set_dot(g, d, 3);
1365             d = grid_get_dot(g, points, cx-2*px   , cy-2*py   ); grid_face_set_dot(g, d, 4);
1366
1367             grid_face_add_new(g, 5);
1368             d = grid_get_dot(g, points, cx        , cy        ); grid_face_set_dot(g, d, 0);
1369             d = grid_get_dot(g, points, cx-2*px   , cy-2*py   ); grid_face_set_dot(g, d, 1);
1370             d = grid_get_dot(g, points, cx-2*px+rx, cy-2*py+ry); grid_face_set_dot(g, d, 2);
1371             d = grid_get_dot(g, points, cx+2*rx-px, cy+2*ry-py); grid_face_set_dot(g, d, 3);
1372             d = grid_get_dot(g, points, cx+2*rx   , cy+2*ry   ); grid_face_set_dot(g, d, 4);
1373         }
1374     }
1375
1376     freetree234(points);
1377     assert(g->num_faces <= max_faces);
1378     assert(g->num_dots <= max_dots);
1379
1380     grid_make_consistent(g);
1381     return g;
1382 }
1383
1384 /* ----------- End of grid generators ------------- */