OBJS= hexagon.o astar.o
SRC=$(OBJS:.o=.c)
TESTS= t/cantor.t t/distance.t t/adjacency.t t/range.t t/hexbin.t \
- t/gridsize.t t/center.t t/astar.t
+ t/gridsize.t t/center.t t/astar.t t/polar.t
PREFIX=/usr/local
all: libhexagon.a docs testfiles
testfiles: $(TESTS)
test: libhexagon.a $(TESTS)
- @prove --exec $(TESTS) '' 2>/dev/null
+ @prove --exec '' $(TESTS) 2>/dev/null
libhexagon.a: $(OBJS)
ar r $@ $+
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 ? */
#endif
+/*
+c = 1.0 = distance from center to vertex
+b = distance to hex side
+a = distance along hex side
+
+A = angle at point center, this is the polar coord angle
+B = angle from vertex, this is 60 degrees
+C = Other angle, which is 180 - 60 - A = 120 - A
+
+sin B = sin 60 = sqrt(3) / 2
+cos B = cos 60 = 1/2
+
+b = c * sin B / ( sin A cos B + sin B cos A)
+
+c * sin B / ( sin A cos B + sin B cos A)
+
+0.5 * sqrt3
+-------------
+sinA 0.5 + sqrt3 * 0.5 cosA
+
+sqrt3
+-------------
+sinA + sqrt3 cosA
+
+b=
+3
+-------------
+cosA + sqrt3 sinA
+
+x = b cosA
+y = b sinA
+*/
+
+#define RD (180.0 / M_PI)
+/* angle ranges from 0-6 */
+/* distance is 0 at origin, 1.0 at the hex side */
+
+/* return the polar distance ? */
+double HL_polar(double angle, double distance, double *x, double *y) {
+ double A, B, C, b, c;
+ double sinB, sinC;
+#if 0
+ double sqrt3;
+
+ sqrt3 = sqrt(3.0);
+#endif
+
+ /* convert angle to radians */
+ angle = angle * M_PI / 3.0;
+
+ /* calculate the distance along the ray to the hex side */
+
+ A = fmod(angle, M_PI/3.0); /* constrain to within an equilateral */
+ B = M_PI / 3.0;
+ C = M_PI - A - B;
+
+ sinB = sin(B);
+ sinC = sin(C);
+
+ c = 1.0;
+ c = HL_vertexv[0];
+#if 0
+ /* provided for completeness, but we don't use the value */
+ sinA = sin(A);
+ a = c * sinA / sinC;
+#endif
+ b = c * sinB / sinC;
+
+ if (x) {
+ *x = b * cos(angle);
+ }
+
+ if (y) {
+ *y = b * sin(angle);
+ }
+
+ return b;
+}
+
void HL_vertices(int cantor, double *vc) {
int i;
double xc, yc;
double HL_center_y(int cantor);
int HL_hexcenter(int cantor, double *x, double *y);
+/* find a point based on a unit hex, given angle and distance from center,
+ * where a distance of 1 is on the hex side. probably not useful
+ * for points outside the hex, that is, distance should almost certainly
+ * be less than or equal to 1.0
+ */
+double HL_polar(double angle, double distance, double *x, double *y);
+
/* how far is it on the hex grid */
int HL_distance(int from_cantor, int to_cantor);
int x,y; /* hmm. would be nice to be able to just point to a generic */
};
+struct hl_point {
+ double x, y;
+};
+
/*
* Pathfinding
*/
double (*heuristic)(int,int);
int (*neighbor)(int,int);
int nodes, allocated;
- struct HL_astar_hex *sets;
struct HL_astar_hex *open;
struct HL_astar_hex *closed;
struct HL_astar_hex *from, *to;
struct HL_astar *HL_astar_init(struct HL_astar *s);
void HL_vertices(int cantor, double *vc);
+extern double HL_vertexv[12];
extern double HL_fand[16];
extern float HL_fanf[16];
extern double HL_hfand[16]; /* horizontal grids */
projects / hexagon / commitdiff