-#include "hexmap.h"
-
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <errno.h>
+#include "hexagon.h"
+
/*
* TODO use binary heap for the openlist and closed list.
* open list should be a min-heap on the f value
#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);
}
if (!state) return NULL;
state->malloced = 1;
}
- state->sets = 0;
state->open = 0;
state->closed = 0;
state->nodes = 0;
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;
}
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;
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
- 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;
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;
}
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;
#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) {
tent_better = 1;
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;
}
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++;
projects / hexagon / blobdiff