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 /* how far is it on the hex grid */
  80 int HL_distance(int from_cantor, int to_cantor);
  81
  82 /* returns 0 for <0 or >5 */
  83 int HL_adjacent_hex(int start, int dir);
  84
  85 /* module direction */
  86 int HL_adjhex(int start, int dir);
  87 int HL_hexes_at_range(int hex, int range, int *list, int size);
  88 int HL_hexes_within_range(int hex, int range, int *list, int size);
  89
  90 typedef double (*HL_costfunc)(int start, int finish);
  91
  92 /* writes up to len cantors to path.  returns last
  93  * value written
  94  * perhaps it should return the last value not written, if the
  95  * path is incomplete?
  96  * either way, it can then be used in a loop
  97  */
  98 int HL_path(int start, int end, int *path, int len);
  99
 100 int HL_map_bounds_ok(int xdim, int ydim);
 101 int HL_map_max_dimension(void);
 102
 103 /*
 104  * Plotting support
 105  */
 106 void HL_trianglefan(int cantor, double *);
 107
 108 struct HL_hex {
 109         int x,y; /* hmm.  would be nice to be able to just point to a generic */
 110 };
 111
 112 /*
 113  * Pathfinding
 114  */
 115
 116 struct HL_astar_hex {
 117         int hex;
 118         double f, g, h;
 119         struct HL_astar_hex *parent;
 120         int     open;
 121         struct HL_astar_hex *next;
 122         struct HL_astar_hex *prev;
 123 };
 124
 125 struct HL_astar {
 126         int start, goal;
 127         int pathlen;
 128         double (*metric)(int,int);
 129         double (*heuristic)(int,int);
 130         int (*neighbor)(int,int);
 131         int nodes, allocated;
 132         struct HL_astar_hex *sets;
 133         struct HL_astar_hex *open;
 134         struct HL_astar_hex *closed;
 135         struct HL_astar_hex *from, *to;
 136         int known, index;
 137         int error, malloced;
 138 };
 139
 140 int HL_findpath(struct HL_astar *s, int loops);
 141 void HL_astar_free(struct HL_astar *s);
 142 struct HL_astar *HL_astar_clear(struct HL_astar *s);
 143 struct HL_astar *HL_astar_init(struct HL_astar *s);
 144
 145 #endif