| 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 | #ifndef PUZZLES_GRID_H |
| 10 | #define PUZZLES_GRID_H |
| 11 | |
| 12 | #include "puzzles.h" /* for random_state */ |
| 13 | |
| 14 | /* Useful macros */ |
| 15 | #define SQ(x) ( (x) * (x) ) |
| 16 | |
| 17 | /* ---------------------------------------------------------------------- |
| 18 | * Grid structures: |
| 19 | * A grid is made up of faces, edges and dots. These structures hold |
| 20 | * the incidence relationships between these types. For example, an |
| 21 | * edge always joins two dots, and is adjacent to two faces. |
| 22 | * The "grid_xxx **" members are lists of pointers which are dynamically |
| 23 | * allocated during grid generation. |
| 24 | * A pointer to a face/edge/dot will always point somewhere inside one of the |
| 25 | * three lists of the main "grid" structure: faces, edges, dots. |
| 26 | * Could have used integer offsets into these lists, but using actual |
| 27 | * pointers instead gives us type-safety. |
| 28 | */ |
| 29 | |
| 30 | /* Need forward declarations */ |
| 31 | typedef struct grid_face grid_face; |
| 32 | typedef struct grid_edge grid_edge; |
| 33 | typedef struct grid_dot grid_dot; |
| 34 | |
| 35 | struct grid_face { |
| 36 | int order; /* Number of edges, also the number of dots */ |
| 37 | grid_edge **edges; /* edges around this face */ |
| 38 | grid_dot **dots; /* corners of this face */ |
| 39 | /* |
| 40 | * For each face, we optionally compute and store its 'incentre'. |
| 41 | * The incentre of a triangle is the centre of a circle tangent to |
| 42 | * all three edges; I generalise the concept to arbitrary polygons |
| 43 | * by defining it to be the centre of the largest circle you can fit |
| 44 | * anywhere in the polygon. It's a useful thing to know because if |
| 45 | * you want to draw any symbol or text in the face (e.g. clue |
| 46 | * numbers in Loopy), that's the place it will most easily fit. |
| 47 | * |
| 48 | * When a grid is first generated, no face has this information |
| 49 | * computed, because it's fiddly to do. You can call |
| 50 | * grid_find_incentre() on a face, and it will fill in ix,iy below |
| 51 | * and set has_incentre to indicate that it's done so. |
| 52 | */ |
| 53 | int has_incentre; |
| 54 | int ix, iy; /* incentre (centre of largest inscribed circle) */ |
| 55 | }; |
| 56 | struct grid_edge { |
| 57 | grid_dot *dot1, *dot2; |
| 58 | grid_face *face1, *face2; /* Use NULL for the infinite outside face */ |
| 59 | }; |
| 60 | struct grid_dot { |
| 61 | int order; |
| 62 | grid_edge **edges; |
| 63 | grid_face **faces; /* A NULL grid_face* means infinite outside face */ |
| 64 | |
| 65 | /* Position in some fairly arbitrary (Cartesian) coordinate system. |
| 66 | * Use large enough values such that we can get away with |
| 67 | * integer arithmetic, but small enough such that arithmetic |
| 68 | * won't overflow. */ |
| 69 | int x, y; |
| 70 | }; |
| 71 | typedef struct grid { |
| 72 | /* These are (dynamically allocated) arrays of all the |
| 73 | * faces, edges, dots that are in the grid. */ |
| 74 | int num_faces; grid_face *faces; |
| 75 | int num_edges; grid_edge *edges; |
| 76 | int num_dots; grid_dot *dots; |
| 77 | |
| 78 | /* Cache the bounding-box of the grid, so the drawing-code can quickly |
| 79 | * figure out the proper scaling to draw onto a given area. */ |
| 80 | int lowest_x, lowest_y, highest_x, highest_y; |
| 81 | |
| 82 | /* A measure of tile size for this grid (in grid coordinates), to help |
| 83 | * the renderer decide how large to draw the grid. |
| 84 | * Roughly the size of a single tile - for example the side-length |
| 85 | * of a square cell. */ |
| 86 | int tilesize; |
| 87 | |
| 88 | /* We really don't want to copy this monstrosity! |
| 89 | * A grid is immutable once generated. |
| 90 | */ |
| 91 | int refcount; |
| 92 | } grid; |
| 93 | |
| 94 | /* Grids are specified by type: GRID_SQUARE, GRID_KITE, etc. */ |
| 95 | |
| 96 | #define GRIDGEN_LIST(A) \ |
| 97 | A(SQUARE,square) \ |
| 98 | A(HONEYCOMB,honeycomb) \ |
| 99 | A(TRIANGULAR,triangular) \ |
| 100 | A(SNUBSQUARE,snubsquare) \ |
| 101 | A(CAIRO,cairo) \ |
| 102 | A(GREATHEXAGONAL,greathexagonal) \ |
| 103 | A(OCTAGONAL,octagonal) \ |
| 104 | A(KITE,kites) \ |
| 105 | A(FLORET,floret) \ |
| 106 | A(DODECAGONAL,dodecagonal) \ |
| 107 | A(GREATDODECAGONAL,greatdodecagonal) \ |
| 108 | A(PENROSE_P2,penrose_p2_kite) \ |
| 109 | A(PENROSE_P3,penrose_p3_thick) |
| 110 | |
| 111 | #define ENUM(upper,lower) GRID_ ## upper, |
| 112 | typedef enum grid_type { GRIDGEN_LIST(ENUM) GRID_TYPE_MAX } grid_type; |
| 113 | #undef ENUM |
| 114 | |
| 115 | /* Free directly after use if non-NULL. Will never contain an underscore |
| 116 | * (so clients can safely use that as a separator). */ |
| 117 | char *grid_new_desc(grid_type type, int width, int height, random_state *rs); |
| 118 | char *grid_validate_desc(grid_type type, int width, int height, char *desc); |
| 119 | |
| 120 | grid *grid_new(grid_type type, int width, int height, char *desc); |
| 121 | |
| 122 | void grid_free(grid *g); |
| 123 | |
| 124 | grid_edge *grid_nearest_edge(grid *g, int x, int y); |
| 125 | |
| 126 | void grid_compute_size(grid_type type, int width, int height, |
| 127 | int *tilesize, int *xextent, int *yextent); |
| 128 | |
| 129 | void grid_find_incentre(grid_face *f); |
| 130 | |
| 131 | #endif /* PUZZLES_GRID_H */ |