From 5c48a06bc8649958e69013c53e925b83398ebc74 Mon Sep 17 00:00:00 2001
From: Nathan Wagner <nw@hydaspes.if.org>
Date: Fri, 26 Nov 2010 12:23:02 +0000
Subject: [PATCH] Improved astar api.  Added doc file.

---
 Makefile     |   2 +-
 astar.c      | 360 +++++++++++++++++++++++++++++++++++----------------
 hexagon.pod  |  80 ++++++++++++
 hexmap.c     | 189 +++------------------------
 hexmap.h     |  37 ++++++
 t/astar.c    |  22 +++-
 t/distance.c |   5 +-
 7 files changed, 406 insertions(+), 289 deletions(-)
 create mode 100644 hexagon.pod

diff --git a/Makefile b/Makefile
index 20f36fc..545d6f4 100644
--- a/Makefile
+++ b/Makefile
@@ -4,7 +4,7 @@
 
 LDFLAGS= $(ARCH) -lm
 CFLAGS=	-Wall -Wno-parentheses $(ARCH) -I. -I..
-OBJS= hexmap.o
+OBJS= hexmap.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
diff --git a/astar.c b/astar.c
index 37bc404..cabe5d0 100644
--- a/astar.c
+++ b/astar.c
@@ -4,158 +4,292 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include <limits.h>
+#include <errno.h>
 
-struct astar_hex {
-	int hex;
-	int f, g, h;
-	int parent;
-};
-
-struct astar {
-	int open, closed; /* how many in open or closed */
-	int closedroom, openroom; /* how much is malloced */
-	struct astar_hex *openlist;
-	struct astar_hex *closedlist;
-	int known, index;
-	int error;
-};
-
-static void astar_init(struct astar *state) {
+/*
+ * TODO use binary heap for the openlist and closed list.
+ * open list should be a min-heap on the f value
+ * closed list is just tested for existence, so a sort on
+ * the hex id is fine
+ */
+
+#if 0
+#define DEBUG_ASTAR 1 
+#endif
+
+static double default_metric(int a, int b) {
+	return 1.0;
+}
+
+static double default_heuristic(int a, int b) {
+	return (double)HL_distance(a, b);
+}
+
+struct HL_astar *HL_astar_init(struct HL_astar *state) {
+	if (!state) {
+		state = malloc(sizeof *state);
+		if (!state) return NULL;
+		state->malloced = 1;
+	}
+	state->sets = 0;
 	state->open = 0;
 	state->closed = 0;
-	state->closedroom = 0;
-	state->openroom = 0;
-	state->openlist = 0;
-	state->closedlist = 0;
+	state->nodes = 0;
+	state->allocated = 0;
 	state->error = 0;
 	state->known = 0;
 	state->index = 0;
+	state->pathlen = 0;
+
+	state->metric = default_metric;
+	state->heuristic = default_heuristic;
+	state->neighbor = HL_adjacent_hex;
 
-	return;
+	return state;
 }
 
-static void removeopen(struct astar *s, int hex) {
-	int index;
+/*
+ * Reset a state to enpty.  Doesn't free memory, so it
+ * can be reused.
+ */
+struct HL_astar *HL_astar_clear(struct HL_astar *s) {
+	if (!s) return NULL;
 
-	if (s->error) return;
-	if (s->open == 0) return;
+	s->open = 0;
+	s->closed = 0;
+	s->nodes = 0;
+	s->pathlen = 0;
 
-	if (s->known != hex) {
-		for (index = 0; index < s->open; index++) {
-			if (s->openlist[index].hex == hex) break;
-		}
-	} else {
-		index = s->index;
-		s->known = 0; s->index = 0;
+	return s;
+}
+
+void HL_astar_free(struct HL_astar *s) {
+	free(s->sets);
+	if (s->malloced) {
+		free(s);
 	}
-	s->openlist[index] = s->openlist[open];
-	s->open--;
 }
 
-static void addopen(struct astar *s, int hex) {
-	struct astar_hex *mem;
-	if (s->error) return;
+static struct HL_astar_hex *add_open(struct HL_astar *s, int hex) {
+	struct HL_astar_hex *node;
+
+	if (!s || s->error) return NULL;
+
+	/* TODO check in open or closed */
 
-	if (s->open + 1 > s->openroom) {
-		mem = realloc(s->openlist, s->openroom * 2 * sizeof *mem);
-		if (mem == NULL) {
-			s->error = errno;
-			return;
+	if (s->nodes == s->allocated) {
+		int newalloc;
+		struct HL_astar_hex *alloc;
+		if (s->allocated) {
+			newalloc = s->allocated * 2;
+		} else {
+			newalloc = 16;
 		}
-		state->openlist = mem;
-		s->openroom = s->openroom * 2;
+		alloc = realloc(s->sets, newalloc * sizeof *node);
+		if (!alloc) {
+			s->error = 1;
+			return NULL;
+		}
+		s->sets = alloc;
+		s->allocated = newalloc;
 	}
 
-	s->openlist[s->open].hex = hex;
-	s->openlist[s->open].f = 0;
-	s->openlist[s->open].g = 0;
-	s->openlist[s->open].h = 0;
-	s->known = hex;
-	s->index = s->open;
-	s->open = s->open + 1;
+	node = &s->sets[s->nodes++];
+
+	node->hex = hex;
+	node->g = 0.0;
+	node->f = 0.0;
+	node->h = 0.0;
+	node->open = 1;
+	node->parent = 0;
+	if (s->open) s->open->prev = node;
+	node->next = s->open;
+	node->prev = NULL;
+	s->open = node;
+
+	return node;
 }
 
-int lowrank(struct astar *s) {
-	int f;
-	int hex;
-	int i;
+static struct HL_astar_hex *closehex(struct HL_astar *s, struct HL_astar_hex *h) {
+	if (!s || s->error) return NULL;
+	if (!h) {
+		s->error = 1;
+		return NULL;
+	}
 
-	if (!s || s->open = 0) return 0;
+#ifdef DEBUG_ASTAR
+	fprintf(stderr, "Closing hex: (%d,%d)\n",  HL_cantor_x(h->hex), HL_cantor_y(h->hex));
+#endif
+	h->open = 0;
+	if (h->prev) h->prev->next = h->next;
+	if (h->next) h->next->prev = h->prev;
+	if (s->closed) s->closed->prev = h;
+	if (s->open == h) s->open = h->next;
+	h->next = s->closed;
+	s->closed = h;
+	h->prev = NULL;
 
-	hex = s->openlist[0].hex;
-	f = s->openlist[0].f;
+	return h;
+}
 
-	for(i=1; i < s->open; i++) {
-		if (s->openlist[i].f < f) {
-			hex = s->openlist[i].hex;
-			f = s->openlist[i].f;
-		}
-		/* TODO check s->openlist[i].tiebreak */
+struct HL_astar_hex *in_closed(struct HL_astar *s, int hex) {
+	struct HL_astar_hex *h;
+	if (!s) return 0;
+
+	for(h = s->closed; h; h = h->next) {
+		if (h->hex == hex) return h;
 	}
+	return NULL;
+}
+
+struct HL_astar_hex *in_open(struct HL_astar *s, int hex) {
+	struct HL_astar_hex *h;
+	if (!s) return 0;
 
-	return hex;
+	for(h = s->open; h; h = h->next) {
+		if (h->hex == hex) return h;
+	}
+	return NULL;
 }
 
-static int default_metric(int a, int b) {
-	return 1;
+static struct HL_astar_hex *lowrank(struct HL_astar *s) {
+	struct HL_astar_hex *n, *r;
+
+	if (!s || s->open == 0) return 0;
+
+	r = s->open;
+	for(n = r; n; n = n->next) {
+		if (n->f < r->f) {
+			r = n;
+		}
+	}
+
+	return r;
 }
 
 /*
  * find a path from start to end.  we use A*
  */
-int HL_findpath(int start, int end, int psize, int *path,
-		double (*metric)(int,int)) {
-	int neighbors[6];
-	int count;
-	int cur = 0;
-	struct astar state;
-	int neighbor;
-
-	if (start == end) return 0;
-	if (!metric) metric = default_metric;
-
-	astar_init(&state);
-	addopen(&state, start);
-
-	while (1) {
-		cur = lowrank(&state);
-		if (cur == end) {
+int HL_findpath(struct HL_astar *s, int loops) {
+	int dir, y;
+	struct HL_astar_hex *node, *x, *yopen;
+	int tent_better;
+	double cost;
+
+	s->error = 0;
+
+	if (s->start == s->goal) return 0;
+
+	node = add_open(s, s->start);
+	node->g = 0.0;
+	node->h = s->heuristic(s->start, s->goal);
+	node->f = node->h;
+
+#ifdef DEBUG_ASTAR
+	fprintf(stderr, "A* findpath: ");
+	fprintf(stderr, "(%d,%d)",  HL_cantor_x(s->start), HL_cantor_y(s->start));
+	fprintf(stderr, " -> ");
+	fprintf(stderr, "(%d,%d)",  HL_cantor_x(s->goal), HL_cantor_y(s->goal));
+	fprintf(stderr, "\n");
+#endif
+
+	while (s->open) {
+
+#ifdef DEBUG_ASTAR
+	fprintf(stderr, "open list: ");
+	for(x = s->open; x; x = x->next) {
+		fprintf(stderr, "(%d,%d)",  HL_cantor_x(x->hex), HL_cantor_y(x->hex));
+	}
+	fprintf(stderr, "\n");
+	fprintf(stderr, "closed list: ");
+	for(x = s->closed; x; x = x->next) {
+		fprintf(stderr, "(%d,%d)",  HL_cantor_x(x->hex), HL_cantor_y(x->hex));
+	}
+	fprintf(stderr, "\n");
+#endif
+
+		x = lowrank(s);
+#ifdef DEBUG_ASTAR
+		fprintf(stderr, "checking lowest f hex = (%d,%d) f = %f, g = %f, h = %f\n",
+			HL_cantor_x(x->hex), HL_cantor_y(x->hex),
+				x->f, x->g, x->h
+				);
+#endif
+		if (x->hex == s->goal) {
 			break;
 		}
-		addclosed(&state, cur);
-		count = HL_hexes_at_range(cur->hex, 1, neighbors, 6);
-		for (i=0;i<count;i++) {
-			neighbor = neighbors[i];
-			cost = g(&state, current) + metric(current, neighbor);
-			if (inopen(&state, neighbor) && cost < g(&state, neighbor)) {
-				removeopen(&state, neighbor);
-			} else
-			if (inclosed(&state, neighbor) && cost < g(&state, neighbor)) {
-				/* should never happen with
-				 * admissible heuristic
-				 */
-				removeclosed(&state, neighbor);
-			} else
-			if (!inopen(&state, neighbor) && !inclosed(&state, neighbor)) {
-				addopen(&state, neighbor);
-				setg(&state, neighbor, cost);
-				setrank(&state, neighbor, cost + h(neighbor,end));
-				setparent(&state, neighbor, current);
+		closehex(s, x);
+		for (dir = 0; y = s->neighbor(x->hex, dir); dir++) {
+			if (in_closed(s, y)) {
+				continue;
+			}
+
+			cost = x->g + s->metric(x->hex, y);
+
+			yopen = in_open(s, y);
+			if (! yopen) {
+				yopen = add_open(s, y);
+
+				tent_better = 1;
+			} else if (cost < yopen->g) {
+				tent_better = 1;
 			} else {
-				abort();
+				tent_better = 0;
+			}
+
+			if (tent_better) {
+				if (yopen->parent) {
+					if (x->f < yopen->parent->f) {
+						yopen->parent = x;
+					}
+				} else {
+					yopen->parent = x;
+				}
+				yopen->g = cost;
+				yopen->h = s->heuristic(y, s->goal);
+				yopen->f = yopen->g + yopen->h;
+#ifdef DEBUG_ASTAR
+		fprintf(stderr, "maybe better hex = (%d,%d) f = %f, g = %f, h = %f\n",
+			HL_cantor_x(yopen->hex), HL_cantor_y(yopen->hex),
+				yopen->f, yopen->g, yopen->h
+				);
+#endif
 			}
 		}
 	}
 
-	count = 0;
-	while (parent(&state, cur) != start) {
-		count++;
-		cur = parent(&state, cur);
-	}
-	cur = end;
-	while (parent(&state, cur) != start) {
-		path[count--] = cur;
-		cur = parent(&state, cur);
+	/* error no path ? */
+	if (x->hex != s->goal) {
+		s->error = 1;
+		return 0;
 	}
 
+#ifdef DEBUG_ASTAR
+	fprintf(stderr, "found path: ");
+#endif
+
+	/* reconstruct path */
+	s->to = x;
+	x->next = 0;
+	for (s->pathlen = 0, yopen = x; yopen; yopen = yopen->parent) {
+		if (yopen->parent) {
+			yopen->parent->next = yopen;
+		}
+		if (yopen->hex == s->start) s->from = yopen;
+#ifdef DEBUG_ASTAR
+		fprintf(stderr, "(%p %d %d,%d)",
+				yopen, yopen->hex,
+				HL_cantor_x(yopen->hex),
+				HL_cantor_y(yopen->hex)
+				);
+#endif
+		s->pathlen++;
+	};
+	s->pathlen--;
+
+#ifdef DEBUG_ASTAR
+	fprintf(stderr, "\n");
+#endif
+
+	return s->pathlen;
 }
diff --git a/hexagon.pod b/hexagon.pod
new file mode 100644
index 0000000..4b41483
--- /dev/null
+++ b/hexagon.pod
@@ -0,0 +1,80 @@
+=head1 NAME
+
+	hexlib - a library for hexagon grids
+
+=head1 SYNOPSIS
+
+	#include <hexagon.h>
+
+=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/hexmap.c b/hexmap.c
index bc20d8d..baeb961 100644
--- a/hexmap.c
+++ b/hexmap.c
@@ -21,7 +21,7 @@ double HL_vertexv[] = {
 	.288675134594812882254574390251, -0.5};
 
 /* these all are for a hex one unit across */
-double          hexptvd[6][2] = {
+static double          hexptvd[6][2] = {
 	{.577350269189625764509148780502, 0.0},	/* 1.0/sqrt3 */
 	{.288675134594812882254574390251, 0.5},	/* 0.5/sqrt3 */
 	{-.288675134594812882254574390251, 0.5},
@@ -30,8 +30,10 @@ double          hexptvd[6][2] = {
 	{.288675134594812882254574390251, -0.5}
 };
 
+#if 0
+
 /* TODO how is this related? to the above? */
-double          texptvd[6][2] = {
+static double          texptvd[6][2] = {
 	{1.154700538379251529018297561004, 0.5},	/* 2.0/sqrt3 */
 	{.866025403784438646763723170753, 1.0},	/* 1.5/sqrt3 */
 	{.288675134594812882254574390251, 1.0},
@@ -40,7 +42,7 @@ double          texptvd[6][2] = {
 	{.866025403784438646763723170753, 0.0}
 };
 
-double          hexpthd[6][2] = {
+static double          hexpthd[6][2] = {
 	{0.0, .577350269189625764509148780502},
 	{0.5, .288675134594812882254574390251},
 	{0.5, -.288675134594812882254574390251},
@@ -49,6 +51,8 @@ double          hexpthd[6][2] = {
 	{-0.5, .288675134594812882254574390251}
 };
 
+#endif
+
 void HL_vertices(int cantor, double *vc) {
 	int i;
 	double xc, yc;
@@ -101,10 +105,7 @@ int HL_hexcenter(int cantor, double *xc, double *yc) {
  * your input coordinates first.
  */
 int HL_cantor_bin(double x, double y) {
-	int i, j;
-
-	HL_hexbin(1.0, x, y, &i, &j);
-	return HL_cantor_xy(i, j);
+	return HL_hexbin(1.0, x, y, 0, 0);
 }
 
 static int xy2ijk(int x, int y, int *i, int *j, int *k) {
@@ -208,6 +209,12 @@ int HL_hexes_at_range(int hex, int range, int *list, int size) {
 	return range * 6;
 }
 
+int HL_adjacent_hex(int start, int dir) {
+	if (dir < 0 || dir > 5) return 0;
+
+	return HL_adjhex(start, dir);
+}
+
 /* direction 0 is positive X , counter clockwise from there */
 int HL_adjhex(int start, int dir) {
 	int c[3];
@@ -232,11 +239,6 @@ int HL_adjhex(int start, int dir) {
 	return HL_cantor_ijkp(c);
 }
 
-/* returns last hex in found path */
-int HL_findpath(int start, int end, int *path, int size) {
-	return 0;
-}
-
 int HL_cantor_xyp(int *xy) {
 	return HL_cantor_xy(xy[0], xy[1]);
 }
@@ -325,165 +327,6 @@ int HL_map_max_dimension(void) {
         return low;
 }
 
-#ifdef ASTAR
-
-struct astar_hex {
-	int hex;
-	int f, g, h;
-	int parent;
-};
-
-struct astar {
-	int open, closed; /* how many in open or closed */
-	int closedroom, openroom; /* how much is malloced */
-	struct astar_hex *openlist;
-	struct astar_hex *closedlist;
-	int known, index;
-	int error;
-};
-
-static void astar_init(struct astar *state) {
-	state->open = 0;
-	state->closed = 0;
-	state->closedroom = 0;
-	state->openroom = 0;
-	state->openlist = 0;
-	state->closedlist = 0;
-	state->error = 0;
-	state->known = 0;
-	state->index = 0;
-
-	return;
-}
-
-static void removeopen(struct astar *s, int hex) {
-	int index;
-
-	if (s->error) return;
-	if (s->open == 0) return;
-
-	if (s->known != hex) {
-		for (index = 0; index < s->open; index++) {
-			if (s->openlist[index].hex == hex) break;
-		}
-	} else {
-		index = s->index;
-		s->known = 0; s->index = 0;
-	}
-	s->openlist[index] = s->openlist[open];
-	s->open--;
-}
-
-static void addopen(struct astar *s, int hex) {
-	struct astar_hex *mem;
-	if (s->error) return;
-
-	if (s->open + 1 > s->openroom) {
-		mem = realloc(s->openlist, s->openroom * 2 * sizeof *mem);
-		if (mem == NULL) {
-			s->error = errno;
-			return;
-		}
-		state->openlist = mem;
-		s->openroom = s->openroom * 2;
-	}
-
-	s->openlist[s->open].hex = hex;
-	s->openlist[s->open].f = 0;
-	s->openlist[s->open].g = 0;
-	s->openlist[s->open].h = 0;
-	s->known = hex;
-	s->index = s->open;
-	s->open = s->open + 1;
-}
-
-int lowrank(struct astar *s) {
-	int f;
-	int hex;
-	int i;
-
-	if (!s || s->open = 0) return 0;
-
-	hex = s->openlist[0].hex;
-	f = s->openlist[0].f;
-
-	for(i=1; i < s->open; i++) {
-		if (s->openlist[i].f < f) {
-			hex = s->openlist[i].hex;
-			f = s->openlist[i].f;
-		}
-		/* TODO check s->openlist[i].tiebreak */
-	}
-
-	return hex;
-}
-
-static int default_metric(int a, int b) {
-	return 1;
-}
-
-/*
- * find a path from start to end.  we use A*
- */
-int HL_findpath(int start, int end, int psize, int *path,
-		double (*metric)(int,int)) {
-	int neighbors[6];
-	int count;
-	int cur = 0;
-	struct astar state;
-	int neighbor;
-
-	if (start == end) return 0;
-	if (!metric) metric = default_metric;
-
-	astar_init(&state);
-	addopen(&state, start);
-
-	while (1) {
-		cur = lowrank(&state);
-		if (cur == end) {
-			break;
-		}
-		addclosed(&state, cur);
-		count = HL_hexes_at_range(cur->hex, 1, neighbors, 6);
-		for (i=0;i<count;i++) {
-			neighbor = neighbors[i];
-			cost = g(&state, current) + metric(current, neighbor);
-			if (inopen(&state, neighbor) && cost < g(&state, neighbor)) {
-				removeopen(&state, neighbor);
-			} else
-			if (inclosed(&state, neighbor) && cost < g(&state, neighbor)) {
-				/* should never happen with
-				 * admissible heuristic
-				 */
-				removeclosed(&state, neighbor);
-			} else
-			if (!inopen(&state, neighbor) && !inclosed(&state, neighbor)) {
-				addopen(&state, neighbor);
-				setg(&state, neighbor, cost);
-				setrank(&state, neighbor, cost + h(neighbor,end));
-				setparent(&state, neighbor, current);
-			} else {
-				abort();
-			}
-		}
-	}
-
-	count = 0;
-	while (parent(&state, cur) != start) {
-		count++;
-		cur = parent(&state, cur);
-	}
-	cur = end;
-	while (parent(&state, cur) != start) {
-		path[count--] = cur;
-		cur = parent(&state, cur);
-	}
-
-}
-
-#endif
-
 static int inversenatcantor(int cantor, int *x, int *y) {
 	int w, t, py;
 
@@ -575,6 +418,8 @@ static int hex_xy(struct hex *h) {
 	return 1;
 }
 
+#if 0
+
 static int hex_iso(struct hex *h) {
 	if (h->iso) return 1;
 
@@ -590,6 +435,8 @@ static int hex_iso(struct hex *h) {
 	return 1;
 }
 
+#endif
+
 int HL_hexbin(double width, double x, double y, int *i, int *j) {
 	double z, rx, ry, rz;
 	double abs_dx, abs_dy, abs_dz;
diff --git a/hexmap.h b/hexmap.h
index 1058653..50665d0 100644
--- a/hexmap.h
+++ b/hexmap.h
@@ -79,6 +79,10 @@ int HL_hexcenter(int cantor, double *x, double *y);
 /* how far is it on the hex grid */
 int HL_distance(int from_cantor, int to_cantor);
 
+/* returns 0 for <0 or >5 */
+int HL_adjacent_hex(int start, int dir);
+
+/* module direction */
 int HL_adjhex(int start, int dir);
 int HL_hexes_at_range(int hex, int range, int *list, int size);
 int HL_hexes_within_range(int hex, int range, int *list, int size);
@@ -105,4 +109,37 @@ struct HL_hex {
 	int x,y; /* hmm.  would be nice to be able to just point to a generic */
 };
 
+/*
+ * Pathfinding
+ */
+
+struct HL_astar_hex {
+	int hex;
+	double f, g, h;
+	struct HL_astar_hex *parent;
+	int	open;
+	struct HL_astar_hex *next;
+	struct HL_astar_hex *prev;
+};
+
+struct HL_astar {
+	int start, goal;
+	int pathlen;
+	double (*metric)(int,int);
+	double (*heuristic)(int,int);
+	int (*neighbor)(int,int);
+	int nodes, allocated;
+	struct HL_astar_hex *sets;
+	struct HL_astar_hex *open;
+	struct HL_astar_hex *closed;
+	struct HL_astar_hex *from, *to;
+	int known, index;
+	int error, malloced;
+};
+
+int HL_findpath(struct HL_astar *s, int loops);
+void HL_astar_free(struct HL_astar *s);
+struct HL_astar *HL_astar_clear(struct HL_astar *s);
+struct HL_astar *HL_astar_init(struct HL_astar *s);
+
 #endif
diff --git a/t/astar.c b/t/astar.c
index bab342d..af88268 100644
--- a/t/astar.c
+++ b/t/astar.c
@@ -10,7 +10,7 @@ void pcheck(struct HL_astar *p, int x1, int y1, int x2, int y2, int expect) {
 	from = HL_cantor_xy(x1,y1);
 	to = HL_cantor_xy(x2,y2);
 
-	HL_astar_init(p);
+	HL_astar_clear(p);
 
 	p->start = from;
 	p->goal = to;
@@ -19,15 +19,27 @@ void pcheck(struct HL_astar *p, int x1, int y1, int x2, int y2, int expect) {
 	ok(p->error == 0, "found path from (%02d, %02d) to (%02d, %02d) with no error",
 		x1, y1, x2, y2);
 	ok(dist == expect,
-			"found path from (%02d, %02d) to (%02d, %02d) path length = %d (expect %d)\n",
+			"found path from (%02d, %02d) to (%02d, %02d) path length = %d (expect %d)",
 		x1, y1, x2, y2, dist, expect);
 }
 
+/* make hex 55 missing */
+int neighbor55(int hex, int dir) {
+	int neighbor;
+
+	neighbor = HL_adjacent_hex(hex, dir);
+	if (neighbor == HL_cantor_xy(5,5)) {
+		return -1;
+	}
+
+	return neighbor;
+}
+
 int main(void) {
 	struct HL_astar *p;
 	int length;
 
-	plan_tests(15);
+	plan_tests(17);
 
 	p = HL_astar_init(0);
 	ok(p != NULL, "allocated astar struct");
@@ -47,6 +59,10 @@ int main(void) {
 	pcheck(p, 1,1, 3,1, 2);
 	pcheck(p, 1,1, 4,7, 8);
 
+	HL_astar_clear(p);
+	p->neighbor = neighbor55;
+	pcheck(p,5,4,5,6,3);
+
 	HL_astar_free(p);
 
 	return exit_status();
diff --git a/t/distance.c b/t/distance.c
index 0f3ef97..28d520e 100644
--- a/t/distance.c
+++ b/t/distance.c
@@ -13,13 +13,16 @@ void dcheck(int x1, int y1, int x2, int y2, int expect) {
 }
 
 int main(void) {
-	plan_tests(5);
+	plan_tests(8);
 
 	dcheck(1,1,2,1,1);
 	dcheck(1,1,2,2,2);
 	dcheck(2,2,2,1,1);
 	dcheck(1,1,2,3,3);
 	dcheck(3,3,3,3,0);
+	dcheck(0,0,1,1,1);
+	dcheck(-1,-1,1,2,4);
+	dcheck(-1,-1,-1,-2,1);
 
 	return exit_status();
 }
-- 
2.40.0