pd.if.org Git - hexagon/blob - hexagon.h

   1 #ifndef HEXLIB_H_
   2 #define HEXLIB_H_ 1
   3
   4 struct HL_hex {
   5         int x, y;
   6 };
   7
   8 struct HL_isohex {
   9         int i,j,k;
  10 };
  11
  12 struct HL_point {
  13         double x, y;
  14 };
  15
  16 struct HL_hex HL_hex_xy(int x, int y);
  17
  18 int HL_hex_cmp(struct HL_hex const *a, struct HL_hex const *b);
  19
  20 int HL_hex_eq(struct HL_hex const *a, struct HL_hex const *b);
  21
  22 /*
  23  * this library implements a generic library for hexgrids for games.
  24  * it avoids display issues, other than some general provisions
  25  * for data
  26  *
  27  * This file is written by Nathan Wagner and dedicated to the
  28  * public domain.
  29  */
  30
  31 /* max size for cantor numbers is 16383, or 32767 if non-negative,
  32  * assuming a 32 bit int
  33  */
  34
  35 /* map from cartesian coordinates to hex coords */
  36 /* cartesian coordinates are positive Y up, hex coords
  37  * are positive Y down.  You may need to pass in the
  38  * negative of your Y coordinate
  39  *
  40  * width is the distance from one hexside to the opposite
  41  * hexside.  i and j are the cartesian coordinates of the hex
  42  * the x,y point falls in.  If a point happens to fall exactly
  43  * on a hex boundary, the result will depend on how the machine
  44  * does the floating point math, but should be consistent.
  45  */
  46 struct HL_hex HL_hexbin(double width, double x, double y);
  47 struct HL_hex HL_bin(double x, double y);
  48
  49 /* generate the cantor mapping of a hexes x,y coordinate.
  50  * See http://en.wikipedia.org/wiki/Cantor_pairing_function.
  51  * We modify the basic formula to support negative coordinates
  52  *
  53  * The cantor mapping is *not* a contiguous mapping, as it maps
  54  * onto a triangle, so you can't use the cantor mapping as
  55  * an index into an array.  Or, you can, but the array
  56  * will be (I think) twice as large as it needs to be
  57  *
  58  * See also http://mathworld.wolfram.com/PairingFunction.html
  59  * for a reference to a square mapping by Stein that doesn't
  60  * have this problem, at least for square maps.
  61  *
  62  * We use the cantor mapping so that the generated integer
  63  * is independent of the size of the grid.
  64  */
  65
  66 /* Cantor encoding/decoding functions */
  67 int HL_cantor(struct HL_hex h);
  68 int HL_cantor_xy(int x, int y);
  69 struct HL_hex HL_uncantor(int cantor);
  70
  71 /*
  72  * layout assistance functions
  73  *
  74  * HL_center_x(int cantor) returns the cartesian X coordinate
  75  * of a given hex, assuming a width of 1.0.  Scaling can
  76  * be done by the caller.
  77  *
  78  * Similarly for HL_center_y() and HL_hexcenter()
  79  */
  80 struct HL_point HL_hexcenter(struct HL_hex hex);
  81
  82 /* find a point based on a unit hex, given angle and distance from center,
  83  * where a distance of 1 is on the hex side.  probably not useful
  84  * for points outside the hex, that is, distance should almost certainly
  85  * be less than or equal to 1.0
  86  */
  87 struct HL_point HL_polar(double angle, double distance, double *d);
  88
  89 /* how far is it on the hex grid */
  90 int HL_distance(struct HL_hex from, struct HL_hex to);
  91
  92 /* module direction */
  93 struct HL_hex HL_adjhex(struct HL_hex, int dir);
  94 int HL_adjhexp(struct HL_hex, int dir, struct HL_hex *adj);
  95 int HL_hexes_at_range(struct HL_hex, int range, struct HL_hex *list, int size);
  96 int HL_hexes_within_range(struct HL_hex, int range, struct HL_hex *list, int size);
  97
  98 typedef double (*HL_costfunc)(int start, int finish);
  99
 100 /* writes up to len cantors to path.  returns last
 101  * value written
 102  * perhaps it should return the last value not written, if the
 103  * path is incomplete?
 104  * either way, it can then be used in a loop
 105  */
 106 int HL_path(int start, int end, int *path, int len);
 107
 108 int HL_map_bounds_ok(int xdim, int ydim);
 109 int HL_map_max_dimension(void);
 110
 111 /*
 112  * Plotting support
 113  */
 114 void HL_trianglefan(struct HL_hex hex, double *);
 115
 116 /*
 117  * Pathfinding
 118  */
 119
 120 struct HL_astar_hex {
 121         struct HL_hex hex;
 122         double f, g, h;
 123         struct HL_astar_hex *parent;
 124         int     open;
 125         struct HL_astar_hex *next;
 126         struct HL_astar_hex *prev;
 127 };
 128
 129 struct HL_astar {
 130         struct HL_hex start, goal;
 131         int pathlen;
 132         double (*metric)(struct HL_hex,struct HL_hex);
 133         double (*heuristic)(struct HL_hex,struct HL_hex);
 134         int (*neighbor)(struct HL_hex,int dir, struct HL_hex *n);
 135         int nodes, allocated;
 136         struct HL_astar_hex *open;
 137         struct HL_astar_hex *closed;
 138         struct HL_astar_hex *from, *to;
 139         int known, index;
 140         int error, malloced;
 141 };
 142
 143 int HL_findpath(struct HL_astar *s, int loops);
 144 void HL_astar_free(struct HL_astar *s);
 145 struct HL_astar *HL_astar_clear(struct HL_astar *s);
 146 struct HL_astar *HL_astar_init(struct HL_astar *s);
 147 void HL_vertices(struct HL_hex hex, double *vc);
 148
 149 extern double HL_vertexv[12];
 150 extern double HL_fand[16];
 151 extern float HL_fanf[16];
 152 extern double HL_hfand[16]; /* horizontal grids */
 153 extern float HL_hfanf[16]; /* horizontal grids */
 154 extern double HL_square;
 155
 156 #endif