pd.if.org Git - hexagon/blob - doc/hexagon.pod

   1 =head1 NAME
   2
   3         hexlib - a library for hexagon grids
   4
   5 =head1 SYNOPSIS
   6
   7         #include <hexagon.h>
   8
   9 =head1 DESCRIPTION
  10
  11 hexagon is a C library for performing calculations on hexagon grids.
  12 Hexagons are represented by their canonical ID, which is a single
  13 integer representation of their two dimensional coordinates.
  14 Algorithms and functions are provided for calculating hexagon
  15 centers, vertexes, and distances on the grid.  An A* algorithm
  16 is also implemented for pathfinding.
  17
  18 The canonical integer id of a hexagon is computed from its
  19 two dimensional integer coordinates using a modified
  20 cantor pairing function.  The canonical integer ids are
  21 referred to as cantors.
  22
  23 =head2 Grid Layout
  24
  25                    __/15\__/35\
  26                 __/04\__/24\__/
  27                /A \__/14\__/34\
  28                \__/03\__/23\__/
  29                /  \__/13\__/33\
  30                \__/02\__/22\__/
  31                /  \__/12\__/32\
  32                \__/01\__/21\__/
  33                /  \__/11\__/31\
  34                \__/00\__/20\__/
  35                   \__/  \__/
  36
  37 The Grid is numbered as above, and generalizes to negative coordinates,
  38 thus the hex labeled A would have coordinates (-1,4), and the
  39 hex (not shown) two hexes below 1,1 would be hex 1,-1.  If you
  40 need different coordinates, you will have to translate them to the
  41 above system.
  42
  43 =head3 Inverted Y coordinates
  44
  45 Many games and displays use a positive Y down, rather than the
  46 usual mathematical positive Y up.  The library uses the mathematical
  47 convention.  In general though, this will not matter.  The Y coordinate
  48 of the hex centers has the same direction as the Y coordinate of the
  49 hex grid.  If your display is Y down, and your grid is too, you can
  50 use the coordinates as given.  If your display is Y up and you want
  51 your grid to be Y down, you will, obviously, need to invert the Y
  52 coordinates for display, and re-invert them when passing them back to
  53 the library.
  54
  55 To convert to a positive Y down, you can take the negative of the Y coordinate
  56 as given by the library.  See the HL_hexbin() example below.
  57
  58 =head3 Horizontal Grids
  59
  60 A horizontal grid layout can be created by either rotating the given
  61 coordinates by 90 degrees, or, equivalently, swapping the X and Y coordinates
  62 as given by the library.  Obviously, you will need to swap them when passing
  63 them into the library also.  You may also need to invert the (resulting) Y
  64 coordinate as above for display if your display is positive Y down.
  65
  66 =head2 Hexagon IDs
  67
  68 Two dimensional hex locations are converted into a single integer
  69 hexagon ID with a pairing function.  A pairing function uniquely
  70 and reversably maps two integers onto one integer.  At the moment,
  71 only a modified Cantor's original triangular pairing function,
  72 extended to handle negative integers,
  73 is available.
  74
  75 As most hexagon grids will only use positive coordinates, additional
  76 pairing functions will be provided in the future.
  77
  78 =head3 int HL_cantor(int x, int y)
  79
  80 Converts a two dimensional coordinate to a canonical id.
  81
  82         int hex;
  83         hex = HL_cantor(1,1); /* hex == 5 */
  84
  85 =head2 Hexagon grid functions
  86
  87 The hexagon grid is constrained to be a vertical grid, with the hexagon at
  88 (2,1) being to the right and half a hex below the hex at (1,1).  Horizontal
  89 grid layouts are not supported.
  90
  91 =head3 int HL_cantor_x(int cantor);
  92
  93 Returns the X coordinate of a hex identified by the given cantor id.
  94
  95         int x = HL_cantor_x(5); /* x == 1 */
  96
  97 =head3 int HL_cantor_y(int cantor);
  98
  99 Returns the Y coordinate of a hex identified by the given cantor id.
 100
 101         int x = HL_cantor_x(5); /* x == 1 */
 102
 103 =head3 int HL_hexbin(double scale, double cx, double cy, int *x, int *y);
 104
 105 This function determines which hex a given cartesian coordinate falls
 106 in.  The width from side to side of a hex is given by scale.  The
 107 function returns the cantor id of the hex.  If x or y are not NULL, the
 108 x and y coordinates of the hex are placed into *x and *y.
 109
 110 If you are inverting the Y coordinate for display, do so on the result
 111 of this function, not the display Y coordinate you pass in to this function.
 112 That is, do
 113
 114         HL_hexbin(scale, cx, cy, &x, &y);
 115         y = -y;
 116
 117 to get the Y coordinate of the hex.  Doing the following
 118
 119         HL_hexbin(scale, cx, -cy, &x, &y);
 120
 121 will give the wrong result for odd numbered hex columns.  This
 122 is because the X axis passes through the center of the even columns,
 123 so the negation works, but it passes along the edge of the odd columns,
 124 and you end up with an off by one error.
 125
 126 =head2 Hexagon data
 127
 128 Some pre-calculated data is available.
 129
 130 =head3 double HL_fand[16]
 131
 132 An array of hexagon coordinates, with the hex center x,y at indexes 0 and
 133 1 (these are 0.0,0.0), and each vertex following.  The first vertex
 134 is repeated at the end of the array.  Each vertex takes up two consecutive
 135 array elements for it's X and Y coordinates.  Thus for hex vertexes 1 to
 136 6, and hex center C this array is CxCy1x1y2x2y3x3y4x4y5x5y6x6y1x1y.
 137 This is suitable for passing directly to opengl for drawing a hexagon
 138 as a triangle fan.
 139
 140 =head3 float HL_fanf[16]
 141
 142 An array of floats, laid out the same way as HL_fand.
 143
 144 =head3 double HL_hfand[16]
 145
 146 This is the same as HL_fand, but will draw a horizontal hex.  The same
 147 effect could be had by rotating 90 degrees.
 148
 149 =head3 float HL_hfanf[16]
 150
 151 An array of float with horizontal layout.
 152
 153 =head2 Pathfinding
 154
 155 The library provides an A* implementation for pathfinding on
 156 a hex grid.
 157
 158         struct HL_astar *state;
 159         state = HL_astar_init(NULL);
 160         state->start = HL_cantor_xy(1,1);
 161         state->goal = HL_cantor_xy(4,14);
 162         int length = HL_astar_findpath(state,0);
 163
 164 The implementation uses three callbacks which can be
 165 set as members of the HL_astar struct.
 166
 167         double (*metric)(int hex, int hex2);
 168         double (*heuristic)(int hex, int hex2);
 169         int (*neighbor)(int hex, int n);
 170
 171 The metric callback is used to get the actual cost to move from
 172 hex to hex2.  It will only be called on adjacent hexes.  HL_astar_init
 173 will set this to a default metric that returns 1.0 for any input.
 174
 175 The heuristic callback is used to estimate the distance between
 176 two hexes, which may not be adjacent.  By default, a function is
 177 used that returns the hex grid distance between the hexes.
 178 It is important that the function not return a distance that is
 179 greater than the actual distance, as the A* algorithm depends on
 180 this.  If you have any hexes that cost less than 1.0 to traverse,
 181 the default heuristic won't work, so you'll need to provide your
 182 own.  You could also provide a metric that multiplied the actual
 183 cost by an amount sufficient to raise the minimum cost to 1.0.
 184 (e.g. if you had roads that reduced the move cost to 1/2, you
 185 could provide a metric returned twice the actual cost).
 186
 187 The neighbor callback should return the id of the neighbor
 188 at the index given by n.  The callback should return 0 if
 189 there is no neighbor with the given index.  It's ok if
 190 a neighbor has more than one index.  That is, you can
 191 return the same neighbor for more than one index.  The
 192 first neighbor should be at index 0.  The HL_findpath
 193 function will call this method starting at index 0 and
 194 working up until the function returns 0, at which point
 195 it is assumed that there are no more neighbors.
 196
 197 =head3 struct HL_astar *HL_astar_init(HL_astar *state);
 198
 199 Initializes the given state.  You can either pass in a pointer to your
 200 own data structure, or pass in NULL, in which case the library
 201 will use malloc(3) to create a new structure.
 202
 203 =head3 void HL_astar_free(HL_astar *state);
 204
 205 Frees any memory allocated by the structure.
 206
 207 =head1 OPTIONS
 208
 209 =head1 DIAGNOSTICS
 210
 211 =head1 BUGS
 212
 213 =head1 AUTHOR
 214
 215 This library was entirely written by Nathan Wagner.
 216
 217 =head1 COPYRIGHT
 218
 219 This library and the source code for it are released into
 220 the public domain.  The author asserts no copyright claim
 221 of any kind.
 222
 223 =head1