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.  To convert to a positive Y down, you can take the
  48 negative of the Y coordinate as given by the library.  See the HL_hexbin()
  49 example below.
  50
  51 =head3 Horizontal Grids
  52
  53 A horizontal grid layout can be created by either rotating the
  54 given coordinates by 90 degrees, or, equivalently, swapping the X and
  55 Y coordinates as given by the library.  Obviously, you will need to
  56 swap them when passing them into the library also.  You may also
  57 need to invert the Y coordinate as above for display.
  58
  59 =head2 Hexagon grid functions
  60
  61 The hexagon grid is constrained to be a vertical grid, with
  62 the hexagon at (2,1) being to the right and half a hex below
  63 the hex at (1,1).  Horizontal grid layouts are not supported.
  64
  65 =head3 int HL_cantor(int x, int y)
  66
  67 Converts a two dimensional coordinate to a canonical id.
  68
  69         int hex;
  70         hex = HL_cantor(1,1); /* hex == 5 */
  71
  72 =head3 int HL_cantor_x(int cantor);
  73
  74 Returns the X coordinate of a hex identified by the given cantor id.
  75
  76         int x = HL_cantor_x(5); /* x == 1 */
  77
  78 =head3 int HL_cantor_y(int cantor);
  79
  80 Returns the Y coordinate of a hex identified by the given cantor id.
  81
  82         int x = HL_cantor_x(5); /* x == 1 */
  83
  84 =head3 int HL_hexbin(double scale, double cx, double cy, int *x, int *y);
  85
  86 This function determines which hex a given cartesian coordinate falls
  87 in.  The width from side to side of a hex is given by scale.  The
  88 function returns the cantor id of the hex.  If x or y are not NULL, the
  89 x and y coordinates of the hex are placed into *x and *y.
  90
  91 If you are inverting the Y coordinate for display, do so on the result
  92 of this function, not the display Y coordinate you pass in to this function.
  93 That is, do
  94
  95         HL_hexbin(scale, cx, cy, &x, &y);
  96         y = -y;
  97
  98 to get the Y coordinate of the hex.  Doing the following
  99
 100         HL_hexbin(scale, cx, -cy, &x, &y);
 101
 102 will give the wrong result for odd numbered hex columns.  This
 103 is because the X axis passes through the center of the even columns,
 104 so the negation works, but it passes along the edge of the odd columns,
 105 and you end up with an off by one error.
 106
 107 =head2 Pathfinding
 108
 109 The library provides an A* implementation for pathfinding on
 110 a hex grid.
 111
 112         struct HL_astar *state;
 113         state = HL_astar_init(NULL);
 114         state->start = HL_cantor_xy(1,1);
 115         state->goal = HL_cantor_xy(4,14);
 116         int length = HL_astar_findpath(state,0);
 117
 118 The implementation uses three callbacks which can be
 119 set as members of the HL_astar struct.
 120
 121         double (*metric)(int hex, int hex2);
 122         double (*heuristic)(int hex, int hex2);
 123         int (*neighbor)(int hex, int n);
 124
 125 The metric callback is used to get the actual cost to move from
 126 hex to hex2.  It will only be called on adjacent hexes.  HL_astar_init
 127 will set this to a default metric that returns 1.0 for any input.
 128
 129 The heuristic callback is used to estimate the distance between
 130 two hexes, which may not be adjacent.  By default, a function is
 131 used that returns the hex grid distance between the hexes.
 132 It is important that the function not return a distance that is
 133 greater than the actual distance, as the A* algorithm depends on
 134 this.  If you have any hexes that cost less than 1.0 to traverse,
 135 the default heuristic won't work, so you'll need to provide your
 136 own.  You could also provide a metric that multiplied the actual
 137 cost by an amount sufficient to raise the minimum cost to 1.0.
 138 (e.g. if you had roads that reduced the move cost to 1/2, you
 139 could provide a metric returned twice the actual cost).
 140
 141 The neighbor callback should return the id of the neighbor
 142 at the index given by n.  The callback should return 0 if
 143 there is no neighbor with the given index.  It's ok if
 144 a neighbor has more than one index.  That is, you can
 145 return the same neighbor for more than one index.  The
 146 first neighbor should be at index 0.  The HL_findpath
 147 function will call this method starting at index 0 and
 148 working up until the function returns 0, at which point
 149 it is assumed that there are no more neighbors.
 150
 151 =head3 struct HL_astar *HL_astar_init(HL_astar *state);
 152
 153 Initializes the given state.  You can either pass in a pointer to your
 154 own data structure, or pass in NULL, in which case the library
 155 will use malloc(3) to create a new structure.
 156
 157 =head3 void HL_astar_free(HL_astar *state);
 158
 159 Frees any memory allocated by the structure.
 160
 161 =head1 OPTIONS
 162
 163 =head1 DIAGNOSTICS
 164
 165 =head1 BUGS
 166
 167 =head1 AUTHOR
 168
 169 This library was entirely written by Nathan Wagner.
 170
 171 =head1 COPYRIGHT
 172
 173 This library and the source code for it are released into
 174 the public domain.  The author asserts no copyright claim
 175 of any kind.
 176
 177 =head1