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

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