X-Git-Url: https://pd.if.org/git/?a=blobdiff_plain;f=astar.c;h=67889c24b0e29402054ea4aa604712e2d1c28eb1;hb=d74b76176b43b9eae3b584c231b077d3a3f0f92b;hp=5bfc60fc2077ae94b16d8ba24e68d7829efc899c;hpb=8ca2b8a06b00066a20f744a61c9bcdd65949a344;p=hexagon

diff --git a/astar.c b/astar.c
index 5bfc60f..67889c2 100644
--- a/astar.c
+++ b/astar.c
@@ -17,11 +17,11 @@
 #define DEBUG_ASTAR 1 
 #endif
 
-static double default_metric(int a, int b) {
+static double default_metric(struct HL_hex a, struct HL_hex b) {
 	return 1.0;
 }
 
-static double default_heuristic(int a, int b) {
+static double default_heuristic(struct HL_hex a, struct HL_hex b) {
 	return (double)HL_distance(a, b);
 }
 
@@ -31,7 +31,6 @@ struct HL_astar *HL_astar_init(struct HL_astar *state) {
 		if (!state) return NULL;
 		state->malloced = 1;
 	}
-	state->sets = 0;
 	state->open = 0;
 	state->closed = 0;
 	state->nodes = 0;
@@ -43,17 +42,27 @@ struct HL_astar *HL_astar_init(struct HL_astar *state) {
 
 	state->metric = default_metric;
 	state->heuristic = default_heuristic;
-	state->neighbor = HL_adjacent_hex;
+	state->neighbor = HL_adjhexp;
 
 	return state;
 }
 
 /*
- * Reset a state to enpty.  Doesn't free memory, so it
- * can be reused.
+ * Reset a state to enpty.
  */
 struct HL_astar *HL_astar_clear(struct HL_astar *s) {
+	struct HL_astar_hex *hex;
 	if (!s) return NULL;
+	while (s->open) {
+		hex = s->open->next;
+		free(s->open);
+		s->open = hex;
+	}
+	while (s->closed) {
+		hex = s->closed->next;
+		free(s->closed);
+		s->closed = hex;
+	}
 
 	s->open = 0;
 	s->closed = 0;
@@ -64,37 +73,46 @@ struct HL_astar *HL_astar_clear(struct HL_astar *s) {
 }
 
 void HL_astar_free(struct HL_astar *s) {
-	free(s->sets);
+	struct HL_astar_hex *hex;
+	/* free open and closed lists */
+	while (s->open) {
+		hex = s->open->next;
+		free(s->open);
+		s->open = hex;
+	}
+	while (s->closed) {
+		hex = s->closed->next;
+		free(s->closed);
+		s->closed = hex;
+	}
+
 	if (s->malloced) {
 		free(s);
 	}
 }
 
-static struct HL_astar_hex *add_open(struct HL_astar *s, int hex) {
+static struct HL_astar_hex *add_open(struct HL_astar *s, struct HL_hex hex) {
 	struct HL_astar_hex *node;
+#ifdef DEBUG_ASTAR
+		fprintf(stderr, "add to open %d\n", HL_cantor(hex));
+#endif
 
-	if (!s || s->error) return NULL;
-
-	/* TODO check in open or closed */
+	if (!s || s->error) {
+#ifdef DEBUG_ASTAR
+		fprintf(stderr, "returning null\n");
+#endif
 
-	if (s->nodes == s->allocated) {
-		int newalloc;
-		struct HL_astar_hex *alloc;
-		if (s->allocated) {
-			newalloc = s->allocated * 2;
-		} else {
-			newalloc = 16;
-		}
-		alloc = realloc(s->sets, newalloc * sizeof *node);
-		if (!alloc) {
-			s->error = 1;
-			return NULL;
-		}
-		s->sets = alloc;
-		s->allocated = newalloc;
+		return NULL;
 	}
+#ifdef DEBUG_ASTAR
+		fprintf(stderr, "mallocing node(%zd)\n", sizeof *node);
+#endif
 
-	node = &s->sets[s->nodes++];
+	/* TODO check in open or closed */
+	node = malloc(sizeof *node);
+#ifdef DEBUG_ASTAR
+		fprintf(stderr, "add to open %d = %p\n", HL_cantor(hex), node);
+#endif
 
 	node->hex = hex;
 	node->g = 0.0;
@@ -102,7 +120,9 @@ static struct HL_astar_hex *add_open(struct HL_astar *s, int hex) {
 	node->h = 0.0;
 	node->open = 1;
 	node->parent = 0;
-	if (s->open) s->open->prev = node;
+	if (s->open) {
+		s->open->prev = node;
+	}
 	node->next = s->open;
 	node->prev = NULL;
 	s->open = node;
@@ -118,7 +138,7 @@ static struct HL_astar_hex *closehex(struct HL_astar *s, struct HL_astar_hex *h)
 	}
 
 #ifdef DEBUG_ASTAR
-	fprintf(stderr, "Closing hex: (%d,%d)\n",  HL_cantor_x(h->hex), HL_cantor_y(h->hex));
+	fprintf(stderr, "Closing hex: (%d,%d)\n",  h->hex.x, h->hex.y);
 #endif
 	h->open = 0;
 	if (h->prev) h->prev->next = h->next;
@@ -132,22 +152,22 @@ static struct HL_astar_hex *closehex(struct HL_astar *s, struct HL_astar_hex *h)
 	return h;
 }
 
-struct HL_astar_hex *in_closed(struct HL_astar *s, int hex) {
+struct HL_astar_hex *in_closed(struct HL_astar *s, struct HL_hex hex) {
 	struct HL_astar_hex *h;
 	if (!s) return 0;
 
-	for(h = s->closed; h; h = h->next) {
-		if (h->hex == hex) return h;
+	for (h = s->closed; h; h = h->next) {
+		if (h->hex.x == hex.x && h->hex.y == hex.y) return h;
 	}
 	return NULL;
 }
 
-struct HL_astar_hex *in_open(struct HL_astar *s, int hex) {
+struct HL_astar_hex *in_open(struct HL_astar *s, struct HL_hex hex) {
 	struct HL_astar_hex *h;
 	if (!s) return 0;
 
-	for(h = s->open; h; h = h->next) {
-		if (h->hex == hex) return h;
+	for (h = s->open; h; h = h->next) {
+		if (h->hex.x == hex.x && h->hex.y == hex.y) return h;
 	}
 	return NULL;
 }
@@ -167,18 +187,29 @@ static struct HL_astar_hex *lowrank(struct HL_astar *s) {
 	return r;
 }
 
+#ifdef DEBUG_ASTAR
+void dump_list(char *name, struct HL_astar_hex *x) {
+	fprintf(stderr, "%s list: ", name);
+	for(; x; x = x->next) {
+		fprintf(stderr, "(%d,%d)",  x->hex.x, x->hex.y);
+	}
+	fprintf(stderr, "\n");
+}
+#endif
+
 /*
  * find a path from start to end.  we use A*
  */
 int HL_findpath(struct HL_astar *s, int loops) {
-	int dir, y;
+	int dir;
+	struct HL_hex y;
 	struct HL_astar_hex *node, *x, *yopen;
 	int tent_better;
 	double cost;
 
 	s->error = 0;
 
-	if (s->start == s->goal) return 0;
+	if (HL_distance(s->start, s->goal) == 0) return 0;
 
 	node = add_open(s, s->start);
 	node->g = 0.0;
@@ -187,47 +218,49 @@ int HL_findpath(struct HL_astar *s, int loops) {
 
 #ifdef DEBUG_ASTAR
 	fprintf(stderr, "A* findpath: ");
-	fprintf(stderr, "(%d,%d)",  HL_cantor_x(s->start), HL_cantor_y(s->start));
+	fprintf(stderr, "(%d,%d)",  s->start.x, s->start.y);
 	fprintf(stderr, " -> ");
-	fprintf(stderr, "(%d,%d)",  HL_cantor_x(s->goal), HL_cantor_y(s->goal));
+	fprintf(stderr, "(%d,%d)",  s->goal.x, s->goal.y);
 	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");
+		dump_list("open", s->open);
+		dump_list("closed", s->closed);
 #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->hex.x, x->hex.y,
 				x->f, x->g, x->h
 				);
 #endif
-		if (x->hex == s->goal) {
+		if (HL_distance(x->hex, s->goal) == 0) {
 			break;
 		}
 		closehex(s, x);
-		for (dir = 0; y = s->neighbor(x->hex, dir); dir++) {
+
+		int n;
+		for (dir = 0; n = s->neighbor(x->hex, dir, &y),dir<6; dir++) {
+			if (n == 0) continue; /* no hex in that direction */
 			if (in_closed(s, y)) {
 				continue;
 			}
+#ifdef DEBUG_ASTAR
+			fprintf(stderr, "checking dir %d, hex (%d, %d)\n", dir,
+					y.x, y.y);
+#endif
 
 			cost = x->g + s->metric(x->hex, y);
 
 			yopen = in_open(s, y);
-			if (! yopen) {
+#ifdef DEBUG_ASTAR
+			fprintf(stderr, "checking inopen = %p\n", yopen);
+#endif
+			if (!yopen) {
 				yopen = add_open(s, y);
 				tent_better = 1;
 			} else if (cost < yopen->g) {
@@ -249,16 +282,17 @@ int HL_findpath(struct HL_astar *s, int loops) {
 				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->hex.x, yopen->hex.y,
 				yopen->f, yopen->g, yopen->h
 				);
 #endif
 			}
 		}
+
 	}
 
 	/* error no path ? */
-	if (x->hex != s->goal) {
+	if (HL_distance(x->hex, s->goal) != 0) {
 		s->error = 1;
 		return 0;
 	}
@@ -274,12 +308,12 @@ int HL_findpath(struct HL_astar *s, int loops) {
 		if (yopen->parent) {
 			yopen->parent->next = yopen;
 		}
-		if (yopen->hex == s->start) s->from = yopen;
+		if (HL_distance(yopen->hex, s->start) == 0) 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)
+				yopen->hex.x,
+				yopen->hex.y
 				);
 #endif
 		s->pathlen++;