X-Git-Url: https://pd.if.org/git/?p=hexagon;a=blobdiff_plain;f=astar.c;h=fd92bfcc8ddc24f611ff3d7b71980a119fead6c4;hp=107a9869ec38505cf40605f0318affbdfc0812a9;hb=c5a7aa5029146b2bcea5daae53c6aa3e5e33ed04;hpb=ce4fd67e5bfd07192ca5cb357798aaa3588512e4

diff --git a/astar.c b/astar.c
index 107a986..fd92bfc 100644
--- a/astar.c
+++ b/astar.c
@@ -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;
@@ -49,11 +48,21 @@ struct HL_astar *HL_astar_init(struct HL_astar *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,7 +73,19 @@ 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);
 	}
@@ -72,29 +93,26 @@ void HL_astar_free(struct HL_astar *s) {
 
 static struct HL_astar_hex *add_open(struct HL_astar *s, int hex) {
 	struct HL_astar_hex *node;
+#ifdef DEBUG_ASTAR
+		fprintf(stderr, "add to open %d\n", 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", 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;
@@ -168,7 +188,7 @@ static struct HL_astar_hex *lowrank(struct HL_astar *s) {
 }
 
 #ifdef DEBUG_ASTAR
-void dump_list(char *name, HL_astar_hex *x) {
+void dump_list(char *name, struct HL_astar_hex *x) {
 	fprintf(stderr, "%s list: ", name);
 	for(; x; x = x->next) {
 		fprintf(stderr, "(%d,%d)",  HL_cantor_x(x->hex), HL_cantor_y(x->hex));
@@ -221,15 +241,23 @@ int HL_findpath(struct HL_astar *s, int loops) {
 			break;
 		}
 		closehex(s, x);
+
 		for (dir = 0; y = s->neighbor(x->hex, dir),dir<6; dir++) {
 			if (y == 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,
+					HL_cantor_x(y), HL_cantor_y(y));
+#endif
 
 			cost = x->g + s->metric(x->hex, y);
 
 			yopen = in_open(s, y);
+#ifdef DEBUG_ASTAR
+			fprintf(stderr, "checking inopen = %p\n", yopen);
+#endif
 			if (!yopen) {
 				yopen = add_open(s, y);
 				tent_better = 1;
@@ -258,6 +286,7 @@ int HL_findpath(struct HL_astar *s, int loops) {
 #endif
 			}
 		}
+
 	}
 
 	/* error no path ? */