-#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
struct HL_astar_hex *h;
if (!s) return 0;
- for(h = s->closed; h; h = h->next) {
+ for (h = s->closed; h; h = h->next) {
if (h->hex == hex) return h;
}
return NULL;
struct HL_astar_hex *h;
if (!s) return 0;
- for(h = s->open; h; h = h->next) {
+ for (h = s->open; h; h = h->next) {
if (h->hex == hex) return h;
}
return NULL;
return r;
}
+#ifdef DEBUG_ASTAR
+void dump_list(char *name, 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));
+ }
+ fprintf(stderr, "\n");
+}
+#endif
+
/*
* find a path from start to end. we use A*
*/
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);
break;
}
closehex(s, x);
- for (dir = 0; y = s->neighbor(x->hex, dir); dir++) {
+ 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;
}
cost = x->g + s->metric(x->hex, y);
yopen = in_open(s, y);
- if (! yopen) {
+ if (!yopen) {
yopen = add_open(s, y);
-
tent_better = 1;
} else if (cost < yopen->g) {
tent_better = 1;