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