if (!state) return NULL;
state->malloced = 1;
}
- state->sets = 0;
state->open = 0;
state->closed = 0;
state->nodes = 0;
}
/*
- * 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;
}
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) {
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;
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;
}
#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));
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;
#endif
}
}
+
}
/* error no path ? */