From c5a7aa5029146b2bcea5daae53c6aa3e5e33ed04 Mon Sep 17 00:00:00 2001 From: Nathan Wagner Date: Wed, 13 Jun 2018 18:48:47 +0000 Subject: [PATCH] add polar coordinate calculation --- Makefile | 4 +-- astar.c | 79 +++++++++++++++++++++++++++++++++++++------------------ hexagon.c | 79 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ hexagon.h | 13 ++++++++- 4 files changed, 147 insertions(+), 28 deletions(-) diff --git a/Makefile b/Makefile index 0ae921c..3856ab7 100644 --- a/Makefile +++ b/Makefile @@ -7,7 +7,7 @@ CFLAGS= -Wall -Wno-parentheses $(ARCH) -I. -I.. 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 @@ -21,7 +21,7 @@ t/%.t: t/%.o t/ctap.o $(OBJS) testfiles: $(TESTS) test: libhexagon.a $(TESTS) - @prove --exec $(TESTS) '' 2>/dev/null + @prove --exec '' $(TESTS) 2>/dev/null libhexagon.a: $(OBJS) ar r $@ $+ 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 ? */ diff --git a/hexagon.c b/hexagon.c index 264734c..2dd1f3a 100644 --- a/hexagon.c +++ b/hexagon.c @@ -101,6 +101,85 @@ static double hexpthd[6][2] = { #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; diff --git a/hexagon.h b/hexagon.h index 6768a62..9578bdd 100644 --- a/hexagon.h +++ b/hexagon.h @@ -76,6 +76,13 @@ double HL_center_x(int cantor); 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); @@ -109,6 +116,10 @@ struct HL_hex { int x,y; /* hmm. would be nice to be able to just point to a generic */ }; +struct hl_point { + double x, y; +}; + /* * Pathfinding */ @@ -129,7 +140,6 @@ struct HL_astar { 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; @@ -143,6 +153,7 @@ struct HL_astar *HL_astar_clear(struct HL_astar *s); 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 */ -- 2.40.0