grid.h

   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 /* Useful macros */
  13 #ifndef SQ
  14 #  define SQ(x) ( (x) * (x) )
  15 #endif
  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 struct grid_edge {
  41   grid_dot *dot1, *dot2;
  42   grid_face *face1, *face2; /* Use NULL for the infinite outside face */
  43 };
  44 struct grid_dot {
  45   int order;
  46   grid_edge **edges;
  47   grid_face **faces; /* A NULL grid_face* means infinite outside face */
  48
  49   /* Position in some fairly arbitrary (Cartesian) coordinate system.
  50    * Use large enough values such that we can get away with
  51    * integer arithmetic, but small enough such that arithmetic
  52    * won't overflow. */
  53   int x, y;
  54 };
  55 typedef struct grid {
  56   /* These are (dynamically allocated) arrays of all the
  57    * faces, edges, dots that are in the grid. */
  58   int num_faces; grid_face *faces;
  59   int num_edges; grid_edge *edges;
  60   int num_dots;  grid_dot *dots;
  61
  62   /* Should be a face roughly near the middle of the grid.
  63    * Used to seed path-generation, and also for nearest-edge
  64    * detection. */
  65   grid_face *middle_face;
  66
  67   /* Cache the bounding-box of the grid, so the drawing-code can quickly
  68    * figure out the proper scaling to draw onto a given area. */
  69   int lowest_x, lowest_y, highest_x, highest_y;
  70
  71   /* A measure of tile size for this grid (in grid coordinates), to help
  72    * the renderer decide how large to draw the grid.
  73    * Roughly the size of a single tile - for example the side-length
  74    * of a square cell. */
  75   int tilesize;
  76
  77   /* We really don't want to copy this monstrosity!
  78    * A grid is immutable once generated.
  79    */
  80   int refcount;
  81 } grid;
  82
  83 grid *grid_new_square(int width, int height);
  84 grid *grid_new_honeycomb(int width, int height);
  85 grid *grid_new_triangular(int width, int height);
  86 grid *grid_new_snubsquare(int width, int height);
  87 grid *grid_new_cairo(int width, int height);
  88 grid *grid_new_greathexagonal(int width, int height);
  89 grid *grid_new_octagonal(int width, int height);
  90 grid *grid_new_kites(int width, int height);
  91
  92 void grid_free(grid *g);
  93
  94 grid_edge *grid_nearest_edge(grid *g, int x, int y);
  95
  96 #endif /* PUZZLES_GRID_H */