From: Nathan Wagner Date: Sat, 27 Nov 2010 06:26:59 +0000 (+0000) Subject: renamed library to hexagon X-Git-Url: https://pd.if.org/git/?p=hexagon;a=commitdiff_plain;h=8ca2b8a06b00066a20f744a61c9bcdd65949a344 renamed library to hexagon --- diff --git a/Makefile b/Makefile index 545d6f4..9b2f442 100644 --- a/Makefile +++ b/Makefile @@ -4,15 +4,15 @@ LDFLAGS= $(ARCH) -lm CFLAGS= -Wall -Wno-parentheses $(ARCH) -I. -I.. -OBJS= hexmap.o astar.o +OBJS= hexagon.o astar.o SRC=$(OBJS:.o=.c) TESTS= t/cantor.t t/distance.t t/adjacency.t t/range.t t/hexbin.t \ - t/gridsize.t t/center.t + t/gridsize.t t/center.t t/astar.t -all: test libhexmap.a +all: test libhexagon.a docs clean: - rm -f $(OBJS) libhexmap.a $(TESTS) + rm -f $(OBJS) libhexagon.a $(TESTS) t/%.t: t/%.o t/tap.o $(OBJS) $(CC) -I.. -I. -o $@ $+ $(LDFLAGS) @@ -20,13 +20,13 @@ t/%.t: t/%.o t/tap.o $(OBJS) test: $(TESTS) @prove --exec '' 2>/dev/null -hextest: hextest.c libhexmap.a - $(CC) $(CFLAGS) -o $@ hextest.c -L. -lhexmap - -libhexmap.a: $(OBJS) +libhexagon.a: $(OBJS) ar r $@ $+ ranlib $@ +docs: + make -C doc + .c.o: $(CC) $(CFLAGS) -c -o $@ $< diff --git a/astar.c b/astar.c index cabe5d0..5bfc60f 100644 --- a/astar.c +++ b/astar.c @@ -1,11 +1,11 @@ -#include "hexmap.h" - #include #include #include #include #include +#include "hexagon.h" + /* * TODO use binary heap for the openlist and closed list. * open list should be a min-heap on the f value @@ -229,7 +229,6 @@ int HL_findpath(struct HL_astar *s, int loops) { yopen = in_open(s, y); if (! yopen) { yopen = add_open(s, y); - tent_better = 1; } else if (cost < yopen->g) { tent_better = 1; diff --git a/doc/Makefile b/doc/Makefile new file mode 100644 index 0000000..d81d254 --- /dev/null +++ b/doc/Makefile @@ -0,0 +1,16 @@ +hexagon.3: hexagon.pod + pod2man --center='hexagon library' --section=3 --release='hexagon 0.1' $+ > $@ + +hexagon.txt: hexagon.pod + pod2text -l $+ + +hexagon.pdf: hexagon.pod + pod2latex -full $+ + pdflatex hexagon.tex + pdflatex hexagon.tex + pdflatex hexagon.tex + rm -f hexagon.tex hexagon.idx hexagon.aux hexagon.toc hexagon.log + +clean: + rm -f hexagon.3 hexagon.pdf hexagon.tex hexagon.txt \ + hexagon.idx hexagon.aux hexagon.log hexagon.toc diff --git a/doc/hexagon.pod b/doc/hexagon.pod new file mode 100644 index 0000000..9dfc4ae --- /dev/null +++ b/doc/hexagon.pod @@ -0,0 +1,177 @@ +=head1 NAME + + hexlib - a library for hexagon grids + +=head1 SYNOPSIS + + #include + +=head1 DESCRIPTION + +hexagon is a C library for performing calculations on hexagon grids. +Hexagons are represented by their canonical ID, which is a single +integer representation of their two dimensional coordinates. +Algorithms and functions are provided for calculating hexagon +centers, vertexes, and distances on the grid. An A* algorithm +is also implemented for pathfinding. + +The canonical integer id of a hexagon is computed from its +two dimensional integer coordinates using a modified +cantor pairing function. The canonical integer ids are +referred to as cantors. + +=head2 Grid Layout + + __/15\__/35\ + __/04\__/24\__/ + /A \__/14\__/34\ + \__/03\__/23\__/ + / \__/13\__/33\ + \__/02\__/22\__/ + / \__/12\__/32\ + \__/01\__/21\__/ + / \__/11\__/31\ + \__/00\__/20\__/ + \__/ \__/ + +The Grid is numbered as above, and generalizes to negative coordinates, +thus the hex labeled A would have coordinates (-1,4), and the +hex (not shown) two hexes below 1,1 would be hex 1,-1. If you +need different coordinates, you will have to translate them to the +above system. + +=head3 Inverted Y coordinates + +Many games and displays use a positive Y down, rather than the +usual mathematical positive Y up. The library uses the mathematical +convention. To convert to a positive Y down, you can take the +negative of the Y coordinate as given by the library. See the HL_hexbin() +example below. + +=head3 Horizontal Grids + +A horizontal grid layout can be created by either rotating the +given coordinates by 90 degrees, or, equivalently, swapping the X and +Y coordinates as given by the library. Obviously, you will need to +swap them when passing them into the library also. You may also +need to invert the Y coordinate as above for display. + +=head2 Hexagon grid functions + +The hexagon grid is constrained to be a vertical grid, with +the hexagon at (2,1) being to the right and half a hex below +the hex at (1,1). Horizontal grid layouts are not supported. + +=head3 int HL_cantor(int x, int y) + +Converts a two dimensional coordinate to a canonical id. + + int hex; + hex = HL_cantor(1,1); /* hex == 5 */ + +=head3 int HL_cantor_x(int cantor); + +Returns the X coordinate of a hex identified by the given cantor id. + + int x = HL_cantor_x(5); /* x == 1 */ + +=head3 int HL_cantor_y(int cantor); + +Returns the Y coordinate of a hex identified by the given cantor id. + + int x = HL_cantor_x(5); /* x == 1 */ + +=head3 int HL_hexbin(double scale, double cx, double cy, int *x, int *y); + +This function determines which hex a given cartesian coordinate falls +in. The width from side to side of a hex is given by scale. The +function returns the cantor id of the hex. If x or y are not NULL, the +x and y coordinates of the hex are placed into *x and *y. + +If you are inverting the Y coordinate for display, do so on the result +of this function, not the display Y coordinate you pass in to this function. +That is, do + + HL_hexbin(scale, cx, cy, &x, &y); + y = -y; + +to get the Y coordinate of the hex. Doing the following + + HL_hexbin(scale, cx, -cy, &x, &y); + +will give the wrong result for odd numbered hex columns. This +is because the X axis passes through the center of the even columns, +so the negation works, but it passes along the edge of the odd columns, +and you end up with an off by one error. + +=head2 Pathfinding + +The library provides an A* implementation for pathfinding on +a hex grid. + + struct HL_astar *state; + state = HL_astar_init(NULL); + state->start = HL_cantor_xy(1,1); + state->goal = HL_cantor_xy(4,14); + int length = HL_astar_findpath(state,0); + +The implementation uses three callbacks which can be +set as members of the HL_astar struct. + + double (*metric)(int hex, int hex2); + double (*heuristic)(int hex, int hex2); + int (*neighbor)(int hex, int n); + +The metric callback is used to get the actual cost to move from +hex to hex2. It will only be called on adjacent hexes. HL_astar_init +will set this to a default metric that returns 1.0 for any input. + +The heuristic callback is used to estimate the distance between +two hexes, which may not be adjacent. By default, a function is +used that returns the hex grid distance between the hexes. +It is important that the function not return a distance that is +greater than the actual distance, as the A* algorithm depends on +this. If you have any hexes that cost less than 1.0 to traverse, +the default heuristic won't work, so you'll need to provide your +own. You could also provide a metric that multiplied the actual +cost by an amount sufficient to raise the minimum cost to 1.0. +(e.g. if you had roads that reduced the move cost to 1/2, you +could provide a metric returned twice the actual cost). + +The neighbor callback should return the id of the neighbor +at the index given by n. The callback should return 0 if +there is no neighbor with the given index. It's ok if +a neighbor has more than one index. That is, you can +return the same neighbor for more than one index. The +first neighbor should be at index 0. The HL_findpath +function will call this method starting at index 0 and +working up until the function returns 0, at which point +it is assumed that there are no more neighbors. + +=head3 struct HL_astar *HL_astar_init(HL_astar *state); + +Initializes the given state. You can either pass in a pointer to your +own data structure, or pass in NULL, in which case the library +will use malloc(3) to create a new structure. + +=head3 void HL_astar_free(HL_astar *state); + +Frees any memory allocated by the structure. + +=head1 OPTIONS + +=head1 DIAGNOSTICS + +=head1 BUGS + +=head1 AUTHOR + +This library was entirely written by Nathan Wagner. + +=head1 COPYRIGHT + +This library and the source code for it are released into +the public domain. The author asserts no copyright claim +of any kind. + +=head1 diff --git a/hexmap.c b/hexagon.c similarity index 99% rename from hexmap.c rename to hexagon.c index baeb961..61bb47b 100644 --- a/hexmap.c +++ b/hexagon.c @@ -1,4 +1,4 @@ -#include "hexmap.h" +#include "hexagon.h" #include #include diff --git a/hexmap.h b/hexagon.h similarity index 100% rename from hexmap.h rename to hexagon.h diff --git a/hexagon.pod b/hexagon.pod deleted file mode 100644 index 4b41483..0000000 --- a/hexagon.pod +++ /dev/null @@ -1,80 +0,0 @@ -=head1 NAME - - hexlib - a library for hexagon grids - -=head1 SYNOPSIS - - #include - -=head1 DESCRIPTION - -hexagon is a C library for performing calculations on hexagon grids. -Hexagons are represented by their canonical ID, which is a single -integer representation of their two dimensional coordinates. -Algorithms and functions are provided for calculating hexagon -centers, vertexes, and distances on the grid. An A* algorithm -is also implemented for pathfinding. - -The canonical integer id of a hexagon is computed from its -two dimensional integer coordinates using a modified -cantor pairing function. The canonical integer ids are -referred to as cantors. - -=head2 Hexagon grid functions - -The hexagon grid is constrained to be a vertical grid, with -the hexagon at (2,1) being to the right and half a hex below -the hex at (1,1). Horizontal grid layouts are not supported. - -=head3 int HL_cantor(int x, int y) - -Converts a two dimensional coordinate to a canonical id. - - int hex; - hex = HL_cantor(1,1); /* hex == 5 */ - -=head3 int HL_cantor_x(int cantor); - -Returns the X coordinate of a hex identified by the given cantor id. - - int x = HL_cantor_x(5); /* x == 1 */ - -=head2 Pathfinding - -The library provides an A* implementation for pathfinding on -a hex grid. - - struct HL_astar *state; - state = HL_astar_init(NULL); - state->start = HL_cantor_xy(1,1); - state->goal = HL_cantor_xy(4,14); - int length = HL_astar_findpath(state,0); - - -=head3 struct HL_astar *HL_astar_init(HL_astar *state); - -Initializes the given state. You can either pass in a pointer to your -own data structure, or pass in NULL, in which case the library -will use malloc(3) to create a new structure. - -=head3 void HL_astar_free(HL_astar *state); - -Frees any memory allocated by the structure. - -=head1 OPTIONS - -=head1 DIAGNOSTICS - -=head1 BUGS - -=head1 AUTHOR - -This library was entirely written by Nathan Wagner. - -=head1 COPYRIGHT - -This library and the source code for it are released into -the public domain. The author asserts no copyright claim -of any kind. - -=head1 diff --git a/t/adjacency.c b/t/adjacency.c index 95750cf..dc2c64f 100644 --- a/t/adjacency.c +++ b/t/adjacency.c @@ -1,4 +1,4 @@ -#include "hexmap.h" +#include "hexagon.h" #include "tap.h" diff --git a/t/astar.c b/t/astar.c index af88268..2ed40c0 100644 --- a/t/astar.c +++ b/t/astar.c @@ -1,6 +1,6 @@ #include -#include "hexmap.h" +#include "hexagon.h" #include "tap.h" @@ -27,10 +27,9 @@ void pcheck(struct HL_astar *p, int x1, int y1, int x2, int y2, int expect) { int neighbor55(int hex, int dir) { int neighbor; - neighbor = HL_adjacent_hex(hex, dir); - if (neighbor == HL_cantor_xy(5,5)) { - return -1; - } + do { + neighbor = HL_adjacent_hex(hex, dir++); + } while (neighbor == HL_cantor_xy(5,5)); return neighbor; } diff --git a/t/cantor.c b/t/cantor.c index a2e9290..0f179d2 100644 --- a/t/cantor.c +++ b/t/cantor.c @@ -1,6 +1,6 @@ #include -#include "hexmap.h" +#include "hexagon.h" #include "tap.h" diff --git a/t/center.c b/t/center.c index 00fdff2..72499a3 100644 --- a/t/center.c +++ b/t/center.c @@ -1,6 +1,6 @@ #include -#include "hexmap.h" +#include "hexagon.h" #include "tap.h" diff --git a/t/distance.c b/t/distance.c index 28d520e..71d7079 100644 --- a/t/distance.c +++ b/t/distance.c @@ -1,4 +1,4 @@ -#include "hexmap.h" +#include "hexagon.h" #include "tap.h" diff --git a/t/gridsize.c b/t/gridsize.c index 784e467..f4335fd 100644 --- a/t/gridsize.c +++ b/t/gridsize.c @@ -1,4 +1,4 @@ -#include "hexmap.h" +#include "hexagon.h" #include "tap.h" diff --git a/t/hexbin.c b/t/hexbin.c index e486bc8..5fc504d 100644 --- a/t/hexbin.c +++ b/t/hexbin.c @@ -1,4 +1,4 @@ -#include "hexmap.h" +#include "hexagon.h" #include "tap.h" diff --git a/t/hextest.c b/t/hextest.c index f7b219b..2f43328 100644 --- a/t/hextest.c +++ b/t/hextest.c @@ -4,7 +4,7 @@ #include #include -#include "hexmap.h" +#include "hexagon.h" #include "tap.h" diff --git a/t/range.c b/t/range.c index b40b86d..7a449e6 100644 --- a/t/range.c +++ b/t/range.c @@ -4,7 +4,7 @@ #include #include -#include "hexmap.h" +#include "hexagon.h" #include "tap.h" diff --git a/t/within.c b/t/within.c index 143b7a8..9294b8b 100644 --- a/t/within.c +++ b/t/within.c @@ -1,4 +1,4 @@ -#include "hexmap.h" +#include "hexagon.h" #include "tap.h"